《树的概念树的遍历及存储二叉树二叉树的遍历线索二叉树哈》由会员分享，可在线阅读，更多相关《树的概念树的遍历及存储二叉树二叉树的遍历线索二叉树哈（53页珍藏版）》请在金锄头文库上搜索。
1、树的概念 树的遍历及存储 二叉树 二叉树的遍历 线索二叉树 哈夫曼树及其应用,第七章 树形结构,树的递定义 树是由 n (n 0) 个结点组成的有限集合。如果 n = 0，称为空树；如果 n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为 m (m 0) 个 互不相交的有限集合T0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树。,树的概念,树的逻辑结构 除了根结点外，每个结点有且仅有一个直接前驱。 所有结点可以有多个直接后继。 1-多,树的表示,(1) 树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非
2、常直观和形象。下图就是采用这种表示法。,(2) 文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。,(3) 凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。,(4) 括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。,ADT List 数据对象: D=ai|1i n, n 0, ai属Elemtype类型 数据关系: R1=| ai ,aj D, 1i n, 1j n, 每个元素只有一个前驱可以有多个后继 基本运算: InitTree(t); ClearTree(t); Parent(
3、t,e); Sons(t,e); ,抽象数据类型数的定义,树的基本常用术语,层次 根为第1层 最大层数为树的深度（高度）,双亲 (直接前驱） 孩子（直接后继） 兄弟 堂兄弟 子孙 祖先,森林-m(m=0)棵互不相交的树的集合。,d=3,d=0,度 一个结点的子树的个数称为该结点的度。,度为零的结点称为叶子结点。,度不为零的结点称为分支结点。,树中所有结点的度的最大值为树的度。dmax=3,d=2,树和森林的遍历,深度优先遍历 先根次序遍历 后根次序遍历 广度优先遍历 按层次序遍历,先根次序遍历 当树非空 *访问根结点 *依次先根遍历根的各子树 D T1 T2 T3 A,BEF,CG,DH IJ
4、,先根次序遍历森林 依次先根遍历各子树 T1 T2 T3,ABCDE,FG,HIKJ,树和森林的遍历,后根次序遍历 当树非空 *依次后根遍历根的各子树 *访问根结点 T1 T2 T3 D A,EFB,GC,H IJD,后根次序遍历森林 依次后根遍历各子树 T1 T2 T3,BCEDA,GF,KIJH,树和森林的遍历,按层次序遍历 当树非空 *自上向下依次遍历每一层 *每层从左向右访问结点 层次： 1 2 3,A,BCD,EFGH IJ,按层次序遍历森林 依次遍历森林中各层结点 层次： 1 2 3,AFH,BCDGIJ,EK, 双亲表示,树的存储结构,A B C D E F G,-1 0 0 0
5、 1 1 3,指向其双亲的位置,特点：很快确定双亲结点, 孩子表示法,每个结点拥有孩子的个数不同， 所以采用单链表链接孩子结点。,孩子结点的序号,指向下一个孩子结点,指向第一个孩子结点,A B C D E F G,1,2,3,4,5,6,typedef struct cnode int child; struct cnode *next; link;,typedef struct datatype data; link *headptr; ctree; ctree Tmaxnode;,特点：很快确定孩子结点 但确定双亲效率低,data parent headprt,-1 0 0 0 1 1 3
6、,孩子双亲表示法, 孩子兄弟表示,指向第一个孩子结点,指向右兄弟结点,定义： 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,二叉树 (Binary Tree),二叉树的五种不同形态,度2 有序树,？二叉树与度为2的树的区别,度 2 =2 序 有序 无序,分别有0个 1个 2个 3个4个结点的不同二叉树如下,n0 =1,n1 =1,n2 =2,n3 =5,n4 =14,0个,1个,2个,3个,4个,性质2 深度为 k 的二叉树至多有 2k-1个结点。(k 1),二叉树的性质,性质1 在二叉树的第 i 层最多有 2i-1
7、 个结点。(i 1),证 （数学归纳法） i=1 , 2i-1 =20=1 。 设i=j成立，即第j层至多2j-1个结点。 则j+1层，最多有2*2j-1= 2(j+1)-1 （由于每个最多有两个后继）,证 20 + 21 + + 2k-1 = 2k-1,性质3 对任何一棵二叉树, 若其叶结点个数为 n0, 度为2的结点个数为 n2, 则有 n0n21。,完全二叉树 (Complete Binary Tree),满二叉树 (Full Binary Tree),满二叉树和完全二叉树,深度为k且有2k-1个结点， 所有分支结点的度为 2， n1=0 叶子结点都在最下一层。,叶子结点都在最下两层，
8、且最下一层集中在最左边。,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,1 2 3 4 5 6 7 8 9 10,若按层次编号，则各结点的编号与其位置1-1对应。,性质4 具有 n (n 0) 个结点的完全二叉树的深度为 log2(n+1) -1,证设完全二叉树的高度为 k， 则有： 2k-1 - 1 n 2k - 1 变形 2k-1 n 2k 取对数 k-1 log2(n) k 因此有 h = log2(n) +1,性质5 一棵有n个结点的完全二叉树，若按层次结点编号，对于任一编号为i结点，则有： 若i = 1, 则结点 i 无双亲 若i 1, 则结点i 的双亲编号
9、为i /2 若2*i= n, 则结点 i 的左孩子编号为 2*i 若2*i= n, 则结点 i 的右孩子编号为2*i +1,1 2 3 4 5 6 7 8 9 10,例： 结点4的双亲编号为2 结点4的左孩子编号为8 结点4的右孩子编号为9,由于（性质5）完全二叉树按层次编号后，可确定各结点与其双亲及孩子的关系，则完全二叉树按编号次序进行顺序表示。,顺序表示,二叉树的存储结构,1 2 3 4 5 6 7 8 9 10,将一般二叉树转换为完全二叉树（添加虚结点），然后按层次编号次序进行顺序表示。,A B C D E F G H I J,结点5： 双亲是结点 2 左孩子是结点 10 没有右孩子,结
10、点E（6）： 双亲是结点C（3） 左孩子是结点 I（12） 没有右孩子（13为空）,完全二叉树,一般二叉树,指向左孩子结点,指向右孩子结点,二叉树的链表表示,三叉树的链表表示,指向双亲结点,typedef struct node /二叉树结点定义 ElemType data; /结点数据域 struct node * lchild, * rchild; /左右孩子指针域 BTNode; BTNode *root; /根指针唯一确定二叉链表,二叉链表结点结构,数据类型,二叉树的遍历,树的遍历就是按某种次序访问树中的所有结点， 要求每个结点访问一次且仅访问一次。 遍历二叉树三方面工作：访问根结点记
11、作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有： 前序 DLR 镜像 DRL 中序 LDR 镜像 RDL 后序 LRD 镜像 RLD,前序 DLR 中序 LDR 后序 LRD,前序遍历二叉树： 若二叉树非空，则 访问根结点 (D) 前序遍历左子树 (L) 前序遍历右子树 (R),void preorder ( BTNode *t ) if ( t != NULL ) visite (t-data); preorder ( t-lchild ); preorder ( t-rchild ); ,前序遍历序列： D L R a,b d e,c f g,中序遍历二叉树：
12、若二叉树非空，则 中序遍历左子树 (L) 访问根结点 (D) 中序遍历右子树 (R),void inorder ( BTNode *t ) if ( t != NULL ) inorder ( t-lchild ); visite (t-data); inorder ( t-rchild ); ,中序遍历序列： L D R a,d b e,c g f,后序遍历二叉树： 若二叉树非空，则 后序遍历左子树 (L) 后序遍历右子树 (R) 访问根结点 (D),后序遍历序列： L R D a,d e b,g f c,void postorder ( BTNode *t ) if ( t != NULL
13、 ) postorder ( t-lchild ); postorder ( t-rchild ); visite (t-data); ,应用二叉树遍历的事例,表达式：a + b * ( c - d ) - e / f,后缀表达式：,a b c d -* + e f / -,二叉树表示表达式 构造原则： *两个操作数分别作为左右子树 *运算符作为根结点,前序遍历序列：- + a * b - c d / e f 中序遍历序列：a + b * c - d - e / f 后序遍历序列：a b c d - * + e f / -,在二叉树中查找指定结点,判断根是否？根是成功,若不是，查找左子树,若左
14、无，查找右子树,？,? find(BTNode *b, elemtype x) if(b=NULL) return(NULL); /*空树*/ if ( b-data=x ) return(b); /*查找成功*/ p=find( b-lchild ,x); /*查找左子树*/ if( p=NULL) p=find( b-rchild ,x); /*查找右子树*/ return( p ); ,int leaf ( BTNode *b ) if ( b = NULL ) return 0; if (?) return 1; nl=leaf( b-lchild ); nr=leaf( b-rchi
15、ld ); return nl+nr; ,统计二叉树叶子结点的个数,空树：n=0,根是叶子：n=1,根是分支：n=nl+nr,？统计二叉树结点的个数 ？统计二叉树分支结点的个数 ？统计二叉树度为2的个数 ？统计二叉树度为1的个数,0,0,0,0,0,0,1,1,1,1,1,0,0,2,3,构造二叉树 由二叉树的前序序列和中序序列 可唯一地确定一棵二叉树。,利用pre 存储二叉树的前序序列 in 存储二叉树的中序序列,构造二叉树立的基本思想： 建立根结点，分别构造左、右子树。,前序序列 ABHFDECKG 中序序列 HBDFAEKCG,ABHFDECKG HBDFAEKCG,右前序 ECKG 中序 EKCG,右前序 ECKG 中序 EKCG,无左,左前序 BHFD 中序 HBDF,左前序 BHFD 中序 HBDF,左,左,右,前序确定根 中序分左右,
