(原創(chuàng))線索二叉樹那點小破事

線索二叉樹


二叉樹的基本定義結構我們都很熟悉咳胃,節(jié)點數(shù)據(jù)加上孩紙指針笋庄,左孩子指娘家泞遗,右孩子指婆家惰许,我們來看這個例子:

我們會發(fā)現(xiàn),有些孩子并沒有地方可以去史辙,例子中的樹一共十個結點汹买,十一個空閑指針,由此引出我們對于空閑指針的計算公式:一個有 n 個結點的二叉樹有 2n 個指針域聊倔,而 n 個結點會產生 n-1 個分支晦毙,每個分支對應其指向孩子的指針域,所以空閑指針數(shù): 2n - (n-1) = n+1 耙蔑,這么多指針域我們怎樣規(guī)劃能避免這些指針便宜null呢见妒?

大佬們提出了這樣一個用途,中序遍歷這棵樹我們可以得到: HDIBJEAFCG 甸陌,很輕松须揣。那么我們可以愉快的知道 I 是 B 的前驅盐股,或者 J 是 B 的后繼這樣的信息,那是借助了遍歷返敬,我們能不能把這些空的指針指向前驅和后繼呢遂庄,當然闊以寥院。

但是馬上有人站出來說劲赠,那指向孩子的指針原來就存在了,這后來的野生指針和指向孩子的指針可怎么區(qū)分呢秸谢,大佬們就決定再加個量來區(qū)分指針的類型凛澎,如果是指向孩子的就用 0 表示,用作前驅后繼的就用 1 表示估蹄,使用的時候進行遍歷就可以一勞永逸地取得前驅后繼的信息塑煎,OK,看看結構的定義變成啥樣了臭蚁。

和原來差不多對不對最铁,多了個枚舉變量的定義

OK,現(xiàn)在我們的線索二叉樹可以算正式出爐遼:

我們把指向前驅和后繼的指針稱為線索垮兑,加上線索的二叉鏈表稱為線索鏈表冷尉,相應的二叉樹就稱為線索二叉樹 (Threaded Binary Tree)

來看一看抽象化結點的結構:ltag = 0 或者 Link,表示這個結點的左指針指向左孩子系枪,ltag = 1 或者?Thread雀哨,表示這個結點的左指針指向前驅

rtag = 0 或者 Link,表示這個結點的右指針指向右孩子私爷,rtag = 1 或者?Thread雾棺,表示這個結點的右指針指向后繼

結點的新式定義

改頭換面的二叉鏈表

中序線索化遍歷的實現(xiàn)

我們來讀一下代碼,樸素的中序遍歷的框架其實還在衬浑,中間加粗的是線索化的代碼捌浩,另外多了 pre 的指針,我們可以發(fā)現(xiàn)這個指針永遠比我們的主角指針 p 慢一拍工秩,它永遠在 p 的前驅結點嘉栓,每次到了一個結點,我們先判斷一哈這個結點有沒有左子樹拓诸,如果沒有侵佃,就使這個節(jié)點的標記值置Thread,表示這個結點被前驅大爺承包了奠支,然后就是讓指針 p 的左孩子管 pre 叫干爹馋辈, 表示這個結點的前驅就定下了;然后是后繼倍谜,我們會發(fā)現(xiàn)這個和前驅有點不同迈螟,這個先看前驅結點的右孩子是否為空叉抡,即 如果 pre -> rchild 為空,就把這個引到 p 指針答毫,我們說 p 指針走的快一步褥民,所以這就找到了后繼,順理成章? pre->rtag = Thread洗搂,pre -> rchild = p; 完美消返! 這兩步表示一輪線索化的一個輪回,弄完這些讓 pre 再向前走一步耘拇,就是 pre = p撵颊,剩下的和中序遍歷沒什么區(qū)別

我們給這個二叉鏈表加上一個頭指針,并且讓頭結點的左孩子指向樹根節(jié)點惫叛,讓中序的第一個節(jié)點指回頭結點的左孩子指針倡勇,用頭結點的右指針指向中序遍歷的最后一個結點,并且把這個指針指回頭結點的右指針嘉涌,形成雙向的指針循環(huán)妻熊,這樣的好處就在于既可以從第一個結點開始沿中序的后繼向后遍歷,也可以利用從頭開始前序遍歷(例子及表述來自《大話數(shù)據(jù)結構》)


附上帶頭結點的線索二叉樹中序遍歷:


首先定義指向根的頭結點 p仑最,我們先看外層這個最大的循環(huán)扔役,這個循環(huán)條件為 p != T ,這個條件首先排除了空樹的遍歷词身,其次按照剛才對帶頭節(jié)點二叉線索表的分析厅目,最后的 p 指針會在窮途末路時等于 T ,這相當于 p 指向頭結點法严,這時 p = T 损敷,故如果不加 p != T ,則會無限循環(huán)下去深啤。進入循環(huán)拗馒,首先是判定p -> ltag 等于Link,內容是指向左子樹溯街,那么這一個循環(huán)表示從根開始直到沒有左子樹的末端诱桂,路徑是A →B→D→H,然后打印H呈昔,目前 p 的右指針是指向直接后繼D的挥等,所以下面一個進入第二個while,打印出D堤尾,D的右邊是孩子指針肝劲,第十五行指向I,然后重復整個過程,相當于從小樹到大樹以鏈表搜索的形勢進行完整的中序遍歷辞槐,完整順序參照下圖


好的掷漱,我們今天的線索二叉樹就到這里遼,最后附上一段我偷來的話:


在實際問題中 榄檬,如果所用的二叉樹需經常遍歷或查找結點時需要某種遍歷序列中的前驅和后繼卜范,那么采用線索二叉鏈表的存儲結構就是非常不錯的選擇。

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末鹿榜,一起剝皮案震驚了整個濱河市海雪,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌犬缨,老刑警劉巖喳魏,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件棉浸,死亡現(xiàn)場離奇詭異怀薛,居然都是意外死亡,警方通過查閱死者的電腦和手機迷郑,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進店門枝恋,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人嗡害,你說我怎么就攤上這事焚碌。” “怎么了霸妹?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵十电,是天一觀的道長。 經常有香客問我叹螟,道長鹃骂,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任罢绽,我火速辦了婚禮畏线,結果婚禮上,老公的妹妹穿的比我還像新娘良价。我一直安慰自己寝殴,他們只是感情好,可當我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布明垢。 她就那樣靜靜地躺著蚣常,像睡著了一般。 火紅的嫁衣襯著肌膚如雪痊银。 梳的紋絲不亂的頭發(fā)上抵蚊,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天,我揣著相機與錄音,去河邊找鬼泌射。 笑死粘姜,一個胖子當著我的面吹牛,可吹牛的內容都是我干的熔酷。 我是一名探鬼主播孤紧,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼拒秘!你這毒婦竟也來了号显?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤躺酒,失蹤者是張志新(化名)和其女友劉穎押蚤,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體羹应,經...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡揽碘,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了园匹。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片雳刺。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖裸违,靈堂內的尸體忽然破棺而出掖桦,到底是詐尸還是另有隱情,我是刑警寧澤供汛,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布枪汪,位于F島的核電站,受9級特大地震影響怔昨,放射性物質發(fā)生泄漏雀久。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一朱监、第九天 我趴在偏房一處隱蔽的房頂上張望岸啡。 院中可真熱鬧,春花似錦赫编、人聲如沸巡蘸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽悦荒。三九已至,卻和暖如春嘹吨,著一層夾襖步出監(jiān)牢的瞬間搬味,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留碰纬,地道東北人萍聊。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像悦析,于是被迫代替她去往敵國和親寿桨。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內容

  • 目錄 1强戴、什么是樹 2亭螟、相關術語 3、二叉樹 3.1骑歹、二叉樹的類型 3.2预烙、二叉樹的性質 3.3、二叉樹的結構 3...
    我哈啊哈啊哈閱讀 2,564評論 0 10
  • 1.樹和二叉樹的定義 (1) 樹的定義 樹是n (n≥0) 個結點的有限集道媚。 n=0 時稱為空樹扁掸。在任意一棵非空樹...
    yinxmm閱讀 2,461評論 0 3
  • 四也糊、樹與二叉樹 1. 二叉樹的順序存儲結構 二叉樹的順序存儲就是用數(shù)組存儲二叉樹炼蹦。二叉樹的每個結點在順序存儲中都有...
    MinoyJet閱讀 1,549評論 0 7
  • 一些概念 數(shù)據(jù)結構就是研究數(shù)據(jù)的邏輯結構和物理結構以及它們之間相互關系羡宙,并對這種結構定義相應的運算,而且確保經過這...
    Winterfell_Z閱讀 5,855評論 0 13
  • 文 | 花開半夏香如故 享受假期掐隐,享受美食狗热。大部分女孩子喜歡吃甜點,其中松軟可口的蛋糕就是甜點中虑省,相當有治愈作用的...
    花開半夏香如故閱讀 805評論 11 16