1樓：聶風2007號
我先說一說 每個 節點 那 五個格 的資料 的含義
中間哪一個 是 儲存資料
從左向右 ，第一個 和 第五個 是指標，具體指向什麼 取決於第二個 和 第四個的值
第二個 如果是零，實線表示，則 第一個指向的是 左孩子
第二個 如果是1，虛線表示，則 第一個 指向的是 在中序遍歷次序下 ，該節點的前驅（即前一個），，如果 該節點 自己就是第一個，沒有前驅，，則為空指標 ，，圖中最左邊 的的c就是這樣
（中序遍歷 是先訪問左孩子，再訪問根，再訪問右孩子，，圖中節點的中根遍歷次序為cbdafhgie）
第四個為0 ，則第五個指向右孩子
第四個為1.則第五個 指向 中序遍歷次序下的後繼，，如本身已經是最後一個 沒有後繼 ，則為空指標
什麼是線索二叉樹,為什麼要使用線索二叉樹 5
2樓：匿名使用者
在有n個結點的二叉連結串列中必定存在n+1個空指標域，因此可以利用這些空指標域存放指向結點的某種遍歷次序下的前趨和後繼結點的指標，這種指向前趨和後繼結點的指標稱為「線索」，加上線索的二叉連結串列稱為線索連結串列，相應的二叉樹被稱為線索二叉樹，相當於一個雙向連結串列
相比二叉樹而言可以更好的找到某個節點的前驅和後繼
線索二叉樹是一種什麼結構？
3樓：demon陌
物理結構。包括線性儲存和非線性儲存其中，線性儲存結構有順序、連結、索引和雜湊4種結構。非線性儲存結構有：樹形儲存結構、圖形儲存結構。
n個結點的二叉連結串列中含有n+1(2n-(n-1)=n+1)個空指標域。利用二叉連結串列中的空指標域，存放指向結點在某種遍歷次序下的前驅和後繼結點的指標。
這種加上了線索的二叉連結串列稱為線索連結串列，相應的二叉樹稱為線索二叉樹(threaded binarytree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。
4樓：無異滄行
物理結構。包括線性儲存和非線性儲存其中，線性儲存結構有順序（sequential）、連結（linked）、索引（indexed）和雜湊（hashing）4種結構。非線性儲存結構有：
樹形儲存結構、圖形儲存結構。
對於n個結點的二叉樹，在二叉鏈儲存結構中有n+1個空鏈域，利用這些空鏈域存放在某種遍歷次序下該結點的前驅結點和後繼結點的指標。
二叉樹的遍歷本質上是將一個複雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和後繼（第一個結點無前驅，最後一個結點無後繼）。對於二叉樹的一個結點，查詢其左右子女是方便的，其前驅後繼只有在遍歷中得到。
線索二叉樹究竟有何意義？
5樓：heart浩皛
一個簡單的中序遍歷大概是這個樣子的。 def inorder(node): # 跳出條件，比如node為空啊什麼的 inorder(node.
left) print node inorder(node.right) 所以說，在遍歷的時候不用擔心什麼前驅後繼啊，函式只操心這個節點本身就好了，至於左節點和右節點直接交給它自己去遞迴好了。
怎麼線索二叉樹？
6樓：北京理工大學出版社
用二叉連結串列作為二叉樹的儲存結構時，因為每個結點中只有指向其左右孩子結點的指標域，所以從任一結點出發只能直接找到該結點的左右孩子結點，而無法直接找到該結點在某種遍歷序列中的前驅和後繼結點。為了儲存遍歷後結點的前驅和後繼資訊，可採用增加向前和向後的指標，但這種方法增加了儲存開銷，不可取。對於具有n個結點的二叉樹，採用二叉連結串列儲存結構時，每個結點有兩個指標域，總共有2n個指標域，其中有n＋1個空指標域。
由此，利用這些空鏈域來存放遍歷後結點的前驅和後繼資訊，這就是線索二叉樹構成的思想。由於遍歷方法不同，所獲得的線性序列中，結點的前驅和後繼也不同，因此線索二叉樹又分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹。
1.線索二叉樹的基本概念（1）線索：將二叉連結串列中的空指標域指向前驅結點和後繼結點的指標稱為線索。
（2）線索連結串列：把加上了線索的二叉連結串列稱為線索連結串列。
（2）線索化：使二叉連結串列中結點的空鏈域存放以某種次序遍歷得到的前驅或後繼資訊的過程稱為線索化。
（4）線索二叉樹：加上線索的二叉樹稱為線索二叉樹。
二叉樹線索化的思想是什麼？ 15
7樓：
線索二叉樹就是
使用的物件：樹節點中沒有使用的n-1個空指標（n個樹節點，空指標永遠都是n+1個，自己推下）。
執行的原則：某種深度遍歷順序——先序，中序，後序
過程：按照中序（當然也可以是其他的遍歷）的前驅後繼關係，若p的左子樹為空，則左子樹指向p的中序前驅，若p的右子樹為空，則p的右子樹節點指向p的後繼，若是子樹都有，就不用搗騰了。第一個節點的左子樹為空（此節點一定是葉節點，而且沒前驅，所以是空），最後一個節點的右子樹也是空。
資料結構：在樹節點的結構是（data，*lchild，*rchild）線索樹的節點是（data，*lchild，*rchild，ltag，rtag），tag為1表示線索數的節點，為0標識樹節點。
目的：方便找到樹在某種遍歷的條件下前驅和後繼。不是用來遍歷的哈
注意的點：只用中序線索樹可以很完美的達到這個效果，前序線索樹在計算前驅的時候會牽扯到自己的父節點，就要使用棧來找，這樣和遍歷查詢沒區別，同理，後序線索樹找後繼會比較麻煩。
話說，要點基本就這樣了。
細節的點，比如說為什麼n+1啊，為什麼前序後序不完美啊，這些一邊就考個知道，而且推理是很快的，所以呢，考試的話，就照著我說的這幾個點就ok了，主要是要會畫，還有就是中序查詢的實現。
中序實現給你一個要點：
找前驅：向左找第一個rtag為1的就是它的前驅了。
因為在中序中，所有的內節點（非葉節點）的前驅和後繼必然是一個葉節點。
要是記不住演算法，記住這點臨場寫也夠了，前提是老兄您在之前弄明白我的要點的意義。
線索二叉樹中關於線索的問題
我覺得你主要是不清楚pre指向的是什麼。我的資料結構書是嚴蔚敏版的，書上是這麼說的 pre始終指向剛剛訪問過的結點，若指標root指向當前訪問的結點，則pre指向它的前續。說的有點抽象。其實主要就是要清楚何時改變pre的值，pre始終指向剛剛訪問過的結點 就是說訪問完一個結點後，就改變pre的值。具...
什麼叫做平衡二叉樹，什麼是平衡二叉樹
這要涉及到 bai滿二叉樹與完全二du叉樹的問題 滿二zhi叉樹是將一個 daon層二叉樹完全排滿的版二叉樹，第n層有權2 n個元素 n層完全二叉樹是將n層滿二叉樹最後一層從後向前依次去處少於2 n個元素 完全二叉樹是平衡二叉樹的一個特例，平衡二叉樹是將完全二叉樹的最後一層元素任意排在空位上的一種二...
什麼是平衡二叉樹,什麼是理想平衡二叉樹
它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹 avl treap 伸展樹等。在平衡二叉搜尋樹中，我們可以看到，其高度一般都良好地維持在o log2n 大大降低了操作的時間複雜度。平衡二叉 樹 balanced binary tree ...