C语言二叉树PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,二叉树,2,回顾,1.,理解队列原理,2.,掌握队列的基本操作,本次课程内容,树的定义及术语,二叉树的定义及基本概念,(,重点,),树与二叉树的存储结构,树与二叉树的遍历（重点）,树是一类重要的非线性数据结构，是以分支关系定义的层次结构,定义,定义：树,(tree),是,n(n0),个结点的有限集,T,，,其中：,有且仅有一个特定的结点，称为树的,根,(root),当,n1,时，其余结点可分为,m(m0),个,互不相交,的有限集,T,1,T2,T,m,，,其中每一个集合本身又是一棵树，称为根的,子树,(,subtree),特点：,树中至少有一个结点,根,树中各子树是互不相交的集合,树的定义,A,只有根结点的树,A,B,C,D,E,F,G,H,I,J,K,L,M,有子树的树,根,子树,树的定义,基本术语,结点,(node),表示树中的元素，包括数据项及若干指向其子树的分支,结点的度,(degree),结点拥有的子树数,叶子,(leaf),度为,0,的结点,孩子,(child),结点子树的根称为该结点的孩子,双亲,(parents),孩子结点的上层结点叫该结点的,兄弟,(sibling),同一双亲的孩子,树的度,一棵树中最大的结点度数,结点的层次,(level),从根结点算起，,根为第一层,，它的孩子为第二层,深度,(depth),树中结点的最大层次数,森林,(forest)m(m,0),棵互不相交的树的集合,树的相关术语,A,B,C,D,E,F,G,H,I,J,K,L,M,结点,A,的度：,3,结点,B,的度：,2,结点,M,的度：,0,叶子：,K,，,L,，,F,，,G,，,M,，,I,，,J,结点,A,的孩子：,B,，,C,，,D,结点,B,的孩子：,E,，,F,结点,I,的双亲：,D,结点,L,的双亲：,E,结点,B,，,C,，,D,为兄弟,结点,K,，,L,为兄弟,树的度：,3,结点,A,的层次：,1,结点,M,的层次：,4,树的深度：,4,结点,F,，,G,为堂兄弟,结点,A,是结点,F,，,G,的祖先,树的相关术语,定义,定义：二叉树是,n(n,0),个结点的有限集，它或为空树(,n=0),，,或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成,特点,每个结点至多有二棵子树,(,即不存在度大于,2,的结点,),二叉树的子树有左、右之分，且其次序不能任意颠倒,基本形态,A,只有根结点,的二叉树,空二叉树,A,B,右子树为空,A,B,左子树为空,A,B,C,左、右子树,均非空,二叉树,性质,1,：,证明：用归纳法证明之,i=1,时，只有一个根结点，,是对的,假设对所有,j(1,j1,则其双亲是,i/2,(2),如果2,in,，,则结点,i,无左孩子；如果2,in,，,则其左孩子是2,i,(3),如果2,i+1n,，,则结点,i,无右孩子；如果2,i+1n,，,则其右孩子是2,i+1,二叉树性质,双亲表示法,实现：定义结构数组存放树的结点，每个结点含两个域：,数据域：存放结点本身信息,双亲域：指示本结点的双亲结点在数组中位置,特点：,找双亲容易，找孩子难,typedef struct node,datatype data;,int parent;,JD;,JD tM;,树的存储结构,a,b,c,d,e,f,h,g,i,a,c,d,e,f,g,h,i,b,0,1,2,2,3,5,5,5,1,0,9,6,0,1,2,3,4,5,7,8,9,data,parent,0,号单元不用或,存结点个数,如何找孩子结点,树的存储结构,孩子表示法,多重链表：每个结点有多个指针域，分别指向其子树的根,结点同构：结点的指针个数相等，为,树的度,D,结点不同构：结点指针个数不等，为该结点的度,d,data child1 child2 .childD,data degree child1 child2 .childd,孩子链表：每个结点的孩子结点用单链表存储，再用含,n,个元素的结构数组指向每个孩子链表,孩子结点：,typedef struct,node,int child;/,该结点在表头数组中下标,struct node *next;/,指向下一孩子结点,JD;,表头结点：,typedef struct tnode,datatype data;/,数据域,struct,node,*fc;/,指向第一个孩子结点,TD;,TD tM;/t0,不用,树的存储结构,a,b,c,d,e,f,h,g,i,6,0,1,2,3,4,5,7,8,9,a,c,d,e,f,g,h,i,b,data,fc,2,3,4,5,9,7,8,6,如何找双亲结点,树的存储结构,带双亲的孩子链表,6,1,2,3,4,5,7,8,9,a,c,d,e,f,g,h,i,b,data,fc,2,3,4,5,9,7,8,6,0,1,2,2,3,5,5,5,1,parent,a,b,c,d,e,f,h,g,i,树的存储结构,孩子兄弟表示法（二叉树表示法）,实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点,特点,操作容易,破坏了树的层次,typedef struct node,datatype data;,struct node *fch,*nsib;,JD;,a,b,c,d,e,f,h,g,i,a,b,c,d,e,f,g,h,i,树的存储结构,顺序,存储结构,实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素,特点：,结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树,a,b,c,d,e,f,g,a b c d e,0 0 0 0,f g,1 2 3 4 5 6 7 8 9 10 11,二叉树的存储结构,链式,存储结构,二叉链表,typedef struct node,datatype data;,struct node *lchild,*rchild;,JD;,lchild data rchild,A,B,C,D,E,F,G,在,n,个结点的二叉链表中，有,n+1,个空指针域,A,B,C,D,E,F,G,二叉树的存储结构,三叉链表,typedef struct node,datatype data;,struct node *lchild,*rchild,*parent;,JD;,lchild data parent rchild,A,B,C,D,E,F,G,A,B,C,D,E,F,G,二叉树的存储结构,树的遍历,遍历,按,一定规律,走遍树的各个顶点，且使每一顶点仅,被访问一次,，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列,常用方法,先根,（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树,后根,（序）遍历：先依次后根遍历每棵子树，然后访问根结点,按,层次,遍历：先访问第一层上的结点，然后依次遍历第二层，,第,n,层的结点,树的遍历,A,B,C,D,E,F,G,H,I,J,K,LM,N,O,先序遍历：,后序遍历：,层次遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,树的遍历,方法,先,序遍历：先访问根结点,然后分别先序遍历左子树、右子树,中,序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树,后,序遍历：先后序遍历左、右子树，然后访问根结点,按,层次,遍历：从上到下、从左到右访问各结点,D,L,R,LDR,、,LRD,、,DLR,二叉树的遍历,D L R,A,D L R,D L R,B,D,C,D L R,先序遍历序列A B D C,A,D,B,C,先序遍历,:,二叉树的遍历,L D R,B,L D R,L D R,A,D,C,L D R,中序遍历序列：,B D A C,A,D,B,C,中序遍历,:,二叉树的遍历,A,D,B,C,L R D,L R D,L R D,A,D,C,L R D,后序遍历序列：,D B C A,后序遍历,:,B,二叉树的遍历,-,+,/,a,*,b,-,e,f,c,d,先序遍历,：,中序遍历：,后序遍历：,层次遍历,：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,二叉树的遍历,总结,树的定义以及基本术语,二叉树的定义及相关的,5,个特性,树,4,种存储结构与二叉树的,3,种存储结构,树与二叉树的前序,中序,后序,层次遍历,作业,已知一棵二叉树的先根序遍历序列为,ABDGCEHF,，中根序遍历序列为,BGDAEH CF,，试画出该二叉树。,已知一棵二叉树的后根序遍历序列为,GDEBHFCA,，中根序遍历序列为,DGBEAF HC,，试画出该二叉树。,预习,数据结构总结,32,