吉林大学数据结构-树和森林

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指向其父节点；否则，令指针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