吉林大學數據結構-樹和森林

1、4.4 樹和森林,樹的遍歷,定義4.1 一個樹（或樹形）就是一個有限非空的結點的集合T，其中： 1）有一個特別標出的被稱為該樹（或樹形）的根root(T)的結點。 2）其他結點被分成m0個不相交的集合 1 , 2 , 稱作root(T)的子樹（或子樹形）。,樹的先根遍歷 樹的后根遍歷,樹的先根遍歷遞歸定義如下: （1）訪問根結點； （2）從左到右依次先根遍歷根結點的諸子樹（如果諸子樹存在）。 樹的后根遍歷遞歸定義如下: （1）后根遍歷根結點的諸子樹（如果諸子樹存在） （2）訪問根結點。,樹的順序存儲,如何對樹進行順序存儲？ 1962年，戈尼（S.Gorn）介紹了通過次數在先根次序下表示的樹。

2、定理4.2 如果已知一棵樹的先根序列和每個結點的度，則能唯一確定該樹的結構。,A,B,C,G,H,D,F,I,L,K,J,E,A B C D E F G H I J K L 4 0 3 0 0 0 0 2 2 0 0 0,層次次序，father數組,樹的鏈接存儲,Father鏈接 孩子鏈表 左兒子-右兄弟鏈接結構,左兒子-右兄弟鏈接存儲結構,FirstChild Data NextBrother,A,B,C,D,E,F,A , B,C, E, F , D ,操 作,搜索父結點 搜索指定數據域的結點 搜索大孩子結點和大兄弟結點 刪除子樹 樹和森林的遍歷,搜索父結點,算法FindFather(t,

3、p.result) /*在以t為根指針的樹中，搜索指針p所指結點的父結點。若找到，則令指針result指向其父節(jié)點；否則，令指針result為空。 */,算法FindFather(t,p.result) qFirstChild(t). while qnull and q p do ( FindFather(q,p.result) if result=null then q NextBrother(q). else return result. ) if q=p then return result t. else return result null. ,搜索指定數據域的結點,算法FindTa

4、rget(t,target.result) /*在以t為根指針的樹中，搜索數據成員等于target的結點。若找到，則令指針result指向該結點；否則，令指針result為空。*/,算法FindTarget(t,target.result) if data(t)=target then return resultt. p FirstChild(t). FindTarget(p,target.result). while p null and result=null do ( p NextBrother(p). FindTarget(p,target.result). ) return resu

5、lt null. ,FindTarget(p,target.result)=null,result,算法FindTarget(t,target.result) if data(t)=target then return resultt. p FirstChild(t). while p null and FindTarget(p,target.result)=null do ( p NextBrother(p). ) if resultnull then return result. else return result null. ,搜索大孩子結點和大兄弟結點,算法GFC(p.q)/GetF

6、irstChild If p null and FirstChild(p) null then return q FirstChild(p). return q null. 算法GNB(p.q)/GetNextBrother If p null and NextBrother(p) null then return q NextBrother (p). return q null. ,刪除子樹,算法DS(t,p) /*算法DS在以t為根的樹中刪除根為p的子樹；*/,算法DS(t,p) If t=null or p=null then return. FindFather(t,p. result

7、). if result=null then (Del(p). root null. return.) if FirstChild(result)=p then ( FirstChild(result) NextBrother(p). Del(p). Return.) q FirstChild(result). while NextBrother(q) p do qNextBrother(q). NextBrother(q) NextBrother(p). Del(p). Return. ,算法Del(p) If p=null then return. q FirstChild(p). whi

8、le qnull do ( next NextBrother(q). Del(q). q next. ) AVAIL=p. ,森林與二叉樹的自然對應,任何一個森林都對應一棵二叉樹，任何一棵二叉樹對應一個唯一的森林。稱這種對應為森林與二叉樹之間的自然對應。,定義4.7 設F=( 1 , 2 , )表示由樹 1 , 2 , 組成的森林，自然對應下森林F的二叉樹B(F)遞歸定義如下： （1）若n=0，則B(F)為空； （2）若n0，則B(F)的根是Root ( 1 )， B(F)的右子樹是B( 2 , 3 , )，左子樹是B( 11 , 12 , 1 )，其中， 11 , 12 , 1 是Root

9、( 1 )的諸子樹。,定義4.8 設二叉樹T的根是Root (T)，T的左子樹是L，T的右子樹是R，則二叉樹T自然對應下的森林F(T)遞歸定義如下： （1）若Root (T)為空，則F(T)為空的森林； （2）若Root (T)非空，則F(T)由第一棵樹 1 和森林F(R)組成。其中， 1 是以Root (T)為根的樹， 1 的諸子樹由森林F(L)組成。,樹、森林與二叉樹的轉換,森林的遍歷,森林的先根遍歷,森林的先根遍歷遞歸定義如下： （1）訪問第一棵樹的根結點； （2）先根遍歷第一棵樹根結點的諸子樹（如果諸子樹存在） （3）先根遍歷其余的諸樹（如果其余的諸樹存在） 森林的先根遍歷序列正好是它

10、自然對應下的二叉樹的先根序列。,森林后根遍歷,森林的后根遍歷遞歸定義如下： （1）后根遍歷第一棵樹根結點的諸子樹（如果諸子樹存在）； （2）訪問這棵樹的根結點； （3）后根遍歷其余的諸樹（如果其余的諸樹存在）。 森林的后根遍歷序列正好是它自然對應下的二叉樹的中根序列。,樹先根遍歷的遞歸算法,算法PreOrder(t) If t=null then return. print(data(t). GetFirstChild(t.child). while childnull do ( PreOrder(child). GNB(child.child). ) ,先根遍歷的迭代算法,算法NPO(t) S=AVAIL. pt. NPO3. while pnull do ( print(data(p). push(S,p). pFirstChild(p). ) while p=null and S非空 do ( pop(S.p). p NextBrother(p). ) if S非空 then goto NPO