第4單元非線性數(shù)據(jù)結(jié)構(gòu)樹、二叉樹主講：劉志強(文件)
【正文】 F G 0 1 2 3 4 5 6 7 A B C D E F G 0 1 2 3 4 5 6 7 A B E A B E 滿樹 非滿樹 下一頁 上一頁 停止放映 第 39 頁 順序存儲（一維數(shù)組） 存儲描述為： define MAXSIZE 100； typedef TElemType SBTree[MAXSIZE]； SBTree bt； 不便查找 。 } SBNode。 leftp ^ ^ A B D E G ^ F 下一頁 上一頁 停止放映 第 44 頁 特殊二叉樹 滿二叉樹 完全二叉樹 平衡二叉樹 二叉排序樹 下一頁 上一頁 停止放映 第 45 頁 滿二叉樹 若 k為二叉樹 T的深度 ， 且 T中共有 2k1個結(jié)點 （ k ? 1） ， 則稱 T為滿二叉樹 。 下一頁 上一頁 停止放映 第 47 頁 滿二叉樹存儲舉例 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個位置 。 – 第 k層從右邊連續(xù)缺若干個結(jié)點 (即只能從右至左不間斷缺少 )。 – 若 2* i +1? n,則結(jié)點 i 的右子結(jié)點的編號為 2*i+1,否則 ,結(jié)點 i為葉結(jié)點 . ? 同理 ,完全二叉樹也可以采用一維樹組作為存儲結(jié)構(gòu) ,且方法完全同滿二叉樹 ,只不過 n ? 2k 1 罷了 . 下一頁 上一頁 停止放映 第 50 頁 平衡二叉樹 二叉樹上任一結(jié)點的左子樹深度減去右子樹深度的差值 ， 稱為該結(jié)點的平衡因子 。 （ a） 二叉排序樹 （ b） 非二叉排序樹 10 5 7 11 14 18 15 15 14 18 5 10 12 13 7 下一頁 上一頁 停止放映 第 53 頁 二叉樹的遍歷 ? 遍歷 （ Traversing） 是樹形結(jié)構(gòu)的一種重要運算 ， 即按一定的次序系統(tǒng)地訪問結(jié)構(gòu)中的所有結(jié)點 ， 使每個結(jié)點只被訪問一次 。 ? 即： 根 左子 右子 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。 } } 前序遍歷二叉樹的序列為： 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=1), 工作變量 p指向 root。 – step4 當前元素進棧 , p取 plc。 while ((p!= NULL)||(top!= 1)) { while ( P!=NULL) { printf(“%d\n”,pdata)。 } if ( top !=1) { p=stack[top]。 舉例 ， 用二叉樹表示表達式： a + b * （ c d ） － ｅ ／ｆ 前序遍歷序列：－＋ａ＊ｂ－ｃｄ／ｅｆ 中序遍歷序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ 后序遍歷序列：ａｂｃｄ－＊＋ｅｆ／－ 分析： – 每個葉結(jié)點為運算對象； – 每個非葉結(jié)點為運算符； – 每個子樹對應一個子表達式 。 d c b a （ 1） （ 2） c d b a （ 3） b*（ cd） a （ 5） a+b*（ cd） （ 4） a+b*（ cd） f e （ 6） e/f a+b*（ cd） （ 7） a+b*（ cd） e/f 下一頁 上一頁 停止放映 第 67 頁 樹、森林與二叉樹的轉(zhuǎn)換 ? 由于二叉樹的存儲結(jié)構(gòu)比較簡單 ，處理起來也比較方便 ， 所以有時需要把復雜的樹 ， 轉(zhuǎn)換為簡單的二叉樹后再作處理 。 下一頁 上一頁 停止放映 第 71 頁 舉例 A B E C F D G A B E C F D G （ a）二叉樹 （ b）加連線 A B E C F D G （ c）刪除與 右子的連線 A B E C F D G （ d）還原后的樹 下一頁 上一頁 停止放映 第 72 頁 中心網(wǎng)址： 作業(yè)提交地址： 我的 Email地址 :
教學課件相關推薦
鄂ICP備17016276號-1