【正文】 parent data rightp 左指針 數(shù)據(jù) 父結(jié)點 右指針 A B C D E F G C ^ ^ ^ ^ ^ ^ 特點 : 找子、找父都易 。 leftp ^ ^ A B D E G ^ F 下一頁 上一頁 停止放映 第 22 頁 特殊二叉樹 ?滿二叉樹 ?完全二叉樹 ?平衡二叉樹 ?二叉排序樹 下一頁 上一頁 停止放映 第 23 頁 滿二叉樹 ? 若 k為二叉樹 T的深度 ， 且 T中共有 2k1個結(jié)點 （ k ? 1） ， 則稱 T為滿二叉樹 。 （ a） 滿二叉樹 （ b） 非滿二叉樹 O O O O O O O O O O O O O 下一頁 上一頁 停止放映 第 24 頁 滿二叉樹的性質(zhì) ? 若 對滿二叉樹從第 1層開始 ,自上而下 、從左至右給每個結(jié)點從 1開始編號的話 ，則稱深度為 k的滿二叉樹的結(jié)點編號滿足： – 對某結(jié)點 i（ 1? i ? 2k 1 1） ， 其左子樹的編號為 2*i（ 偶數(shù) ） ， 其右子樹的編號為 2* i +1（ 奇數(shù) ） ； （ 非葉結(jié)點 ） – 若 i1, 則結(jié)點 i 父結(jié)點的編號為i/2(整除 )。 下一頁 上一頁 停止放映 第 25 頁 滿二叉樹存儲 1 4 3 2 5 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 ?第 i個結(jié)點就存放在第 i個位置上； ?第 i個結(jié)點（ i1)的父結(jié)點就存放在第 i/2個位置 。 ?第 i個結(jié)點（ i? 2k 1 1)的左子結(jié)點就存放在 第 2*i的個位置 。右子存放在第2*i+1位置 . 下一頁 上一頁 停止放映 第 26 頁 完全二叉樹 ? 深度為 k的二叉樹 T,每層結(jié)點數(shù)目若滿足 : – 第 i層 (1 ? i ? k1)上的結(jié)點個數(shù)均為 2i1(非葉結(jié)點 )。 – 第 k層從右邊連續(xù)缺若干個結(jié)點 (即只能從右至左不間斷缺少 )。 稱這樣的樹為完全二叉樹 。 ? （ a） 完全二叉樹 （ b） 非完全二叉樹 ? 特點 : 葉結(jié)點只可能出現(xiàn)在層次最大的兩層上 . O O O O O O O O O O O 下一頁 上一頁 停止放映 第 27 頁 完全二叉樹的性質(zhì) ? 設(shè)完全二叉樹的結(jié)點總數(shù)為 n， 深度為 k， 某結(jié)點編號為 i（ 1 ?i ? n ） ， 則有： – 若 i1,則結(jié)點 i的雙親結(jié)點的編號為 i /2。 – 若 2* i ? n,則結(jié)點 i 的左子結(jié)點的編號為 2* i,否則 ,結(jié)點 i為葉結(jié)點 。 – 若 2* i +1? n,則結(jié)點 i 的右子結(jié)點的編號為2*i+1,否則 ,結(jié)點 i為葉結(jié)點 . ? 同理 ,完全二叉樹也可以采用一維樹組作為存儲結(jié)構(gòu) ,且方法完全同滿二叉樹 ,只不過 n ? 2k 1 罷了 . 下一頁 上一頁 停止放映 第 28 頁 平衡二叉樹 ? 二叉樹上任一結(jié)點的左子樹深度減去右子樹深度的差值 ， 稱為該結(jié)點的平衡因子 。 ? 任意結(jié)點左 、 右子樹的深度之差的絕對值?1 ， 這樣的樹稱為平衡二叉樹 。 ? （ a） 平衡二叉樹 （ b） 非平衡二叉樹 O O O O O O O O O O O O O O 下一頁 上一頁 停止放映 第 29 頁 二叉排序樹定義（一） ? 二叉排序樹 – 或者是空二叉樹； – 或者是： ?左子樹上所有結(jié)點的值均小于根結(jié)點的值； ?右子樹上所有結(jié)點的值均大于等于根結(jié)點的值； – 左 、 右子樹本身又是一棵二叉排序樹 。 下一頁 上一頁 停止放映 第 30 頁 二叉排序樹定義（二） ? X是二叉排序樹 T中的一個結(jié)點； – 所有的左后裔小于 X； – 所有的右后裔大于等于 X； – T可以為空樹； T稱為二叉排序樹 。 （ a） 二叉排序樹 （ b） 非二叉排序樹 10 5 7 12 14 18 15 15 14 18 5 10 12 13 7 下一頁 上一頁 停止放映 第 31 頁 二叉樹的 遍 歷 ? 遍 歷 （ Traversing） 是樹形結(jié)構(gòu)的一種重要運算 ， 即按一定的次序系統(tǒng)地訪問樹中的所有結(jié)點 ， 使每個結(jié)點只被訪問一次 。 ? 遍 歷的方法很多 ， 常用的有： – 先序法 （ PreOrder） – 中序法 （ InOrder） – 后序法 （ PostOrder） 下一頁 上一頁 停止放映 第 32 頁 先序法（ PreOrder） ? 方法描述： – 訪問根結(jié)點 ， – 先序遍歷左子樹 ， – 先序遍歷右子樹 。 ? 即： 根 左子樹 右子樹 o o o o o o o o o A B C D E F G H I ABDEGCFHI 下一頁 上一頁 停止放映 第 33 頁 中序法（ InOrder） ? 方法描述： – 中序遍歷左子樹 ， – 訪問根結(jié)點 ， – 中序遍歷右子樹 。 ? 即： 根 左子樹 右子樹 o o o o o o o o o A B C D E F G H I DBGEACHFI 下一頁 上一頁 停止放映 第 34 頁 后序法（ PostOrder） ? 方法描述： – 后序遍歷左子樹 ， – 后序遍歷右子樹 ， – 訪問根結(jié)點 ? 即： 根 左子數(shù) 右子樹 o o o o o o o o o A B C D E F G H I DGEBHIFCA 下一頁 上一頁 停止放映 第 35 頁 二叉樹遍歷算法 ? 二叉樹 遍 歷方法分為： – 遞歸算法 – 非遞歸算法 ? 遞歸算法和非遞歸算法中又分： – 前序法 – 中序法 – 后序法 下一頁 上一頁 停止放映 第 36 頁 二叉樹遍歷算法 （遞歸算法） ?二叉鏈表的 C++語言描述： struct tnode { int data； struct tnode *lchild， *rchild ； } ； typedef struct tnode TNODE。 下一頁 上一頁 停止放映 第 37 頁 二叉樹遍歷算法 （遞歸、前序法程序） ? void preOrder_t (TNODE *root) { if ( root != NULL ) {coutrootdata“ “。 proOrder_t(rootlchild)。 proOrder_t(rootrchild)。 } } ? 前序遍歷二叉樹的序列為： A B C D E F A B C D E F 下一頁 上一頁 停止放映 第 38 頁 二叉樹遍歷算法 （遞歸、中序法程序） ? void inOrder_t(TNODE *root) { if ( root != NULL ) {inorder_t(rootlchild)。 outrootdata“ “。 inorder_t(rootrchild)。 } } A B C D E F 下一頁 上一頁 停止放映 第 39 頁 二叉樹遍歷算法 （遞歸、后序法程序） ? void postOrder_t(TNODE *root) { if ( root != NULL ) { postOrder_t(rootlchild)。 postOrder_t(rootrchild)。 outrootdata“ “。 } } A B C D E F 下一頁 上一頁 停止放映 第 40 頁 建立二叉樹 include include struct tnode{ char data。 struct tnode *lchild, *rchild。 } 。 typedef struct tnode