下一頁
周遊概念
所謂周遊(Traversal)是指沿着某條搜尋路線，依次對樹中每個結點均做一次且僅做一次通路。通路結點所做的操作依賴于具體的應用問題。
周遊是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。
周遊方案
1．周遊方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。是以，在任一給定結點上，可以按某種次序執行三個操作：
（1）通路結點本身(N)，
（2）周遊該結點的左子樹(L)，
（3）周遊該結點的右子樹(R)。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故隻讨論先左後右的前三種次序。
2．三種周遊的命名
根據通路結點操作發生位置命名：
① NLR：前序周遊(PreorderTraversal亦稱(先序周遊))
——通路結點的操作發生在周遊其左右子樹之前。
② LNR：中序周遊(InorderTraversal)
——通路結點的操作發生在周遊其左右子樹之中(間)。
③ LRN：後序周遊(PostorderTraversal)
——通路結點的操作發生在周遊其左右子樹之後。
注意：
由于被通路的結點必是某子樹的根，是以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分别又稱為先根周遊、中根周遊和後根周遊。
周遊算法
1．中序周遊的遞歸算法定義：
若二叉樹非空，則依次執行如下操作：
(1)周遊左子樹；
(2)通路根結點；
(3)周遊右子樹。
2．先序周遊的遞歸算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 通路根結點；
(2) 周遊左子樹；
(3) 周遊右子樹。
3．後序周遊得遞歸算法定義：
若二叉樹非空，則依次執行如下操作：
(1)周遊左子樹；
(2)周遊右子樹；
(3)通路根結點。
4．中序周遊的算法實作
用二叉連結清單做為存儲結構，中序周遊算法可描述為：
void InOrder(BinTree T)
{ //算法裡①~⑥是為了說明執行過程加入的标号
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 通路結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
線索二叉樹概念
1．定義
n個結點的二叉連結清單中含有n+1個空指針域。利用二叉連結清單中的空指針域，存放指向結點在某種周遊次序下的前趨和後繼結點的指針（這種附加的指針稱為"線索"）。
這種加上了線索的二叉連結清單稱為線索連結清單，相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。
注意：
線索連結清單解決了二叉連結清單找左、右孩子困難的問題，出現了無法直接找到該結點在某種周遊序列中的前趨和後繼結點的問題。
2．線索連結清單的結點結構
線索連結清單中的結點結構為：
其中:
ltag和rtag是增加的兩個标志域，用來區分結點的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或後繼的線索。
3．線索二叉樹的表示
【例】下面(a)圖所示的中序線索二叉樹，其線索連結清單如下面(b)圖所示。
注意：
圖中的實線表示指針，虛線表示線索。
結點C的左線索為空，表示C是中序序列的開始結點，無前趨；
結點E的右線索為空，表示E是中序序列的終端結點，無後繼。
線索二叉樹中，一個結點是葉結點的充要條件為：左、右标志均是1。
二叉樹具有以下重要性質：
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)。
證明：用數學歸納法證明：
歸納基礎：i=1時，有2i-1=20=1。因為第1層上隻有一個根結點，是以命題成立。
歸納假設：假設對所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個結點，證明j=i時命題亦成立。
歸納步驟：根據歸納假設，第i-1層上至多有2i-2個結點。由于二叉樹的每個結點至多有兩個孩子，故第i層上的結點數至多是第i-1層上的最大結點數的2倍。即j=i時，該層上至多有2×2i-2=2i-1個結點，故命題成立。
性質2 深度為k的二叉樹至多有2k-1個結點(k≥1)。
證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數時，其樹中結點數最多。是以利用性質1可得，深度為k的二叉樹的結點數至多為：
20+21+…+2k-1=2k-1
故命題正确。
性質3 在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1。
證明：因為二叉樹中所有結點的度數均不大于2，是以結點總數(記為n)應等于0度結點數、1度結點(記為n1)和2度結點數之和：
n=no+n1+n2 (式子1)
另一方面，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：
nl+2n2
樹中隻有根結點不是任何結點的孩子，故二叉樹中的結點總數又可表示為：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1
滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。
1、滿二叉樹(FullBinaryTree)
一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。
滿二叉樹的特點：
（1） 每一層上的結點數都達到最大值。即對給定的高度，它是具有最多結點數的二叉樹。
（2） 滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。
2、完全二叉樹(Complete BinaryTree)
若一棵二叉樹至多隻有最下面的兩層上結點的度數可以小于2，并且最下一層上的結點都集中在該層最左邊的若幹位置上，則此二叉樹稱為完全二叉樹。
特點：
（1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
（2） 在滿二叉樹的最下一層上，從最右邊開始連續删去若幹結點後得到的二叉樹仍然是一棵完全二叉樹。
（3） 在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。
【例】如圖(c)中，結點F沒有左孩子而有右孩子L，故它不是一棵完全二叉樹。
【例】圖(b)是一棵完全二叉樹。
性質4 具有n個結點的完全二叉樹的深度為
證明：設所求完全二叉樹的深度為k。由完全二叉樹定義可得：
深度為k得完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結點。
由于完全二叉樹深度為k，故第k層上還有若幹個結點，是以該完全二叉樹的結點個數：
n>2k-1-1。
另一方面，由性質2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取對數後有：
k-1≤lgn<k
又因k-1和k是相鄰的兩個整數，故有
,
由此即得：
注意：
的證明【參見參考書目】
原文位址：http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.2.2.htm