数据结构-二叉树的存储结构和遍历ppt课件

二叉树的存储结构和遍历,二叉树的遍历,二叉树的存储结构,小结和作业,顺序存储,二叉链表,三叉链表,链式存储,问题的提出,递归遍历算法,遍历的应用实例,二叉树的顺序存储,顺序存储是用一组连续的存储单元存放数据,顺序存储要求数据是线性结构,二叉树是非线性结构,如何把二叉树转换为线性结构，而且保持结点之间的父/子关系?,二叉树的顺序存储,A,C,G,B,D,E,F,K,L,H,J,I,M,N,O,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,满二叉树：从上到下，从左往右依次编号,二叉树的顺序存储,0123456789101112131415,数组的下标，也是结点的编号,0123456789101112131415,二叉树的顺序存储,完全二叉树：从上到下，从左往右依次编号,012345678910,二叉树的顺序存储,一般的二叉树：想象成一个完全二叉树,0,0,0,0,0,0,0,0,二叉树的顺序存储,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,二叉树的顺序存储,01234567891011121314,01234567891011121314,如何知道有无数据？,#defineMAX_TREE_SIZE100/二叉树的最大结点数typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/1号单元存储根结点SqBiTreebt;,二叉树的顺序存储,#defineMAX_TREE_SIZE100/二叉树的最大结点数typedefstructTElemTypedataMAX_TREE_SIZE;charflagMAX_TREE_SIZE;SqBiTree;,二叉树的顺序存储,适用于一般的二叉树,链式存储二叉链表,二叉链表的结点结构:,左指针域，指向当前结点的左子树,数据域，存储当前结点的取值信息,右指针域，指向当前结点的右子树,指向二叉树根结点,头指针：,前述二叉树的二叉链表如下所示：,A,F,E,C,D,B,root,链式存储二叉链表,typedefstructBiTNode/结点结构TElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;,结点结构:,二叉链表的C语言类型描述如下:,左指针域,数据域,右指针域,链式存储二叉链表,三叉链表的结点结构:,指向双亲结点的指针域,左指针域,数据域,右指针域,链式存储三叉链表,root,E,二叉树的三叉链表表示：,链式存储三叉链表,typedefstructTriTNodeTElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*parent;TriTNode,*TriTree;,三叉链表的C语言类型描述如下:,结点结构:,/结点结构,/左右孩子指针,/双亲指针,链式存储三叉链表,问题的提出,在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。,问题的提出,定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,作用：遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。,问题的提出,线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。,二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。,问题的提出,二叉树存在下述三条搜索路径：,1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；DLR，LDR，LRD3先右（子树）后左（子树）的遍历。DRL，RDL，RLD,先序（根）遍历,根,左子树,右子树,若二叉树为空树，则空操作；否则，（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树,先序（根）遍历,A,B,C,D,E,F,G,H,K,A,B,C,D,E,F,G,H,K,A,BCD,EFGHK,课堂练习,写出先序遍历的结果,voidPreorder(BiTreeT,void(*visit)(TElemType/遍历右子树,先序遍历,中序（根）遍历,左子树,右子树,根,根,左子树,右子树,若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树,中序（根）遍历,A,B,C,D,E,F,G,H,K,A,B,C,D,E,F,G,H,K,A,BDC,EHGKF,中序遍历,voidInorder(BiTreeT,void(*visit)(TElemType/遍历右子树,后序（根）遍历,左子树,右子树,根,根,左子树,右子树,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,后序（根）遍历,A,B,C,D,E,F,G,H,K,A,DCB,HKGFE,voidPostorder(BiTreeT,void(*visit)(TElemType/访问结点,后序遍历,课堂练习,写出三种遍历的结果,先序序列：,中序序列：,后序序列：,ABCDEFGHK,BDCAEHGKF,DCBHKGFEA,三种遍历的比较,1、如果不考虑visit，三种遍历的算法在结构上是一样的，因此，压栈和出栈的过程相同。,三种遍历的比较,2、三种遍历的执行过程是不一样的（visit的位置不一样）。,3、由前序序列和中序序列，或者后序和中序序列可以唯一确定一颗二叉树,先序序列：,中序序列：,后序序列：,ABCDEFGHK,BDCAEHGKF,DCBHKGFEA,三种遍历的比较,3、复制二叉树,4、建立二叉树,2、查询二叉树中某个结点,应用举例,1、统计二叉树中结点的个数,遍历访问了每个结点一次且仅一次,设置一个全局变量count=0,统计二叉树中结点的个数,将visit改为:count+,统计二叉树中结点的个数,voidPreOrder(BiTreeT),if(!T)return;,count+;,Preorder(T-lchild);,Preorder(T-rchild);,voidPreorder(BiTreeT,void(*visit)(TElemType/遍历右子树,统计二叉树中结点的个数,intcount=0;,main(),PreOrder(T);,printf(”%d”,count);,递归思想:,如果是空树，返回0,统计二叉树中结点的个数,求出左子树的结点的个数m,求出右子树的结点的个数n,返回m+n+1,统计二叉树中结点的个数,intCountNode(BiTreeT)/返回指针T所指二叉树中所有叶子结点个数,if(!T)return0;/空树,m=CountNode(T-lchild);,n=CountNode(T-rchild);,return(m+n+1);,求二叉树的深度,课堂练习：,空树的深度为0，,求二叉树的深度,intDepth(BiTreeT)/返回二叉树的深度,if(!T)return(0);,depthLeft=Depth(T-lchild);,depthRight=Depth(T-rchild);,depthval=1+(depthLeftdepthRight?depthLeft:depthRight);,returndepthval;,查询二叉树中的某个结点,给定指向二叉树的根结点的指针T和x，在T中查找数据元素的值等于x的结点，如果找到，则返回一个指针，指向这个结点，否则，返回空指针。,T,X=C,查询二叉树中的某个结点,1.在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回指向根结点的指针,2.否则在左子树中进行查找,若找到,则返回指针,3.否则继续在右子树中进行查找,若找到,则返回指针,否则返回空指针,查询二叉树中的某个结点,BiTreeSearch(BiTreeT,TElemTypex),if(!T)return(NULL);if(T-data=x)return(T)；,if(p)/返回值不是空指针，则表示x在左子树中return(p);elsereturn(Search(T-rchild,x);,p=Search(T-lchild,x);,复制二叉树(练习),给定一棵二叉树，T指向其根结点，复制一棵二叉树，返回一个指向新树根结点的指针,根元素,T,右子树,NEWT,左子树,右子树,左子树,复制二叉树,1、如果T为空，则返回空指针,2、复制根结点，p指向新结点,3、复制左子树，pl指向左子树的根,4、复制右子树，pr指向右子树的根,5、p-lchid=pl，p-rchild=pr,6、返回p,复制二叉树,BitreeCopy(BitTreeT),if(!T)return(NULL);,p=newBiNode;p-data=T-data,pl=Copy(T-lchild);,pr=Copy(T-rchild);,p-lchild=pl;p-rchild=pr;,return(p);,以下列字符串表示,ABCD,建立二叉树,以字符串的形式“根左子树右子树”定义一棵二叉树,以空白字符“”表示,1）空树,2）只含一个根结点的二叉树,A,以字符串“A”表示,3）,建立二叉树,ABCD,A,B,C,D,A,T,B,C,D,建立二叉树,StatusCreateBiTree(BiTree/生成根结点,returnOK;,if(!(T=newBiTNode)exit(OVERFLOW);,if(ch=)T=NULL;,CreateBiTree(T-lchild);/构造左子树,CreateBiTree(T-rchild);/构造右子树,小结,1）二叉树的顺序存储表示,2）二叉树的二叉链表存储表示,二叉链表,双亲链表,三叉链表,3）二叉树的遍历,前序（先根）,中序（中根）,后序（后根）,作业,作业：6.12，6.42，6.43,建立二叉树,由二叉树的先序和中序序列建树,二叉树的先序序列：,二叉树的中序序列：,左子树,左子树,右子树,右子树,根,根,建立二叉树,abcdefg,cbdaegf,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序:中序:,建立二叉树,BiNode*Bitree:create(T