第4單元非線性數(shù)據(jù)結(jié)構(gòu)樹(shù)、二叉樹(shù)主講：劉志強(qiáng)-資料下載頁(yè)
2025-10-15 15:15本頁(yè)面
【導(dǎo)讀】數(shù)據(jù)間不是一一對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如何描述？結(jié)構(gòu)的基礎(chǔ)上進(jìn)行操作（增、刪、為什么采用二叉樹(shù)？叉樹(shù)能夠相互轉(zhuǎn)換嗎？結(jié)點(diǎn)、根、葉、路徑、結(jié)點(diǎn)度、結(jié)點(diǎn)的層次、子結(jié)點(diǎn)、父結(jié)點(diǎn)。樹(shù)形結(jié)構(gòu)是以分支關(guān)系來(lái)定義的層次結(jié)構(gòu)。–各種社會(huì)組織機(jī)構(gòu)；D是具有相同特性的數(shù)據(jù)元素的集合；–D中其余數(shù)據(jù)元素都有且只有一個(gè)前趨；繼（子樹(shù)），或無(wú)后繼（葉結(jié)點(diǎn)）；0）個(gè)互不相交的集合T1，且每個(gè)集合又是一棵樹(shù)，它們稱為這個(gè)根的子樹(shù)。樹(shù)的度樹(shù)中結(jié)點(diǎn)的最大度數(shù)；上述樹(shù)的度為3。；H，I，J互為兄弟。為1，子結(jié)點(diǎn)為2，依次類推。例如，結(jié)點(diǎn)A到M的高度為4。中每個(gè)結(jié)點(diǎn)而言，其子樹(shù)的集合即為森林。點(diǎn)均為該結(jié)點(diǎn)的祖先。找不到第i個(gè)子結(jié)點(diǎn)則返回空值。CREATE（x，T1，T2，…,Tk)生成一個(gè)結(jié)點(diǎn)x,下。中各個(gè)結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)只能被訪問(wèn)一次。一個(gè)指示器指示其雙親結(jié)點(diǎn)在數(shù)組中的位置。
【正文】 1), 工作變量 p指向 root。 – step2 p非空 (p!=NULL) 或棧非空 (top!=1)循環(huán) 。 – step3 p非空循環(huán) 。 訪問(wèn) p(打印 pdata)。 – step4 當(dāng)前元素進(jìn)棧 , p取 plc。 執(zhí)行 step3； – step5 p為空 ， 棧非空 ， 則出棧 ， p取 prc, 返回 step2. 下一頁(yè) 上一頁(yè) 停止放映 第 63 頁(yè) 二叉樹(shù)遍歷算法 （ 非遞歸算法 前序法程序） define N m void preorder_t(TNODE * root) { TNODE *p, *stack[N]。 int top=1。 p=root。 while ((p!= NULL)||(top!= 1)) { while ( P!=NULL) { printf(“%d\n”,pdata)。 top ++。 stack[top]=p。 p=plc。 } if ( top !=1) { p=stack[top]。 top 。 p=prc。 } } } 下一頁(yè) 上一頁(yè) 停止放映 第 64 頁(yè) 二叉樹(shù)遍歷算法 （非遞歸、前序法程序驗(yàn)證） 打印 A – A進(jìn)棧 ， 取 A?.左子 ( B ) – 打印 B B進(jìn)棧，取 B?.左子 ( C ) 打印 C – C 進(jìn)棧， 取 C?.左子 ( 空 ) – C 退棧， 取 C?.右子 ( 空 ) B 退棧， 取 B?.右子 ( D ) 打印 D – D進(jìn)棧，取 D?.左子 ( E ) – 打印 E E進(jìn)棧，取 E?.左子 ( 空 ) E退棧， 取 E?.右子 ( 空 ) – D退 棧，取 D?.右子 ( F ) – 打印 F F進(jìn)棧，取 F?.左子 ( 空 ) F退棧， 取 F?.右子 ( 空 ) – A退 棧，取 A?.右子 ( 空 ) 結(jié)束 F E D C B A 下一頁(yè) 上一頁(yè) 停止放映 第 65 頁(yè) 表達(dá)式樹(shù)及應(yīng)用 在計(jì)算機(jī)中對(duì)表達(dá)式進(jìn)行分析和計(jì)算是一項(xiàng)重要的任務(wù) 。 舉例 ， 用二叉樹(shù)表示表達(dá)式： a + b * （ c d ） － ｅ ／ｆ 前序遍歷序列：－＋ａ＊ｂ－ｃｄ／ｅｆ 中序遍歷序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ 后序遍歷序列：ａｂｃｄ－＊＋ｅｆ／－ 分析： – 每個(gè)葉結(jié)點(diǎn)為運(yùn)算對(duì)象； – 每個(gè)非葉結(jié)點(diǎn)為運(yùn)算符； – 每個(gè)子樹(shù)對(duì)應(yīng)一個(gè)子表達(dá)式 。 表達(dá)式處理一般采用后序法 ， 也稱 ? 逆波蘭 ? 法 。 表達(dá)式處理規(guī)則： – 見(jiàn)運(yùn)算數(shù)入棧； – 見(jiàn)運(yùn)算符 ， 取兩個(gè)棧頂元素運(yùn)算后再壓棧； – 直到處理結(jié)束 。 － ＋ ／ － e f ＊b － c d a 下一頁(yè) 上一頁(yè) 停止放映 第 66 頁(yè) 表達(dá)式樹(shù)應(yīng)用舉例 （ 1） a b c d 入棧 ， （ 2） 遇 ‘ ’， c d 出棧 ， 運(yùn)算后再壓棧； （ 3） 遇 ‘ *’ ， （ c d） 和 b 出棧 ， 運(yùn)算后再壓棧； （ 4） 遇 ‘ +’， b*（ cd） 和 a出棧 ， 運(yùn)算后再壓棧； （ 5） e f 入棧； （ 6） 遇 ‘ /’， f e 出棧 ， 運(yùn)算后再壓棧； （ 7） 遇 ‘ ’， a+b*（ cd） 和 e/f出棧 ， 運(yù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 下一頁(yè) 上一頁(yè) 停止放映 第 67 頁(yè) 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 ? 由于二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)比較簡(jiǎn)單 ，處理起來(lái)也比較方便 ， 所以有時(shí)需要把復(fù)雜的樹(shù) ， 轉(zhuǎn)換為簡(jiǎn)單的二叉樹(shù)后再作處理 。 ? 樹(shù)轉(zhuǎn)換成二叉樹(shù) ? 森林轉(zhuǎn)換成二叉樹(shù) 下一頁(yè) 上一頁(yè) 停止放映 第 68 頁(yè) 樹(shù)轉(zhuǎn)換成二叉樹(shù) 操作算法： – 保留一個(gè)結(jié)點(diǎn)的最左子結(jié)點(diǎn)； – 抹掉其余兄弟結(jié)點(diǎn)與上級(jí)結(jié)點(diǎn)的連線； – 將兄弟結(jié)點(diǎn)連在一起； – 以根為軸 ， 順時(shí)針旋轉(zhuǎn)一個(gè)角度 。 舉例： 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 下一頁(yè) 上一頁(yè) 停止放映 第 69 頁(yè) 森林轉(zhuǎn)換成二叉樹(shù) 操作算法： – 將森林中每棵樹(shù)的樹(shù)根連接起來(lái)； – 將每棵樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)； – 以森林中第一棵樹(shù)的根為軸順時(shí)針旋轉(zhuǎn)一個(gè)角度 。 舉例 o o o o o o o o o 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 o o o 下一頁(yè) 上一頁(yè) 停止放映 第 70 頁(yè) 將二叉樹(shù)還原成樹(shù) 將二叉樹(shù)還原成樹(shù)的操作步驟為： step1 若某結(jié)點(diǎn)是其雙親的左子，則把該結(jié)點(diǎn)的右子、右子的右子、 … ,都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái)； step2 刪除原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右子結(jié)點(diǎn)的連線； step3 整理 2兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。 下一頁(yè) 上一頁(yè) 停止放映 第 71 頁(yè) 舉例 A B E C F D G A B E C F D G （ a）二叉樹(shù) （ b）加連線 A B E C F D G （ c）刪除與 右子的連線 A B E C F D G （ d）還原后的樹(shù) 下一頁(yè) 上一頁(yè) 停止放映 第 72 頁(yè) 中心網(wǎng)址： 作業(yè)提交地址： 我的 Email地址 : 答疑安排： 星期四下午： 4:00～ 6:00 地點(diǎn)：計(jì)教中心 102房間 (1300大教室對(duì)面 ) 謝謝，再見(jiàn)！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1