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

Presentation on theme: "二叉树和其他树 (Binary and other trees)"— Presentation transcript:

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

2 本章内容 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 应用

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

4 例 8.1 Joe的后代

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

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

7 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.

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

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

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

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

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

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

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

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

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

17 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.

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

19 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))

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

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

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

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

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

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

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

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

28 链表二叉树的节点类 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;

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

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

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

32 前序:/+-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**/ --表达式的前缀形式 --表达式的中缀形式 --表达式的后缀形式

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

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

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

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

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

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

39 逐层遍历 输出: 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

40 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

41 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 }

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

43 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：逐层遍历 }

44 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);}//用私有函数实现

45 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); }

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

47 共享成员函数 ----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代表两棵子树 }

48 共享成员函数 ----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; }

49 私有成员函数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); } ……

50 共享成员函数--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;} }

51 利用前序遍历 计算节点个数 #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 }

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

53 输出（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

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

55 计算高度（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; }

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

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

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

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

60 森林的二叉树表示 森林（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

61 森林的二叉树表示

62 8.10.2 在线等价类 初始时有n 个元素，每个元素都属于一个独立的等价类。 需要执行以下的操作： combine(a,b) 等价于:
在线等价类 初始时有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问题.

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

64 8.10.2 在线等价类 树的描述 int *parent； 5 5 8 8 20 20 ……. Parent:
在线等价类 树的描述 int *parent； ……. Parent: ……. e……… n

65 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;

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

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

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

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

70 练习题： 已知一棵二叉树的中序、后序序列分别如下： 要求： 中序：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)画出该二叉树对应的森林；