赵海燕 zhhy@sei.pku.edu.cn 软件研究所 14 Apr. 2005 第5章 树与二叉树 之三 赵海燕 zhhy@sei.pku.edu.cn 软件研究所 14 Apr. 2005

2005 Spring Data Structures by Haiyan Zhao 二叉树（binary tree） 由结点的有限集合构成: 或者为空集 或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树(它们也是结点的集合)组成 递归的定义。二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空。也即它的每一个结点至多有两棵子树，并且子树有左右之分，不能随意颠倒 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的基本形态  （2）只有一个根结点 （1）空二叉树 左子树 右子树 左子树 右子树 （3）有根结点 和左子树 （4）有根结点 和右子树 （5）有根结点左、右子树 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树 vs 树 二叉树不是树的特殊情形，它们是两种数据结构 树和二叉树之间最主要的差别： 二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 (3)和（4）是两棵不同的二叉树，但作为树，它们是相同的 在二叉树中可定义类似树中的概念 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

满二叉树（Full Binary Tree） 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

完全二叉树（Complete Binary Tree） 若一棵二叉树 最多只有最下面的两层结点度数可以小于2 最下面一层的结点都集中在该层最左边的若干位置上 则称此二叉树为完全二叉树 在许多算法和算法分析中都明显地或隐含地用到完全二叉树的概念 完全二叉树一定是满二叉树? 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

扩充二叉树（Extended Binary Tree） 当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶 对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶 对于原来二叉树的树叶，在它下面增加两个空树叶 扩充的二叉树是满二叉树，新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 扩充二叉树 外部路径长度E 从扩充的二叉树的根到每个外部结点的路径长度之和 内部路径长度I 扩充的二叉树里从根到每个内部结点的路径长度之和 E和I两个量之间的关系为 E=I+2n n 是内部结点的个数 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 性质1. 在非空二叉树的第i层上至多有2i个结点（i0） 证明：采用归纳法 i=0, 结点数=1=20 . 假设对于j(0j i), 结点数至多有2j . 对于i=j+1,结点数至多为 2* 2j=2j+1 . 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 性质2. 深度为 k 的二叉树至多有2k+1-1个结点 （k  0） 证明：假设第i层上的最大结点个数为mi，由性质1可知，深度为k的二叉树中最大的结点个数为 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 示例 1 2 3 7 6 12 15 14 13 5 4 8 11 10 9 1 2 3 4 结点最少的二叉树： 1+1+1+1 结点最多的二叉树： 20+21+22+23 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 性质3. 对任何一棵非空二叉树T，如果叶结点 数为n0,度为2的结点数为n2,则n0=n2+1 证明： n0+n1+n2 = 所有结点的度数和+1 = n1+ 2*n2 +1 由此可得： n0=n2+1 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 性质4. 具有n个结点的完全二叉树的深度k为 log2n . 证明： n = 20 + 21 + 22 + … + 2k-1 + mk = 2k – 1 + mk 2k-1  n  2k+1-1 2k  n  2k+1 k  log2n  k+1  k = log2n 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 完全二叉树示例 1 2 3 7 6 12 5 4 8 11 10 9 完全二叉树层次序列反映出它的结构 1 2 3 4 5 6 7 8 9 10 11 12 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 性质5. 如果对一棵有n个结点的完全二叉树按层次次序从1开始编号，则对任一结点i （1  in)，有： 1）i=1，序号结点i是根；i>1, 其双亲结点是  i/2  2）2i  n，序号为i的结点的左子女结点的序号为2i；2i>n ,序号为i的结点无左子女 3）2i+1  n，序号为i的结点的右子女结点的序号为2i+1; 2i+1 > n,序号为i的结点无右子女 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 证明: 对于（2）和（3）当i=1时,若2i = 2  n，左子女结点的序号为2。2i+1 = 3  n，右子女结点的序号为3。 假设对于序号为j的结点，命题成立。 对于i=j+1， 其左子女结点的序号等于j的右子女结点的序号加1，即2j+1+1=2(j+1) 其右子女结点的序号等于：2(j+1)+1。 根据（2）和（3），可知i的父结点的序号为i/2. 结论：完全二叉树的层次序列，反映了它的结构。 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 性质5的示例 1 2 3 j j+1 2j 2j+1 2(j+1) 2(j+1)+1 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 性质6. 在扩充的二叉树中，新增加的外部结点个数比原来的内部结点个数多1。 证明：n 个结点的二叉树扩充后 边数 = 2n; 结点数 = 2n+1 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1。 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 性质7. 对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足 E = I + 2n的关系， 其中n为内部结点个数。 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 示例 a b c d e f 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的性质 证明：当n=1时，I=0, E=2, 此等式成立。 设有n个内部结点的扩充二叉树，下式成立。 En = In+2n (1) 对于 n+1 个内部结点的扩充二叉树，去掉一个原来为树叶、路径长度为K的内部结点，内部路径长度变为： In = In+1-K (2) 外部路径长度变为： En = En+1-2(K+1)+K = En+1 -K-2 即： En+1= En+K+2 En+1 = (In+2n) +K+2 = (In+1-K) +2n+K+2 代入（1） 代入（2） = In+1+2(n+1) 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的基本运算 二叉树的类型：BTree；二叉树中结点的类型：BNode。除了树上的一般运算之外， 1. BNode leftchild(BNode p) 求二叉树中某个指定结点的左子女结点，当指定结点没有左子女时，返回一特殊值NULL； 2. BNode rightchild(BNode p) 求二叉树中某个指定结点的右子女结点，当指定结点没有右子女时，返回一特殊值NULL； 3. 二叉树的周游 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 周游二叉树 周游 系统地访问数据结构中的每个结点。每个结点都正好被访问且仅被访问到一次。 周游一棵二叉树的过程实际上就是把二叉树的结点放入一个线性序列的过程，或者说是把二叉树进行线性化 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 周游二叉树的方法 深度优先周游二叉树（depth-first traversal） 广度优先周游二叉树（breadth-first traversal） 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先周游二叉树 D L R 通过变换根结点的周游顺序，可以得到以下三种方案： 前序周游(DLR次序)： 访问根结点；前序周游左子树；前序周游右子树。 中序周游(LDR次序)，也称对称序周游： 中序周游左子树；访问根结点；中序周游右子树。 后序周游(LRD次序)： 后序周游左子树；后序周游右子树；访问根结点。 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先周游二叉树 深度周游如下二叉树 前序周游：ABDCEGFHI 中序周游：DBAEGCHFI 后序周游：DBGEHIFCA 某种序列下的前驱/后继 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 表达式的二叉树表示 对右图进行前序、后序和中序次序周游可分别得到如下的结点序列： 前序序列：-ab+cd 前缀表示(波兰表示法) 后序序列：ab-cd+  后缀表示(逆波兰表示法) 对称序列：a-b  c+d 中缀表示  - + a b c d 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树的周游算法 按实现方式分为： 递归算法 void visit(BNode p); /*p是被周游的二叉树的结点*/ 非递归算法 算法中维持一个栈 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先递归实现：前序次序 访问根； visit(p); 按前序次序周游根的左子树； preOrder(leftchild(p)); 按前序次序周游根的右子树; preOrder(rightchild(p)); void preOrder(BNode p) { if (p= =NULL) return; visit(p); preOrder(leftchild(p)); preOrder(rightchild(p)); } 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先递归实现：对称序 按对称序周游根的左子树；inOrder(leftchild(p)); 访问根； visit(p); 按对称序周游根的右子树；inOrder(rightchild(p)); void inOrder(BNode p) { if (p= =NULL) return; inOrder(leftchild(p)); visit(p); inOrder(rightchild(p)); } 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先递归实现：后序次序 按后序次序周游根的左子树；postOrder(leftchild(p)); 按后序次序周游根的右子树；postOrder(rightchild(p)); 访问根； visit(p); void postOrder(BNode p) { if (p= =NULL) return; postOrder(leftchild(p)); postOrder(rightchild(p)); visit(p); } 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先非递归实现：前序次序 用自定义的栈来代替系统的栈 void preOrder(BNode p) { do { while (p != NULL) { visit(p); push(st,p); p = leftchild(p); } while ((p == NULL) && (!isEmptyStack(st))) { p = top(st); pop(st); p = rightchild(p); } while (p!=NULL || !isEmptyStack(st)); 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先非递归实现：中序次序 void inOrder(BNode p) { do { while (p!=NULL) { push(st, p); p=leftchild(p); } while (p == NULL && (!isEmptyStack(st))) { p = top(st); pop(st); visit(p); p=rightchild(p); } while(p!=NULL || !isEmptyStack(st)) 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先非递归实现：后序次序 每个结点要到其左、右子树都周游完时才得访问，所以在周游其左、右子树之前都需进栈。当该结点出栈时，需要判断是 从左子树回来（第一次：刚周游完左子树，此时需要周游右子树） 从右子树回来（第二次：刚周游完右子树，此时需要访问该结点） 因此，进栈的结点需要伴随着一个标记tag。 1 周游左子树(第一次出栈） 2 周游右子树(第二次出栈） tag = 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 深度优先非递归实现：后序次序 D D.tag =1; D进栈； 后序周游L; continueflag = t ; D出栈； L R D.tag=2; D进栈； continueflag= f ; /*下一步要访问右子树R，不能退栈*/ p=rightchild(p); 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 栈中元素的类型 typedef struct { BNode ptr; /*进栈结点*/ int tag; /*标记*/ } Elem; struct Stack { Elem s[MAXNUM]; int t; }; typedef struct Stack *PStack; /*栈的指针类型*/ 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 算法5.13 使用栈的后序次序周游算法 void nPostOrder1(BTree t) { Stack st; Elem stnode; BNode p; /*当前要处理的结点*/ char continueflag; /*标记，是否继续退栈*/ if (t==NULL) return; st = createEmptyStack( ); p = root(t); /*从根结点开始*/ do { while (p!=NULL) { stnode.ptr=p; stnode.tag=1; push(st, stnode); p =leftchild(p); } continueflag= t ; while ((continueflag==t)&&(! isEmptyStack(st))) { stnode=top(st); pop(st); p=stnode.ptr; if (stnode.tag ==1) { stnode.tag = 2; push(st,stnode); continueflag =f ; p=rightchild(p); else visit(p); } while(!isEmptyStack(st)); 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 算法5.14 使用栈的后序次序周游 把后序次序的逆序列(DRL)压入栈中，然后按出栈的顺序访问结点 void postOrder2(BTree t) { Stack st; BNode p; if (t==NULL) return; st = createEmptyStack(); p = root(t); stackchild(st, p); // 把后序次序的逆序列推入栈 while (!isEmptyStack(st)) { visit(top(st)); pop(st); } 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 算法5.14 使用栈的后序次序周游 void stackchild(Stack st, BNode p) { if (p==NULL) return; push(st, p); if (rightchild(p) != NULL) stackchild(st, rightchild(p)); if (leftchild(p) != NULL) stackchild(st, leftchild(p)); } D L R 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 非递归方式周游二叉树 优点：减少了递归调用的开销 缺点：程序员需要决定栈的大小 （太小容易发生栈溢出，太大浪费） 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

广度优先周游二叉树 （breadth-first） 从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问 例如：ABCDEFGHI 适用于完全二叉树等 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 树/树林与二叉树的转换 在树或树林与二叉树之间有一个自然的一一对应的关系 任何树林都唯一地对应到一棵二叉树；反过来，任何二叉树也都唯一地对应到一个树林 二叉树 树、树林 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 树、树林转换为二叉树 执行步骤： （1）在所有相邻的兄弟结点之间连一条线； （2）对每个非终端结点，只保留它到其最左子女的连线，删去它与其它子女的连线； （3）以根结点为轴心，将整棵树进行旋转。 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 树（林）转换成二叉树示例 A B C K D E F G H J A B C K D E F G H J 树林转换为二叉树 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树转换为树、树林 执行步骤： （1）若某结点是其父母的左子女，则把该结点的右子女，右子女的右子女，…… ，都与该结点的父母用线连接起来； （2）去掉原二叉树中所有父母到右子女的连线； （3）整理（1）、（2）两步所得到的树或树林，使之结构层次分明。 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树转换为树林示例 A B D C E K H F J G 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 树林与二叉树的等价转换 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 树林到二叉树的等价转换 把森林F看作树的有序集合，F=(T1,T2,…,Tn)，对应于F的二叉树B(F)的定义是： 若n=0，则B(F)为空 若n>0，则B(F)的根是T1的根W1，B(F)的左子树是B(T11，T12，…，T1m)，其中T11，T12，…，T1m是W1的子树；B(F)的右子树是B(T2，…，Tn) 此定义精确地确定了从树林到二叉树的转换 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao 二叉树到树林的等价转换 设B是一棵二叉树，rt是B的根，L是rt的左子树，R是rt的右子树，则对应于B的树林 F(B)的定义是： 若B为空，则F(B)是空的树林 若B不为空，则F(B)是一棵树T1加上树林F(R)，其中树T1的根为rt，rt的子树为F(L) 2005-4-14 2005 Spring Data Structures by Haiyan Zhao

2005 Spring Data Structures by Haiyan Zhao Homework 书面作业： 4月14日布置，4月24日子夜前提交 教材p.155-156上的12、13题 上机题 4月14日布置，4月28日子夜前提交 教材p.156上的上机题的1、3 2005-4-14 2005 Spring Data Structures by Haiyan Zhao