第4單元非線性數(shù)據(jù)結(jié)構(gòu)樹、二叉樹主講：劉志強(qiáng)(已改無錯字)
2022-12-06 15:15:40 本頁面
【正文】 7 第 i個結(jié)點(diǎn)就存放在第 i個位置上； 第 i個結(jié)點(diǎn)（ i1)的父結(jié)點(diǎn)就存放在第 i/2個位置 。 第 i個結(jié)點(diǎn)（ i? 2k1 1)的左子結(jié)點(diǎn)就存放在 第 2*i的個位置 。右子存放在第 2*i+1位置。 下一頁 上一頁 停止放映 第 48 頁 完全二叉樹 ? 深度為 k的二叉樹 T,每層結(jié)點(diǎn)數(shù)目若滿足 : – 第 i層 (1 ? i ? k1)上的結(jié)點(diǎn)個數(shù)均為 2i1(非葉結(jié)點(diǎn) )。 – 第 k層從右邊連續(xù)缺若干個結(jié)點(diǎn) (即只能從右至左不間斷缺少 )。 稱這樣的樹為完全二叉樹 。 ? （ a） 完全二叉樹 （ b） 非完全二叉樹 特點(diǎn) : 葉結(jié)點(diǎn)只可能出現(xiàn)在層次最大的兩層上 . O O O O O O O O O O O 下一頁 上一頁 停止放映 第 49 頁 完全二叉樹的性質(zhì) ? 設(shè)完全二叉樹的結(jié)點(diǎn)總數(shù)為 n， 深度為 k， 某結(jié)點(diǎn)編號為 i（ 1 ?i ? n ） ， 則有： – 若 i1,則結(jié)點(diǎn) i的雙親結(jié)點(diǎn)的編號為 i /2。 – 若 2* i ? n,則結(jié)點(diǎn) i 的左子結(jié)點(diǎn)的編號為 2* i,否則 ,結(jié)點(diǎn) i為葉結(jié)點(diǎn) 。 – 若 2* i +1? n,則結(jié)點(diǎn) i 的右子結(jié)點(diǎn)的編號為 2*i+1,否則 ,結(jié)點(diǎn) i為葉結(jié)點(diǎn) . ? 同理 ,完全二叉樹也可以采用一維樹組作為存儲結(jié)構(gòu) ,且方法完全同滿二叉樹 ,只不過 n ? 2k 1 罷了 . 下一頁 上一頁 停止放映 第 50 頁 平衡二叉樹 二叉樹上任一結(jié)點(diǎn)的左子樹深度減去右子樹深度的差值 ， 稱為該結(jié)點(diǎn)的平衡因子 。 任意結(jié)點(diǎn)左 、 右子樹的深度之差的絕對值?1 ， 這樣的樹稱為平衡二叉樹 。 （ a） 平衡二叉樹 （ b） 非平衡二叉樹 O O O O O O O O O O O O O O 下一頁 上一頁 停止放映 第 51 頁 二叉排序樹定義（一） 二叉排序樹 或者是空二叉樹； 或者是： 左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 右子樹上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值； 左 、 右子樹本身又是一棵二叉排序樹 。 下一頁 上一頁 停止放映 第 52 頁 二叉排序樹定義（二） X是二叉排序樹 T中的一個結(jié)點(diǎn)； – 所有的左后裔小于 X； – 所有的右后裔大于等于 X； – T可以為空樹； T稱為二叉排序樹 。 （ a） 二叉排序樹 （ b） 非二叉排序樹 10 5 7 11 14 18 15 15 14 18 5 10 12 13 7 下一頁 上一頁 停止放映 第 53 頁 二叉樹的遍歷 ? 遍歷 （ Traversing） 是樹形結(jié)構(gòu)的一種重要運(yùn)算 ， 即按一定的次序系統(tǒng)地訪問結(jié)構(gòu)中的所有結(jié)點(diǎn) ， 使每個結(jié)點(diǎn)只被訪問一次 。 ? 遍歷的方法很多 ， 常用的有： – 前序法 （ PreOrder） – 中序法 （ InOrder） – 后序法 （ PostOrder） 下一頁 上一頁 停止放映 第 54 頁 前序法（ PreOrder） 方法描述： – 從根結(jié)點(diǎn) a開始訪問 ， – 接著訪問左子結(jié)點(diǎn) b， – 最后訪問右子結(jié)點(diǎn) c。 即： 根 左子 右子 a b c 下一頁 上一頁 停止放映 第 55 頁 中序法（ InOrder） 方法描述： 從左子結(jié)點(diǎn) b開始訪問 ， 接著訪問根結(jié)點(diǎn) a， 最后訪問右子結(jié)點(diǎn) c。 即： 根 左子 右子 a b c 下一頁 上一頁 停止放映 第 56 頁 后序法（ PostOrder） ? 方法描述： – 從左子結(jié)點(diǎn) b開始訪問 ， – 接著訪問右子結(jié)點(diǎn) c， – 最后訪問根結(jié)點(diǎn) a。 ? 即： 根 左子 右子 a b c 下一頁 上一頁 停止放映 第 57 頁 二叉樹的遍歷舉例 o o o o o o o o o A B C D E F G H I 前序遍歷序列： ABDEGCFHI 中序遍歷序列： DBGEACHFI 后序遍歷序列： DGEBHIFCA 下一頁 上一頁 停止放映 第 58 頁 二叉樹遍歷算法 二叉樹 遍 歷方法分為： – 遞歸算法 – 非遞歸算法 遞歸算法和非遞歸算法中又分： – 前序法 – 中序法 – 后序法 下一頁 上一頁 停止放映 第 59 頁 二叉樹遍歷算法（遞歸算法） 二叉鏈表的 C語言描述： struct tnode { char data； struct tnode *lchild， *rchild ； } ； typedef struct tnode TNODE。 下一頁 上一頁 停止放映 第 60 頁 二叉樹遍歷算法（遞歸、前序法程序 ） void preorder_t (TNODE *root) { if ( root != NULL ) { printf(“%d \n”,rootdata)。 if (rootlc!=NULL) proorder_t(rootlc)。 if (rootrc!=NULL) proorder_t(rootrc)。 } } 前序遍歷二叉樹的序列為： A B C D E F A B C D E F 下一頁 上一頁 停止放映 第 61 頁 二叉樹遍歷算法（遞歸、前序法程序驗證 ） 打印 A – 取 A?.左子 (B) – 打印 B 取 B?.左子 (C) 打印 C – 取 C?.左子 (空 ) – 取 C?.右子 (空 ) 取 B?.右子 (D) 打印 D – 取 D?.左子 (E) – 打印 E 取 E?.左子 (空 ) 取 E?.右子 (空 ) – 取 D?.右子 (F) – 打印 F 取 F?.左子 (空 ) 取 F?.右子 (空 ) – 取 A?.右子 (空 ) 結(jié)束 A B C D E F 下一頁 上一頁 停止放映 第 62 頁 二叉樹遍歷算法 （非遞歸算法 前序法） ? 算法步驟 : – step1 初始化 ,置棧為空 (top=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1