北大数据结构与算法课件05树

数据结构与算法第五章树信息科学与技术学院网络与信息系统研究所北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2主要内容„5.1树的概念„5.2树的链式存储„5.3树的顺序存储„5.4K叉树„补充树计数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page35.1树的概念„5.1.1树和森林„5.1.2森林与二叉树的等价转换„5.1.3树的抽象数据类型„5.1.4树的周游北京大学信息学院张铭编写©版权所有，转载或翻印必究Page45.1.1树和森林„树的逻辑结构„树形结构的各种表示法„树的定义和概念„森林的定义JIFEGABCDH北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5树的逻辑结构„包含n个结点的有穷集合K(n0)，且在K上定义了一个关系N，关系N满足以下条件：„有且仅有一个结点k0∈K，它对于关系N来说没有前驱。结点k0称作树的根„除结点k0外，K中的每个结点对于关系N来说都有且仅有一个前驱„除结点k0外的任何结点k∈K，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，其中有序对ki-1，ki∈N(1≤i≤s)。这样的结点序列称为从根到结点k的一条路径北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6树形结构的各种表示法„树形表示法„形式语言表示法„文氏图表示法„凹入表表示法„嵌套括号表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7树形表示法JIFEGABCDH（a）树形表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8形式语言表示法树的逻辑结构是：结点集合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}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9文氏图表示法ABCDFJIEHG（b）文氏图表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10凹入表表示法BADEIJFGHC（c）凹入表表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page115树5.1树的概念5.1.1树和森林5.1.2森林与二叉树的等价转换5.1.3树的抽象数据类型5.1.4树的周游5.2树的链式存储5.2.1子结点表表示法5.2.2左子结点/右兄弟结点表示法5.2.3动态结点表示法5.2.4动态“左子结点/右兄弟结点”二叉链表表示法5.2.5父指针表示法及等价类的并查算法5.3树的顺序存储5.3.1带右链的先根次序表示法5.3.2带双标记位的先根次序表示法5.3.3带左链的层次次序表示法5.3.4带度数的后根次序表示法5.4K叉树„图书目录，杜威表示法凹入表表示法(例子)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12嵌套括号表示法(A(B(D)(E(I)(J))(F))(C(G)(H)))（d）嵌套括号表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13文氏图到嵌套括号表示的转化ABCDEIJHGF(A)(B(D)(E(I)(J))(C(G)(H))(F))从昀外层依次将表示集合的方框转化成括号对北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14树的定义„树是包括n个结点的有限集合T（n≥1），使得：„有一个特别标出的称作根的结点„除根以外的其它结点被分成m个(m≥0)不相交的集合T1，T2，…，Tm，而且这些集合的每一个又都是树。树T1，T2，…，Tm称作这个根的子树„这个定义是递归的，我们用子树来定义树：只包含一个结点的树必然仅由根组成，包含n1个结点的树借助于少于n个结点的树来定义北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15树结构中的概念(1)„若k，k′∈N，则称k是k′的父结点（或称“父母”），而k′则是k的子结点(或“儿子”、“子女”)„若有序对k，k′及k，k″∈N，则称k′和k″互为兄弟„若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙„树形结构中，两个结点的有序对，称作连接这两结点的一条边北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16树结构中的概念(2)„没有子树的结点称作树叶或终端结点„非终端结点称为分支结点„一个结点的子树的个数称为度数„根结点的层数为0，其它任何结点的层数等于它的父结点的层数加1北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17树结构中的概念(3)„有序树在树T中如果子树T1，T2，…，Tm的相对次序是重要的，则称树T为有向有序树，简称有序树。„在有序树中可以称T1是根的第一棵子树，T2是根的第二棵子树，等等北京大学信息学院张铭编写©版权所有，转载或翻印必究Page185.1.2森林与二叉树的等价转换„森林(forest)森林是零棵或多棵不相交的树的集合(通常是有序集合)。„删去树根，树就变成森林„加上一个结点作树根，森林就变成树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page19森林与二叉树的等价转换(续)„在树或森林与二叉树之间有一个自然的一一对应的关系。„任何森林都唯一地对应到一棵二叉树；反过来，任何二叉树也都唯一地对应到一个森林。„树所对应的二叉树里„一个结点的左子结点是它在原来树里的第一个子结点„右子结点是它在原来的树里的下一个兄弟北京大学信息学院张铭编写©版权所有，转载或翻印必究Page20图示：森林与二叉树GFDHJT2EAB1T11T12T1CKGFHDCAB1KEJ北京大学信息学院张铭编写©版权所有，转载或翻印必究Page21形式化：森林到二叉树„把森林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)„此定义精确地确定了从森林到二叉树的转换北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22形式化：二叉树到森林„设B是一棵二叉树，rt是B的根，L是rt的左子树，R是rt的右子树，则对应于B的森林F(B)的定义是：„若B为空，则F(B)是空的森林。„若B不为空，则F(B)是一棵树T1加上森林F(R)，其中树T1的根为rt，rt的子树为F(L)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page235.1.3树/森林的结点ADT(1)templateclassTclassTreeNode{public:TreeNode(constT&);//拷贝构造函数virtual~TreeNode(){};//析构函数boolisLeaf();//如果结点是叶，返回trueTValue();//返回结点的值TreeNodeT*LeftMostChild();//返回第一个左孩子TreeNodeT*RightSibling();//返回右兄弟北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24树/森林的结点ADT(2)voidsetValue(T&);//设置结点的值//设置左子结点voidsetChild(TreeNodeT*pointer);//设置右兄弟voidsetSibling(TreeNodeT*pointer);//以第一个左子结点身份插入结点voidInsertFirst(TreeNodeT*node);//以右兄弟的身份插入结点voidInsertNext(TreeNodeT*node);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25树/森林的ADT(1)templateclassTclassTree{public:Tree();//构造函数virtual~Tree();//析构函数//返回树中的根结点TreeNodeT*getRoot();//创建树中的根结点，使根结点元素的值为rootValuevoidCreateRoot(constT&rootValue);//判断是否为空树，如果是则返回trueboolisEmpty();北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26树/森林的ADT(2)//返回current结点的父结点TreeNodeT*Parent(TreeNodeT*current);//返回current结点的前一个邻居结点TreeNodeT*PrevSibling(TreeNodeT*current);//删除以subroot为根的子树的所有结点voidDeleteSubTree(TreeNodeT*subroot);//先根深度优先周游树voidRootFirstTraverse(TreeNodeT*root);//后根深度优先周游树voidRootLastTraverse(TreeNodeT*root);//广度优先周游树voidWidthTraverse(TreeNodeT*root);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page275.1.4森林的周游„按深度方向周游„先根次序„后根次序„按广度方向周游„宽度优先周游„层次周游北京大学信息学院张铭编写©版权所有，转载或翻印必究Page28森林的周游ABCKFDEGHJGFHDCABKEJ北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29周游森林vs周游二叉树„先根次序周游森林„前序法周游二叉树„后根次序周游森林„按中序法周游对应的二叉树„中根周游？„无法明确规定根在哪两个子结点之间北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30补充：一种广度优先周游森林ABCKFDEGHJGFHDCABKEJ„PrevSibling()函数采用本框架北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31广度优先周游森林templateclassTvoidTreeT::WidthTraverse2(TreeNodeT*root){usingstd::queue;//使用STL队列queueTreeNodeT*aQueue;TreeNodeT*pointer=root;while(pointer){aQueue.push(pointer);pointer=pointer-RightSibling()；}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page32广度优先周游森林(续)while(!aQueue.empty()){pointer=aQueue.front();//取队首aQueue.pop();//出队列Visit(pointer-Value());//访问pointer=pointer-LeftMostChild();while(pointer){aQueue.push(pointer);pointer=pointer-RightSibling()；}}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33教材广度优先周游图示ABCKFDEGHJGFHDCABKEJ北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34广度优先周游森林（教材）templateclassTvoidTreeT::WidthTraverse1(TreeNodeT*root){usingstd::queue;//使用STL队列queueTreeNodeT*aQueue;TreeNodeT*pointer=root;if(!pointer)return;aQueue.push(pointer);while(!aQueue.empty()){pointer=aQueue.front();//取队列首结点指针北京大学信息学院张铭编写©版权所有，转载或翻印必究Page