二叉树.ppt

本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件,第五章 树,本章主要内容,树的基本概念 二叉树 二叉树的存储表示 二叉树的遍历及其应用 二叉树遍历的非递归算法 二叉树的计数 树与二叉树的转换 堆 Huffman树及其应用,2,树的基本概念,树是由n (n0) 个结点组成的有限集合： 有一个特定的称之为根 (root) 的结点； 除根以外的其它结点划分为 m (m0) 个互不相交的有限集合T1, T2, , Tm，其中每个集合也是一棵树，并被称为根的子树。 这个定义是递归的,3,树的基本概念,4,结点 结点的度 叶结点 分支结点,1层,2层,4层,3层,深度 = 4 高度 = 4,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 个结点。 证明：(用数学归纳法) 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 对任何一棵非空二叉树, 如果其叶结点有 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层或是满的，或是从右到左缺若干结点,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 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,leftChild,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,二叉树,静态链表结构,二叉树的遍历及其应用,二叉树的遍历就是按某种次序访问树中的结点一次且仅一次 访问当前结点记为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 ); 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) 首先后序遍历左子树 (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 / ,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 ( 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 BinTreeNode; 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个孩子结点 输入结点值的顺序对应二叉树前序遍历顺序 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-) printf(“*”);/输出(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,2,1出栈，其右左孩子3和2入栈,1入栈,2出栈，其右左孩子5和4入栈,二叉树遍历的非递归算法,利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈,3,5,4,1出栈，其右左孩子3和2入栈,1入栈,2出栈，其右左孩子5和4入栈,4出栈，其无孩子,5出栈，其无孩子,3出栈，其右左孩子7和6入栈,二叉树遍历的非递归算法,利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈,7,6,1出栈，其右左孩子3和2入栈,1入栈,2出栈，其右左孩子5和4入栈,4出栈，其无孩子,5出栈，其无孩子,3出栈，其右左孩子7和6入栈,6出栈，其无孩子,7出栈，其无孩子,出栈顺序，即遍历顺序为：1 2 4 5 3 6 7,二叉树遍历的非递归算法,利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈,4出栈，其无右孩子,1入栈，1的左孩子2入栈，2的左孩子4入栈,1,2,4,2出栈，其右孩子5入栈,二叉树遍历的非递归算法,利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈,4出栈，其无右孩子,1入栈，1的左孩子2入栈，2的左孩子4入栈,1,5,2出栈，其右孩子5入栈,5出栈，其无右孩子,1出栈，1的右孩子3入栈，3的左孩子6入栈,二叉树遍历的非递归算法,利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈,4出栈，其无右孩子,1入栈，1的左孩子2入栈，2的左孩子4入栈,3,6,2出栈，其右孩子5入栈,5出栈，其无右孩子,1出栈，1的右孩子3入栈，3的左孩子6入栈,6出栈，其无右孩子,3出栈，其右孩子7入栈,二叉树遍历的非递归算法,利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈,4出栈，其无右孩子,1入栈，1的左孩子2入栈，2的左孩子4入栈,7,2出栈，其右孩子5入栈,5出栈，其无右孩子,1出栈，1的右孩子3入栈，3的左孩子6入栈,6出栈，其无右孩子,3出栈，其右孩子7入栈,7出栈，其无右孩子,出栈顺序，即遍历顺序为：4 2 5 1 6 3 7,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, L,2, L,4, L,栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, L,2, L,4, R,4无右子树，4R出栈,栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历,2访完左子树，访2右子树，栈顶改为2R，5L入栈,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, L,2, R,4无右子树，4R出栈,栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历,2访完左子树，访2右子树，栈顶改为2R，5L入栈,5, L,5无左子树，访5右子树，栈顶改为5R,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, L,2, R,4无右子树，4R出栈,栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历,2访完左子树，访2右子树，栈顶改为2R，5L入栈,5, R,5无左子树，访5右子树，栈顶改为5R,5无右子树，5R出栈,2访完右子树，2R出栈,1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, R,3, L,4无右子树，4R出栈,栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历,2访完左子树，访2右子树，栈顶改为2R，5L入栈,6, L,5无左子树，访5右子树，栈顶改为5R,5无右子树，5R出栈,2访完右子树，2R出栈,1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈,6无左子树，访6右子树，栈顶改为6R,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, R,3, L,4无右子树，4R出栈,2访完左子树，访2右子树，栈顶改为2R，5L入栈,6, R,5无左子树，访5右子树，栈顶改为5R,5无右子树，5R出栈,2访完右子树，2R出栈,1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈,6无左子树，访6右子树，栈顶改为6R,6无右子树，6R出栈,3访完左子树，访3右子树，栈顶改为3R，7L入栈；,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, R,3, R,4无右子树，4R出栈,2访完左子树，访2右子树，栈顶改为2R，5L入栈,7, L,5无左子树，访5右子树，栈顶改为5R,5无右子树，5R出栈,2访完右子树，2R出栈,1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈,6无左子树，访6右子树，栈顶改为6R,6无右子树，6R出栈,3访完左子树，访3右子树，栈顶改为3R，7L入栈；,7无左子树，访7右子树，栈顶改为7R,二叉树遍历的非递归算法,利用栈的后序遍历非递归算法 每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据,4无左子树，访4右子树，栈顶改为4R,访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈,1, R,3, R,4无右子树，4R出栈,2访完左子树，访2右子树，栈顶改为2R，5L入栈,7, R,5无左子树，访5右子树，栈顶改为5R,5无右子树，5R出栈,2访完右子树，2R出栈,1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈,6无左子树，访6右子树，栈顶改为6R,6无右子树，6R出栈,3访完左子树，访3右子树，栈顶改为3R，7L入栈；,7无左子树，访7右子树，栈顶改为7R,7无右子树，7R出栈,3访完右子树，3R出栈,1访完右子树，1R出栈,出栈顺序，即遍历顺序为：4 5 2 6 7 3 1,二叉树遍历的非递归算法,利用队列的层次序遍历 根入队列 若队列不空，出队列v，v的左右孩子入队列,1出队列，其左右孩子2和3入队列,1入队列,2出队列，其左右孩子4和5入队列,1,2,3,4,5,6,7,3出队列，其左右孩子6和7入队列,4出队列，其无孩子,5出队列，其无孩子,6出队列，其无孩子,7出队列，其无孩子,出队列顺序，即按层次遍历顺序为：1 2 3 4 5 6 7,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树,47,前序序列：A B H F D E C K G,中序序列：H B D F A E K C G,扫描A,扫描B,扫描H,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树,48,前序序列：A B H F D E C K G,中序序列：H B D F A E K C G,扫描F,扫描E,扫描D,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树,49,前序序列：A B H F D E C K G,中序序列：H B D F A E K C G,扫描C,扫描G,扫描K,二叉树的计数,由二叉树的后序序列和中序序列可唯一地确定一棵二叉树?,50,后序序列：H D F B K G C E A,中序序列：H B D F A E K C G,作业：画出这棵二叉树,二叉树的计数,前序序列固定不变，给出不同中序序列，可得不同二叉树 共可构造多少种不同的二叉树？,51,6,1,2,3,4,5,7,8,9,6,1,2,3,7,5,8,4,9,前序序列：1 2 3 4 5 6 7 8 9,二叉树的计数,例如，前序序列 1, 2, 3，可构造5种不同的二叉树，其中序序列分别为123，132，213，231，321,52,二叉树的计数,bn表示有n个结点的不同二叉树棵数,53,bn等于Catalan函数：,例如：,树与二叉树的转换,将一般树化为二叉树就是用树的子女-兄弟表示来存储树的结构 森林与二叉树的转换可以借助树的二叉树表示来实现。,54,树与二叉树的转换,森林F转换二叉树B 若F为空，则B也为空 若F不空，则 二叉树B的根是F中第一棵树T1的根； B的左子树为B(T11, T12, , T1m )，其中，T11,T12,T1m是T1的根的子树； B的右子树为B(T2, T3, , Tn )，其中，T2,T3,Tn是除T1外其它树构成的森林。 树T转换成二叉树B 若T为空，则B也为空 若T不为空，则B的根是T的根；B的左子树是由T的根的子树构成的森林转换而来,55,树与二叉树的转换,56,T1,T2,T3,T1,T2,T3,