北工大(数据结构)11-DSch6Tree

第6章树6.1树的定义和基本术语6.2树的链式存储结构6.3树的顺序存储6.4K叉树(不讲)6.1树的定义和基本术语6.1.1树和森林6.1.2 森林与二叉树的等价转换6.1.3树的抽象数据类型6.1.4树的周游6.1.1树和森林

树的定义(递归)树(tree)是包括n个结点的有限集合T(n≥1)，使:有且仅有一个特定结点称为根(root)除根以外的其它结点被分成m个(m≥0)不相交的集合T1，T2，…，Tm，而且这些集合的每一个又都是树。树T1，T2，…，Tm称作这个根的子树(subtree)6.1.1树和森林

树的逻辑结构包含n个结点的有穷集合K(n>0)，且在K上定义了一个满足以下条件的二元关系R={r}：有且仅有一个结点k0∈K，它对于关系N来说没有前驱。结点k0称作树的根除结点k0外，K中的每个结点对于关系r来说都有且仅有一个前驱

除结点k0外的任何结点k∈K，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，其中有序对<ki-1，ki>∈r(1≤i≤s)。这样的结点序列称为从根k0到结点k的一条路径6.1.1树和森林

树形结构的各种表示法树的逻辑结构是：结点集合K={A，B，C，D，E，F，G，H，I，J}K上的关系r={ <A，B>，<A，C>， <B，D>，<B，E>，<B，F>， <C，G>，<C，H>， <E，I>，<E，J>}（d）嵌套括号表示法（b）文氏图表示法（a）树形表示法（c）凹入表表示法(A(B(D(I,J),E),(C(F,G())(H)))树形结构的各种表示法6.1.1树和森林

树结构中的概念一棵树若存在结点k指向结点k’的连线(<k，k’>∈r)则称k是k’的父结点，k’则是k的子结点，有向连线称作边同一个父结点的子结点之间互称兄弟没有父结点的结点称为根，没有子结点的结点称为叶结点的度：结点子树数目树的度：树中各结点度的最大值若树中存在结点序列k0,k1…ks,使得<k0,k1>，<k1,k2>，…<ks-1,ks>都是树中的边，成从结点k0到结点ks存在一条路径，则称k0是ks的祖先，ks是k0的子孙

结点层数：根为第0层，子结点层数=父结点层数+16.1.1树和森林

树结构中的概念在树T中如果子树T1，T2，…，Tm的相对次序是重要的，则称树T为有序树为方便计算机处理，将子结点从左到右依次编号，即树是有序树(orderedtree)度为2的有序树≠二叉树度为2的有序树：删除第1子结点后,第2子结点顶替为第1子结点二叉树：度为2且严格区分左右两个子结点的有序树才是二叉树6.1.1树和森林

森林与树森林(forest)是零棵或多棵不相交的树的集合(通常是有序集合)。树森林：删去树根，树就变成森林。森林树：加上一个结点作树根，森林就变成树在树或森林与二叉树之间有一个一一对应的关系任何森林都唯一地对应到一棵二叉树任何二叉树也都唯一地对应到一个森林ABDC^^EFG^^^^^^firstchildnextsiblingABDEFGCABDEFGCleftchildrightchild6.1.2森林与二叉树的等价转换

树与二叉树的等价转换举例角色互换ABDEFGCABDEFGCABDEFGC6.1.2森林与二叉树的等价转换

树二叉树转换规则理解一.树（森林）二叉树将第一个孩子当作左孩子,将下一个兄弟当作右孩子(各树的根当作兄弟)二.二叉树树（森林）将左孩子当作第一个孩子,将右孩子当作下一个兄弟(共有一个双亲)(各树的根当作兄弟)ABDEFGCABDEFGC6.1.2森林与二叉树的等价转换

图式森林由３部分组成：森林中第一棵树的根结点森林中第一棵树的子树森林森林中其它树构成的森林6.1.2森林与二叉树的等价转换

举例

6.1.2森林与二叉树的等价转换

森林与二叉树的转换规则

F(T1,T2,…,Tn)T1(root,t11,t12,…t1m)

B(LBT,Node(root),RBT)

森林二叉树若F=空，则B=空否则由Root(T1)Node(root)由(t11,t12,…,t1m)LBT由(T2,T3,…,Tn)RBT森林二叉树若B=空，则F=空否则由Node(root)Root(T1)由LBT(t11,t12,…,t1m)由RBT

(T2,T3,…,Tn)6.1.3树的抽象数据类型

树结点的抽象数据类型[代码6.1]1/2 template<classT> classTreeNode { public: TreeNode(constT&value);//用于拷贝的构造函数 virtual~TreeNode(); //析构函数 boolisLeaf();//判断当前结点是否是叶(返true/false) TValue(); //返回结点的值 TreeNode<T>*LeftMostChild();//返回第一个左孩子 TreeNode<T>*RightSibling();//返回右兄弟树结点的抽象数据类型2/2 voidsetValue(T&); //设置结点的值 voidsetChild(TreeNode<T>*pointer);//设置左子结点 voidsetSibling(TreeNode<T>*pointer);//设置右兄弟 voidInsertFirst(TreeNode<T>*node); //以当前结点第一个左子结点身份插入结点 voidInsertNext(TreeNode<T>*node); //以右兄弟的身份插入结点};6.1.3树的抽象数据类型

树的抽象数据类型[代码6.2]1/2 template<classT> classTree{ public: Tree(); //构造函数 virtual~Tree(); //析构函数 TreeNode<T>*getRoot();//返回树中的根结点 voidCreateRoot(constT&rootValue); //创建值为rootValue的根结点 boolisEmpty();//判空树(返true/false)树的抽象数据类型2/2TreeNode<T>*Parent(TreeNode<T>*current); //返回current结点父结点 TreeNode<T>*PrevSibling(TreeNode<T>*current); //返回current结点的前一个兄弟结点 voidDeleteSubTree(TreeNode<T>*subroot); //删除以subroot为根的子树的所有结点 voidRootFirstTraverse(TreeNode<T>*root);

//先根深度优先周游树 voidRootLastTraverse(TreeNode<T>*root); //后根深度优先周游树

voidWidthTraverse(TreeNode<T>*root); //广度优先周游树};6.1.4树的周游

1、深度优先周游树一.先根次序周游森林≡前序周游二叉树首棵树根；首棵树各子树；余下各树根；左子树；右子树依次从左至右对森林每棵树进行先序周游二.后根次序周游森林≡中序周游二叉树首棵树各子树；首棵树根；余下各树

左子树；根；右子树依次从左至右对森林每棵树进行后序周游先序：ABCEFDGHJI后序：BEFCDAJHIGABCFEDGHJIABGHCEFIDJ6.1.4树的周游

1深度优先周游

先根深度优先周游树算法6.3template<classT>voidTree<T>::RootFirstTraverse(TreeNode<T>*root){ while(root!=NULL){ Visit(root->Value());//访问当前结点 RootFirstTraverse(root->LeftMostChild()); //周游头一棵树树根的子树 root=root->RightSibling();//周游其他的树 }}6.1.4树的周游

后根深度优先周游树算法6.4template<classT>voidTree<T>::RootLastTraverse(TreeNode<T>*root){ while(root!=NULL){ RootLastTraverse(root->LeftMostChild()); //周游头一棵树树根的子树 Visit(root->Value()); //访问当前结点 root=root->RightSibling();//周游其他的树 }}6.1.4树的周游

2、广度优先周游森林breadth-first,也称宽度优先周游、层次周游从根开始自上至下逐层周游，同层从左到右逐一访问下图广度优先周游森林的结点序列AGBCDHIEFJABCFEDGHJI6.1.4树的周游广度优先周游树/森林template<classT>//[算法6.5]voidTree<T>::WidthTraverse(TreeNode<T>*root){ usingstd::queue; //使用STL队列 queue<TreeNode<T>*>aQueue; TreeNode<T>*pointer=root; while(pointer!=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=pointer->RightSibling();}}}6.2树的链式存储结构6.2.1子结点表表示法6.2.2静态左子/右兄表示法6.2.3动态结点表示法6.2.4动态“左子/右兄”二叉链表表示法6.2.5父指针表示法6.2树的链式存储结构

6.2.1子结点表表示法用数组存储各结点，每个结点信息包括结点值、其父结点在数组中下标、一个指向孩子链表的头指针每个结点的所有孩子结点链接成表，数组存储其头指针查找firstchild易，但查找nextsibling难12456父孩子^^ABCFEDG3^值000223\6.2.2静态左子/右兄表示法

两树合并举例ABCFED左子值父右兄0123456789GHJI1A\\\B024C03\D0\\E25\F2\\G\\9H68\I6\\J7\09A作H首子：H任A作左子A认H作父A认J作右兄76.2树的链式存储结构

6.2.2静态左子/右兄表示法用数组存储各结点，每个结点包括4个域：结点的值，父结点、最左子结点和右侧兄弟结点的下标ADT的基本操作可通过读取结点中的一个值来实现。如果两棵树存储在同一个数组中，那么把其中一个添加为另一棵树的子树只需简单设置三个指针值即可。此法比子结点表表示法空间效率更高，能方便访问右兄弟,而且结点数组中的每个结点仅需要固定大小的存储空间6.2树的链式存储结构

6.2.3动态表示法定长：为每个结点分配确定数目的指针（对结点度小的树浪费空间，对度大结点难以扩充）变长：每个结点空间动态分配可变的存储空间

每个结点存储子结点数目和一个相应长度的(孩)子结点指针表（见p145图6.9）本质上“子结点表”表示法相同，但是它动态地分配结点空间，而不是把结点分配在数组中6.2树的链式存储结构

6.2.4动态左子/右兄二叉链表表示法(最常用)ABDC^^EFG^^^^^^ABDEFGC每一个结点除数据域,还设两个指针域指向该结点的第一个孩子LeftChild下一个兄弟RightSiblingpChildpSibling树结点抽象数据类型的实现//补充与具体实现相关的私有成员变量申明private: Tm_Value; //树结点的值 TreeNode<T>* pChild; //左子结点 TreeNode<T>* pSibling; //右兄弟结点树结点抽象数据类型的实现template<classT>boolTreeNode<T>::isLeaf(){ //如果结点是叶，返回true if(pChild==NULL) returntrue; returnfalse; }template<classT>voidTreeNode<T>::setValue(Tvalue){ //设置结点的值 m_Value=value; }template<classT>voidTreeNode<T>::InsertFirst(TreeNode<T>*node){ //以第一个子结点的身份插入结点 if(!pChild) pChild=node;//this没左子:node作 else{ node->pSibling=pChild;//有:原左子作node右兄 pChild=node; } }//node作左子树抽象数据类型的部分实现[算法6.7]//与具体实现相关的私有成员变量private: TreeNode<T>*root; //树根结点//部分成员函数的具体实现

template<classT>Tree<T>::Tree() { //构造函数 root=NULL; }template<classT>TreeNode<T>*Tree(T)::Parent(TreeNode<T>*current){ usingstd::queue;Queue<TreeNode<T>*>aQueue;//边按层周游边找TreeNode<T>*pointer=root;TreeNode<T>*upperlevelpointer=NULL;//存父结点if(current!=NULL&&pointer!=current){ while(pointer!=NULL){

//森林所有树根入队 if(current==pointer)returnNULL; aQueue.push(pointer); pointer=pointer->RightSibling(); } while(!aQueue.empty()){ pointer=aQueue.front(); aQueue.pop();//取队头 upperlevelpointer=pointer;//父 pointer=pointer->LeftMostChild();//子 while(pointer){//pointer的所有兄弟与current比 if(current==pointer)//若等 returnupperlevelpointer;//找到parent else{ aQueue.push(pointer);//比pointer其他兄弟 pointer=pointer->RightSibling();}}}}returnNULL; }template<classT>voidTree<T>::DestoryNodes(TreeNode<T>*root){//删除以root为根的子树的所有结点（后序周游） if(root!=NULL){ DestroyNodes(root->LeftMostChild()); DestroyNodes(root->RightSibling()); deleteroot; } }树抽象数据类型的实现 template<classT> voidTree<T>::DeleteSubTree(TreeNode<T>*subroot) {//删除以subroot为根的子树的所有结点[代码6.7] TreeNode<T>*pointer; if(subroot==NULL)return;//空树不必删 pointer=Parent(subroot);//point指向(被删子树根的)父结点 if(pointer==NULL)//被删树是森林第1棵树让第2棵树作root root=subroot->RightSibling(); elseif(pointer->LeftMostChild()==subroot_)//被删点是父最左子 pointer->setChild(subroot->RightSibling());//让右兄作父最左子 else{//被删(不是最左子)有左兄,让左兄的右兄是被删点右兄 pointer=pointer->LeftMostChild(); while(pointer->RightSibling()!=subroot)//则找直接左兄 pointer=pointer->RightSibling(); pointer->setSibling(subroot->RightSibling()); } //让左兄pointer的右兄是被删点subroot的右兄

subroot->setSibling(NULL);//被删点的右兄为空(成为树而非森林) DestroyNodes(subroot);}//删树6.2.5父指针表示法父指针(parentpointer)表示法：每个结点只保存一个指针域指向其父结点用数组实现，查找父结点的T(n)=O(1)方便实现求根和求祖先算法等”向上”的操作不适合求子孙算法节省空间，适合无序树查询结点的根、合并树父指针数组表示法父节点索引标记结点索引6.3树的顺序存储6.3.1带右链的先根次序表示6.3.2带双标记位的先根次序表示6.3.3带度数的后根次序表示6.3.4带双标记的层次次序表示ABCFEDGHJI6.3.1带右链的先根次序表示在带右链的先根次序表示中，结点按先根次序顺序存储在一片连续的存储单元中。每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为:info是结点的数据，rlink是右指针，指向结点的下一个兄弟、即对应的二叉树中结点的右子结点ltag是一个一位的左标记，当结点没有子结点，即对应的二叉树中结点没有左子结点时，ltag为1，否则为0带右链的先根次序表示法这种表示法与llink—rlink表示法相比，用ltag代替了llink，占用的存储单元要少些，但并不丢失信息可以从结点的次序和ltag的值完全可以推知llinkltag==0:有左子，它的llink指向该结点数组右邻ltag==1:没有左子，它的llink为空6.3.2带双标记位的先根次序表示法带右链先根序表示法中每个结点都含ltag和rlink域，rlink也可替换为一位的rtagltag==1：叶，llink=NULLltag==0：有孩子，左子为其右邻居rtag==1：没右兄，rlink=NULLrtag==0：有右兄，但暂时不知，入栈等待确定右兄ltaginfortag6.3.2带双标记位的先根次序表示法1000010111infoltagHFDECKABJG1010110011rtagltag==1：叶，llink=NULLltag==0：有孩子，左子为其右邻rtag==1：没右兄，rlink=NULLrtag==0：有右兄，但暂时不知6.3.2带双标记位的先根次序表示法任何结点的子树结点在先根序列中都排在该结点之后；任何结点的子树结点在先根序列中排在最后的一个结点一定没有子结点(ltag为1)由结点排列次序和ltag，rtag的值就可推知rlink的值。当一个结点x的rtag为1时（无右兄），rlink应为空当一个结点x的rtag为0时（有右兄），其rlink应指向结点序列中排在结点x的子树结点后面的那个结点y如何确定x的右兄y?由于先根次序表示的树结构是嵌套的，需要用一个栈来记录待配置rlink的结点带双标记位的先根次序表示法虽然节省空间，但因需要耗费时间推导失去的信息，所以采用得更多的还是带右链的先根次序表示法带双标记位先根次序树构造算法template<classT>classDualTagTreeNode//双标记位先根次序树结点类{ public: T info; //树结点信息 int ltag; //左标记 intrtag; //右标记 DualTagTreeNode(); virtual~DualTagTreeNode();};算法6.10算法框架newp,作rootfor(count-1) p数值=node[i] ifnode[i].rtag==0:(有右兄)入栈等待确定右兄 ifnode[i].rtag==1:(无右兄)p->rlink=NULL newtempp; ifnode[i].ltag==0:(有子)p->llink=tempp; ifnode[i].ltag==1:(叶)为栈顶确定右兄 { p->llink=NULL 出栈p p->rlink=tempp;} p=tempp;最后结点被赋值ABCFEDGHJI带双标记位先根次序树构造算法[算法6.10]template<classT>//构造左子右兄树Tree<T>::Tree(DualTagTreeNode<T>*nodeArray,intcount){ usingstd::stack;//使用STL中的stack stack<TreeNode<T>*>aStack; TreeNode<T>*pointer=newTreeNode<T>;//建立结点p root=pointer; //作根for(inti=0;i<count-1;i++)//处理一个结点{ pointer->setValue(nodeArray[i].info); if(nodeArray[i].rtag==0) aStack.push(pointer);//有右兄入栈待定 else pointer->setSibling(NULL);//没右兄，rlink设为空 TreeNode<T>*temppointer=newTreeNode<T>;//建tempp if(nodeArray[i].ltag==0)pointer->setChild(temppointer);//有子 else{pointer->setChild(NULL);//叶：llink设为空 pointer=aStack.top(); aStack.pop(); //出栈ppointer->setSibling(temppointer); }//p->rlink=tempp;

pointer=temppointer; }//endfor带双标记位先根次序树构造算法[算法6.10]//处理最后一个结点 pointer->setValue(nodeArray[count-1].info); pointer->setChild(NULL); pointer->setSibling(NULL); }带度数的后根次序表示法在带度