第六章 树_修改

1、第六章 树1 继续本章介绍非线性结构树。 一般树和森林 其特点是每一个元素可以有唯一的直接前驱和任意的直接后继。2树（Tree） 定义 树(tree)是包括 n 个结点的有限集合 T (n1)，使得：n有一个特别标出的称作根（root）的结点；n除根以外的其它结点被分成m个(m0)不相交的集合T1, T2, , Tm，而且这些集合的每一个又都是树。 其中，树T1, T2, , Tm称作这个根的子树(subtree)。3树（Tree） 例：4ABCJDEILDEKG树（Tree） 逻辑定义 包含n个结点的有穷集合K (n0)，且在K上定义了一个关系N，关系N满足以下条件： 有且仅有一个结点k0K

2、，它对于关系N来说没有前驱。结点k0称作树的根； 除结点k0外，K中的每个结点对于关系N来说都有且仅有一个前驱 ；5树（Tree） 逻辑定义 包含n个结点的有穷集合K (n0)，且在K上定义了一个关系N，关系N满足以下条件： 除结点k0外的任何结点kK，都存在一个结点序列k0，k1，ks，使得k0就是树根，且ks=k，其中有序对N(1is)。这样的结点序列称为从根到结点k的一条路径。6树（Tree）的表示 树的形式化表示逻辑表示： 结点集合K=A，B，C，D，E，F，G，H，I，J K上的关系N= ， ， ， 7树（Tree）的表示 树的树形表示：8ABCJDEILDEKG树（Tree）的表示

3、 树的凹入表示法：9树（Tree）的表示 树的文氏图表示：10树（Tree）的表示 树的嵌套括号表示：(A(B(D)(E(I)(J)(F)(C(G)(H)11树的基本术语 树的基本术语和二叉树中大体相同，但有一点要注意有序无序： 二叉树是有序树； 根据其子树是否有序可分为是无序树（交换子树还是同一个树）和有序树，除非特殊说明一般提到的树都是无序树。森林(forest) 森林(forest) 森林是零棵或多棵不相交的树的集合(通常是有序集合)。 注意： 自然界的树和森林是不同的概念，而数据结构的树和森林只有微小的差别。 删去树根，树就变成森林。加上一个结点作树根，森林就变成树。/树结点的抽象数据

4、类型templateclass TreeNode public: TreeNode(const T& value);/拷贝构造函数 virtual TreeNode( ) /析构函数 bool isLeaf( ); /如果结点是叶，返回true T Value( ); /返回结点的值 TreeNode* LeftMostChild( ); /返回第一个左孩子 TreeNode* RightSibling( ); /返回右兄弟void setValue(T&);/设置结点的值 /设置左子结点 void setChild(TreeNode* pointer); /设置右兄弟 voi

5、d setSibling(TreeNode* pointer); /以第一个左子结点身份插入结点 void InsertFirst(TreeNode* node); /以右兄弟的身份插入结点 void InsertNext(TreeNode* node);14/树结点的抽象数据类型templateclass TreeNode public: TreeNode(const T& value);/拷贝构造函数 virtual TreeNode( ) /析构函数 bool isLeaf( ); /如果结点是叶，返回true T Value( ); /返回结点的值 TreeNode* Left

6、MostChild( ); /返回第一个左孩子 TreeNode* RightSibling( ); /返回右兄弟void setValue(T&);/设置结点的值 /设置左子结点 void setChild(TreeNode* pointer); /设置右兄弟 void setSibling(TreeNode* pointer); /以第一个左子结点身份插入结点 void InsertFirst(TreeNode* node); /以右兄弟的身份插入结点 void InsertNext(TreeNode* node);15/树的抽象数据类型template class Tree pu

7、blic:Tree();/构造函数virtual Tree();/析构函数/返回树中的根结点TreeNode* getRoot();/创建树中的根结点，使根结点元素的值为rootValuevoid CreateRoot(const T& rootValue);/判断是否为空树，如果是则返回truebool isEmpty();/返回current结点的父结点TreeNode* Parent(TreeNode* current); /返回current结点的前一个邻居结点TreeNode* PrevSibling(TreeNode* current); /删除以subroot为根的子树的

8、所有结点void DeleteSubTree(TreeNode* subroot); /先根深度优先周游树void RootFirstTraverse(TreeNode* root); /后根深度优先周游树void RootLastTraverse(TreeNode* root); /宽度优先周游树void WidthTraverse(TreeNode* root);16/树的抽象数据类型template class Tree public:Tree();/构造函数virtual Tree();/析构函数/返回树中的根结点TreeNode* getRoot();/创建树中的根结点，使根结点元素

9、的值为rootValuevoid CreateRoot(const T& rootValue);/判断是否为空树，如果是则返回truebool isEmpty();/返回current结点的父结点TreeNode* Parent(TreeNode* current); /返回current结点的前一个邻居结点TreeNode* PrevSibling(TreeNode* current); /删除以subroot为根的子树的所有结点void DeleteSubTree(TreeNode* subroot); /先根深度优先周游树void RootFirstTraverse(TreeNo

10、de* root); /后根深度优先周游树void RootLastTraverse(TreeNode* root); /宽度优先周游树void WidthTraverse(TreeNode* root);17树的物理实现 存储结构： 顺序存储方式（无法实现） 链式存储结构非连续空间（指针） 连续空间（下标） 树运算： 树的查找遍历（深度和广度）18树和森林与二叉树的转换 转换基础 在树或森林与二叉树之间有一个自然的一一对应的关系。 条件： 各树或子树有序， 如果无序自定义一个顺序19树和森林与二叉树的转换 把F看作树的有序集合，F=( T1, T2, , Tn )，F可按如下规则转换为二叉树

11、B(F)： 若n=0，则B（F）为空； 若n0，则B(F)的根是T1的根W1，B(F)的左子树是B( T11, T12, , T1m )，其中T11, T12, , T1m是W1的子树；B(F)的右子树是B( T2, , Tn )。20树和森林与二叉树的转换 简单的讲，树和森林到二叉树的转换可用连线、切线和旋转三步来说明： 连线：将兄弟用线连起来； 切线：保留父结点与其第一个子结点的连线，将父结点到其它子结点的连线切断； 旋转：以根为轴，平面下顺时针方向旋转一定角度。美观21ABCHEFILDJKGM 树转二叉树实例（初始）ABCHEFILDJKGM 树转二叉树实例（连线）ABCHEFILDJ

12、KGM 树转二叉树实例（切线）：ABCHEFILDJKGM 树转二叉树（切线）ABCHEFILDJKGM 树转二叉树（旋转）BCHEFILDJKGM 森林转二叉树增加一个虚拟的根即可ABCHEFILDJKGM 森林转二叉树增加一个虚拟的根即可 森林转二叉树（旋转）BCHEFILDJKGM树和森林与二叉树的转换 特点 树转换而得的二叉树根无右枝 森林转换而得的二叉树根有右枝（两棵树以上）30树和森林与二叉树的转换 设：B是一棵二叉树，rt是B的根，L是rt的左子树，R是rt的右子树，则对应于B的森林 F(B)的定义是： 若B为空，则F(B)是空的森林。 若B不为空，则F(B)是一棵树T1加上森林

13、F(R)，其中树T1的根为rt，rt的子树为F(L)31树和森林与二叉树的转换 简单的讲，二叉树到树和森林的转换可用加线抹线和调整三步来说明： 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来； 抹线：抹掉原二叉树中双亲与右孩子之间的连线； 调整：将结点按层次排列，形成树结构。32 二叉树转树/森林（初始）ABCDEFGHI 二叉树转树/森林（加线）ABCDEFGHI 二叉树转树/森林（抹线）ABCDEFGHI 二叉树转树/森林（抹线）ABCDEFGHI 二叉树转树/森林（调整）ABCDEFGHI树和森林与二叉树的转换 结论 树和

14、森林可以以二叉树的结构存储 下面给出树的动态二叉链表存储方式，由于表示的是一般树转换成的二叉树，所以其结构叫做动态“左孩子右兄弟”表示法。38动态“左子/右兄”存储方式 特点 本质上，我们使用二叉树来替换树。 新的结构中左子结点在树中是结点的最左子结点。右子结点是结点原来的右侧兄弟结点 ； 可以很容易的把这种转化推广到森林，因为森林中每棵树的根结点可以看成互为兄弟结点 39动态“左子/右兄”存储方式 特点 结构简单，易于实现 由于树的每个结点均包含固定数目的指针，而且树的ADT的每个函数均能有效实现。 因此动态“左子结点/右兄弟”表示法比其他方法更为常用。40/树结点类实现树结点类实现temp

15、lateclass TreeNode private:T m_Value; /树结点的值树结点的值TreeNode*pChild; /左子结点左子结点TreeNode*pSibling;/右兄弟结点右兄弟结点 public: 41/拷贝构造函数拷贝构造函数templateTreeNode:TreeNode(const T& value) m_Value = value;pChild = NULL;pSibling = NULL;/返回结点的值返回结点的值template T TreeNode:Value( )return m_Value;42/返回第一个左子结点返回第一个左子结点tem

16、plateTreeNode*TreeNode:LeftMostChild( ) return pChild;/返回右兄弟返回右兄弟templateTreeNode* TreeNode:RightSibling( ) return pSibling;43/设置结点的值设置结点的值templatevoid TreeNode:setValue ( T& value ) m_Value = value;/设置左子结点设置左子结点templatevoid TreeNode:setChild ( TreeNode * pointer ) pChild = pointer;44/设置右兄弟设置右兄弟

17、templatevoid TreeNode:setSibling ( TreeNode * pointer ) pSibling = pointer;/如果当前结点是叶子，返回如果当前结点是叶子，返回truetemplatebool TreeNode:isLeaf( ) if ( pChild = NULL)/左指针指向孩子左指针指向孩子return true;return false;45/InsertFirst实现实现以第一个子结点的身份插入结点以第一个子结点的身份插入结点template void TreeNode:InsertFirst ( TreeNode* node ) if (

18、! pChild )pChild = node;else node-pSibling = pChild;pChild = node;46/InsertNext实现实现以右兄弟的身份插入结点以右兄弟的身份插入结点templatevoid TreeNode:InsertNext ( TreeNode* node ) if( ! pSibling )pSibling = node;else node - pSibling = pSibling;pSibling = node;47/树类实现树类实现template class Tree private:TreeNode * root;void Des

19、toryNodes ( TreeNode* root ); TreeNode* getParent( TreeNode* root, TreeNode* current ); public:48/构造函数构造函数template Tree:Tree( ) root=NULL;/析构函数析构函数template Tree:Tree()while ( root )DeleteSubTree( root );49/返回树中的根结点返回树中的根结点template TreeNode * Tree:getRoot( ) return root;/创建树中的根结点创建树中的根结点，使根结点元素的值为使根结

20、点元素的值为rootValuetemplate void Tree:CreateRoot ( const T& rootValue ) if( !root )root = new TreeNode ( rootValue );50/判断是否为空树，如果是则返回判断是否为空树，如果是则返回truetemplate bool Tree:isEmpty ( )if ( root )return false;return true;51/私有成员函数，私有成员函数，返回返回current的父节点的父节点，由函数由函数Parent调用调用TreeNode* Tree:getParent( Tre

21、eNode* root, TreeNode* current )TreeNode* temp;if ( root = NULL )return NULL;if ( root-LeftMostChild ( ) = current ) return root;temp = getParent ( root-LeftMostChild( ), current );if( temp != NULL ) return temp;else return getParent ( root-RightSibling( ), current );52/Parent实现实现(递归递归)template /返回返

22、回current结点的父结点结点的父结点TreeNode* Tree : Parent ( TreeNode* current )TreeNode* pointer = current; if ( pointer = NULL )return NULL;/查找查找current结点最左侧的兄弟结点最左侧的兄弟TreeNode* leftmostChild = NULL;leftmostChild = PrevSibling ( pointer ); while ( leftmostChild != NULL) pointer = leftmostChild;leftmostChild = Pr

23、evSibling ( pointer ); leftmostChild = pointer;pointer = root;if ( leftmostChild = root )return NULL;elsereturn getParent ( pointer , leftmostChild );53/Parent实现实现(递归递归)template /返回返回current结点的父结点结点的父结点TreeNode* Tree : Parent ( TreeNode* current )TreeNode* pointer = current; if ( pointer != NULL )re

24、turn NULL;/查找查找current结点最左侧的兄弟结点最左侧的兄弟TreeNode* leftmostChild = NULL;leftmostChild = PrevSibling ( pointer ); while ( leftmostChild != NULL) pointer = leftmostChild;leftmostChild = PrevSibling ( pointer ); leftmostChild = pointer;pointer = root;if ( leftmostChild = root )return NULL;elsereturn getPa

25、rent ( pointer , leftmostChild );54/Parent实现实现(非递归非递归)template /返回返回current结点的父结点结点的父结点TreeNode* Tree : Parent ( TreeNode* current )using std : queue;/使用使用STL队列队列queue TreeNode * aQueue;TreeNode * pointer = root; /指向其父结点指向其父结点TreeNode * upperlevelpointer = NULL;if ( current != NULL & pointer !=

26、NULL ) /待查找结点不空，也不是空树或空森林待查找结点不空，也不是空树或空森林while ( pointer != NULL ) /森林的所有根入队森林的所有根入队if ( current = pointer ) /待查结点为根待查结点为根return NULL;aQueue.push ( pointer );pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );aQueue.pop ( );upperlevelpointer = pointer;/指向上层

27、结点指向上层结点pointer = pointer - LeftMostChild ( ); while ( pointer ) if ( current = pointer ) return upperlevelpointer; else aQueue.push ( pointer ); pointer = pointer - RightSibling ( ); return NULL;55/Parent实现实现(非递归非递归)template /返回返回current结点的父结点结点的父结点TreeNode* Tree : Parent ( TreeNode* current )using

28、 std : queue;/使用使用STL队列队列queue TreeNode * aQueue;TreeNode * pointer = root; /指向其父结点指向其父结点TreeNode * upperlevelpointer = NULL;if ( current != NULL & pointer != NULL ) /待查找结点不空，也不是空树或空森林待查找结点不空，也不是空树或空森林while ( pointer != NULL ) /森林的所有根入队森林的所有根入队if ( current = pointer ) /待查结点为根待查结点为根return NULL;aQ

29、ueue.push ( pointer );pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );aQueue.pop ( );upperlevelpointer = pointer;/指向上层结点指向上层结点pointer = pointer - LeftMostChild ( ); while ( pointer ) if ( current = pointer ) return upperlevelpointer; else aQueue.push ( po

30、inter ); pointer = pointer - RightSibling ( ); return NULL;56/Parent实现实现(非递归非递归)template /返回返回current结点的父结点结点的父结点TreeNode* Tree : Parent ( TreeNode* current )using std : queue;/使用使用STL队列队列queue TreeNode * aQueue;TreeNode * pointer = root; /指向其父结点指向其父结点TreeNode * upperlevelpointer = NULL;if ( current

31、 != NULL & pointer != NULL ) /待查找结点不空，也不是空树或空森林待查找结点不空，也不是空树或空森林while ( pointer != NULL ) /森林的所有根入队森林的所有根入队if ( current = pointer ) /待查结点为根待查结点为根return NULL;aQueue.push ( pointer );pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );aQueue.pop ( );upperle

32、velpointer = pointer;/指向上层结点指向上层结点pointer = pointer - LeftMostChild ( ); while ( pointer ) if ( current = pointer ) return upperlevelpointer; else aQueue.push ( pointer ); pointer = pointer - RightSibling ( ); return NULL;57/树类树类PrevSibling实现实现template /返回返回current结点的前一个邻居结点结点的前一个邻居结点TreeNode* Tree:

33、PrevSibling ( TreeNode* current )using std:queue; /使用使用STL队列队列queueTreeNode* aQueue;TreeNode* pointer=root; /标识当前结点标识当前结点/标识当前结点的前一个兄弟结点标识当前结点的前一个兄弟结点TreeNode* prev=NULL; /当前结点为空，树为空或所求结点为根结点时，返回当前结点为空，树为空或所求结点为根结点时，返回NULLif ( ( current = NULL ) | ( pointer = NULL ) | ( current = pointer ) )return N

34、ULL;while ( pointer )if ( pointer = current )return prev; /找到当前结点找到当前结点aQueue.push ( pointer );prev = pointer;/沿当前结点右兄弟链寻找沿当前结点右兄弟链寻找pointer = pointer - pSibling;while ( ! aQueue.empty ( ) ) prev = NULL;pointer = aQueue.front ( );aQueue.pop ( ); /出队出队pointer = pointer-LeftMostChild( ); /下到左子结点下到左子结点

35、while ( pointer ) if ( pointer = current )return prev;aQueue.push ( pointer );prev = pointer; /沿当前结点右链寻找沿当前结点右链寻找pointer = pointer - pSibling; /end while /end whilereturn NULL;58/树类树类PrevSibling实现实现template /返回返回current结点的前一个邻居结点结点的前一个邻居结点TreeNode* Tree:PrevSibling ( TreeNode* current )using std:que

36、ue; /使用使用STL队列队列queueTreeNode* aQueue;TreeNode* pointer=root; /标识当前结点标识当前结点/标识当前结点的前一个兄弟结点标识当前结点的前一个兄弟结点TreeNode* prev=NULL; /当前结点为空，树为空或所求结点为根结点时，返回当前结点为空，树为空或所求结点为根结点时，返回NULLif ( ( current = NULL ) | ( pointer = NULL ) | ( current = pointer ) )return NULL;while ( pointer )if ( pointer = current )r

37、eturn prev; /找到当前结点找到当前结点aQueue.push ( pointer );prev = pointer;/沿当前结点右兄弟链寻找沿当前结点右兄弟链寻找pointer = pointer - pSibling;while ( ! aQueue.empty ( ) ) prev = NULL;pointer = aQueue.front ( );aQueue.pop ( ); /出队出队pointer = pointer-LeftMostChild( ); /下到左子结点下到左子结点while ( pointer ) if ( pointer = current )retu

38、rn prev;aQueue.push ( pointer );prev = pointer; /沿当前结点右链寻找沿当前结点右链寻找pointer = pointer - pSibling; /end while /end whilereturn NULL;59/树类树类PrevSibling实现实现template /返回返回current结点的前一个邻居结点结点的前一个邻居结点TreeNode* Tree:PrevSibling ( TreeNode* current )using std:queue; /使用使用STL队列队列queueTreeNode* aQueue;TreeNode

39、* pointer=root; /标识当前结点标识当前结点/标识当前结点的前一个兄弟结点标识当前结点的前一个兄弟结点TreeNode* prev=NULL; /当前结点为空，树为空或所求结点为根结点时，返回当前结点为空，树为空或所求结点为根结点时，返回NULLif ( ( current = NULL ) | ( pointer = NULL ) | ( current = pointer ) )return NULL;while ( pointer )if ( pointer = current )return prev; /找到当前结点找到当前结点aQueue.push ( pointer

40、 );prev = pointer;/沿当前结点右兄弟链寻找沿当前结点右兄弟链寻找pointer = pointer - pSibling;while ( ! aQueue.empty ( ) ) prev = NULL;pointer = aQueue.front ( );aQueue.pop ( ); /出队出队pointer = pointer-LeftMostChild( ); /下到左子结点下到左子结点while ( pointer ) if ( pointer = current )return prev;aQueue.push ( pointer );prev = pointer

41、; /沿当前结点右链寻找沿当前结点右链寻找pointer = pointer - pSibling; /end while /end whilereturn NULL;60/树类树类DestroyNodes实现实现template void Tree:DestroyNodes ( TreeNode* root )/删除以删除以root为根的子树的所有结点为根的子树的所有结点if ( root ) /递归删除第一子树递归删除第一子树DestroyNodes ( root - LeftMostChild ( ) );/递归删除其他子树递归删除其他子树DestroyNodes ( root - Ri

42、ghtSibling ( ) ); delete root;/删除根结点删除根结点61/树类DeleteSubTree实现template void Tree:DeleteSubTree ( TreeNode* subroot )/删除以subroot为根的子树的所有结点TreeNode* pointer;if ( subroot = NULL ) return;pointer = Parent ( subroot );if ( pointer = NULL ) /subroot为森林的第一个树根 root = subroot - RightSibling ( );else /subroot为

43、最靠左子结点 if ( pointer-LeftMostChild ( ) = subroot ) pointer-setChild( subroot-RightSibling( ) ); else /subroot有兄弟 pointer = pointer-LeftMostChild ( ); while ( pointer - RightSibling ( ) != subroot ) pointer = pointer - RightSibling ( ); pointer-setSibling( subroot-RightSibling( ) ); subroot-setSibling

44、( NULL ); DestroyNodes(subroot); /销毁以subroot为根的子树62/树类DeleteSubTree实现template void Tree:DeleteSubTree ( TreeNode* subroot )/删除以subroot为根的子树的所有结点TreeNode* pointer;if ( subroot = NULL ) return;pointer = Parent ( subroot );if ( pointer = NULL ) /subroot为森林的第一个树根 root = subroot - RightSibling ( );else /

45、subroot为最靠左子结点 if ( pointer-LeftMostChild ( ) = subroot ) pointer-setChild( subroot-RightSibling( ) ); else /subroot有兄弟 pointer = pointer-LeftMostChild ( ); while ( pointer - RightSibling ( ) != subroot ) pointer = pointer - RightSibling ( ); pointer-setSibling( subroot-RightSibling( ) ); subroot-se

46、tSibling( NULL ); DestroyNodes(subroot); /销毁以subroot为根的子树63树和森林的周游 树和森林的周游分类 深度优先周游 广度优先周游64深度优先周游树 深度优先周游算法的基本思想是 尽可能的沿分支向深度方向进行周游。 对树和森林的周游可以有两种： 先根次序周游 后根次序周游65深度优先周游树和森林 先根次序周游 访问头一棵树的根； 在先根次序下周游头一棵树根的子树森林； 在先根次序下周游其它树构成的森林。 得到的结点有序序列称为树/森林的先根序列。66深度优先周游树和森林 后根次序周游 在后根次序下周游头一棵树根的子树森林； 访问森林中第一颗树的

47、根结点； 在后根次序下周游其它树构成的森林。 得到的结点有序序列称为树/森林的后根序列。67深度优先周游二叉树 例：先根次序遍历：ABEFCGKLDHIJM后根次序遍历：EFBKLGCHIMJDA68深度优先周游二叉树 例：69前序遍历：ABEFCGKLDHIJM中序遍历：EFBKLGCHIMJDA深度优先周游树和森林 结论 按先根次序周游森林正好等同于按前序法周游对应的二叉树 按后根次序周游森林正好等同于按中序法周游对应的二叉树 深度优先周游树和森林 补充 有的书把后根周游叫做中根周游，而后根周游则被定义为： 后根次序遍历第一棵树的子树森林； 后根次序遍历其它树的构成的森林； 访问第一棵树的

48、根结点。71/先根遍历树和森林(递归实现)templatevoid Tree: RootFirstTraverse ( TreeNode * root ) while ( root != NULL ) Visit ( root - value ( ) );/访问当前结点/遍历第一颗树树根的子树RootFirstTraverse ( root - leftMostChild ( ) );root = root - RightSibling ( ) );/遍历其它树72/后根遍历树和森林(递归实现)templatevoid Tree: RootLastTraverse ( TreeNode * r

49、oot ) while ( root != NULL ) RootLastTraverse ( root - leftMostChild ( ) );Visit ( root - value ( ) );root = root - RightSibling ( ) );73深度优先周游树和森林 作业： 给出深度优先周游树和森林的非递归算法， 给出其复杂度分析。74广度优先周游树/森林 广度优先（宽度/层次）遍历基本思想： 从树的第一层（根结点）开始，自上至下逐层遍历； 在同一层中，按照从左到右的顺序对结点逐一访问。 对于森林，把不同树的根看作同层兄弟75/广度优先周游树/森林template

50、void Tree:WidthTraverse ( TreeNode* root ) using std:queue;/使用STL队列queueTreeNode* aQueue;TreeNode* pointer = root;while ( pointer != NULL ) aQueue.push ( pointer ); pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );/取队首结点 aQueue.pop ( ); Visit ( pointer - V

51、alue ( ) );/访问当前结点 pointer = pointer - LeftMostChild ( ); while ( pointer != NULL ) /当前结点的子结点入队 aQueue.push( pointer );pointer - RightSibling ( ); 76/广度优先周游树/森林template void Tree:WidthTraverse ( TreeNode* root ) using std:queue;/使用STL队列queueTreeNode* aQueue;TreeNode* pointer = root;while ( pointer !

52、= NULL ) aQueue.push ( pointer ); pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );/取队首结点 aQueue.pop ( ); Visit ( pointer - Value ( ) );/访问当前结点 pointer = pointer - LeftMostChild ( ); while ( pointer != NULL ) /当前结点的子结点入队 aQueue.push( pointer );pointer - Ri

53、ghtSibling ( ); 77 算法分析 时间复杂度 如果访问函数处理时间是常数，则任何一种遍历时间复杂度都为O(n)。 空间复杂度 所需辅助空间为遍历时队列的最大容量，即树/森林的宽度（有最多结点的层）。最坏情况出现在有n个树的森林中，所以空间复杂度为O(n)。广度优先周游二叉树78树/森林的其它存储方式 “子结点表”表示法 静态“左子/右兄”表示法 动态表示法多重链表 父指针表示法 带右链的先根次序表示 带双标记的先根次序表示 带度数的后根次序表示 带双标记的层次次序表示子结点表表示法（带双亲）612345789acdefghibdatafc 2 3 4 5 9 7 8 601223

54、5551parentabcdefhgi子结点表表示法（不带双亲）6012345789acdefghibdata fc 2 3 4 5 9 7 8 6abcdefhgi静态“左子/右兄”表示法 使用连续空间表示“左子/右兄”表示法LeftChildElementRightSiblingabcdefhgi静态“左子/右兄”表示法135-16-1-1-1-1abcdefghi-12-14-1-178-1012345678LeftChildElement RightSibling静态“左子/右兄”表示法 三重链表表示法 为了既能方便地从双亲查找孩子，又能方便地从孩子查找双亲，可以将双亲表示法和孩子兄弟

55、表示法结合起来，这就是三重链表表示法。这种方法中，每个结点有三个链域，形成三重链表，每个结点的结构为：LeftChildElementRightSiblingParent动态表示法多重链表ABCDEFGABCDEFG data degreechild1child2childDdata child1child2childd父指针表示法 双亲表示：以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。ABCDEFGdataparentGFEDCBA311000-16543210静态表示父指针表示法 (a) 双亲表示法示意图；(b) 双亲表示法(链接存储)父指针表示法 作

56、业 实现并查集 思考： 为什么并查集适合使用父指针表示法实现？并给出理由。带右链的先根次序表示 存储方式 结点按先根次序顺序存储在一片连续的存储单元中。 每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为:带右链的先根次序表示 存储方式 各结点域含义为： info是结点的数据； rlink是右指针，指向结点的下一个兄弟、即对应的二叉树中结点的右子结点； ltag是一个左标记，当结点没有子结点，即对应的二叉树中结点没有左子结点时，ltag为1，否则为0。CDEF GIJ K LX 评价： 这种表示法与llinkrlink表示法相比，用ltag代替了llink，占用的存储单元

57、要少些，但并不丢失信息； 可以从结点的次序和ltag的值完全可以推知llink； ltag为0的结点有左子结点，它的llink指向存储区中该结点顺序的下一个结点 ltag为1的结点没有左子结点，它的llink为空带双标记的先根次序表示 基本思想 带右链的先根次序表示法中每个结点都包括ltag和rlink字段，事实上rlink也不是必需的。代之以一位的rtag就足以表示出整个森林的结构信息 规定：当结点没有下一个兄弟，即对应的二叉树中结点没有右子结点时rtag为1，否则为0 带双标记的先根次序表示1000010111infoltagH FD ECKA BJ G1010110011rtag 如何确

58、定结点的下一个兄弟？ 由结点的排列次序和ltag，rtag的值就可推知rlink的值。 当结点x的rtag为1时，它的rlink显然应为空； 当结点x的rtag为0时，它的rlink应指向结点序列中排在结点x的子树结点后面的那个结点y。带双标记的先根次序表示 如何确定这个结点y呢？ 分析先根序列的特征 任何结点的子树结点在先根序列中都排在该结点之后； 并且，任何结点的子树结点，在先根序列中排在最后的一个结点一定没有子结点，所以它的ltag为1带双标记的先根次序表示 如何确定这个结点y呢？ 查找y的基本思想 在顺序扫描带双标记位的先根次序表示，试图确定各结点的rlink值的过程中， 当遇到一个r

59、tag为0的结点x时，要继续往后扫描，在结点x的子树结点中找ltag为1的、该子树的最后一个结点， 序列中排在这个结点后面的那个结点就是结点x的rlink应该指向的结点y 带双标记的先根次序表示 最后一个问题 由于先根次序表示的树结构是嵌套的，因此在扫描结点x的子树结点序列找最后一个结点的过程中，极有可能遇到一棵更小的子树的根结点x，它的rtag也等于0 即：如何确定x结点子树的最后结点？带双标记的先根次序表示 如何确定x结点子树的最后结点？ 处理过程中需要用一个栈来记录待配置rlink的结点， 其使用方法为： 扫描到一个rtag为0的结点就将其入栈； 扫描到一个ltag为1的结点就从栈顶弹出

60、一个结点并为其设置rling带双标记的先根次序表示1000010111infoltagH FD ECKA BJ G1010110011rtag带双标记的先根次序表示带双标记的先根次序表示 评价 带双标记位的先根次序表示法虽然比带右键的先报次序表示法进一步节省了存储空间， 但由于需要额外的处理来推导失去的信息， 所以采用得更多的还是带右键的先根次序表示法 /双标记位先根次序树结点类templateclass DualTagTreeNode public:Tinfo;/树结点信息intltag;/左标记int rtag;/右标记DualTagTreeNode();virtual DualTagTreeNode();/构造templateDualTagTreeNode:DualTagT