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