大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第五章：樹和二叉樹-第五節(jié)-森林和樹

第五節(jié)森林和樹一、樹的存儲結(jié)構(gòu)1、雙親表示法在雙親表示法中，每個存儲結(jié)點由兩個域組成：數(shù)據(jù)域--存儲樹上結(jié)點的數(shù)據(jù)元素；雙親域--存儲雙親結(jié)點在結(jié)點數(shù)組中的下標值。在這種表示法下，求指定結(jié)點的祖先很方便，但求指定結(jié)點的子孫則不方便。2、孩子鏈表表示法孩子鏈表表示法的基本思想是：為樹上的每個結(jié)點X建立一個"孩子鏈表"，存儲X中的數(shù)據(jù)元素和指向X的所有孩子的指針。一個孩子鏈表是一個帶頭結(jié)點的單鏈表，單鏈表的頭結(jié)點含兩個域：數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域用于存儲結(jié)點X中的數(shù)據(jù)元素；指針域用于存放指向該單鏈表中第一個表結(jié)點（首結(jié)點）的指針。為了檢索方便，所有頭結(jié)點組織成一個數(shù)組，稱為表頭數(shù)組。對每個結(jié)點X的孩子鏈表來說，其中的所有表結(jié)點也含兩個域，孩子域（即數(shù)據(jù)域）和指針域。第i個表結(jié)點的孩子域存儲X的第i個孩子在頭結(jié)點數(shù)組中的下標值。為了便于查找雙親，可在各個頭結(jié)點中增加一個雙親域以存儲雙親結(jié)點在頭結(jié)點數(shù)組中的下標值，稱其為帶雙親的孩子鏈表表示法。3、孩子兄弟表示法孩子兄弟表示法又稱二叉鏈表表示法，孩子兄弟表示法中所有存儲結(jié)點的形式相同，均含三個域：數(shù)據(jù)域--存儲樹上結(jié)點的數(shù)據(jù)元素；孩子域--存放指向本結(jié)點第一個孩子的指針；兄弟域--存放指向本結(jié)點下一個兄弟的指針。二、樹、森林與二叉樹的轉(zhuǎn)換1、樹、森林轉(zhuǎn)換為二叉樹（1）樹轉(zhuǎn)換為二叉樹將一棵樹轉(zhuǎn)換為二叉樹可以按以下步驟進行：①在所有相鄰兄弟結(jié)點之間分別加一條連線。②對每個分支結(jié)點，除了其最左孩子外，刪去該結(jié)點與其他孩子結(jié)點的連線。③以根結(jié)點為軸心，順時針旋轉(zhuǎn)45°。注意：由樹轉(zhuǎn)換的二叉樹的根結(jié)點的右孩子始終為空，原因是樹的根結(jié)點不存在兄弟結(jié)點。下圖給出的例子顯示了這一轉(zhuǎn)換過程。（2）森林轉(zhuǎn)換為二叉樹將森林轉(zhuǎn)換為二叉樹的步驟可以歸納如下：①分別將樹林中的每棵樹轉(zhuǎn)換為二叉樹。②從最后那棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹的根結(jié)點的右孩子，直到所有二叉樹全部連接，這樣得到的二叉樹的根結(jié)點就是樹林中第一棵樹的根結(jié)點。【真題選解】（例題?選擇題）森林T中有4棵樹，第1、2、3、4棵樹的結(jié)點個數(shù)分別是n1、n2、n3、n4，那么當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點的左子樹上有（）個結(jié)點。A．n1-1B．n1C．nl+n2+n3D．n2+n3+n4隱藏答案【解答】A【解析】將森林轉(zhuǎn)換成一棵二叉樹時，它的第一棵樹除根結(jié)點外將構(gòu)成二叉樹的左子樹，其余各棵樹將構(gòu)成二叉樹的右子樹。所以轉(zhuǎn)換后得到的二叉樹，其左子樹上的結(jié)點個數(shù)為森林的第一棵樹除其根結(jié)點外其余結(jié)點數(shù)，本題為n1-1；其右子樹上的結(jié)點個數(shù)為森林中除第一棵樹外其余各棵樹的結(jié)點總和，本題為n2+n3+n4。（3）二叉樹轉(zhuǎn)換為樹將一棵二叉樹轉(zhuǎn)換為樹可以按下列步驟進行：①若某結(jié)點是其雙親結(jié)點的左孩子，則將該結(jié)點的右孩子以及當(dāng)且僅當(dāng)連續(xù)地沿著此右孩子的右子樹方向不斷地搜索到的所有右孩子，都分別與該結(jié)點的雙親結(jié)點用虛線連接起來。②刪去原二叉樹中所有雙親結(jié)點與其右孩子的連線。③將圖形規(guī)整化，使各結(jié)點按層次排列，并且將虛線改成實線。（4）二叉樹轉(zhuǎn)換為森林將一棵二叉樹轉(zhuǎn)換為森林可以按下列步驟進行：①去掉二叉樹的右子樹，將去掉右子樹后剩下的二叉樹轉(zhuǎn)換為一棵樹。②將在第①步中被去掉的右子樹再執(zhí)行第①步。③重復(fù)前兩步，直到轉(zhuǎn)換完成?！菊骖}選解】（例題?簡答題）已知二叉樹如下：請畫出該二叉樹對應(yīng)的森林。隱藏答案【解析】【答案】三、樹和森林的遍歷1、樹的遍歷（1）樹的前序遍歷定義：①訪問根結(jié)點；②依次前序遍歷根的各子樹。（2）樹的后序遍歷定義：①依次后序遍歷根的各子樹；②訪問根結(jié)點R?！纠繉懗鋈鐖D所示樹的前序遍歷和后序遍歷的序列和該樹對應(yīng)二叉樹的前序遍歷、中序遍歷和后序遍歷的序列樹的前序遍歷序列：ABEFGCHDIJ二叉樹的前序遍歷序列：ABEFGCHDIJ樹的后序遍歷序列：EFGBHCIJDA二叉樹的中序遍歷序列：EFGBHCIJDA二叉樹的后序遍歷序列：GFEHJIDCBA注意：①

前序遍歷一棵樹恰好等價于前序遍歷該樹對應(yīng)的二叉樹；②

后序遍歷一棵樹恰好等價于中序遍歷該樹對應(yīng)的二叉樹。2、森林的遍歷（1）前序遍歷森林若森林非空，則：①訪問森林中第一棵樹的根結(jié)點；②前序遍歷第一棵樹中根結(jié)點的各子樹所構(gòu)成的森林③前序遍歷除第一棵樹外其它樹構(gòu)成的森林。（2）后序遍歷森林若森林非空，則：①后序遍歷森林中第一棵樹的根結(jié)點的各子樹所構(gòu)成的森林；②訪問第一棵樹的根結(jié)點；③后序遍歷除第一棵樹外其它樹構(gòu)成的森林。當(dāng)前講授【例】寫出如圖所示森林的前序遍歷和后序遍歷的序列和該樹對應(yīng)二叉樹的前序遍歷、中序遍歷和后序遍歷的序列樹的前序遍歷序列：ABCDEFGHJK二叉樹的前序遍歷序列：ABCDEFGHJK樹的后序遍歷序列：BCDAFEJHGK二叉樹的中序