第4單元非線性數(shù)據(jù)結(jié)構(gòu)樹、二叉樹主講：劉志強(參考版)
2024-10-28 15:15本頁面
【正文】 下一頁 上一頁 停止放映 第 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地址 : 答疑安排： 星期四下午： 4:00～ 6:00 地點：計教中心 102房間 (1300大教室對面 ) 謝謝，再見！ 。 舉例： o o o o o o o o o o o o o o 加線 抹線 o o o o o o o 旋轉(zhuǎn) o o o o o o o 下一頁 上一頁 停止放映 第 69 頁 森林轉(zhuǎn)換成二叉樹 操作算法： – 將森林中每棵樹的樹根連接起來； – 將每棵樹轉(zhuǎn)換成對應(yīng)的二叉樹； – 以森林中第一棵樹的根為軸順時針旋轉(zhuǎn)一個角度 。 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)比較簡單 ，處理起來也比較方便 ， 所以有時需要把復(fù)雜的樹 ， 轉(zhuǎn)換為簡單的二叉樹后再作處理 。 表達式處理規(guī)則： – 見運算數(shù)入棧； – 見運算符 ， 取兩個棧頂元素運算后再壓棧； – 直到處理結(jié)束 。 舉例 ， 用二叉樹表示表達式： a + b * （ c d ） － ｅ ／ｆ 前序遍歷序列：－＋ａ＊ｂ－ｃｄ／ｅｆ 中序遍歷序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ 后序遍歷序列：ａｂｃｄ－＊＋ｅｆ／－ 分析： – 每個葉結(jié)點為運算對象； – 每個非葉結(jié)點為運算符； – 每個子樹對應(yīng)一個子表達式 。 p=prc。 } if ( top !=1) { p=stack[top]。 stack[top]=p。 while ((p!= NULL)||(top!= 1)) { while ( P!=NULL) { printf(“%d\n”,pdata)。 int top=1。 – step4 當(dāng)前元素進棧 , p取 plc。 – step3 p非空循環(huán) 。 } } 前序遍歷二叉樹的序列為： 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。 if (rootlc!=NULL) proorder_t(rootlc)。 ? 即： 根 左子 右子 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 下一頁 上一頁 停止放映 第 55 頁 中序法（ InOrder） 方法描述： 從左子結(jié)點 b開始訪問 ， 接著訪問根結(jié)點 a， 最后訪問右子結(jié)點 c。 （ 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） 非平衡二叉樹 O O O O O O O O O O O O O O 下一頁 上一頁 停止放映 第 51 頁 二叉排序樹定義（一） 二叉排序樹 或者是空二叉樹； 或者是： 左子樹上所有結(jié)點的值均小于根結(jié)點的值； 右子樹上所有結(jié)點的值均大于等于根結(jié)點的值； 左 、 右子樹本身又是一棵二叉排序樹 。 – 若 2* i +1? n,則結(jié)點 i 的右子結(jié)點的編號為 2*i+1,否則 ,結(jié)點 i為葉結(jié)點 . ? 同理 ,完全二叉樹也可以采用一維樹組作為存
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1