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

《数据结构-二叉树的存储结构和遍历.ppt》由会员分享，可在线阅读，更多相关《数据结构-二叉树的存储结构和遍历.ppt（56页珍藏版）》请在三一办公上搜索。

1、二叉树的存储结构和遍历,二叉树的遍历,二叉树的存储结构,小结和作业,顺序存储,二叉链表,三叉链表,链式存储,问题的提出,递归遍历算法,遍历的应用实例,二叉树的顺序存储,顺序存储是用一组连续的存储单元存放数据,顺序存储要求数据是线性结构,二叉树是非线性结构,如何把二叉树转换为线性结构，而且保持结点之间的父/子关系?,二叉树的顺序存储,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,满二叉树：从上到下，从左往右依次编号,二叉树的顺序存储,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,数

2、组的下标，也是结点的编号,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,二叉树的顺序存储,完全二叉树：从上到下，从左往右依次编号,0 1 2 3 4 5 6 7 8 9 10,二叉树的顺序存储,一般的二叉树：想象成一个完全二叉树,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,二叉树的顺序存储,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,如何知道有无数据？,#define

3、 MAX_TREE_SIZE 100/二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/1号单元存储根结点SqBiTree bt;,二叉树的顺序存储,#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef struct TElemType dataMAX_TREE_SIZE;char flagMAX_TREE_SIZE;SqBiTree;,二叉树的顺序存储,适用于一般的二叉树,链式存储二叉链表,二叉链表的结点结构:,左指针域，指向当前结点的左子树,数据域，存储当前结点的取值信息,右指针域，指向当前结点的右子树,指向

4、二叉树根结点,头指针：,前述二叉树的二叉链表如下所示：,A,F,E,C,D,B,root,链式存储二叉链表,typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,结点结构:,二叉链表的C 语言类型描述如下:,左指针域,数据域,右指针域,链式存储二叉链表,三叉链表的结点结构:,指向双亲结点的指针域,左指针域,数据域,右指针域,链式存储三叉链表,root,E,二叉树的三叉链表表示：,链式存储三叉链表,typedef struct TriTNode TElem

5、Type data;struct TriTNode*lchild,*rchild;struct TriTNode*parent;TriTNode,*TriTree;,三叉链表的C 语言类型描述如下:,结点结构:,/结点结构,/左右孩子指针,/双亲指针,链式存储三叉链表,问题的提出,在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。,问题的提出,定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,作用：遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。

6、,问题的提出,线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。,二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。,问题的提出,二叉树存在下述三条搜索路径：,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,B C D,E

7、 F G H K,课堂练习,写出先序遍历的结果,void Preorder(BiTree T,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,B D C,E H G K F,中序遍历,void Inorder(BiTree T,void(*visit)(TElemType/遍历右子树,后序（根）遍历,左子树,右子树,根,根,左子树,右子

8、树,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,后序（根）遍历,A,B,C,D,E,F,G,H,K,A,D C B,H K G F E,void Postorder(BiTree T,void(*visit)(TElemType/访问结点,后序遍历,课堂练习,写出三种遍历的结果,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,三种遍历的比较,1、如果不考虑visit，三种遍历的算法在结构上是一样的，因此，压栈和出栈的过程相同。,三种遍历的比较,2、

9、三种遍历的执行过程是不一样的（visit的位置不一样）。,3、由前序序列和中序序列，或者后序和中序序列可以唯一确定一颗二叉树,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,三种遍历的比较,3、复制二叉树,4、建立二叉树,2、查询二叉树中某个结点,应用举例,1、统计二叉树中结点的个数,遍历访问了每个结点一次且仅一次,设置一个全局变量count=0,统计二叉树中结点的个数,将visit改为:count+,统计二叉树中结点的个数,void PreOrder(BiTree T),if(!T)return;

10、,count+;,Preorder(T-lchild);,Preorder(T-rchild);,void Preorder(BiTree T,void(*visit)(TElemType/遍历右子树,统计二叉树中结点的个数,int count=0;,main(),PreOrder(T);,printf(”%d”,count);,递归思想:,如果是空树，返回0,统计二叉树中结点的个数,求出左子树的结点的个数m,求出右子树的结点的个数n,返回m+n+1,统计二叉树中结点的个数,int CountNode(BiTree T)/返回指针T所指二叉树中所有叶子结点个数,if(!T)return 0;/

11、空树,m=CountNode(T-lchild);,n=CountNode(T-rchild);,return(m+n+1);,求二叉树的深度,课堂练习：,空树的深度为0，,求二叉树的深度,int Depth(BiTree T)/返回二叉树的深度,if(!T)return(0);,depthLeft=Depth(T-lchild);,depthRight=Depth(T-rchild);,depthval=1+(depthLeft depthRight?depthLeft:depthRight);,return depthval;,查询二叉树中的某个结点,给定指向二叉树的根结点的指针T和x，在

12、T中查找数据元素的值等于x的结点，如果找到，则返回一个指针，指向这个结点，否则，返回空指针。,T,X=C,查询二叉树中的某个结点,1.在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回指向根结点的指针,2.否则在左子树中进行查找,若找到,则返回指针,3.否则继续在右子树中进行查找,若找到,则返回指针,否则返回空指针,查询二叉树中的某个结点,BiTree Search(BiTree T,TElemType x),if(!T)return(NULL);if(T-data=x)return(T)；,if(p)/返回值不是空指针，则表示x在左子树中return(p);else retur

13、n(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,复制二叉树,Bitree Copy(BitTree T),if(!T)return(NULL);,p=new BiNode;p-data=T-data,p

14、l=Copy(T-lchild);,pr=Copy(T-rchild);,p-lchild=pl;p-rchild=pr;,return(p);,以下列字符串表示,AB C D,建立二叉树,以字符串的形式“根左子树右子树”定义一棵二叉树,以空白字符“”表示,1）空树,2）只含一个根结点的二叉树,A,以字符串“A”表示,3）,建立二叉树,A B C D,A,B,C,D,A,T,B,C,D,建立二叉树,Status CreateBiTree(BiTree&T)/CopyTree,scanf(,else,T-data=ch;/生成根结点,return OK;,if(!(T=new BiTNode)e

15、xit(OVERFLOW);,if(ch=)T=NULL;,CreateBiTree(T-lchild);/构造左子树,CreateBiTree(T-rchild);/构造右子树,小结,1）二叉树的顺序存储表示,2）二叉树的二叉链表存储表示,二叉链表,双亲链表,三叉链表,3）二叉树的遍历,前序（先根）,中序（中根）,后序（后根）,作业,作业：6.12，6.42，6.43,建立二叉树,由二叉树的先序和中序序列建树,二叉树的先序序列：,二叉树的中序序列：,左子树,左子树,右子树,右子树,根,根,建立二叉树,a b c d e f g,c b d a e g f,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 pre,T in,int prepos,int low,int high)if(low high)return(NULL);BiNode*p=new BiNode;for(int i=low;i*pl,*pr;pl=create(pre,in,prepos+1,low,i-1);pr=create(pre,in,prepos+i-low+1,i+1,high);p-data=preprepos;p-lchild=pl;p-rchild=pr;return(p);,