<4D F736F F F696E74202D20536C FB5DACBC4D5C220CAF7D3EBB6FEB2E6CAF7205BBCE6C8DDC4A3CABD5D>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20536C FB5DACBC4D5C220CAF7D3EBB6FEB2E6CAF7205BBCE6C8DDC4A3CABD5D>"

铸野魏
7 years ago
Views:

1 第四章树二叉树森林树的基本概念二叉树定义主要特征存储结构 : 顺序链式遍历线索二叉树 : 基本概念构造树森林存储结构 : 树森林与二叉树的转换遍历 : 树森林应用二叉排序树 Huffman 树和哈夫曼编码

2 树和有根树两种树 : 自由树有根树

3 树 (Tree) 和森林的概念自由树无回路的连通图 : 一棵自由树 T f 可定义为一个二元组 T f = (V, E) 其中 : V = {v 1,..., v n } : 顶点集合由 n (n>0) 个元素组成的有限非空集合 E = { (v i, v j ) v i, v j V, 1 i, j n } : 边集合 n-1 个序对的集合 E 中的元素 (v i, v j ) 称为边或分支自由树

4 有根树 (rooted tree) 一棵有根树 T, 简称为树 (Tree) n (n 0) 个结点的有限集合当 n = 0 时,T 为空树 ; 否则,T 是非空树, 记作 : T Φ, { r,t,t,...,t 1 2 m } n 0 n 0 r 是一个特定的称为根 (root) 的结点, 它只有直接后继, 但没有直接前驱 ; 根以外的其他结点划分为 m (m 0) 个互不相交的有限集合 T 1, T 2,, T m 每个集合又是一棵树, 且称为根的子树每棵子树的根结点有且仅有一个直接前驱, 但可以有 0 个或多个直接后继,

5 树的基本术语 (Terminology) 结点的层次 (level) 规定根结点在第一层, 其子女结点的层次等于它的层次加一以下类推深度 (depth) 结点的深度 : 即结点的层次树的深度 : 离根最远结点的层次 A 1 层 E B F C G H D I J 2 层 3 层 depth = 4 K L M 4 层

6 子女 (child) 若结点的子树非空, 结点子树的根即为该结点的子女双亲 (parent) 若结点有子女, 该结点是子女双亲兄弟 (sibling) 同一结点的子女互称为兄弟祖先 (ancestor) 某结点到根结点的路径上的各个结点都是该结点的祖先子孙 (descendant) 某结点的所有下属结点, 都是该结点的子孙

7 度 (degree) 结点的子女个数, 即为该结点的度树的度 : 树中各个结点的度的最大值分支结点 (branch) / 非终端结点度不为 0 的结点叶结点 (leaf) 度为 0 的结点 E B F A C G degree(a)=3 H D I J degree(b)=2, degree(c)=1, degree(d)=3 K L M degree(m)=0

8 高度 (height) 规定 : 叶结点的高度为 1 其双亲结点的高度等于它的高度加一树的高度等于根结点的高度, 即根结点所有子女高度的最大值加一 A 4 1 层 E B F C G H D I J 23层 32层 depth = 4 height = 4 K L M 4 层 1

9 有序树树中结点的各棵子树 T 0, T 1, 是有次序的无序树树中结点的各棵子树之间的次序是不重要的, 可以互相交换位置森林 (forest) 森林是 m(m 0) 棵树的集合

10 树的抽象数据类型 template <class T> class Tree { /* 对象 : 树是由 n ( 0) 个结点组成的有限集合在类界面中的 position 是树中结点的地址在顺序存储方式下是下标型, 在链表存储方式下是指针型 T 是树结点中存放数据的类型, 要求所有结点的数据类型都是一致的 */ public: Tree (); ~Tree ();

11 BuildRoot (const T& value); // 建立树的根结点 position FirstChild(position p); // 返回 p 第一个子女地址, 无子女返回 0 position NextSibling(position p); // 返回 p 下一兄弟地址, 若无下一兄弟返回 0 position Parent(position p); // 返回 p 双亲结点地址, 若 p 为根返回 0 T getdata(position p); // 返回结点 p 中存放的值 bool InsertChild(position p, T& value); // 在结点 p 下插入值为 value 的新子女, 若插 // 入失败, 函数返回 false, 否则返回 true

12 }; bool DeleteChild (position p, int i); // 删除结点 p 的第 i 个子女及其全部子孙结 // 点, 若删除失败, 则返回 false, 否则返回 true void DeleteSubTree (position t); // 删除以 t 为根结点的子树 bool IsEmpty (); // 判树空否, 若空则返回 true, 否则返回 false void Traversal (void (*visit)(position p)); // 遍历以 p 为根的子树

13 第四章树二叉树森林树的基本概念二叉树定义主要特征存储结构 : 顺序链式遍历线索二叉树 : 基本概念构造树森林存储结构 : 树森林与二叉树的转换遍历 : 树森林应用二叉排序树 Huffman 树和哈夫曼编码

14 二叉树 (Binary Tree) 定义一棵二叉树是结点的一个有限集合, 该集合或者为空, 或者是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成 L R L R 二叉树的五种不同形态

15 二叉树的性质性质 1 若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 2 i-1 个结点 ( i 1) [ 证明用数学归纳法 ] 当 i=1 时, = 2 0 = 1, 结论成立 ; 假定对所有 j (1=<j<i), 结论成立, 即第 j 层最多有 2 j-1 个结点 ; 则, 在第 i-1 层最多有 2 i-2 个结点 ; 由于, 二叉树每个结点最多有 2 个子女, 因而, 第 i 层上的最大结点数为第 i-1 层上最大结点数的 2 倍 : 2*2 i-2 = 2 i-1

16 性质 2 深度为 k 的二叉树最少有 k 个结点, 最多有 2 k -1 个结点 ( k 1 ) 因为每一层最少要有 1 个结点, 因此, 最少结点数为 k 最多结点个数借助性质 1 用求等比级数前 k 项和的公式 : k-1 = 2 k -1

17 性质 3 对任何一棵二叉树, 如果其叶结点有 n 0 个, 度为 2 的非叶结点有 n 2 个, 则有 : n 0 =n 2 +1 若设度为 1 的结点有 n 1 个, 总结点数为 n, 总边数为 e, 则根据二叉树的定义, n = n 0 +n 1 +n 2 e = 2n 2 +n 1 = n-1 因此, 有 2n 2 +n 1 = n 0 +n 1 +n 2-1 n 2 = n 0-1 n 0 = n 2 +1

18 定义 1 满二叉树 (Full Binary Tree) 每一层节点数都为最大值 2 i-1 定义 2 完全二叉树 (Complete Binary Tree) 若设二叉树的深度为 k, 则共有 k 层除第 k 层外, 其它各层 (1~k-1) 的结点数都达到最大个数, 第 k 层从右向左连续缺若干结点, 这就是完全二叉树

19 性质 4 具有 n (n 0) 个结点的完全二叉树的深度为 log 2 (n+1) 设完全二叉树的深度为 k, 则有 2 k-1-1 < n 2 k -1 上面 k-1 层结点数第 k 层的最大结点数变形 2 k-1 < n+1 2 k 取对数 k-1< log 2 (n+1) k 有 log 2 (n+1) = k

20 性质 5 如将一棵有 n 个结点的完全二叉树自顶向下, 同一层自左向右连续给结点编号 1, 2,, 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 所在的层次为 log 2 i

21 正则二叉树理想平衡二叉树满的定义 : 在二叉树中, 如果每个结点的出度恰好等于 2 或 0, 则称该树为正则二叉树即 : 不存在子树个数为 1 的结点定义 : 在二叉树中, 如果第 1 层到第 k-1 层是满二叉树, 第 k 层的结点不集中在最左边

22 二叉树的抽象数据类型 (ADT) template <class T> class BinaryTree { // 对象 : 结点的有限集合, 二叉树是有序树 public: BinaryTree (); // 构造函数 BinaryTree (BinTreeNode<T> *lch, BinTreeNode<T> *rch, T item); // 构造函数, 以 item 为根, lch 和 rch 为左右子 // 树构造一棵二叉树 int Height (); // 求树深度或高度 int Size (); // 求树中结点个数

23 BinTreeNode<T> *Parent (BinTreeNode<T> *t); // 求结点 t 的双亲 BinTreeNode<T> *LeftChild (BinTreeNode<T> *t); // 求结点 t 的左子女 BinTreeNode<T> *RightChild (BinTreeNode<T> *t); // 求结点 t 的右子女 bool Insert (T item); // 在树中插入新元素 bool Remove (T item); // 在树中删除元素 bool Find (T& item); // 判断 item 是否在树中 bool getdata (T& item); // 取得结点数据 bool IsEmpty (); // 判二叉树空否?

24 BinTreeNode<T> *getroot (); // 取根 }; void preorder (void (*visit) (BinTreeNode<T> *t)); // 前序遍历, visit 是访问函数 void inorder (void (*visit) (BinTreeNode<T> *t)); // 中序遍历, visit 是访问函数 void postorder (void (*visit) (BinTreeNode<T> *t)); // 后序遍历, (*visit) 是访问函数 void levelorder (void (*visit)(bintreenode<t> *t)); // 层次序遍历, visit 是访问函数

25 第四章树二叉树森林树的基本概念二叉树定义主要特征存储结构 : 顺序链式遍历线索二叉树 : 基本概念构造树森林存储结构 : 树森林与二叉树的转换遍历 : 树森林应用二叉排序树 Huffman 树和哈夫曼编码

26 二叉树的顺序表示完全二叉树的顺序表示一般二叉树的顺序表示

27 极端情形 : 只有右单支的二叉树

28 二叉树的链表表示 ( 二叉链表 ) 二叉树结点定义 : 每个结点有 3 个数据成员 data 域存储结点数据 leftchild 存放指向左子女的指针 rightchild 存放指向右子女的指针 leftchild data rightchild data 二叉链表 leftchild rightchild

29 二叉树的链表表示 ( 三叉链表 ) 每个结点 : 增加一个指向双亲的指针 parent, 使得查找双亲也很方便 leftchild data parent rightchild 三叉链表 parent data leftchild rightchild

30 root root root A A A B B B C D C D C D E F E F E 二叉树二叉链表三叉链表二叉树链表表示的示例 F

31 C root A B D E F data parent leftchild rightchild A B C D E F 二叉树的静态链表结构

32 二叉树的类定义

33 template <class T> struct BinTreeNode { // 二叉树结点类定义 T data; // 数据域 BinTreeNode<T> *leftchild, *rightchild; // 左子女右子女链域 BinTreeNode () // 构造函数 { leftchild = NULL; rightchild = NULL; } }; BinTreeNode (T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) { data = x; leftchild = l; rightchild = r; }

34 template <class T> class BinaryTree { // 二叉树类定义 public: BinaryTree () : root (NULL) { } // 构造函数 BinaryTree (T value) : RefValue(value), root(null) { } // 构造函数 BinaryTree (BinaryTree<T>& s); // 复制构造函数 ~BinaryTree () { destroy(root); } // 析构函数 bool IsEmpty () { return root == NULL;} // 判二叉树空否 int Height () { return Height(root); } // 求树高度 int Size () { return Size(root); } // 求结点数

35 BinTreeNode<T> *Parent (BinTreeNode <T> *t) { return (root == NULL root == t)? NULL : Parent (root, t); } // 返回双亲结点 BinTreeNode<T> *LeftChild (BinTreeNode<T> *t) { return (t!= NULL)?t->leftChild : NULL; } // 返回左子女 BinTreeNode<T> *RightChild (BinTreeNode<T> *t) { return (t!= NULL)?t->rightChild : NULL; } // 返回右子女 BinTreeNode<T> *getroot () const { return root; } // 取根

36 void preorder (void (*visit) (BinTreeNode<T> *t)) { preorder (root, visit); } // 前序遍历 void inorder (void (*visit) (BinTreeNode<T> *t)) { inorder (root, visit); } // 中序遍历 void postorder (void (*visit) (BinTreeNode<T> *t)) { postorder (root, visit); } // 后序遍历 void levelorder (void (*visit)(bintreenode<t> *t)); // 层次序遍历 int Insert (const T item); // 插入新元素 BinTreeNode<T> *Find (T item) const; // 搜索

37 protected: BinTreeNode<T> *root; // 二叉树的根指针 T RefValue; // 数据输入停止标志 void CreateBinTree (istream& in, BinTreeNode<T> *& subtree); // 从文件读入建树 bool Insert (BinTreeNode<T> *& subtree, T& x); // 插入 void destroy (BinTreeNode<T> *& subtree); // 删除 bool Find (BinTreeNode<T> *subtree, T& x); // 查找

38 BinTreeNode<T> *Copy (BinTreeNode<T> *r); // 复制 int Height (BinTreeNode<T> *subtree); // 返回树高度 int Size (BinTreeNode<T> *subtree); // 返回结点数 BinTreeNode<T> *Parent (BinTreeNode<T> * subtree, BinTreeNode<T> *t); // 返回父结点 BinTreeNode<T> *Find (BinTreeNode<T> * subtree, T& x) const; // 搜寻 x

39 void Traverse (BinTreeNode<T> *subtree, ostream& out); // 前序遍历输出 void preorder (BinTreeNode<T>& subtree, void (*visit) (BinTreeNode<T> *t)); // 前序遍历 void inorder (BinTreeNode<T>& subtree, void (*visit) (BinTreeNode<T> *t)); // 中序遍历 void postorder (BinTreeNode<T>& Tree, void (*visit) (BinTreeNode<T> *t)); // 后序遍历

40 }; friend istream& operator >> (istream& in, BinaryTree<T>& Tree); // 重载操作 : 输入 friend ostream& operator << (ostream& out, BinaryTree<T>& Tree); // 重载操作 : 输出

41 部分成员函数的实现

42 template <class T> BinTreeNode<T> *BinaryTree<T>:: Parent (BinTreeNode <T> *subtree, BinTreeNode <T> *t) { // 私有函数 : 从结点 subtree 开始, 搜索结点 t 的双 // 亲, 若找到则返回双亲结点地址, 否则返回 NULL if (subtree == NULL) return NULL; if (subtree->leftchild == t subtree->rightchild == t ) return subtree; // 找到, 返回父结点地址 BinTreeNode <T> *p; if ((p = Parent (subtree->leftchild, t))!= NULL) return p; // 递归在左子树中搜索 else return Parent (subtree->rightchild, t); // 递归在左子树中搜索 };

43 template<class T> void BinaryTree<T>:: destroy (BinTreeNode<T> * subtree) { // 私有函数 : 删除根为 subtree 的子树 if (subtree!= NULL) { destroy (subtree->leftchild); // 删除左子树 destroy (subtree->rightchild); // 删除右子树 delete subtree; // 删除根结点 } };

44 template<class T> istream& operator >> (istream& in, BinaryTree<T>& Tree) { // 重载操作 : 输入并建立一棵二叉树 Tree in 是输 // 入流对象 CreateBinTree (in, Tree.root); // 建立二叉树 return in; };

45 第四章树二叉树森林树的基本概念二叉树定义主要特征存储结构 : 顺序链式遍历线索二叉树 : 基本概念构造树森林存储结构 : 树森林与二叉树的转换遍历 : 树森林应用二叉排序树 Huffman 树和哈夫曼编码

46 二叉树遍历二叉树的遍历就是按某种次序访问树中的结点, 要求每个结点访问一次且仅访问一次设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV

47 中序遍历 (Inorder Traversal) 中序遍历二叉树算法的框架是 : 若二叉树为空, 则空操作 ; 否则 - 中序遍历左子树 (L); 访问根结点 (V); + / 中序遍历右子树 (R) a * e f 遍历结果 a + b * c - d - e / f b - c d

48 二叉树递归的中序遍历算法 template <class T> void BinaryTree<T>::InOrder (BinTreeNode<T> * subtree, void (*visit) (BinTreeNode<T> *t)) { if (subtree!= NULL) } { } InOrder (subtree->leftchild, visit); // 遍历左子树 visit (subtree); // 访问根结点 InOrder (subtree->rightchild, visit); // 遍历右子树

49 前序遍历 (Preorder Traversal) 前序遍历二叉树算法的框架是 : 若二叉树为空, 则空操作 ; - 否则访问根结点 (V); + / 前序遍历左子树 (L); 前序遍历右子树 (R) a * e f 遍历结果 b a * b - c d / e f c d

50 二叉树递归的前序遍历算法 template <class T> void BinaryTree<T>::PreOrder (BinTreeNode<T> * subtree, void (*visit) (BinTreeNode<T> *t)) { if (subtree!= NULL) } { } visit (subtree); // 访问根结点 PreOrder (subtree->leftchild, visit); // 遍历左子树 PreOrder (subtree->rightchild, visit); // 遍历右子树

51 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的框架是 : 若二叉树为空, 则空操作 ; 否则 - 后序遍历左子树 (L); 后序遍历右子树 (R); + / 访问根结点 (V) a * e f 遍历结果 a b c d - * + e f / - b c - d

52 二叉树递归的后序遍历算法 template <class T> void BinaryTree<T>::PostOrder (BinTreeNode<T> * subtree, void (*visit) (BinTreeNode<T> *t ) { if (subtree!= NULL ) { PostOrder (subtree->leftchild, visit); // 遍历左子树 PostOrder (subtree->rightchild, visit); // 遍历右子树 visit (subtree); // 访问根结点 } }

53 应用 : 二叉树遍历 template <class T> int BinaryTree<T>::Size (BinTreeNode<T> * subtree) const { // 私有函数 : 利用二叉树后序遍历算法计算二叉 // 树的结点个数 if (subtree == NULL) return 0; // 空树 else return 1+Size (subtree->leftchild) + Size (subtree->rightchild); };

54 template <class T> int BinaryTree<T>::Height ( BinTreeNode<T> * subtree) const { // 私有函数 : 利用二叉树后序遍历算法计算二叉 // 树的高度或深度 if (subtree == NULL) return 0; // 空树高度为 0 else { int i = Height (subtree->leftchild); int j = Height (subtree->rightchild); return (i < j)? j+1 : i+1; };

55 利用二叉树前序遍历建立二叉树以递归方式建立二叉树输入结点值的顺序必须对应二叉树结点前序遍历的顺序约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在 RefValue 中或用 -1 表示字符序列或正整数序列空结点

56 如图所示 : 二叉树的前序遍历顺序为 A D G B E @

57 template<class T> void BinaryTree<T>::CreateBinTree (ifstream& in, BinTreeNode<T> *& subtree) { // 私有函数 : 以递归方式建立二叉树 T item; if (!in.eof () ) { // 未读完, 读入并建树 in >> item; // 读入根结点的值 if (item!= RefValue) { subtree = new BinTreeNode<T>(item); // 建立根结点 if (subtree == NULL) {cerr << 存储分配错! << endl; exit (1);}

58 }; } CreateBinTree (in, subtree->leftchild); // 递归建立左子树 CreateBinTree (in, subtree->rightchild); // 递归建立右子树 } else subtree = NULL; // 封闭指向空子树的指针

59 利用栈的二叉树 3 种遍历非递归算法

60 利用栈的中序遍历非递归算法 aa b cc b a a d a a d e e 左空退栈访问左空退栈访问退栈访问 e c c c 左空退栈访问右空退栈访问栈空结束

61 利用栈的中序遍历非递归算法 template <class T> void BinaryTree<T>:: InOrder (void (*visit) (BinTreeNode<T> *t)) { stack<bintreenode<t>*> S;

62 }; BinTreeNode<T> *p = root; do { while (p!= NULL) { // 遍历指针向左下移动 S.Push (p); // 该子树沿途结点进栈 p = p->leftchild; } if (!S.IsEmpty()) { // 栈不空时退栈 S.Pop (p); visit (p); // 退栈, 访问 p = p->rightchild; // 遍历指针进到右子女 } } while (p!= NULL!S.IsEmpty ());

63 利用栈的前序遍历非递归算法 b a c c d c c d e 访问 a 进栈 c 左进 b 访问 b 进栈 d 左进空退栈 d 访问 d 左进空退栈 c 访问 c 左进 e 访问 e 左进空栈空结束

64 利用栈的前序遍历非递归算法 template <class T> void BinaryTree<T>:: PreOrder (void (*visit) (BinTreeNode<T> *t) ) { stack<bintreenode<t>*> S; BinTreeNode<T> *p = root; S.Push (NULL); while (p!= NULL) { visit(p); // 访问结点 if (p->rightchild!= NULL) S.Push (p->rightchild); // 预留右指针在栈中

65 }; } if (p->leftchild!= NULL) p = p->leftchild; // 进左子树 else S.Pop(p); // 左子树为空

66 利用栈的后序遍历非递归算法 b d a e c al bl al br al dl br al dr br al br al al ar el cl ar er cl ar cl ar cr ar ar

67 利用栈的后序遍历非递归算法在后序遍历过程中所用栈的结点定义 template <class T> ptr tag{l,r} struct stknode { BinTreeNode<T> *ptr; // 树结点指针 enum tag {L, R}; // 退栈标记 stknode (BinTreeNode<T> *N = NULL) : ptr(n), tag(l) { } // 构造函数 }; tag = L, 表示从左子树退回还要遍历右子树 ; tag = R, 表示从右子树退回要访问根结点

68 后序遍历的非递归算法 template <class T> void BinaryTree<T>:: PostOrder (void (*visit) (BinTreeNode<T> *t) { Stack<stkNode<T>> S; stknode<t> w; BinTreeNode<T> * p = root; //p 是遍历指针 do { while (p!= NULL) { w.ptr = p; w.tag = L; S.Push (w); p = p->leftchild; } int continue1 = 1; // 继续循环标记, 用于 R

69 }; while (continue1 &&!S.IsEmpty ()) { S.Pop (w); p = w.ptr; switch (w.tag) { // 判断栈顶的 tag 标记 case L: w.tag = R; S.Push (w); continue1 = 0; p = p->rightchild; break; case R: visit (p); break; } } } while (!S.IsEmpty ()); // 继续遍历其他结点 cout << endl;

70 层次序遍历二叉树的算法层次序遍历二叉树就是从根结点开始, 按层次逐层遍历, 如图 : - + / a * e f b - c d 遍历顺序

71 算法是非递归的这种遍历需要使用一个先进先出的队列, 在处理上一层时, 将其下一层的结点直接进到队列 ( 的队尾 ) 在上一层结点遍历完后, 下一层结点正好处于队列的队头, 可以继续访问它们

72 Q a a 进队 b d a e c Q Q Q b c c d d e a 出队, 访问 a b 进队 c 进队 b 出队, 访问 b d 进队 c 出队, 访问 c e 进队 Q e d 出队, 访问 d Q e 出队, 访问 e

73 层次序遍历的 ( 非递归 ) 算法 template <class T> void BinaryTree<T>:: levelorder (void (*visit) (BinTreeNode<T> *t)) { if (root == NULL) return; Queue<BinTreeNode<T> * > Q; BinTreeNode<T> *p = root; Q.EnQueue (p); while (!Q.IsEmpty ()) { Q.DeQueue (p); visit(p);

74 }; } if (p->leftchild!= NULL) Q.EnQueue (p->leftchild); if (p->rightchild!= NULL) Q.EnQueue (p->rightchild);

75 二叉树的计数二叉树遍历的结果是将一个非线性结构中的数据通过访问排列到一个线性序列中前序序列 :a b d c e 特点是第一个访问的 a 一定是树根, 只要左子树非空, 后面紧跟的 b 一定是根的左子女, a 中序序列 :b d a e c 特点是树根 a 把整个中序分成两部分, a 左侧子序列是根的左子树上 b c 的结点数据, 右侧子序列是根的右子树上的结点数据 d e

76 ! 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树例, 前序序列 { A B H F D E C K G } 和中序序列 { H B D F A E K C G }, 构造二叉树过程如下 : A A HBDF EKCG B EKCG H DF

77 A A B EKCG B E H F H F KCG D D A B E H F C D K G

78 如果前序序列固定不变, 给出不同的中序序列, 可得到不同的二叉树

79 固定前序排列, 选择所有可能的中序排列, 可能构造多少种不同的二叉树?

80 例如, 有 3 个数据 { 1, 2, 3 }, 可得 5 种不同的二叉树它们的前序排列均为 123, 中序序列可能是 321,231,213,132, 前序序列为 123, 中序序列为 312 的二叉树不存在

81 有 0 个, 1 个, 2 个, 3 个结点的不同二叉树如下 b 0 =1 b 1 =1 b 2 =2 b 3 =5 b 4 =14

82 !! )! ( n n n n n b C n n n 计算具有 n 个结点的不同二叉树的棵数 Catalan 函数 b i b n-i n i i n i n b b b C b C b

83 第四章树二叉树森林树的基本概念二叉树定义主要特征存储结构 : 顺序链式遍历线索二叉树 : 基本概念构造树森林存储结构 : 树森林与二叉树的转换遍历 : 树森林应用二叉排序树 Huffman 树和哈夫曼编码

84 线索化二叉树 (Threaded Binary Tree) 通过二叉树的遍历, 可将二叉树中所有结点的数据排列在一个线性序列中, 可以找到某数据在这种排列下它的前驱和后继希望不必每次都通过遍历找出这样的线性序列只要事先做预处理, 将某种遍历顺序下的前驱后继关系记在树的存储结构中以后就可以高效地找出某结点的前驱后继

85 线索 (Thread) pred leftchild data rightchild succ pred b pred a pred succ d e c succ succ pred succ B C succ succ pred pred pred succ D A root E 增加前驱 Pred 指针和后继 Succ 指针的二叉树

86 这种设计的缺点 : 是每个结点增加两个指针, 当结点数很大时存储消耗较大改造树结点 : 将 pred 指针和 succ 指针压缩到 leftchild 和 rightchild 的空闲指针中, 并增设两个标志 ltag 和 rtag, 指明指针是指示子女还是前驱 / 后继后者称为线索 leftchild ltag data rtag rightchild ltag ( 或 rtag) = 0, 表示相应指针指示左子女 ( 或右子女结点 ); ltag ( 或 rtag) = 1, 表示相应指针为前驱 ( 或后继 ) 线索

87 线索化二叉树的链表表示 leftchild ltag data rtag rightchild a 0 A 0 root pred b pred succ d pred e c succ succ B 1 0 C succ 0 1 pred pred 1 D 1 1 E 1 succ

88 通过中序遍历建立中序线索化二叉树

89 pre == NULL root current 0 A 0 0 B 0 0 C 0 0 D 0 0 E 0

90 pre == NULL current root 0 A 0 1 B 0 0 C 0 0 D 0 0 E 0

91 root pre 0 A 0 1 B 0 0 C 0 current 1 D 0 0 E 0

92 current root 0 A 0 1 B 0 0 C 0 pre 1 D 1 0 E 0

93 pre root 0 A 0 1 B 0 0 C 0 current 1 D 1 1 E 0

94 root 0 A 0 current 1 B 0 0 C 0 pre 1 D 1 1 E 1

95 root 0 A 0 后处理 pre 1 B 0 0 C 1 1 D 1 1 E 1

96 template <class T> void ThreadTree<T>::createInThread () { ThreadNode<T> *pre = NULL; // 前驱结点指针 if (root!= NULL) { // 非空二叉树, 线索化 createinthread (root, pre); // 中序遍历线索化二叉树 pre->rightchild = NULL; pre->rtag = 1; // 后处理中序最后一个结点 } }

97 template <class T> void ThreadTree<T>:: createinthread (ThreadNode<T> *current, ThreadNode<T> *& pre) { // 通过中序遍历, 对二叉树进行线索化 if (current == NULL) return; createinthread (current->leftchild, pre); // 递归, 左子树线索化 if (current->leftchild == NULL) { // 建立当前结点的前驱线索 current->leftchild = pre; current->ltag = 1; }

98 if (pre!= NULL && pre->rightchild == NULL) // 建立前驱结点的后继线索 { pre->rightchild = current; pre->rtag = 1; } } pre = current; // 前驱跟上, 当前指针向前遍历 createinthread (current->rightchild, pre); // 递归, 右子树线索化

99 寻找当前结点在中序下的后继 D B E A C F if (current->rtag ==1) 后继为 current->rightchild else //current->rtag == 0 后继为当前结点右子树的中序下的第一个结点 G H I J K

100 寻找当前结点在中序下的前驱 A D B G E C H F if (current->ltag == 1) 前驱为 current->leftchild else //current->ltag == 0 前驱为当前结点左子树 I 中序下的最后一个结点 J K L

101 前序线索化二叉树在前序线索化二叉树中寻找当前结点的后继 B D A E 前序序列 C A B D C E p->ltag==1? 前驱线索 = 左子女无后继 p->rightchild == NULL? = 后继为 p->rightchild 后继为 p->leftchild

102 在后序线索化二叉树中寻找当前结点的后继 B D A E C 后序序列 D B E C A 后序线索化二叉树 p->rtag==1? 后继线索 = 右子女后继为 p->rightchild q=p->parent q==null? q->rtag==1 q->rightchild==p? = = 无后继后继为 q 后继为 q 的右子树中后序下第一个结点

Microsoft PowerPoint - 6-.pptx

Microsoft PowerPoint - 6-.pptx 基本概念树的存储结构树的线性表示树的遍历二叉树二叉树的存储表示二叉树的各种遍历线索化二叉树堆计算二叉树的数目二叉树的应用 : 霍夫曼树和霍夫曼编码本章小结 6.1 基本概念树是由一个或多个结点组成的有限集 T, 它满足下面两个条件 : 有一个特定的结点, 称之为根结点 ; 其余的结点分成 m (m 0) 个互不相交的有限集 T 0, T 1,, T m-1 其中每个集合又都是一棵树,