二叉树和其他树 (Binary and other trees) 第8章 二叉树和其他树 (Binary and other trees)

本章内容 8.1 树 8.2 二叉树 8.3 二叉树的特性 8.4 二叉树的描述 8.5 二叉树常用操作 8.6 二叉树遍历 8.1 树 8.2 二叉树 8.3 二叉树的特性 8.4 二叉树的描述 8.5 二叉树常用操作 8.6 二叉树遍历 8.7 抽象数据类型BinaryTree 8.8 类BinaryTree 8.9 抽象数据类型及类的扩充 8.10 应用

8.1 Trees Linear and tabular data structures are generally not suitablke for the representation of hierarchical data (线性和表数据结构一般不适合于描述具有层次结构的数据) 例：descendant tree (家族图谱） 连通并且没有回路的图

例 8.1 Joe的后代

例 8.2 合作机构 总裁 销售副总裁 市场副总裁 …… 财务副总裁 开发副总裁 …

例 8.3 政府机构 联邦政府 国防部 教育部 …… 税务部 陆军 海军 空军 海军陆战队

A recursively definition on a binary tree A tree t is a finite nonempty set of elements. One of these elements is called root, and the remaining elements (if any) are partitioned into trees which are called the sub-trees of t.

术语 层次中最高层的元素为根 (root) 。 余下的元素分成不相交的集合。根的下一级的元素是根的孩子(children) 。是余下元素所构成的子树的根。 树中没有孩子的元素称为叶子(leaves)

术语 父母(Parent),孙子(grandchildren),祖父(Grandparent), 兄弟(Siblings),祖先(Ancestors),后代(Descendents) 叶子= {Mike,AI,Sue,Chris} 父母(Mary) = Joe 祖父(Sue) = Mary 兄弟(Mary) = {Ann,John} 祖先(Mike) = {Ann,Joe} 后代(Mary}={Mark,Sue}

术语 级（level）：指定树根的级为1，其孩子（如果有）的级为2。 1级 2级 3级 4级

术语 元素的度(Degree of an element) 是指其孩子的个数。

术语 树的度(The degree of a tree)是其元素度的最大值。 树的度 = 3

8.2 二叉树 定义[二叉树] : 二叉树（ binary tree）t 是有限个元素的集合（可以为空）。 当二叉树非空时，其中有一个称为根(root)的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树.

二叉树和树的区别 二叉树可以为空，但树不能为空。 二叉树中每个节点的子数个数2. 而树中节点子树个数没有限制。 在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。 - 被看作二叉树— -被看作树—

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

编译时数学表达式的二叉树表示

8.3 二叉树的特性 Property 1 The drawing of every binary tree with n elements, n>0, has exactly n-1 edges. Proof. Every element in a binary tree (except the root) has exactly one parent. There is exactly one edge between each child and its parent. SO the number of edge is n-1.

8.3 二叉树的特性 二叉树的高度（height）或深度（depth）是指该二叉树的层数。 特性 2: 若二叉树的高度为h，h≥0，则该二叉树最少有h个元素，最多有2h-1 个元素。 证明： 元素数最少为h 第i 层节点元素最多为2i-1 元素的总数最多为∑ 2i-1 =2h-1 个元素

8.3 二叉树的特性 特性 3: 包含n（n≥0）个元素的二叉树的高度最大为n，最小为(log2(n+1)). 证明： n≤2h-1 高度最小为： 高度最大为n。 n≤2h-1 h≥ log2(n+1) h= (log2(n+1))

满二叉树 当高度为h 的二叉树恰好有 2h-1 个元素时， 称其为满二叉树（full binary tree).

完全二叉树 从满二叉树中删除k个元素，其编号为2h-i, 1≤i≤k，所得到的二叉树被称为完全二叉树（ complete binary tree）。

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

完全二叉树 满二叉树是完全二叉树的一个特例. 有n个元素的完全二叉树的深度为 (log2(n+1)) 完全二叉树 非完全二叉树

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

8.4 二叉树描述 公式化描述 链表描述

8.4.1 公式化描述 完全二叉树： 按照二叉树对元素的编号方法，将二叉树的元素存储在数组中。

LeftChild data RightChild 8.4.2 链表描述 二叉树最常用的描述方法。 每个元素都用一个节点表示，每个节点： LeftChild data RightChild

链表二叉树的节点类 template<class T> class BinaryTreeNode { public: // 3 个构造函数 BinaryTreeNode() { LeftChild = RightChild = NULL; } // 建立空子树 BinaryTreeNode(const T& e) {//建立根的data=e独立顶点树 data = e; LeftChild = RightChild = NULL; } BinaryTreeNode(const T& e, BinaryTreeNode *l, BinaryTreeNode *r) { data = e; LeftChild = l; RightChild = r; // data + links 参数 }//建立根值为e，左子树为l, 右子树为r的新2叉树。 private: T data; BinaryTreeNode<T> *LeftChild, *RightChild;

8.5 二叉树常用操作 确定其高度 确定其元素数目 复制 在屏幕或纸上显示二叉树 确定两棵二叉树是否一样 删除整棵树 若为数学表达式树，计算该数学表达式 若为数学表达式树，给出对应的带括号的表达式

8.6 二叉树遍历 许多二叉树操作是通过对二叉树进行遍历来完成。 在二叉树的遍历中，每个元素仅被访问一次。在访问时执行对该元素的相应操作（复制、删除、输出等）。 有四种遍历二叉树的方法：(依据对根节点访问的位置） 前序遍历 preorder，先访问根，左子树，右子树 中序遍历 Inorder 先访问左子树，根和右子树 后序遍历 Postorder 先访问左子树、右子树和根 逐层遍历 level order (breadth first order)//从根逐层遍历 注：“访问”可以代表对节点操作的函数操作，如输出

遍历示例 (visit(t)= cout(t ->data)) 前序:+*ab/cd 前序:+++abcd 中序:a*b+c/d 中序:a+b+c+d 后序:ab+c+d+ 后序:ab*cd/+ 中序是传统的表示，其他在计算机中表示

前序:/+-a+xy*+b*ca --表达式的前缀形式 中序:-a+x+y/+b*c*d --表达式的中缀形式 Get the infix,prefix and postfix forms of expression by three order visit 前序:/+-a+xy*+b*ca 中序:-a+x+y/+b*c*d 后序:a-xy++b+ca**/ --表达式的前缀形式 --表达式的中缀形式 --表达式的后缀形式

前序遍历 template<class T> void PreOrder (BinaryTreeNode<T> *t) {//对*t进行前序遍历 if (t) { Visit(t); //访问根节点 PreOrder(t->LeftChild); //前序遍历左子树 PreOrder(t->RightChild); //前序遍历右子树 }

中序遍历 template<class T> void InOrder(BinaryTreeNode<T> *t) if (t) { InOrder(t->LeftChild); //中序遍历左子树 Visit(t); //访问根节点 InOrder(t->RightChild); //中序遍历右子树 }

后序遍历 template<class T> void PostOrder(BinaryTreeNode<T> *t) {//对*t进行后序遍历 if (t) { PostOrder(t->LeftChild); //后序遍历左子树 PostOrder(t->RightChild); //后序遍历右子树 Visit(t); //访问根节点 }

数学表达式二叉树的遍历 x+(y*z) (x+y)*z 若不考虑*优先于+运算时，表达式的中缀形式存在歧义: x+y*z * + z x y

数学表达式二叉树的遍历 ((x)+((y)*(z))) (((x)+(y))*z) 完全括号化的中缀表达式: 每个操作符和相应的操作数都用一对括号括起来。更甚者把操作符的每个操作数也都用一对括号括起来。 * + z x y + x * y z ((x)+((y)*(z))) (((x)+(y))*z)

输出完全括号化的中缀表达式 template <class T> void Infix(BinaryTreeNode<T> *t) {// 输出表达式的中缀形式 if (t) {cout << '('; Infix(t->LeftChild);// 左操作数 cout << t->data; // 操作符 Infix(t->RightChild);//右操作数 cout << ')';} } 前缀和后缀表达式中不会存在歧义。

逐层遍历 输出: a b c d e f g h i j 在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问。 逐层示例 (visit(t)= cout(t->data)) 输出: a b c d e f g h i j

template<class T> class LinkedQueue { //基类 public: LinkedQueue() {front = rear = 0;} ~LinkedQueue(); bool IsEmpty() const {return ((front) ? false : true);} bool IsFull() const; T First() const; // 返回第一个元素 T Last() const; // 返回最后一个元素 LinkedQueue<T>& Add(const T& x); LinkedQueue<T>& Delete(T& x); private: Node<T> *front; Node<T> *rear; } ; 40

Using Queue to implement level order traval template <class T> void LevelOrder(BinaryTreeNode<T> *t) {//对* t逐层遍历，队列的数据类型是二叉树节点类 LinkedQueue<BinaryTreeNode<T>>* Q; while (t) { Visit(t); //访问t //将t的左右孩子放入队列 if (t->LeftChild) Q.Add(t->LeftChild); if (t->RightChild) Q.Add(t->RightChild); try {Q.Delete(t);} //访问下一个节点 . catch (OutOfBounds) {return;}//Q is empty }

空间复杂性和时间复杂性 设二叉树中元素数目为n。四种遍历算法： 空间复杂性均为O(n) 。 时间复杂性均为(n)。

8.7 The ADT BinaryTree AbstractDataType BinaryTree Instance: collection elements; if not empty, the collection is partitioned into a root, left subtree and rightsubtree, each subtree is also a binary tree; Operations: Create()：创建一个空的二叉树； IsEmpty：如果二叉树为空，则返回true，否则返回false Root(x)：x is set to root element; return fail if the operation fails；otherwise return true MakeTree(root，left，right)：create a binary tree with root as the root element, left(right) as the left (right) tree BreakTree(root，left，right); inverse of create PreOrder：前序遍历 InOrder：中序遍历 PostOrder：后序遍历 LevelOrder：逐层遍历 }

8.8 Class BinaryTree template<class T> class BinaryTree { public : BinaryTree() {root=0;}; ~BinaryTree() {}; bool IsEmpty( ) const {return ((root) ? false : true);} bool Root(T& x) const; void MakeTree(const T& element，BinaryTree<T>&left，BinaryTree<T>& right);//两棵树要求不一样! void BreakTree(T& element，BinaryTree<T>&left ， BinaryTree<T>& right); void PreOrder( void(*Visit) (BinaryTreeNode<T> *u) ) //参数是对visit {PreOrder(Visit，root);}//用私有函数实现

void Inorder(void (*Visit) (BinaryTreeNode<T> *u)) {Inorder(Visit，root);} void PostOrder(void(*Visit ) (BinaryTreeNode<T> *u)); {Postorder (Visit, root); } void LevelOrder(void(*Visit) (BinaryTreeNode<T> *u)); private: BinaryTreeNode<T>*root;//根节点指针 void PreOrder(void (*Visit) (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);// void InOrder(void(*Visit) (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); void PostOrder(void(*Visit) (BinaryTreeNode<T> *u),BinaryTreeNode<T> *t); }

共享成员函数 ----Root template<class T> bool BinaryTree<T>::Root(T& x) const {// 取根节点的data域，放入x // 如果没有根节点，则返回false if (root) {x = root->data; return true;} else return false; // 没有根节点 }

共享成员函数 ----MakeTree template<class T> void BinaryTree < T > : : MakeTree(const T& element, BinaryTree<T>& left, BinaryTree<T>& right) {// 将left, right和element 合并成一棵新树 // left, right和this必须是不同的树 // 创建新树 root = new BinaryTreeNode< T > (element, left.root, right.root); //阻止访问left和right所代表的子树。 left.root = right.root = 0;//注意left,right代表两棵子树 }

共享成员函数 ----BreakTree template<class T> void BinaryTree < T >::BreakTree(T& element, BinaryTree<T>& left, BinaryTree<T>& right) {// left, right和this必须是不同的树，但都是空子树可以 // 检查树是否为空 if (!root) throw BadInput(); // 空树 // 分解树 element = root->data; left.root = root->LeftChild; // left is tree formed by Lefttree right.root = root->RightChild; delete root; root = 0; }

私有成员函数PreOrder,InOrder,PostOrder template<classT> void BinaryTree<T>::PreOrder (void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t) {//前序遍历 ,Visit is an function, e.g. Output If (t) {Visit(t); PreOrder(Visit,t->LeftChild); PreOrder(Visit,t->RightChild); } ……

共享成员函数--LevelOrder template<classT> void BinaryTree<T>::LevelOrder(void(*Visit)(BinaryTreeNode<T>*u)) {//逐层遍历 LinkedQueue<BinaryTreeNode<T>*> Q; BinaryTreeNode<T> *t; t=root; while(t){ Visit(t); if (t->LeftChild) Q.Add(t->LeftChild); if (t->RightChild) Q.Add(t->RightChild); try{Q.Delete(t);} catch(OutOfBounds){return;} }

利用前序遍历 计算节点个数 #include <iostream.h> #include "binary.h" Int count=0; BinaryTree<int> a,x,y,z; //空子树 Template <class T> Void ct(BinaryTreeNode<T>*t) {count++;} Void main(void) { y.MakeTree(1,a,a); z.MakeTree(2,a,a); x.MakeTree(3,y,z); y.MakeTree(4,x,a); y.PreOrder(ct); cout<<count<<endl; // 4 }

8.9 抽象数据类型及类的扩充 将ADT 进行扩充，增加如下操作: PreOutput()：按前序方式输出数据域。 InOutput()：按中序方式输出数据域。 PostOutput()：按后序方式输出数据域。 LevelOutput()：逐层输出数据域。 Delete()：删除一棵二叉树，释放其节点。 Height()：返回树的高度。 Size()：返回树中节点数。

输出（Output） visit Private: …… static void Output(BinaryTreeNode<T> *t) { cout << t->data << ' ' ;} Public: void PreOutput( ) { PreOrder(Output，root); cout << end1;} void InOutput( ) { InOrder(Output，root); cout << end1;} void PostOutput( ) {PostOrder(Output，root); cout<<end1;} void LevelOutput( ) { LevelOrder(Output); cout << end1;} visit

删除（Delete） private： …… static void Free(BinaryTreeNode<T> *t) {delete t;} Public: void Delete( ) { PostOrder (Free，root); root = 0; }

计算高度（Height） Public: …… int Height( ) const {return Height (root);} private： int Height (BinaryTreeNode<T> *t) const; template <class T> int BinaryTree<T>::Height(BinaryTreeNode<T> *t) const {//返回树*t的高度 If (!t) return 0; // 空树 int hl = Height(t->LeftChild); // 左子树的高度 int hr = Height(t->RightChild); // 右子树的高度 if (hl > hr) return ++hl; Else return ++hr; }

统计节点数（Size） int _count;//类定义之外定义的一个整型变量 Public: ……. int Size ( ) PreOrder(Add1，root);// replace visit by add1 return _count;} private： …… static void Add1(BinaryTreeNode<T> *t) { _count++;}

8.10 应用 8.10.1 树与森林的二叉树表示 8.10.2 在线等价类

树的二叉树描述 对于树t的每个节点x，x节点的LeftChild指针指向x的第一个孩子。x节点的RightChild域指向x的下一个兄弟。

树的二叉树描述 a b c d g h f e i j

森林的二叉树表示 森林（forest）是一棵或多棵树的集合. 森林的二叉树表示 首先得到树林中每棵树（设有m棵树）的二叉树描述 . 然后，第i棵作为第i-1棵树的右子树（ 2≤i≤m）. a b c d g h f e i j a b c f g h d e i j

森林的二叉树表示

8.10.2 在线等价类 初始时有n 个元素，每个元素都属于一个独立的等价类。 需要执行以下的操作： combine(a,b) 等价于: 8.10.2 在线等价类 初始时有n 个元素，每个元素都属于一个独立的等价类。 需要执行以下的操作： (1) Combine(a,b)---- 把包含a和b的等价类合并成一个等价类。 (2) Find(e)---- 确定哪个类包含元素e 。 combine(a,b) 等价于: i=Find(a); j=Find(b); If (i!=j) Union(i, j); 向R中添加新关系 (a,b) : if(i!=j) Union(i, j); 在线等价类问题，通常又称之为union-find问题.

8.10.2 在线等价类 等价类可以看成元素的离散集合 在线等价类问题也称作离散集合合并/搜索(union-find)问题 解决方案: 8.10.2 在线等价类 等价类可以看成元素的离散集合 在线等价类问题也称作离散集合合并/搜索(union-find)问题 解决方案: 每个集合(类)描述为一棵树。 每个非根节点都指向其父节点。 用根元素作为集合标识符。

8.10.2 在线等价类 树的描述 int *parent； 5 5 8 8 20 20 ……. Parent: 8.10.2 在线等价类 树的描述 int *parent； 5 5 8 8 20 20 ……. Parent: 1 2 3 4 5 6 ……. e……… n

void Initialize(int n) {// 初始化，每个类/树有一个元素 parent = new int[n+1]; for (int e = 1; e <= n; e++) parent[e] = 0; } int Find(int e) { / /返回包含e的树的根节点，即代表元 while (parent[e]) e = parent[e]; // 上移一层 return e; void Union(int i, int j) {// 将根为i 和j的两棵树进行合并 parent[j] = i;

性能评价 假设要执行u 次合并和f 次查找。因为每次合并前都必须执行两次查找，因此可假设f＞u。 每次合并所需时间为Q(1)。而每次查找所需时间由树的高度决定。 在最坏情况下，有m个元素的树的高度为m。当执行以下操作序列时，即可导致最坏情况出现： Union(2,1)，Union(3,2)，Union(4,3)，Union(5,4)，⋯ 因此每一次查找需花费Q(q)时间，其中q是在执行查找之前所进行的合并操作的次数。

性能改进 在对树i和树j进行合并操作时，使用重量规则或高度规则 定义[重量规则]若树i节点数少于树j节点数，则将j作为i的父节点。否则，将i作为j的父节点。 定义[高度规则]若树i的高度小于树j的高度，则将j作为i的父节点，否则将i作为j的父节点。

提高在最坏情况下的性能的方法 缩短从元素e到根的查找路径。 路径的缩短可以通过称为路径压缩(path compression) 的过程实现。 紧凑路径法(path compaction) 改变从e到根节点路径上所有节点的parent指针，使其指向根节点。 路径分割法(path splitting) 改变从e到根节点路径上每个节点(除了根和其子节点)的parent指针，使其指向各自的祖父节点。 路径对折法(path halving) 改变从e到根节点路径上每隔一个节点(除了根和其子节点)的parent域，使其指向各自的祖父节点。

作业： 3,４，７，8，9，10，11，13，15，19 31，36

练习题： 已知一棵二叉树的中序、后序序列分别如下： 要求： 中序：D C E F B H G A K J L I M 后序：D F E C H G B K L J M I A 要求： ⑴ 画出该二叉树； ⑵ 写出该二叉树的先序序列。 (3)画出该二叉树对应的森林；