第五章树讲解材料.ppt

第五章树,任课教员：张铭,北京大学信息学院版权所有，转载或翻印必究Page2,主要内容,5.1树的概念5.2树的链式存储5.3树的顺序存储5.4K叉树,北京大学信息学院版权所有，转载或翻印必究Page3,5.1树的概念,5.1.1树和森林5.1.2森林与二叉树的等价转换5.1.3树的抽象数据类型5.1.4树的周游,北京大学信息学院版权所有，转载或翻印必究Page4,树的逻辑结构,包含n个结点的有穷集合K(n0)，且在K上定义了一个关系N，关系N满足以下条件：有且仅有一个结点k0K，它对于关系N来说没有前驱结点k0称作树的根除结点k0外，K中的每个结点对于关系N来说都有且仅有一个前驱除结点k0外的任何结点kK，都存在一个结点序列k0，k1，，ks，使得k0就是树根，且ks=k，其中有序对N(1is)这样的结点序列称为从根到结点k的一条路径,北京大学信息学院版权所有，转载或翻印必究Page6,树形结构的各种表示法,（a）树形表示法,北京大学信息学院版权所有，转载或翻印必究Page7,树形结构的各种表示法,（b）文氏图表示法,北京大学信息学院版权所有，转载或翻印必究Page8,树形结构的各种表示法,（c）凹入表表示法,北京大学信息学院版权所有，转载或翻印必究Page9,树形结构的各种表示法,,(A(B(D)(E(I)(J)(F))(C(G)(H))),（d）嵌套括号表示法,北京大学信息学院版权所有，转载或翻印必究Page10,树的定义,,树是包括n个结点的有限集合T（n1），使得：有一个特别标出的称作根的结点除根以外的其它结点被分成m个(m0)不相交的集合T1，T2，，Tm，而且这些集合的每一个又都是树。

树T1，T2，，Tm称作这个根的子树这个定义是递归的，我们用子树来定义树：只包含一个结点的树必然仅由根组成，包含n1个结点的树借助于少于n个结点的树来定义,北京大学信息学院版权所有，转载或翻印必究Page11,树结构中的概念,若N，则称k是k的父结点（或称“父母”），而k则是k的子结点(或“儿子”、“子女”)若有序对及N，则称k和k互为兄弟若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙树形结构中，两个结点的有序对，称作连接这两结点的一条边,北京大学信息学院版权所有，转载或翻印必究Page12,树结构中的概念,没有子树的结点称作树叶或终端结点非终端结点称为分支结点一个结点的子树的个数称为度数根结点的层数为0，其它任何结点的层数等于它的父结点结点的层数加1,北京大学信息学院版权所有，转载或翻印必究Page13,树结构中的概念,有序树在树T中如果子树T1，T2，，Tm的相对次序是重要的，则称树T为有向有序树，简称有序树在有序树中可以称T1是根的第一棵子树，T2是根的第二棵子树，等等,北京大学信息学院版权所有，转载或翻印必究Page14,森林与树,森林(forest)森林是零棵或多棵不相交的树的集合(通常是有序集合)。

自然界的树和森林是不同的概念，而数据结构的树和森林只有微小的差别删去树根，树就变成森林加上一个结点作树根，森林就变成树,北京大学信息学院版权所有，转载或翻印必究Page15,森林与二叉树的等价转换,在树或森林与二叉树之间有一个自然的一一对应的关系任何森林都唯一地对应到一棵二叉树；反过来，任何二叉树也都唯一地对应到一个森林树所对应的二叉树里一个结点的左子结点是它在原来树里的第一个子结点右子结点是它在原来的树里的下一个兄弟,北京大学信息学院版权所有，转载或翻印必究Page16,森林与二叉树的等价转换,北京大学信息学院版权所有，转载或翻印必究Page17,森林到二叉树的等价转换,把森林F看作树的有序集合，F=(T1，T2，，Tn)，对应于F的二叉树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)此定义精确地确定了从森林到二叉树的转换,北京大学信息学院版权所有，转载或翻印必究Page18,森林到二叉树的等价转换,设B是一棵二叉树，rt是B的根，L是rt的左子树，R是rt的右子树，则对应于B的森林F(B)的定义是：若B为空，则F(B)是空的森林。

若B不为空，则F(B)是一棵树T1加上森林F(R)，其中树T1的根为rt，rt的子树为F(L),北京大学信息学院版权所有，转载或翻印必究Page19,树/森林的抽象数据类型,templateclassTreeNodepublic:TreeNode(constT//返回右兄弟,北京大学信息学院版权所有，转载或翻印必究Page20,树/森林的抽象数据类型,voidsetValue(T,北京大学信息学院版权所有，转载或翻印必究Page21,树/森林的抽象数据类型,templateclassTreepublic:Tree();//构造函数virtualTree();//析构函数//返回树中的根结点TreeNode*getRoot();//创建树中的根结点，使根结点元素的值为rootValuevoidCreateRoot(constT,北京大学信息学院版权所有，转载或翻印必究Page22,树/森林的抽象数据类型,//返回current结点的父结点TreeNode*Parent(TreeNode*current);//返回current结点的前一个邻居结点TreeNode*PrevSibling(TreeNode*current);//删除以subroot为根的子树的所有结点voidDeleteSubTree(TreeNode*subroot);//先根深度优先周游树voidRootFirstTraverse(TreeNode*root);//后根深度优先周游树voidRootLastTraverse(TreeNode*root);//宽度优先周游树voidWidthTraverse(TreeNode*root);;,北京大学信息学院版权所有，转载或翻印必究Page23,森林的周游,按深度的方向周游先根次序：a)访问头一棵树的根b)在先根次序下周游头一棵树树根的子树c)在先根次序下周游其他的树后根次序：a)在后根次序下周游头一棵树树根的子树b)访问头一棵树的根c)在后根次序下周游其他的树,北京大学信息学院版权所有，转载或翻印必究Page24,先根深度优先周游森林,templatevoidTree::RootFirstTraverse(TreeNode*root)while(root!=NULL)Visit(root-Value());//访问当前结点//周游头一棵树树根的子树RootFirstTraverse(root-LeftMostChild());root=root-RightSibling();//周游其他的树,北京大学信息学院版权所有，转载或翻印必究Page25,后根深度优先周游森林,templatevoidTree::RootLastTraverse(TreeNode*root)while(root!=NULL)//周游头一棵树树根的子树RootLastTraverse(root-LeftMostChild());Visit(root-Value());//访问当前结点root=root-RightSibling();//周游其他的树,北京大学信息学院版权所有，转载或翻印必究Page26,深度优先周游森林,按先根次序周游森林正好等同于按前序法周游对应的二叉树按后根次序周游森林正好等同于按中序法周游对应的二叉树不方便仿照中序法定义树的中根周游，因为当一个根多于两个子结点时无法明确给出根与这些子结点的次序,北京大学信息学院版权所有，转载或翻印必究Page27,宽度优先周游森林,templatevoidTree::WidthTraverse2(TreeNode*root)usingstd::queue;//使用STL队列queue*aQueue;TreeNode*pointer=root;if(pointer)aQueue.push(pointer);while(!aQueue.empty())pointer=aQueue.front();//取队列首结点指针,北京大学信息学院版权所有，转载或翻印必究Page28,宽度优先周游森林,,Visit(pointer-Value());//访问当前结点while(pointer-RightSibling())if(pointer-LeftMostChild())//左子结点进入队列aQueue.push(pointer-LeftMostChild());pointer=pointer-RightSibling();Visit(pointer-Value());//访问右兄弟结点,北京大学信息学院版权所有，转载或翻印必究Page29,宽度优先周游森林,if(pointer-LeftMostChild())aQueue.push(pointer-LeftMostChild());aQueue.pop();//出队列//endwhile//endif,北京大学信息学院版权所有，转载或翻印必究Page30,5.2森林的链式存储,5.2.1子结点表表示法5.2.2左子结点/右兄弟结点表示法5.2.3动态结点表示法5.2.4动态“左子结点/右兄弟结点”二叉链表表示法5.2.5父指针表示法,北京大学信息学院版权所有，转载或翻印必究Page31,子结点表表示法,每个分支结点均存储其子结点信息，子结点按照从左至右的顺序形成一个链表“子结点表”表示法在数组中存储树的结点。

每个结点包括结点值、一个父指针以及一个指向子结点链表的指针结点的最左子结点可由链表的第一个表项直接找到找到结点的右侧兄弟结点要困难一些,北京大学信息学院版权所有，转载或翻印必究Page32,左子结点/右兄弟结点表示法,每个结点都存储结点的值，以及指向父结点、最左子结点和右侧兄弟结点的指针ADT的基本操作可通过读取结点中的一个值来实现如果两棵树存储在同一个数组中，那么把其中一个添加为另一棵树的子树只需简单设置三个指针值即可这种表示法比子结点表表示法空间效率更高，而且结点数组中的每个结点仅需要固定大小的存储空间,北京大学信息学院版权所有，转载或翻印必究Page33,动态结点表示法,为每个结点分配可变的存储空间将一个指向子结点的指针数组作为结点的一部分分配给结点实质上，每个结点存储一个基于数组的子结点指针表在子结点的数目不变时，这种方法效果最佳；如果子结点的数目发生变动（特别是增加），就必须提供一种专门的校正机制来改变子结点指针数组的大小每个结点存储一条子结点指针链表本质上“子结点表”表示法相同，但是它动态地分配结点空间，而不是把结点分配在数组中,北京大学信息学院版权所有，转载或翻印必究Page34,动态“左子结点/右兄弟结点”二叉链表表示法,本质上，我们使用二叉树来替换树新的结构中左子结点在树中是结点的最左子结点。

右子结点是结点原来的右侧兄弟结点可以很容易的把这种转化推广到森林，因为森林中每棵树的根结点可以看成互为兄弟结点由于树的每个结点均包含固定数目的指针，而且树的ADT的每个函数均能有效实现，因此动态“左子结点/右兄第结点”表示法比以上介绍的其他方法更为常用,北京大学信息学院版权所有，转载或翻印必究Page35,树结点抽象数据类型的实现,//补充与具体实现相关的私有成员变量申明private:Tm_Value;//树结点的值TreeNode*pChild;//左子结点TreeNode*pSibling;//右兄弟结点//公有成员函数的具体实现templateTreeNode::TreeNode(constT,北京大学信息学院版权所有，转载或翻印必究Page36,树结点抽象数据类型的实现,templateTTreeNode::Value()//返回结点的值returnm_Value;template。