二叉樹基本性質

第 i 層的節點數最多為2^i-1 個(i>=1)，
深度為K 的二叉樹中，節點總數N最多為2^K-1個(k>=1)，
eg: 設k為4，為滿二叉樹，證明2^k-1方程，
2⁰+2¹+2²+2³ = 2⁴-1
1. 由第二條可推算出，具有N個結點的二叉樹的深度為 [log₂N]+1 ，
  --------即 K=[log₂N]+1 --------
總節點數N=N₁ 個度為1的結點，N₂個度為2的結點，N₀個度為0的結點相加，
--------即N=N₀+N₁+N₂--------
總分支數M=總結點數N-1，即M=N-1；如果由度為1或度為2的結點來計算總分支數M，**
--------即M=N₁+2N₂--------
1. 由第四條可推算出，總結點N=度為1的結點+2倍的度為2的結點+1，
  --------即N=N₁+2N₂+1--------
2. 由第三條和第五條結合可推算出，度為0的結點總比度為2的結點多一個，
  --------即N₀=N₂-1--------
設一顆有N個結點的完全二叉樹的結點從1到N按照層次順序編號（從左到右）編號，對任意一結點 i（1<=i<=N），有多種情況，
1. i=1時，結點 i 是二叉樹的根，沒有父結點，
2. i>1時，父結點的編號為 [i/2]，（向下舍入）
3. 2i>N時，在此范圍內無左子結點，
4. 2i<N時，左子結點的編號為 2i ，
5. 2i+1>N時，在此范圍內無右子結點，
6. 2i+1<N時，右子結點的編號為2i+1，

二叉樹的存盤結構

二叉樹可用順序存盤結構也可用鏈式存盤結構，

鏈式存盤結構

存盤方法：資料域、指標域（左指標域、右指標域）
二叉樹的存盤方法
可根據二叉樹的性質來計算出各結點的層次關系，

順序存盤結構

將二叉樹存盤在一個陣列里，通過存盤元素的下標來反映元素之間的上下件關系，

二叉樹的遍歷

遍歷指按一定的次序訪問二叉樹中的每一個結點，

遍歷：前序遍歷（DLR）、中序遍歷（LDR）、后序遍歷（LRD）
D(Data)：訪問根結點
L(lchild)：遍歷根結點的左子樹
R(rchild)：遍歷根結點的右子樹

??：二叉樹為空時，則結束回傳，

前序遍歷（DLR）/ 先根遍歷 / 先序遍歷

訪問順序為（1）訪問根結點（2）遍歷根結點的左子樹（3）遍歷根結點的右子樹
前序遍歷
解釋：首先訪問根結點A并記錄，隨后進行遍歷根結點A的左子樹；將B作為根結點進行訪問并記錄，隨后進行遍歷根結點B的左子樹；將D作為根結點進行訪問并記錄，隨后進行遍歷根結點D的左子樹；將G作為根結點進行訪問并記錄，隨后進行遍歷根結點G的左子樹，因根結點G無左子樹，所以轉換為遍歷右子樹；將I作為根結點進行訪問并記錄，因根結點I的左子樹和右子樹都為無，所以向上回傳到根結點G；因根結點G的左右子樹已遍歷完，所以再向上回傳到根結點D；因根結點D的右子樹為無，所以再向上回傳到根結點B；開始遍歷根結點B的右子樹，將E作為根結點進行訪問并記錄，因根結點E的左子樹和右子樹都為無，所以向上回傳到根結點A；開始遍歷根結點A的右子樹；將C作為根結點進行訪問并記錄，因根結點C無左子樹，所以轉換為遍歷右子樹；將F作為根結點進行訪問并記錄，隨后進行遍歷根結點F的左子樹；將H作為根結點進行訪問并記錄，隨后進行遍歷根結點J的左子樹；將J作為根結點進行訪問并記錄，因根結點J的左子樹和右子樹都為無，所以向上回傳到根結點H；開始遍歷根結點H的右子樹，將K作為根結點進行訪問并記錄，因根結點K的左子樹和右子樹都為無，所以向上回傳到根結點H；因根結點H的左右子樹已遍歷完，所以再向上回傳到根結點F，根結點F的右子樹為無，所有節點訪問完成，

中序遍歷（LDR）/ 中根遍歷

訪問順序為（1）遍歷根結點的左子樹（2）訪問根結點（3）遍歷根結點的右子樹
中序遍歷
解釋：首先遍歷根結點A的左子樹，因根結點A有左子樹，所以將B作為根結點開始遍歷根結點B的左子樹；因根結點B有左子樹，所以將D作為根結點開始遍歷根結點D的左子樹；因根結點G無左子樹，所以開始訪問并記錄根結點G；隨后進行遍歷根結點G的右子樹；將I作為根結點，因根結點I無左子樹，所以開始訪問并記錄根結點I；因根結點I無右子樹，所以回傳根結點G；因根結點G已遍歷完，所以回傳根結點D；開始訪問并記錄根結點D；因根結點D無右子樹，所以回傳根結點B；開始訪問并記錄根結點B；隨后進行遍歷根結點B的右子樹；將E作為根結點，因根結點E無左子樹，所以開始訪問并記錄根結點E；因根結點E無右子樹，所以回傳根結點B；因根結點B已遍歷完，所以回傳根結點A；開始訪問并記錄根結點A；隨后進行遍歷根結點A的右子樹；將C作為根結點，因根結點C無左子樹，所以開始訪問并記錄根結點C；隨后進行遍歷根結點C的右子樹；將F作為根結點，因根結點F有左子樹，所以將H作為根結點開始遍歷根結點H的左子樹；因根結點H有左子樹，所以將J作為根結點；因根結點J無左子樹，所以開始訪問并記錄根結點J；因根結點J無右子樹，所以回傳根結點H；開始訪問并記錄根結點H；隨后進行遍歷根結點H的右子樹；將K作為根結點，因根結點K無左子樹，所以開始訪問并記錄根結點K；因根結點K無右子樹，所以回傳根結點H；因根結點H已遍歷完，所以回傳根結點F；開始訪問并記錄根結點F；所有節點訪問完成，

后序遍歷（LRD）/ 后根遍歷

訪問順序為（1）遍歷根結點的左子樹（2）遍歷根結點的右子樹（3）訪問根結點
后序遍歷
解釋：首先遍歷根結點A的左子樹，因根結點A有左子樹，所以將B作為根結點開始遍歷根結點B的左子樹；因根結點B有左子樹，所以將D作為根結點開始遍歷根結點D的左子樹；因根結點G無左子樹，所以轉換為訪問根結點G的右子樹；將I作為根結點，因根結點I無左右子樹，所以開始訪問并記錄根結點I；因根結點I已遍歷完，所以回傳根結點G；因根結點G已遍歷完，所以開始訪問并記錄根結點G；隨后回傳根結點D；因根結點D無右子樹，所以開始訪問并記錄根結點D；因根結點D已遍歷完，所以開始訪問并記錄根結點D；隨后回傳根結點B；隨后進行遍歷根結點B的右子樹；將E作為根結點，因根結點E無左右子樹，所以開始訪問并記錄根結點E；隨后回傳根結點B；因根結點B已遍歷完，所以開始訪問并記錄根結點B；隨后回傳根結點A；隨后進行遍歷根結點A的右子樹；將C作為根結點，因根結點C無左子樹，隨后進行遍歷根結點C的右子樹；將F作為根結點，因根結點F有左子樹，所以將H作為根結點開始遍歷根結點H的左子樹；因根結點H有左子樹，所以將J作為根結點；因根結點J無左右子樹，所以開始訪問并記錄根結點J；因根結點J已遍歷完，所以回傳根結點H；隨后進行遍歷根結點H的右子樹；將K作為根結點，因根結點K無左右子樹，所以開始訪問并記錄根結點K；因根結點K已遍歷完，所以回傳根結點H；因根結點H已遍歷完，所以開始訪問并記錄根結點H；隨后回傳根結點F；因根結點F無右子樹，所以開始訪問并記錄根結點F；隨后回傳根結點C；因根結點C已遍歷完，所以開始訪問并記錄根結點C；隨后回傳根結點A；因根結點A已遍歷完，所以開始訪問并記錄根結點A；所有節點訪問完成，

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/158170.html

標籤：其他

上一篇：資料存盤計量單位換算

下一篇：第六章：可執行檔案的裝載與行程--重點知識概括整理

筆記：計算機公共基礎知識學習內容——樹與二叉樹(二)