Chapter8 Binary and Other Trees 二叉树(Binary Trees) 二叉树的特性(Properties of Binary Trees) 二叉树描述(Representation of Binary Trees) 二叉树常用操作(Common Binary Tree Operations) 二叉树遍历(Binary Tree Traversal) 11/17/2018

本章重点 树的概念，相关概念 二叉树描述及实现 二叉树特性 二叉树遍历 11/17/2018

祖先-后代 11/17/2018

上级-下属 11/17/2018

整体-部分 11/17/2018

8.1树的定义 定义 树t是一个非空的有限元素的集合，其中一个元素为根（root），余下的元素（如果有的话）组成t 的子树（subtree）。 递归定义。 11/17/2018

例如: A( ) B(E, F(K, L)), C(G), D(H, I, J(M)) T1 T2 T3 树根 A C D B E F G 11/17/2018

树的表示 在画一棵树时，每个元素都代表一个节点。树根在上面，其子树画在下面。 在树根与其子树的根（如果有子树）之间有一条边。同样的，每一棵子树也是根在上，其子树在下。 在一棵树中，边连结一个元素及其子节点。 11/17/2018

树的相关概念 节点 叶子节点 子节点 父节点 级 元素的度 树的度 树的深度 11/17/2018

节点(node) 节点的度(degree) 分支(branch)节点 叶(leaf)节点 子女(child)节点 双亲(parent)节点 兄弟(sibling)节点 祖先(ancestor)节点 子孙(descendant)节点 节点所处层次(level) 树的高度(depth) 树的度(degree) 有序树 无序树 森林 11/17/2018

概念定义 指定树根的级为1，其孩子（如果有）的级为2，孩子的孩子为3，等等。 元素的度是指其孩子的个数。叶节点的度为0。 树的度是其元素度的最大值。 11/17/2018

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 线性结构 树型结构 根结点 (无前驱) 第一个数据元素 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继) 11/17/2018

8.2二叉树 定义 二叉树t 是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。 11/17/2018

二叉树的基本形态 空 仅有根节点 仅有左子树 仅有右子树 左右子树 11/17/2018

二叉树的基本形态 11/17/2018

二叉树和树的区别 二叉树可以为空，但树不能为空。 二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树中每个元素可有若干子树。 在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而树的子树间是无序的。 11/17/2018

树和二叉树 T T T1 T2 T3 T2 T1 T3 树 T T 二叉树 T ○ T TL TR TL TR 11/17/2018

问题 二叉树等价于度为2的树？ 11/17/2018

满二叉树 当高度为h 的二叉树恰好有2h - 1个元素时，称其为满二叉树。 在树深度不变的情况下，具有最大可能节点数的二叉树。所有叶节点都在最底层，除叶节点外，每个节点的度均为2。 11/17/2018

满二叉树 11/17/2018

完全二叉树 深度为k具有n个节点的二叉树是一颗完全二叉树，当且仅当它与k层满二叉树前1 ~ n个节点所构成的二叉树结构相同。 k层完全二叉树:1)前k-1层为满二叉树； 2)第k层上的节点都连续排列于第k层的左端。 11/17/2018

完全二叉树 11/17/2018

1 1 1 2 3 2 3 2 3 4 4 7 5 6 5 7 6 (a)完全二叉树 ( c)非完全二叉树 (b)非完全二叉树 11/17/2018

8.3二叉树的特性 包含n (n> 0 )个元素的二叉树边数为n-1。 若二叉树的高度为h，h≥0，则该二叉树最少有h个元素，最多有2h - 1个元素。 包含n 个元素的二叉树的高度最大为n，最小为「log2(n+ 1 ) 。 11/17/2018

证明： 设完全二叉树的高度为h，则有 2h - 1 < n  2h+1 - 1 2h < n +1  2h+1 取对数 h < log2(n+1)  h+1 11/17/2018

二叉树的特性 4.设完全二叉树中一元素的序号为i, 1≤i≤n。则有以下关系成立： 1) 当i = 1时，该元素为二叉树的根。若i > 1，则该元素父节点的编号为i / 2。 2) 当2i >n时，该元素无左孩子。否则，其左孩子的编号为2i。 3) 若2i + 1 >n，该元素无右孩子。否则，其右孩子编号为2i + 1。 11/17/2018

二叉树的特性 5.度为0的结点数＝度为2的节点数 + 1 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1 + 2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 11/17/2018

思考 一棵树，有n1个度为1的节点，n2个度为2 的节点，……，nm个度为m的节点。有多少个叶节点？ 叶节点=1+n2+2n3+…+(m-1)nm 11/17/2018

思考 总分支数 e = n-1 = n0 + n1 + n2 + … + nm - 1 = m*nm + (m-1)*nm-1 + … + 2*n2 + n1 则有 11/17/2018

节点编号为i的节点，其第1个子节点若存在，编号为多少？ (i-1)*k +2 i若>1,他的父节点编号为 (i+k-2)/k 」 N= ki-1/k-1 节点编号为i的节点，其第1个子节点若存在，编号为多少？ (i-1)*k +2 i若>1,他的父节点编号为 (i+k-2)/k 」 11/17/2018

8.4二叉树描述 二叉树可以作为缺少了部分元素的完全二叉树 11/17/2018

二叉树公式化描述 11/17/2018

一个有n 个元素的二叉树可能最多需要2n-1个空间来存储。 当每个节点都是其他节点的右孩子时，存储空间达到最大。 二叉树描述 一个有n 个元素的二叉树可能最多需要2n-1个空间来存储。 当每个节点都是其他节点的右孩子时，存储空间达到最大。 11/17/2018

右斜二叉树 11/17/2018

二叉树链表描述 二叉树最常用的描述方法是用链表或指针。每个元素都用一个有两个指针域的节点表示，这两个域为L e f t C h i l d和R i g h t C h i d。除此两个指针域外，每个节点还有一个d a t a域。 11/17/2018

结点结构: root lchild data rchild A D E B C F  11/17/2018

链表描述的二叉树节点类 11/17/2018

三叉表示 11/17/2018

二叉树链表表示的示例 11/17/2018

二叉树的模拟指针表示 11/17/2018

8.6二叉树遍历 • 前序遍历 • 中序遍历 • 后序遍历 • 逐层遍历 11/17/2018

先左后右的遍历算法 先（根）序的遍历算法 根 根 根 根 根 根 中（根）序的遍历算法 后（根）序的遍历算法 左 子树 右 子树 11/17/2018

先（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 11/17/2018

中（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 11/17/2018

例如： 先序序列： A B C D E F G H K A B C D E F G H K 中序序列： B D C A E H G K F 后序序列： D C B H K G F E A 11/17/2018

后（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 11/17/2018

中序遍历结果 a + b * c - d - e / f 11/17/2018

中序遍历二叉树的递归过程图解 11/17/2018

各种遍历的结果 A B C D E F G 11/17/2018

前序：ABDEGCF 中序：DBGEAFC 后序：DGEBFCA 逐层：ABCDEFG 11/17/2018

由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： 11/17/2018

如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。 问题是有 n 个数据值，可能构造多少种不同的二叉树？我们可以固定前序排列，选择所有可能的中序排列。 11/17/2018

例如，有 3 个数据 { 1, 2, 3 }，可得5种不同的二叉树。它们的前序排列均为 123，中序序列可能是 123，132，213，231，321。 11/17/2018

有0个, 1个, 2个, 3个结点的不同二叉树如下 11/17/2018

结论 若二叉树中各节点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 11/17/2018

11/17/2018

11/17/2018

11/17/2018

11/17/2018

11/17/2018

公式化描述的遍历 template <class T> void InOrder(T a[], int last, int i) {// Inorder traversal of binary tree with root a[i]. if (i <= last && a[i]) { InOrder(a, last, 2*i); // do left subtree Visit(a, i); // visit tree root InOrder(a, last, 2*i+1); // do right subtree } 11/17/2018

template <class T> void LevelOrder(T a[], int last) { // Level-order traversal of a binary tree. LinkedQueue<int> Q; if (!last) return; // empty tree int i = 1; // start at root while (true) { Visit(a, i); // put children on queue if (2*i <= last && a[2*i]) Q.Add(2*i); // add left child if (2*i+1 <= last && a[2*i+1]) Q.Add(2*i+1); // add right child // get next node to visit try {Q.Delete(i); } catch (OutOfBounds) {return;} } 11/17/2018

作业 设t是数据域类型为int 的二叉树，每个节点的数据都不相同。根据数据域的前序和中序排列构造二叉树。指出函数的时间复杂性。 11/17/2018

8.5二叉树常用操作 • 确定其高度。 • 确定其元素数目。 • 复制。 • 在屏幕或纸上显示二叉树。 • 确定两棵二叉树是否一样。 • 删除整棵树。 11/17/2018

求二叉树的高度 算法基本思想: 首先分析二叉树的高度和它的左、右子树高度之间的关系。 从二叉树深度的定义可知，二叉树的高度应为其左、右子树高度的最大值加1。由此，需先分别求得左、右子树的高度，算法中“访问结点”的操作为:求得左、右子树高度的最大值，然后加1。 11/17/2018

求二叉树的高度 int Depth (BiTree T ){ // 返回二叉树的高度 if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } return depthval; 11/17/2018

统计二叉树中叶子节点个数 算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点” 的操作改为:若是叶子，则计数器增1。 11/17/2018

统计叶子节点个数 int CountLeaf (BiTree T){ //返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; if (!T->lchild && !T->rchild) return 1; else{ m = CountLeaf( T->lchild); n = CountLeaf( T->rchild); return (m+n); } //else } // CountLeaf 11/17/2018

统计所有结点 int Count (BiTree T){ //返回指针T所指二叉树中所有结点个数 if (!T ) return 0; if (!T->lchild && !T->rchild) return 1; else{ m = Count ( T->lchild); n = Count ( T->rchild); return (m+n+1); } //else } // CountLeaf 11/17/2018

复制二叉树 其基本操作为:生成一个结点。 NEWT T 根元素 根元素 右子树 左子树 右子树 左子树 左子树 右子树 11/17/2018

(其数据域为item,左指针域为lptr,右指针域为rptr) 生成一个二叉树的结点 (其数据域为item,左指针域为lptr,右指针域为rptr) BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ if (!(T = new BiTNode)) exit(1); T-> data = item; T-> lchild = lptr; T-> rchild = rptr; return T; } 11/17/2018

BiTNode *CopyTree(BiTNode *T) { if (!T ) return NULL; if (T->lchild ) newlptr = CopyTree(T->lchild); //复制左子树 else newlptr = NULL; if (T->rchild ) newrptr = CopyTree(T->rchild); //复制右子树 else newrptr = NULL; newT = GetTreeNode(T->data, newlptr, newrptr); return newT; } // CopyTree 11/17/2018

例如:下列二叉树的复制过程如下: A B C D E F G H K newT A ^ B E ^ C ^ F ^ ^ D ^ G 11/17/2018

思考 二叉树的删除算法？ 二叉树中序遍历的非递归实现算法？ 11/17/2018

二叉树中序遍历非递归 void Inorder (BinaryTreeNode<T> *t ) { InitStack(S); BinaryTreeNode<T> *p=t； while (p || !StackEmpty(S)) { if (p) {Push(S,p); p=p->lchild;} else{ Pop(S,p); visit(p); p=p->rchild; } 11/17/2018

8.7二叉树的抽象数据类型描述 抽象数据类型BinaryTree{ 实例 元素集合；如果不空，则被划分为根节点、左子树和右子树； 每个子树仍是一个二叉树 操作 Create()：创建一个空的二叉树； IsEmpty：如果二叉树为空，则返回true，否则返回false Root(x)：取x为根节点；如果操作失败，则返回false，否则返回true 11/17/2018

二叉树的抽象数据类型描述 MakeTree(root，left，right)：创建一个二叉树，root作为根节点，left作为左子树，right作为右子树 BreakTree(root，left，right)：拆分二叉树 PreOrder：前序遍历 InOrder：中序遍历 PostOrder：后序遍历 LevelOrder：逐层遍历 } 11/17/2018

11/17/2018

11/17/2018

11/17/2018

11/17/2018

11/17/2018

11/17/2018

补充：线索二叉树 如何找到一个节点的下一个节点？ 如何利用节点中的空指针？ 11/17/2018

补充：线索二叉树 利用空闲指针，加入线索，分别指向相应序 列中该节点的前驱和后继节点 对中序遍历来说： 从初始节点出发： 若右指针为线索，则指针所指为后继节点 若非线索，则应该是右儿子的最左后代 11/17/2018

T A ^ B C ^ ^ D ^ E ^ F ^ G ^ H ^ ^ K ^ 11/17/2018 86

补充：树与二叉树的转换 树t的每个节点x，用其孩子节点的RightChild域把x的所有孩子链成一条链。 x节点的LeftChild指针指向该链的第一个节点。 x节点的RightChild域用来指向x的兄弟。 11/17/2018

树的二叉树描述 11/17/2018

森林与二叉树的转换 1)把森林中的每一棵树转换为二叉树 ① 在所有的兄弟之间加一条连线 ① 在所有的兄弟之间加一条连线 ② 对每一个结点，除了保留与最左边的子女的连线外，去掉与其它子女的连线； ③ 整理：将保留下来的边作为左子树的边，兄弟间的连线作为右子树的边 2) 将转换后各二叉树的根结点看成兄弟，用线把它们连到一起，经整理后得到一个二叉树。 11/17/2018

森林与二叉树的转换 A D G B C H I E K F A D B G C E H F I 11/17/2018 K

森林的遍历 对森林的遍历操作是指按照某种次序系统地访问树林中的每个结点，且对每个结点只访问一次。 遍历森林的方法主要有深度优先遍历和广度优先遍历。 11/17/2018

森林的深度优先遍历 ① 先根遍历 访问头一棵树的根结点 从左到右先根遍历头一棵树树根的各子树 先根遍历其它的树 11/17/2018

对下图所示的森林,按先根次序遍历后得到的结点序列为： 对下图所示的森林,按先根次序遍历后得到的结点序列为：　 A B D E C F G H J I A B D E C G F H I J 11/17/2018

森林的深度优先遍历 ② 后根遍历  从左到右后根遍历头一棵树树根的子树  访问头一棵树的根结点  后根遍历其它的树 11/17/2018

对下图所示的森林，按后根遍历所得的结点序列为： D E B C A G J H I F A B D E C G F H I J 11/17/2018

森林的广度优先遍历 是一种按照层次遍历树林的方法，具体的遍历过程是：首先从左到右访问层数为0的所有结点，然后再从左到右访问层数为1的所有结点，...，直到访问完其余各层所有的结点。 11/17/2018

按广度优先遍历图示的树林 ,所得到的结点序列为： AF BCGHI DEJ A B D E C G F H I J 11/17/2018

A B C D E F G H I J K A B E A B F A C A D G H I A D G H J A D G H K 输出树中所有从根到叶子的路径的算法: A B C D E F G H I J K 例如：对左图所示的树，其输出结果应为： A B E A B F A C A D G H I A D G H J A D G H K 11/17/2018

输出二叉树上从根到所有叶子结点的路径 void AllPath( BiTree T, Stack& S ) { if (T) { Push( S, T->data ); if (!T->Lchild && !T->Rchild ) PrintStack(S); else { AllPath( T->Lchild, S ); AllPath( T->Rchild, S ); } Pop(S); } // if(T) } // AllPath 11/17/2018

输出树中所有从根到叶的路径 void OutPath( Bitree T, Stack& S ) { while ( !T ) { Push(S, T->data ); if ( !T->firstchild ) Printstack(S); else OutPath( T->firstchild, S ); Pop(S); T = T->nextsibling; } // while } // OutPath 11/17/2018

8.10 应用 设置信号放大器(Placement of Signal Boosters) 在线等价类(Online Equivalence Classes) 11/17/2018

问题形式化 为简化问题，设分布网络是一树形结构，源是树的根。树中的每一节点(除了根)表示一个可以用来放置放大器的子节点。信号从一个节点流向其子节点。每条边上标出从父节点到子节点的信号衰减量。 11/17/2018

问题形式化 信号从节点p 流到节点v 的衰减量为?。从节点q 到节点x 的衰减量为? 11/17/2018

定义 设D(i)为从节点i到以i为根节点的子树的任一叶子的衰减量的最大值。 D(叶节点)=? D(s)=? D(i)= max {D(j) + d(j)} j是i的一个孩子 如何计算D？ 11/17/2018

思想 计算D并放置放大器s 的伪代码为： D(i) = 0 ; for (i的每个孩子j ) if ((D(j)+d(j))>tolerance) 在j 放置放大器; else D(i) = max{D(i),D(j)+d(j)}; 11/17/2018

在线等价类 n个元素初始各在其自己的类中，然后执行一系列Find和Combine操作。 操作Find(e)返回元素e所在类的唯一特征。 Combine(a,b)用来合并包含a和b的类。 其复杂性为O(n+ulogu+f)。 在线等价类问题也称作离散集合合并/搜索问题(disjoint setunion-find problem)。 11/17/2018

树形描述 元素1、2、20、30等在以20为根的集合中；元素11、16、25、28在以16为根的集合中；元素15在以15为根的集合中；元素26和32在以26为根的集合中(或简称为集合26) 11/17/2018

树形描述 使用模拟指针。 每个节点有一个parent域。每个parent 域给出父节点的索引。 11/17/2018

基于树结构的合并/搜索问题解决方案 void Initialize(int n) {//初始化，每个类/树有一个元素 parent=new int[n+1]; for(int e=1;e<=n;e++) parent[e]=0; } 11/17/2018

基于树结构的合并/搜索问题解决方案 Int Find(int e) {//返回包含e的树的根节点 while(parent[e]) return e; } void Union(int i,int j) {//将根为i和j的两棵树进行合并 parent[j]=i; 11/17/2018

方法 缩短从元素e到根的查找路径。 路径的缩短可以通过称为路径压缩(path compression)的过程实现。 紧凑路径法(path compaction) 路径分割法(path splitting) 路径对折法(path halving) 11/17/2018

路径分割法 改变从e到根节点路径上每个节点(除了根和其子节点)的parent指针，使其指向各自的祖父节点。 11/17/2018

路径对折法 改变从e到根节点路径上每隔一个节点(除了根和其子节点)的parent域，使其指向各自的祖父节点。 11/17/2018

第八章 总结 树的概念，相关概念 二叉树描述及实现 二叉树特性 二叉树遍历 树的二叉树描述 应用 11/17/2018