《树与二叉树 》ppt课件

《《树与二叉树 》ppt课件》由会员分享，可在线阅读，更多相关《《树与二叉树 》ppt课件（87页珍藏版）》请在金锄头文库上搜索。

1、,第八章 树与二叉树,1.树的定义及其基本概念,2.二叉树的基本概念和存储结构,3.二叉树的遍历,4.线索二叉树的概念及其遍历,6.哈夫曼树及其构造方法,7.树与森林,5.二叉排序树,8.1 树的概念和基本术语,一、树的定义 树是由 n (n 0) 个结点的有限集合。如果 n = 0，称为空树；如果 n 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱； 当n 1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。,根,子树,特点：树中至少有一个结点根 树中各

2、子树是互不相交的集合,二、树的表示,1树形结构表示法,2. 凹入法表示法,3. 嵌套集合表示法（文氏图表示法）,4.广义表表示法（括号表现法） 对树结构，广义表表示法可表示为： (A(B(E(J，K，L)，F)，C(G)，D(H(M)，I),分支(branch)：结点之间的二元关系（序偶）。 结点(node)：一个数据元素及指向其子树的分支。 结点的度(degree)：结点拥有的子树个数。 叶结点(leaf)：度为零的结点。 分支结点(branch node):有后继的结点称为分支结点。 儿子(sons)：结点x的子树的根。 父亲(parent):结点x的前驱结点称为x的父亲。 兄弟(brot

3、her)：同一父亲的结点的子女结点。 祖先(ancestor)：根到该结点路径上的所有结点。 子孙(descendant)：某结点为根的子树上的任意结点。 堂兄弟(cousin):父亲是兄弟关系或堂兄弟关系的结点。,结点层次(level)：从根开始，根为第一层，根的子女为第二层，以此类推。 树的深度（高度）(depth)：树中结点的最大层次数 树的度：一棵树中最大的结点度数。 结点按层编号（层中编号）：将树中结点按从上层到下层，同层从左到右的次序排成一个线性序列，依次给他们编以连续的自然数。 祖辈（上层）：层号比结点x小的结点，称为x的祖辈。 后辈（下层）：层号比结点x大的结点，称为x的后辈。

4、 有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。 森林(forest)：m(m 0)棵互不相交的树。,三、树的基本术语,1层,2层,4层,3层,height = 4,A,C,G,B,D,E,F,K,L,H,M,I,J,结点 结点的度 叶结点 分支结点,子女 双亲 兄弟,祖先 子孙 结点层次,树的深度 树的度 有序树 无序树 森林,结点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，

5、C，D为兄弟 结点K，L为兄弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,结点F，G为堂兄弟 结点A是结点F，G的祖先,8.2 二叉树 (Binary Tree),定义:,五种形态:,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,特点:,每个结点至多只有两棵子树（二叉树中 不存在度大于2的结点）,二叉树的基本操作,（1）creat_tree(bt,str) 根据二叉树的括号表示法str建立一棵二叉树bt。 （2）disptree(bt) 以凹入法显示一棵二叉树bt。 （3）depth_bttree

6、(bt) 求一棵二叉树bt的深度。 （4）count_bttree(bt) 求一棵二叉树bt的结点个数。 （5）leafcount_bttree(bt) 求一棵二叉树bt的叶子结点个数。 （6）nleafcount_bttree(bt) 求一棵二叉树bt 的非叶子结点个数。,性质1 在二叉树的第 i 层上至多有 2i 1个结点。(i 1) 证明用归纳法 证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，ij1，命题成立，即第j层上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i 2个结点。 由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1

7、层上的最大结点数的2倍，即2* 2i 2= 2 i-1。,二叉树的性质,性质2 深度为 k 的二叉树至多有 2k -1个结点(k 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为,性质3 对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0n21. 证明：若度为1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,定义1 满二叉树 (Full Bin

8、ary Tree) 一棵深度为k且有2k -1个结点的二叉树称为满二叉树。,两种特殊形态的二叉树,非完全二叉树,定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 (0 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。,完全二叉树,性质4 具有 n (n 0) 个结点的完全二叉树的深度为log2(n) 1 证明： 设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有 2h1 - 1 n 2h - 1或 2h1 n 2h 取对数 h1 log2n h，又h是整数， 因此有 h =

9、 log2(n) 1,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1, 2, , n，则有以下关系： 若i = 1, 则 i 无双亲 若i 1, 则 i 的双亲为(i /2) 若2*i n, 则 i 无左孩子,否则其左孩子是结点2i. 若2*i+1n,则结点i无右孩子,否则其右孩子为结点2*i+1,完全二叉树 一般二叉树 的顺序表示 的顺序表示,8.3 二叉树的存储结构,一、顺序表示,二、链表表示,二叉树链表表示的示例,二叉树 二叉链表 三叉链表,typedef struct btnode struct btnode *lchild; int data; st

10、ruct btnode *rchild; bitnode,*bitree;,二叉链表的定义,若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n+1个空链域。 证明：边数e=n-1;即非空链域为n-1个，则空链域为2n-(n-1)=n+1个。,三、二叉链表的递归创建及其基本操作的实现,char s= ,a,b,c,d, , ,e,f,g, , , , ,h,I; root =creat_tree(s,1); bitree creat_tree(char *s,int p) bitree new; if(sp= |p15) return NULL; else new=(bit

11、ree)malloc(sizeof(bitree); new-data=sp; new-lchild=creat_tree(s,2*p); new-rchile=creat_tree(s,2*p+1); return new; ,8.4 二叉树遍历,树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 中序 LVR 后序 LRV,中序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果

12、a + b * c - d - e / f,中序遍历 (Inorder Traversal),void inorder (bitree bt) if (bt!= NULL ) inorder ( bt-lchild ); printf(“ %c”,bt-data); inorder ( bt-rchild ); ,中序遍历二叉树的递归算法,前序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,前序遍历 (Preorder Traversal),前序遍历二叉树的递

13、归算法 void preorder (bitree bt) if (bt!= NULL ) printf(“ %c”,bt-data); preorder ( bt-lchild ); preorder (bt-rchild ); ,后序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / -,后序遍历 (Postorder Traversal),后序遍历二叉树的递归算法： void postorder (bitree bt) if ( bt != NULL ) pos

14、torder ( bt-lchild ); postorder ( bt-rchild ); printf(“ %c”,bt-data); ,非递归实现先序遍历二叉树 利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为： 1、从二叉树根结点开始，先将根结点入栈。 2、然后将栈顶结点出栈，输出结点的值，同时判断该结点有没有右子树，有则将右子树的根结点入栈；再判断有没有左子树，有则将左子树的根结点入栈。如果栈不空则重复第2步，直到栈为空。,void preorder (bitree root) bitree p, stack100; int top=-1; /top为栈顶指针 if(root

15、!=NULL) top+; stacktop=root;/将根结点压入栈内 while(top!=-1) p=stacktop; top-; printf(“%d ”,p-data); if(p-rchild!=NULL) stack+top=p-rchlid; /压右子树 if(p-lchild!=NULL) stack+top=p-lchild; /压左子树 ,非递归实现中序遍历二叉树 同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为： 1、将所指的结点的左子树入栈，其下面的左子树也入栈 2、弹出一个结点并输出，判断其是否有右子树，有则入栈，再转到第1步，没有右子树则判断栈是否为空，不空则弹出一个结点，转回第2步，为空则结束。,void inorder ( bitree root) bitree p=root,stack100; /s为一个栈，top为栈顶指针 int top=-1; do while(p!=NULL) top+; stacktop=p; p=p-lchild; if(top=0) p=stacktop; top-; printf(“%d ”,p-data); p=p-rchild; while(p!=NULL|top=0); ,非递归实现后序遍历二叉树