二叉树.ppt
《二叉树.ppt》由会员分享,可在线阅读,更多相关《二叉树.ppt(56页珍藏版)》请在三一文库上搜索。
1、本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件,第五章 树,本章主要内容,树的基本概念 二叉树 二叉树的存储表示 二叉树的遍历及其应用 二叉树遍历的非递归算法 二叉树的计数 树与二叉树的转换 堆 Huffman树及其应用,2,树的基本概念,树是由n (n0) 个结点组成的有限集合: 有一个特定的称之为根 (root) 的结点; 除根以外的其它结点划分为 m (m0) 个互不相交的有限集合T1, T2, , Tm,其中每个集合也是一棵树,并被称为根的子树。 这个定义是递归的,3,树的基本概念,4,结点 结点的度 叶结点 分支结点,1层,2层,4层,3层,深度 = 4 高度 = 4
2、,A,C,G,B,D,E,F,K,L,H,M,I,J,根,子女结点 父结点 兄弟结点 祖先结点 子孙结点,结点所处层次 树的深度 树的高度 树的度,有序树 无序树 森林,高度 = 3,深度 = 2,树的基本概念,树的其他表示方法,5,目录表示,集合表示,凹入表表示,二叉树,二叉树是结点的有限集合: 该集合或者为空; 或者由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 这个定义也是递归的,6,L,R,R,L,空,只有根,右子树为空,右子树为空,左右子树不为空,二叉树,性质1 若二叉树的层次从 1 开始, 则在二叉树的第 i ( i1)层最多有 2i-1 个结点。 证明:(用
3、数学归纳法) i = 1时,根结点只有1个,21-1 = 20 =1; 若设 i = k 时性质成立,即该层最多有 2k-1 个结点,则当 i = k+1 时,由于第 k 层每个结点最多可有 2 个子女,第 k+1 层最多结点个数可有 2*2k-1 = 2k 个,故性质成立。,7,二叉树,性质2 高度为 h (h1) 的二叉树最多有 2h -1个结点。 证明:(用求等比级数前k项和的公式) 高度为 h 的二叉树有 h 层,各层最多结点个数相加,得到等比级数,求和得: 20 + 21 + 22 + + 2h-1 = 2h-1 空树的高度为 0,只有根结点的树的高度为 1。,8,二叉树,性质3 对
4、任何一棵非空二叉树, 如果其叶结点有 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,9,二叉树,满二叉树 深度为k的满二叉树是有2k-1个结点的二叉树 特点:每一层结点数都达到了最大数 完全二叉树 深度为 k 的完全二叉树中每一个结点的编号都与深度为k的满二叉树中编号一一对应 特点:从第1层到第k-1层是满的,仅最下面第k层或是满
5、的,或是从右到左缺若干结点,10,二叉树,11,满二叉树,完全二叉树,二叉树,性质4 具有n个结点的完全二叉树的深度为log2(n+1) 证明: 设完全二叉树的深度为h,则有 2h-1-1n 2h-1 2h-1n+12h h-1log2(n+1)h h = log2(n+1),12,上面h-1层结点数,包括h层的最大结点数,性质4也适用于理想平衡二叉树,二叉树,性质5 若将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2,3,n,则有: 若i = 1, 则 i 无父结点; 若i 1, 则 i 的父结点为i/2; 若2*i n, 则 i 的左子女为 2*i; 若2*i+1
6、n, 则 i 的右子女为2*i+1; 若 i 为奇数, 且i !=1, 则其左兄弟为i-1; 若 i 为偶数, 且i != n,则其右兄弟为i+1。 i所在层次为log2(i+1)(或者log2i +1,两者等效),13,二叉树的存储表示,二叉树的数组存储表示,14,完全二叉树的顺序表示,一般二叉树的顺序表示,二叉树的存储表示,二叉树的数组存储表示 完全二叉树适用于数组存储表示 一般二叉树不适用,15,单支树的顺序表示,二叉树的存储表示,二叉树的链表存储表示,16,leftChild,data,rightChild,data,左孩子指针,右孩子指针,leftChild,rightChild,l
7、eftChild,data,rightChild,data,左孩子指针,右孩子指针,leftChild,rightChild,parent,parent,二叉链表,三叉链表,找子女时间O(1), 找父亲要从根开始,时间O(log2i),找子女时间O(1), 找父亲时间O(1),Struct TNode Type Data; TNode *leftChild; TNode *rightChild; TNode *parent; ;,二叉树的存储表示,二叉树的链表存储表示,17,root,root,root,二叉树,二叉链表,三叉链表,二叉树的存储表示,二叉树的链表存储表示,18,root,二叉树
8、,静态链表结构,二叉树的遍历及其应用,二叉树的遍历就是按某种次序访问树中的结点一次且仅一次 访问当前结点记为V 访问结点的左子树记为L 访问结点的右子树记为R 遍历次序一般有 前序遍历 (VLR) 中序遍历 (LVR) 后序遍历 (LRV),19,二叉树的遍历及其应用,前序遍历 (VLR) 首先访问当前结点 (V) 其次前序遍历左子树 (L) 最后前序遍历右子树 (R),20,-,-,/,+,a,b,c,d,e,f,void PreOrder ( BinTreeNode *T ) if ( T != NULL ) visit( T-data ); PreOrder ( T-leftChild
9、); PreOrder ( T-rightChild ); ,前序遍历: + a b c d / e f,二叉树的遍历及其应用,中序遍历 (LVR) 首先中序遍历左子树 (L) 其次访问当前结点 (V) 最后中序遍历右子树 (R),21,void InOrder ( BinTreeNode *T ) if ( T != NULL ) InOrder ( T-leftChild ); visit( T-data ); InOrder ( T-rightChild ); ,-,-,/,+,a,b,c,d,e,f,中序遍历: a + b c d e / f,二叉树的遍历及其应用,后序遍历 (LRV)
10、 首先后序遍历左子树 (L) 其次后序遍历右子树 (R) 最后访问当前结点 (V),22,void PostOrder ( BinTreeNode *T ) if ( T != NULL ) PostOrder ( T-leftChild ); PostOrder ( T-rightChild ); visit( 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
11、 / ,23,-,a,e,f,+,/,b,-,c,d,二叉树的遍历及其应用,计算二叉树的结点个数 (后序遍历) 对左子树递归计数a 对右子树递归计数b 返回1+a+b,24,int Count ( BinTreeNode *T ) if ( T = NULL ) return 0; else int a = Count ( T-leftChild ); int b = Count ( T-rightChild ); return 1+a+b; ,二叉树的遍历及其应用,计算二叉树的深度 (后序遍历) 计算左子树的深度a 计算右子树的深度b 返回(ab)?a+1:b+1,25,int Height
12、 ( BinTreeNode *T ) if ( T = NULL ) return 0; else int a = Height ( T-leftChild ); int b = Height ( T-rightChild ); return (ab)?a+1:b+1; ,二叉树的遍历及其应用,二叉树的复制 (前序遍历) 复制根结点数据 复制左子树 复制右子树 返回根结点指针,26,BinTreeNode * Copy( BinTreeNode *T ) if ( T = NULL ) return NULL; else BinTreeNode * temp = new BinTreeNod
13、e; temp-data = T-data; Temp-leftChild = Copy ( T-leftChild ); Temp-rightChild = Copy( T-rightChild ); return temp; ,二叉树的遍历及其应用,判断两棵二叉树是否相等 (前序遍历) 判断两棵树数据是否相等 判断两棵树左子树是否相等 判断两棵右子树是否相等,27,bool BinTreeNode * equal ( BinTreeNode *a, BinTreeNode *b ) if ( a = NULL ,二叉树的遍历及其应用,前序遍历建立二叉树 结点值为正整数,每个结点有2个或0个
14、孩子结点 输入结点值的顺序对应二叉树前序遍历顺序 0表示叶子结点,28,void CreatBinTree ( BinTreeNode *T ) scanf (“%d”, ,1,2,3,7,0,0,0,0,0,0,0,前序遍历对应的整数序列:1 2 3 0 0 4 5 0 7 0 0 6 0 0 0,0,二叉树的遍历及其应用,前序遍历输出二叉树 以凹入表表示输出,29,void PrintBinTree ( int depth, BinTreeNode *T ) if (T != NULL) for (int i=1; idata); for (int i=6; idepth; i-) pri
15、ntf(“*”);/输出(6-depth)*4个星号 PrintBinTree( depth+1, T-leftChild ); PrintBinTree( depth+1, T-rightChild ); ,1 * 2 * 4 * 5 * 3 * 6 * 7 *,凹入表表示:,二叉树遍历的非递归算法,利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v,对v进行操作 v的右孩子入栈,v的左孩子入栈,1,1出栈,其右左孩子3和2入栈,1入栈,二叉树遍历的非递归算法,利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v,对v进行操作 v的右孩子入栈,v的左孩子入栈,3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉
链接地址:https://www.31doc.com/p-4229964.html