第六章树和二叉树第一节树的类型定义A为“根”T1、T2和T3都是一棵树，称为A的子树。称根和子树根之间的连线为“分支”结点分支的个数定义为“结点的度”，如结点B的度为2，D的度为3。树中所有结点度的最大值定义为“树的度”。称度为零的结点为“叶子”或“终端结点”所有度不为零的结点被称作"分支结点"基本定义森林为m(m≥0)棵互不相交的树的集合。树的深度定义为树中叶子结点所在最大层次数。称根结点为子树根的"双亲"。称子树根为根结点的"孩子“根的所有子树根互为“兄弟”。有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。树的抽象数据类型：ADTTree{ 数据对象：D是具有相同特性的数据元素的集合。 数据关系： 若D为空集，则称为空树； 若D中仅含一个数据元素，则关系R为空集； 否则R={H}， (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即
H,i=1,2,…,m。基本操作： {结构初始化} InitTree(&T); 操作结果：构造空树T。 CreateTree(&T,definition); 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 {销毁结构} DestroyTree(&T); 初始条件：树T存在。 操作结果：销毁树T。{引用型操作} TreeEmpty(T); 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否则返回FALSE。 TreeDepth(T); 初始条件：树T存在。 操作结果：返回T的深度。 Root(T); 初始条件：树T存在。 操作结果：返回T的根。 Value(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。Parent(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则返回"空"。LeftChild(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回"空"。 RightSibling(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回"空"。TraverseTree(T,visit()); 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。{加工型操作} Assign(T,cur_e,value); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。 ClearTree(&T); 初始条件：树T存在。 操作结果：将树T清为空树。 InsertChild(&T,&p,i,c); 初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度＋1，非空树c与T不相交。 操作结果：插入c为T中p所指结点的第i棵子树。 DeleteChild(&T,&p,i); 初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。 操作结果：删除T中p所指结点的第i棵子树。}ADTTree树和线性结构对照：第二节二叉树类型定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。二叉树的5种形态：ø(a)(b)(c)(d)(e)6.2.1二叉树的类型定义ADTBinaryTree{ 数据对象：D是具有相同特性的数据元素的集合。 数据关系： 若D为空集，称BinaryTree为空二叉树； 否则关系R={H}： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)D中其余元素必可分为两个互不相交的子集L和R，每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树。如果左子树L不空，则必存在一个根结点，它是root的"左后继"(∈H)，如果右子树R不空，则必存在一个根结点为root的"右后继"(∈H)。基本操作P：{结构初始化} InitBiTree(&T); 操作结果：构造空二叉树T。 CreateBiTree(&T,definition); 初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T。 {销毁结构} DestroyBiTree(&T); 初始条件：二叉树T存在。 操作结果：销毁二叉树T。{引用型操作} BiTreeEmpty(T); 初始条件：二叉树T存在。 操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。 BiTreeDepth(T); 初始条件：二叉树T存在。 操作结果：返回T的深度。 Root(T); 初始条件：二叉树T存在。 操作结果：返回T的根。 Value(T,e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的值。Parent(T,e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲，否则返回"空"。LeftChild(T,e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左孩子。若e无左孩子，则返回"空"。RightChild(T,e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右孩子。若e无右孩子，则返回"空"。LeftSibling(T,e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左兄弟。若e是其双亲的左孩子或无左兄弟，则返回"空"。RightSibling(T,e); 初始条件：二叉树T存在，e是T的结点。 操作结果：返回e的右兄弟。若e是其双亲的右孩子或无右兄弟，则返回"空"。PreOrderTraverse(T,visit()); 初始条件：二叉树T存在,visit是对结点操作的应用函数。 操作结果：先序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。InOrderTraverse(T,vsit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。PostOrderTraverse(T,visit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：后序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。LevelOrderTraverse(T,visit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：层序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。{加工型操作} ClearBiTree(&T); 初始条件：二叉树T存在。 操作结果：将二叉树T清为空树。 Assign(&T,&e,value); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：结点e赋值为value。InsertChild(&T,p,LR,c); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点原有左或右子树成为c的右子树。DeleteChild(&T,p,LR); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。}ADTBinaryTree6.2.2二叉树的几个特性一、在二叉树的第i层上至多有2i-1个结点(i≥1)。二、深度为k的二叉树中至多含有2k-1个结点，(k≥1)。三、对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。假如一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一、一对应，则称这类二叉树为完全二叉树。第三节二叉树的存储
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示6.3.1顺序存储结构二叉树的顺序存储结构的定义如下：constMAXSIZE=100;//暂定二叉树中结点数的最大值为100typedefstruct{ ElemType*data; //存储空间基址(初始化时分配空间) intnodeNum; //二叉树中结点数}SqBiTree; //二叉树的顺序存储结构6.3.2链式存储结构二叉树的二叉链表存储表示typedefstructBiTNode{ ElemTypedata; structBiTNode*Lchild,*Rchild;//左、右孩子指针 }*BiTree;二叉树的三叉链表存储表示typedefstructTriTNode{ ElemTypedata; structBiTNode*Lchild,*Rchild;//左、右孩子指针 structBiTNode*parent; //双亲指针 }*TriTree;二叉树的双亲链表存储表示typedefstructBPTNode{ //结点结构 ElemTypedata; int*parent; //指向双亲的指针 charLRTag; //左、右孩子标志域}BPTNode第四节二叉树的遍历“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。由于二叉树中每个结点都有两个后继，则可以有三条搜索路径： 1)先左(子树)后右(子树)； 2)先右(子树)后左(子树)； 3)按层次从上到下。6.4.1先左后右的遍历6-4-1遍历.swfGHDEFBCA先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA先序遍历递归算法voidPreOrder(BTreeBT){if(BT){Visit(BT);PreOrder(BT->Lchild);PreOrder(BT->Rchild);}}6-4-2-1.swf中序遍历递归算法voidInOrder(BTreeBT){if(BT){InOrder(BT->Lchild);Visit(BT);InOrder(BT->Rchild);}}6-4-2-2.swf后序遍历递归算法voidPostOrder(BTreeBT){if(BT){PostOrder(BT->Lchild);PostOrder(BT->Rchild);Visit(BT);}}6-4-2-3.swf按层次遍历二叉树按层次遍历该二叉树的序列为：ABCDEFGHGHDEFBCA二叉树用链式存储结构表示时，按层遍历的算法实现（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；GHDEFBCAvoidLevelOrder(BTree*BT){if(!BT)exit;InitQueue(Q);p=BT;//初始化Visite(p);EnQueue(&Q,p);//访问根结点，并将根结点入队while(!QueueEmpty(Q)){//当队非空时重复执行下列操作DeQueue(&Q,&p);//出队if(!p->Lchild){Visite(p->Lchild);EnQueue(&Q,p->Lchild);}//处理左孩子if(!p->Rchild){Visite(p->Rchild);EnQueue(&Q,p->Rchild);}//处理右孩子}}建立二叉树voidCreateBiTree(BiTree&T) { //在先序遍历二叉树的过程中输入二叉树的"先序字符串"， //建立根指针为T的二叉链表存储结构。在先序字符串中， //字符'#'表示空树，其它字母字符为结点的数据元素 cin>>ch； if(ch=='#')T=NULL; //建空树 else{ T=newBiTNode;//"访问"操作为生成根结点 T->data=ch; CreateBiTree(T->Lchild); //递归建(遍历)左子树 CreateBiTree(T->Rchild); //递归建(遍历)右子树 } }6-4-6.swf统计二叉树中叶子结点的个数voidCountLeaf(BiTreeT,int&count) { //先序遍历二叉树，以count返回二叉树中叶子结点的数目 if(T){ if((!T->Lchild)&&(!T->Rchild)) count++; //对叶子结点计数 CountLeaf(T->Lchild,count); CountLeaf(T->Rchild,count); }//if }求二叉树的深度voidBiTreeDepth(BiTreeT,intlevel,int&depth) {//T指向二叉树的根，level为T所指结点所在层次，其初值为1，depth为当前求得的最大层次,其初值为0 if(T){ if(level>depth)depth=level; BiTreeDepth(T->Lchild,level+1,depth); BiTreeDepth(T->Rchild,level+1,depth); } }6-4-3求二叉树的深度.swf复制二叉树生成一个二叉树的结点的算法：BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr) {//生成一个其元素值为item，左指针为lptr，右指针为rptr的结点 T=newBiTNode;T->data=item; T->Lchild=lptr;T->Rchild=rptr; returnT; }后序遍历复制二叉树的操作为:BiTNode*CopyTree(BiTNode*T) { //已知二叉树的根指针为T，本算法返回它的复制品的根指针 if(!T) returnNULL; //复制一棵空树 if(T->Lchild) newlptr=CopyTree(T->Lchild); //复制(遍历)左子树 elsenewlptr=NULL; if(T->Rchild) newrptr=CopyTree(T->Rchild);//复制(遍历)右子树 elsenewrptr=NULL; newnode=GetTreeNode(T->data,newlptr,newrptr);//生成根结点 returnnewnode; }6-4-5后序遍历复制.swf在二叉树上查询某个结点voidlocate(BiTreeT,ElemTypex,BiTree&p){ //若二叉树T中存在和x相同的元素，则p指向该结点，否则p的值不变，p的初值为NULL if(T) {if(T->data==x)p=T; locate(T->lchild,x,p); locate(T->rchild,x,p); }}中序遍历（非递归）InitStack(S);Push(S,T);//根入栈while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);//向左到尽头Pop(S,p);//空指针出栈if(!StackEmpty(S))//访问，向右{Pop(S,p);if(!Visit(p->data))returnERROR;Push(S,p->rchild);}}returnOK;表达式的二叉树二叉树的线索链表将在二叉树中每个结点（除第一个和最后一个外）的直接前驱和直接后继保存起来。这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。typedefenumPointerType{Link=0,Thread=1};//定义指针类型，以Link表示指针，Thread表示线索 typedefstructBiThrNode{ ElemTypedata; structBiThrNode*Lchild,*Rchild;//左右指针 PointerTypeLTag,RTag;//左右指针类型标志 }*BiThrTree;在线索链表中添加了一个"头结点"，头结点的左指针指向二叉树的根结点，其右线索指向中序序列中的最后一个结点以中序线索链表为存储结构的中序遍历voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(ElemTypee)) {//T指向中序线索链表中的头结点，头结点的左指针Lchild指向二叉树的根结点，头结点的右线索Rchild指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历，对树中每个元素调用函数Visit进行访问操作 p=T->Lchild; //p指向二叉树的根结点 while(p!=T){ //空树或遍历结束时，p==Thead while(p->LTag==Link)p=p->Lchild; Visit(p->data); //访问其左子树为空的结点 while(p->RTag==Thread&&p->Rchild!=T){ p=p->rchild;Visit(p->data);//访问“右线索”所指后继结点 } p=p->Rchild; //p进至其右子树根 } }p=T->Lchild; //p指向二叉树的根结点while(p!=T){ //空树或遍历结束时，p==Thead while(p->LTag==Link)p=p->Lchild; Visit(p->data); //访问其左子树为空的结点 while(p->RTag==Thread&&p->Rchild!=T){ p=p->rchild;Visit(p->data);//访问“右线索”所指后继结点 } p=p->Rchild; //p进至其右子树根}6-5-1.swf线索链表的生成voidInThreading(BiThrTreep，BiThrTree&pre){ //对p指向根结点的二叉树进行中序遍历，遍历过程中进行“中序线索化”。若p所指结点的左指针为空，则将它改为“左线索”，若pre所指结点的右指针为空，则将它改为“右线索”。指针pre在遍历过程中紧随其后，即始终指向p所指结点在中序序列中的前驱。 if(p){ InThreading(p->Lchild,pre);//对左子树进行线索化 if(!p->Lchild) {p->LTag=Thread;p->Lchild=pre;}//建前驱线索 if(!pre->Rchild) {pre->RTag=Thread;pre->Rchild=p;}//建后继线索 pre=p; //保持pre指向p的前驱 InThreading(p->Rchild,pre);//对右子树进行线索化 }}voidInOrderThreading(BiThrTree&Th,BiThrTreeBT){ //BT为指向二叉树根结点的指针，由此二叉链表建立二叉树的中序线索链表，Thead指向线索链表中的头结点。 BiThrTreepre; if(!(Th=newBiThrNode))exit(1);//存储分配失败 Th->LTag=Link;Th->RTag=Thread; //建头结点 Th->Rchild=Th; //右指针回指 if(!BT)Th->Lchild=Th; //若二叉树空，则左指针回指 else{ Th->Lchild=BT;pre=Thead; InThreading(BT,pre); //中序遍历进行中序线索化 pre->Rchild=Th;pre->RTag=Thead;//对中序序列中最后一个结点进行线索化 Th->Rchild=pre; //建非空树的头结点的"右线索" }}6-5-2.swf树和森林的存储表示1树的双亲表示法constMAX_TREE_SIZE=100;typedefstruct{//结点结构 ElemTypedata; intparent;//双亲位置域}PTNode;typedefstruct{//树结构 PTNodenodes[MAX_TREE_SIZE]; intr,n;//根的位置和结点数}PTree;2树的孩子表示法树的孩子链表存储表示 typedefstructCTNode{ //孩子结点 intchild; structCTNode*next; }*ChildPtr; typedefstruct{ ElemTypedata;//结点的数据元素 ChildPtrfirstchild;//孩子链表头指针 }CTBox; typedefstruct{ CTBoxnodes[MAX_TREE_SIZE]; intn,r; //结点数和根结点的位置 }CTree;3树和森林的孩子兄弟表示法存储表示typedefstructCSNode{ ElemTypedata; structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;firstchild指向该结点的"第一个"子树根结点，nextsibling指向它的"下一个"兄弟结点。树的孩子-兄弟链表森林的孩子-兄弟链表森林和二叉树的转换森林－>二叉树6-6-1.swf二叉树森林6-6-2.swf树的遍历一、先根(次序)遍历树 若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树；ABEHIJCDFGK6-7-3.swf二、后根(次序)遍历树 若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；HIJEBCFKGDA6-7-4.swf森林的遍历一、先序遍历森林 若森林不空，则可依下列次序进行遍历 (1)访问森林中第一棵树的根结点； (2)先序遍历第一棵树中的子树森林； (3)先序遍历除去第一棵树之后剩余的树构成的森林。二、中序遍历森林 若森林不空，则可依下列次序进行遍历： (1)中序遍历第一棵树中的子树森林； (2)访问森林中第一棵树的根结点； (3)中序遍历除去第一棵树之后剩余的树构成的森林。求森林的深度森林的深度=Max{每一棵树的深度}树的深度=其子树森林的深度+1intDepth_Tree(CSTreeT){//T是以孩子-兄弟链表存储的森林的头指针，返回该森林的深度 if(!T)return0; else{ dep=0; //初始化森林的深度为0 p=T; //指针p指向第一棵树的根 while(p){ d=Depth_Tree(p->firstchild);//返回*p的子树森林的深度 if(d+1>dep)dep=d+1; //求各棵树的深度的最大值 p=p->nextsibling; //指针p移向下一棵树的根 } returndep; }}
浙公网安备 33021202002483