6-数据结构与算法-北京大学2008-张铭-树

数据结构与算法第6章树本章由王腾蛟主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。主要内容6.1树的定义和基本术语6.2树的链式存储结构6.3树的顺序存储结构6.4K叉树6.5树知识点总结“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.1树和森林6.1.2森林与二叉树的等价转换6.1.3树的抽象数据类型6.1.4树的周游6.1树的定义和基本术语“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.1树和森林树(tree)是包括n个结点的有限集合T（n≥1），使得：有且仅有一个特定的称为根(root)的结点。除根以外的其它结点被分成m个(m≥0)不相交的有限集合T1，T2，…，Tm，而每一个集合又都是树。其中树T1，T2，…，Tm称作这个根的子树(subtree)。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.1树和森林图6.1树形表示法ABCDEFGHIJKL“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.1树和森林树的逻辑结构可以这样描述：树是包含n个结点的有穷集合K(n0)，且在K上定义了一个满足以下条件的二元关系R={r}：有且仅有一个结点k0∈K，它对于关系r来说没有前驱。结点k0称作树的根。除结点k0外，K中的每个结点对于关系r来说都有且仅有一个前驱。除结点k0外的任何结点k∈K，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，其中有序对ki-1，ki∈R（1≤i≤s）。这样的结点序列称为从根k0到结点k的一条路径。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。树形结构的各种表示法树的逻辑结构是：结点集合K={A，B，C，D，E，F，G，H，I，J}K上的关系N={A，B，A，C，B，D，B，E，B，F，C，G，C，H，E，I，E，J}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。树结构中的概念在一棵树中，若存在结点k指向结点k’的连线，则称k是k’的父结点，而k’则是k的子结点，有向连线k,k’称作边。同一个父结点的子结点之间互称兄弟。树中没有父结点的结点称为根。没有子结点的结点称为树叶。结点的子树数目称为结点的度，树的度是树中各结点度的最大值，二叉树的度是2。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。树结构中的概念若树中存在结点序列k0，k1，…，ks，使得k0，k1，k1，k2，…，ks-1，ks都是树中的边，则称从结点k0到结点ks存在一条路径。若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙。结点的层数同样由树根开始定义的，根结点为第0层，非根结点的层数是其父结点的层数加1。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。树结构中的概念有序树：计算机的存储是有序的，为方便计算机处理，往往把子结点按从左到右的次序顺序编号，即把树作为有序树(orderedtree)看待。度为2的有序树并不是二叉树，因为在第一子结点被删除后，第二子结点自然顶替成为第一子结点。因此，度为2并且严格区分左右两个子结点的有序树才是二叉树。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。森林与树森林(forest)是零棵或多棵不相交的树的集合（通常是有序集合）。对于树中的每个结点，其子树组成的集合就是森林；而加入一个结点作为根，森林就可以转化成一棵树了。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。树形结构的各种表示法树形结构在客观世界中是大量存在的，有多种逻辑表示方法：如树形表示法、凹入表示法、文氏图表示法、嵌套括号表示法等。ABCDEFGHIJKLABCDEIJFHGKL（a）凹入表表示法（b）文氏图表示法(A(B(D(I，J)，E)，C(F，G(K，L)，H)))（c）嵌套括号表示法图6.2树形结构的各种表示法“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.2森林与二叉树的等价转换树与二叉树、森林与二叉树之间可以相互转化，而且这种转换是一一对应的。树和森林转化成二叉树后，那么森林或树的相关操作都可以转换成对二叉树的操作。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.2森林与二叉树的等价转换树和森林到二叉树的转换过程可用连线、切线、旋转“三步曲”来说明：连线：将兄弟结点用线连接起来。切线：保留父结点与其第一个子结点的连线，将父结点到其它子结点的连线切掉。旋转：以根为轴，平面向下顺时针方向旋转一定的角度。旋转只是为了调整画面，使得转化后的二叉树看起来比较规整。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.2森林与二叉树的等价转换T1,T2两棵树构成的森林ABCDEFGHT1T2IJKLM(a)T11T12T111T112T121ABCDEFGHIJKLM(b)经过连线、切线处理图6.3森林转换为二叉树ABCDEFGHIJKLM(c)旋转操作“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.2森林与二叉树的等价转换森林或树转化成二叉树的形式定义如下：设有序集合F={T1，T2，…，Tn}表示由树T1，T2，…，Tn组成的森林，则森林F可以按如下规则递归转换成二叉树B(F)：若F为空，即n=0，则B(F)为空。若F非空，即n0，则B(F)的根是森林中第一棵树T1的根W1，B(F)的左子树是树T1中根结点W1的子树森林F={T11，T12，…，T1m}转换成的二叉树B(T11，T12，…，T1m)；B(F)的右子树是从森林F’={T2，…，Tn}转换而成的二叉树。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.2森林与二叉树的等价转换二叉树转换为树或森林的操作：旋转：以根为轴，平面逆时针方向旋转。补线：若结点x是父结点y的左子结点，则把x的右子结点，右子结点的右孩子，依此类推，直到最右孩子，用连线与y连起来。删线：去掉所有父结点到右孩子的连线。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.2森林与二叉树的等价转换图6.4二叉树转换为森林ABCDEFGHIJABCDEFGHJI(a)(b)(T1)(T2)(T3)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.2森林与二叉树的等价转换二叉树转化成森林或树的形式定义如下：设B是一棵二叉树，root是B的根，BL是root的左子树，BR是root的右子树，则对应于二叉树B的森林或树F(B)的形式定义是：若B为空，则F(B)是空的森林若B不为空，则F(B)是一棵树T1加上森林F(BR)，其中树T1的根为root，root的子树为F(BL)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.3树的抽象数据类型【代码6.1】树结点的抽象数据类型templateclassTclassTreeNode{public:TreeNode(constT&value);//拷贝构造函数virtual~TreeNode(){};//析构函数boolisLeaf();//判断当前结点是否为叶结点TValue();//返回结点的值TreeNodeT*LeftMostChild();//返回第一个左孩子TreeNodeT*RightSibling();//返回右兄弟voidsetValue(constT&value);//设置当前结点的值voidsetChild(TreeNodeT*pointer);//设置左孩子voidsetSibling(TreeNodeT*pointer);//设置右兄弟voidInsertFirst(TreeNodeT*node);//以第一个左孩子身份插入结点voidInsertNext(TreeNodeT*node);//以右兄弟的身份插入结点};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.3树的抽象数据类型【代码6.2】树的抽象数据类型templateclassTclassTree{public:Tree();//构造函数virtual~Tree();//析构函数TreeNodeT*getRoot();//返回树中的根结点voidCreateRoot(constT&rootValue);//创建值为rootValue的根结点boolisEmpty();//判断是否为空树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.3树的抽象数据类型TreeNodeT*Parent(TreeNodeT*current);//返回当前结点的父结点TreeNodeT*PrevSibling(TreeNodeT*current);//返回当前结点的前一个兄弟voidDeleteSubTree(TreeNodeT*subroot);//删除以subroot为根的子树voidRootFirstTraverse(TreeNodeT*root);//先根深度优先周游树voidRootLastTraverse(TreeNodeT*root);//后根深度优先周游树voidWidthTraverse(TreeNodeT*root);//广度优先周游树};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.4树的周游按深度的方向周游先根次序：a)访问头一棵树的根b)在先根次序下周游头一棵树树根的子树c)在先根次序下周游其他的树后根次序：a)在后根次序下周游头一棵树树根的子树b)访问头一棵树的根c)在后根次序下周游其他的树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。6.1.4树的周游图6.5(a)所示的森林，按先根次序周游得到的结点序列是ABCEFDGHJI按先根次序周游森林的序列正好等同于其对应二叉树的前序序列。按后根次序周游得到的结点序列是BEFCDAJHIG后根次序周游得到的排列正好是该森林对应的二叉树在中序次序周游下的结点序列。图6.5森林和对应的二叉树ABCDEFGHIJABCDEFGHIJ(a)(b)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。先根深度优先周游树或森林【算法6.3】先根深度优先周游树或森林templateclassTvoidTreeT::RootFirstTraverse(TreeNodeT*root){while(root!=NULL){Visit(root-Value());//访问当前结点RootFirstTraverse(root-LeftMostChil