第六章 树与森林 树和森林的概念 二叉树 (Binary Tree) 二叉树的表示 二叉树遍历 (Binary Tree Traversal) 堆 ( Heap ) 树与森林 (Tree & Forest) 二叉树的计数 霍夫曼树 (Huffman Tree)

6.3.4、二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下：

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

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

计算具有n个结点的不同二叉树的棵数 Catalan函数 例如，具有4个结点的不同二叉树

6.4 线索化二叉树 6.4 线索化二叉树 6.4.1 线索 用于指示前驱与后继的指针，加了线索的二叉树叫线索化二叉树

6.5 堆 ( Heap ) 6.5.1 堆的定义 定义 最小堆:任一节点的关键码均小于或等于它的左、右子女的关键码，位于堆顶（即完全二叉树根结点位置）的结点的关键码是整个集合中最小的。 最大堆:任一节点的关键码均大于或等于它的左、右子女的关键码，位于堆顶（即完全二叉树根结点位置）的结点的关键码是整个集合中最大的。

图例

最小堆的类定义 template <class Type> class MinHeap : public MinPQ <Type> { public: MinHeap ( int maxSize ) const; MinHeap ( Type arr[ ], int n ); ~MinHeap ( ) { delete [ ] heap; } const MinHeap<Type> & operator = ( const MinHeap &R ); int Insert ( const Type &x ); int RemoveMin ( Type &x ); int IsEmpty ( ) const { return CurrentSize == 0; }

int IsFull ( ) const { return CurrentSize == MaxHeapSize; } void MakeEmpty ( ) { CurrentSize = 0; } private: enum { DefaultSize = 10 }; Type *heap; int CurrentSize; int MaxHeapSize; void FilterDown ( int i, int m ); void FilterUp ( int i ); }

6.5.2 堆的建立 方法一：通过构造函数MinHeap建空堆 template <class Type> MinHeap <Type>:: MinHeap ( int maxSize ) { //根据给定大小maxSize,建立堆对象 MaxHeapSize = DefaultSize < maxSize ? maxSize : DefaultSize; //确定堆大小 heap = new Type [MaxHeapSize]; //创建堆空间 CurrentSize = 0; //初始化 } MinHeap ( Type arr[ ], int n ) { //根据给定数组中的数据和大小,建立堆对象

方法二：复制一个记录数组并对其加以调整形成一个堆 算法： template <class Type> MinHeap <Type>:: MinHeap ( Type arr[ ], int n ) { //根据给定数组中的数据和大小,建立堆对象

MaxHeapSize = DefaultSize < n ? n : DefaultSize; heap = new Type [MaxHeapSize]; heap = arr; //数组传送 CurrentSize = n; //当前堆大小 int currentPos = (CurrentSize-2)/2; //最后非叶 while ( currentPos >= 0 ) { //从下到上逐步扩大,形成堆 FilterDown ( currentPos, CurrentSize-1 ); //从currentPos开始,到CurrentSize为止, 调整 currentPos--; }

template <class Type> void MinHeap<Type>:: FilterDown ( const int start, const int EndOfHeap ) { int i = start, j = 2*i+1; // j 是 i 的左子女 Type temp = heap[i]; while ( j <= EndOfHeap ) { if ( j < EndOfHeap && heap[j].key > heap[j+1].key ) j++; //两子女中选小者 if ( temp.key <= heap[j].key ) break; else { heap[i] = heap[j]; i = j; j = 2*j+1; } } heap[i] = temp;

图例 自下向上逐步调整为最小堆

6.5.3 堆的插入与删除 插入 算法： template <class Type> int MinHeap<Type>:: Insert ( const Type &x ) { //在堆中插入新元素 x if ( CurrentSize == MaxHeapSize ) //堆满 { cout << "堆已满" << endl; return 0; } heap[CurrentSize] = x; //插在表尾 FilterUp (CurrentSize); //向上调整为堆 CurrentSize++; //堆元素增一 return 1; }

template <class Type> void MinHeap<Type>:: FilterUp ( int start ) { //从 start 开始,向上直到0,调整堆 int j = start, i = (j-1)/2; // i 是 j 的双亲 Type temp = heap[j]; while ( j > 0 ) { if ( heap[i].key <= temp.key ) break; else { heap[j] = heap[i]; j = i; i = (i -1)/2; } } heap[j] = temp;

图例 最小堆的向上调整

删除 template <class Type> int MinHeap <Type>:: RemoveMin ( Type &x ) { if ( !CurrentSize ) { cout << “ 堆已空 " << endl; return 0; } x = heap[0]; //最小元素出队列 heap[0] = heap[CurrentSize-1]; CurrentSize--; //用最小元素填补 FilterDown ( 0, CurrentSize-1 ); //从0号位置开始自顶向下调整为堆 return 1; }

6.6 树与森林 6.6.1 树的存储表示 1、广义表表示 树的广义表表示 (结点的utype域没有画出)

2、双亲表示

3、左子女-右兄弟表示法 图例 第一种解决方案 第二种解决方案 data child1 child2 child3 childd firstChild nextSibling 树的左子女-右兄弟表示

用左子女-右兄弟表示实现的树的类定义 template <class Type> class Tree; template <class Type> class TreeNode { friend class<Type> Tree; private: Type data; TreeNode<Type> *firstChild, *nextSibling; TreeNode ( Type value=0, TreeNode<Type> *fc=NULL, TreeNode<Type> *ns=NULL ) : data (value), firstChild (fc), nextSibling (ns) { } };

template <class Type> class Tree { public: Tree ( ) { root = current = NULL; } int Root(); int leftchild(); int RightSibling(); void RemovesubTree(TreeNode<Type> *p); void FindParent(TreeNode<Type> *t,TreeNode <Type> *p); …… private: TreeNode<Type> *root, *current; void PreOrder ( ostream & out, TreeNode<Type> *p ); int Find ( TypeNode<Type> *p, Type target ); void RemovesubTree ( TreeNode<Type> *p ); int FindParent ( TreeNode<Type> *t, *p ); }

6.6.2 森林与二叉树的转换 森林与二叉树的对应关系

(1) 森林转化成二叉树的规则  若F为空，即n = 0，则 对应的二叉树B为空二叉树。  若F不空，则 对应二叉树B的根root (B)是F中第一棵树T1的根root (T1)； 其左子树为B (T11, T12, …, T1m)，其中，T11, T12, …, T1m是root (T1)的子树； 其右子树为B (T2, T3, …, Tn)，其中，T2, T3, …, Tn是除T1外其它树构成的森林。

(2) 二叉树转换为森林的规则  如果B为空，则 对应的森林F也为空。  如果B非空，则 F中第一棵树T1的根为root； T1的根的子树森林{ T11, T12, …, T1m }是由 root 的左子树 LB 转换而来，F 中除了 T1 之外 其余的树组成的森林{ T2, T3, …, Tn } 是由 root 的右子树 RB 转换而成的森林。

6.6.3 树的遍历 1、深度优先遍历 树的二叉树表示

(1) 树的先根次序遍历的递归算法 template <class Type> void Tree<Type>:: PreOrder ( ) { if ( !IsEmpty ( ) ) { visit ( ); //访问根结点 TreeNode<Type> *p = current; //暂存当前结点 int i = FirstChild ( ); //当前结点转到长子 while (i) { PreOrder ( ); i = NextSibling ( ); } //递归先根遍历各棵子树 current = p; //递归完恢复当前结点 }

(2) 树的后根次序遍历的递归算法 template <class Type> void Tree<Type>:: PostOrder ( ) { if ( !IsEmpty ( ) ) { TreeNode<Type> *p = current; //暂存当前结点 int i = FirstChild ( ); //当前结点转到长子 while (i) { PostOrder ( ); i = NextSibling ( ); } //递归后根遍历各棵子树 current = p; //递归完恢复当前结点 visit ( ); //访问根结点 }

2、广度优先遍历 按层次次序遍历树的算法 template <class Type> void Tree<Type>:: LevelOrder ( ) {

Queue<TreeNode<Type>*> Qu ( DefaultSize ); if ( ! IsEmpty ( ) ) { TreeNode<Type> *p = current; Qu.EnQueue ( current ); //根进队列 while ( !Qu.IsEmpty ( ) ) { //队列不空 current = Qu.DeQueue ( ); visit ( ); //退出队列,访问 FirstChild ( ); //转向长子 while ( !IsEmpty ( ) ) //结点指针不空 { Qu.EnQueue ( current ); NextSibling ( ); } } current = p;

6.6.4 森林的遍历 (1) 先根次序遍历的规则： 若森林F为空, 返回；否则 访问F的第一棵树的根结点； 先根次序遍历第一棵树的子树森林； 先根次序遍历其它树组成的森林。 森林的二叉树表示

(2) 后根次序遍历的规则： 若森林F为空，返回；否则 后根次序遍历第一棵树的子树森林； 后根次序遍历其它树组成的森林； 访问F的第一棵树的根结点。 森林的二叉树表示

森林的遍历 (3) 广度优先遍历(层次序遍历) ： 若森林F为空，返回；否则 依次遍历各棵树的根结点； 依次遍历各棵树根结点的所有子女； 依次遍历这些子女结点的子女结点。 森林的二叉树表示

6.7 霍夫曼树 (Huffman Tree) 6.7.1 路径长度 (Path Length) 两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。 具有不同路径长度的二叉树

n个结点的二叉树的路径长度不小于下述数列前n项的和，即 其路径长度最小者为 (完全二叉树满足这个条件） 6.7.2 霍夫曼树 带权路径长度 ( Weighted Path Length, WPL ) 树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。

具有不同带权路径长度的扩充二叉树 霍夫曼树 带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。

霍夫曼算法 (1) 由给定的n个权值{w0, w1, w2, …, wn-1}，构造具有n棵扩充二叉树的森林F = {T0, T1, T2, …, Tn-1}，其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到F中仅剩下一棵树为止： ① 在F中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在F中删去这两棵二叉树。 ③ 把新的二叉树加入F。

霍夫曼树的构造过程

扩充二叉树的类定义 template <class Type> class ExtBinTree; template <class Type> class Element { friend class ExtBinTree; private: Type data; Element<Type> *leftChild, *rightChild; }; template <class Type> class ExtBinaryTree { public: ExtBinTree ( ExtBinTree<Type> &bt1, ExtBinTree<Type> &bt2 ) {

root→leftChild = bt1.root; root→rightChild = bt2.root; root→data.key = bt1.root→data.key + bt2.root→data.key; } protected: const int DefaultSize = 20; Element <Type> *root; //扩充二叉树的根 MinHeap < ExtBinTree <Type> > hp; //最小堆

建立霍夫曼树的算法 template <class Type> void HuffmanTree (Type *fr, int n, ExtBinTree <Type> & newtree ) { ExtBinTree <Type> & first, & second; ExtBinTree <Type> Node[DafualtSize]; if ( n > DefaultSize ) { cout << “大小 n ” << n << “超出了数组边界 ” << endl; return; } for ( int i = 0; i < n; i++ ) { Node[i].root→data.key = fr[i]; Node[i].root→leftChild = Node[i].root→rightChild = NULL; } //传送初始权值

hp.MinHeap ( Node, n ); for ( int i = 0; i < n-1; i++ ) { //建立霍夫曼树的过程，做n-1趟 hp.DeleteMin ( first ); //选根权值最小的树 hp.DeleteMin ( second ); //选根权值次小的树 newtree = new ExtBinTree <Type> ( first, second ); //建新的根结点 hp.Insert ( newtree ); //形成新树插入 } return hp.RemoveMin ( newtree );

字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 6 .7.3 霍夫曼编码 主要用途是实现数据压缩。 设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }。

化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立霍夫曼树。左分支赋 0，右分支赋 1，得霍夫曼编码(变长编码)。 A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于 霍夫曼树的带权路径长 度WPL。 霍夫曼编码是一种无 前缀编码。解码时不会 混淆。 霍夫曼编码树