Microsoft PowerPoint - Chapter7.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chapter7.ppt"

宣创邢
7 years ago
Views:

1 第 7 章树和二叉树 7.1 树的概念和性质 7.2 二叉树的概念与性质 7.3 二叉树的存储结构 7.4 二叉树的遍历 7.5 二叉树的其他操作算法 7.6 线索二叉树 7.7 树的存储结构与算法 7.8 Huffman 树与 Huffman 编码 7.9 树与等价类

2 树的定义 : 树和森林的概念是 n(n 0) 个结点的有限集合 T, 对于任意一棵非空树, 它满足 : (1) 有且仅有一个特定的称为根的结点 (2) 当 n>1 时, 其余结点可分为 m(m>0) 个互不相交的有限集 T 1,T 2,.,T m, 其中每个集合本身又是一棵树, 称为根的子树显然 : 上述树的定义是一个递归定义

3 树的表示方法 : A B C D ( A( B(E(K,L), F ), C(G), D(H(M), I, J) ) 广义表 E F G H I J K L M 树形表示凹入表 E K L F B A C G C M I D J 文氏图

4 树的基本术语 : 结点 (node) 结点的度 (degree) 结点的子树个数分支 (branch) 结点度不为 0 的结点叶 (leaf) 结点度为 0 的结点孩子 (child) 结点某结点子树的根结点双亲 (parent) 结点某个结点是其子树之根的双亲兄弟 (sibling) 结点具有同一双亲的所有结点祖先 (ancestor) 结点若树中结点 k 到 k s 存在一条路径, 则称 k 是 k s 的祖先子孙 (descendant) 结点若树中结点 k 到 k s 存在一条路径, 则称 k s 是 k 的子孙结点所处层次 (level) 根结点的层数为 1,, 其余结点的层数为双亲结点的层数加 1 树的高度 (depth) 树中结点的最大层数树的度 (degree)

5 有序树无序树森林子树的次序不能互换子树的次序可以互换互不相交的树的集合

6 树的基本操作 1 初始化 (InitTree) 2 建立树 (CreateTree) 3 求指定结点的双亲结点 ( Parent) 4 求指定结点的左孩子结点 (LeftChild) 5 求指定结点的右兄弟结点 (RightSibling) 6 将一棵树插入到另一树的指定结点下作为它的子树 (InsertChild) 7 删除指定结点的某一子树 (DeleteChild) 8 树的遍历 (TraverseTree)

7 二叉树的定义 7. 2 二叉树的概念与性质一棵二叉树是 n (n 0) 个结点的一个有限集合, (1) 该集合或者为空, (2) 或者是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成二叉树的五种不同形态

8 问题 : 试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态 8

9 二叉树的性质性质 1 若二叉树的层次从 1 开始, 则在二叉树的第 i 层最多有 2 i-1 个结点 (i 1) 证明 : i = 1 时, 有 2 i-1 = 2 0 =1, 成立假定 : i = k 时性质成立 ; 当 i = k+1 时, 第 k+1 层的结点至多是第 k 层结点的两倍, 即总的结点个数至多为 2 2 k-1 = 2 k 故命题成立

10 性质 2 高度为 k 的二叉树最多有 2 k -1 个结点 (k 1) 证明 : 仅当每一层都含有最大结点数时, 二叉树的结点数最多, 利用性质 1 可得二叉树的结点数至多为 : k-1 = 2 k - 1

11 性质 3 对任何一棵二叉树, 如果其叶结点个数为 n 0, 度为 2 的非叶结点个数为 n 2, 则有 n 0 =n 2 +1 证明 : 1 结点总数为度为 0 的结点加上度为 1 的结点再加上度为 2 的结点 : n = n 0 + n 1 + n 2 2 另一方面, 二叉树中一度结点有一个孩子, 二度结点有二个孩子, 根结点不是任何结点的孩子, 因此, 结点总数为 : n = n 1 + 2n 两式相减, 得到 : n 0 = n 2 + 1

12 定义 1 满二叉树 (Full Binary Tree) 一棵深度为 k 且有 2 k -1 个结点的二叉树满二叉树的特点 : 每一层都取最大结点数定义 2 完全二叉树 (Complete Binary Tree) 高度为 k, 有 n 个结点的二叉树是一棵完全二叉树, 当且仅当其每个结点都与高度为 k 的满二叉树中层次编号 1--n 相对应

13 完全二叉树的特点 --- (1) 除最后一层外, 每一层都取最大结点数, 最后一层结点都有集中在该层最左边的若干位置 (2) 叶子结点只可能在层次最大的两层出现 (3) 对任一结点, 若其右分支下的子孙的最大层次为 L, 则其左分支下的子孙的最大层次为 L 或 L+1

14 性质 4 具有 n 个结点的完全二叉树的高度证明 : 为 log 2 n +1 设深度为 k, 根据二叉树性质二知 : 2 k-1-1<n 2 k -1, 即 : 2 k-1 n < 2 k, 于是有 : k 1 log Qk为整数, 取 k 2 n k = n log 2 + 1

15 性质 5 如果将一棵有 n 个结点的完全二叉树自顶向下, 同一层自左向右连续给结点编号 1, 2,, n- 1,n, 然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为 i 的结点为结点 i (1 i n) 则有以下关系 : 若 i == 1, 则 i 无双亲若 i > 1, 则 i 的双亲为 i /2 若 2*i <= n, 则 i 的左孩子为 2*i; 否则,i, 无左孩子, 必定是叶结点, 二叉树中 i> n/2 的结点必定是叶结点若 2*i+1 <= n, 则 i 的右孩子为 2*i+1 +1, 否则,i, 无右孩子若 i 为奇数, 且 i 不为 1, 则其左兄弟为 i-1, 否则无左兄弟 ; 若 i 为偶数, 且小于 n, 则其右兄弟为 i+1, 否则无右兄弟 i 所在层次为 log 2 i +1

17 7.3 二叉树的存储一. 顺序存储结构指用一组连续的存储单元存储二叉树的结点数据要求 : 必须把二叉树中的所有结点, 按照一定的次序排成为一个线性序列, 结点在这个序列中的相互位置能反映出结点之间的逻辑关系对于完全二叉树和满二叉树, 结点的层次序列足以反映整个二叉树的结构对于一般二叉树, 则需要通过添加虚结点将其扩充为完全二叉树

18 由于一般二叉树必须仿照完全二叉树那样存储, 可能会浪费很多存储空间, 单支树就是一个极端情况单支树若要在树中经常插入和删除结点时, 由于要大量移动结点, 显然在这种情况下采用顺序方式并不可取

19 二. 链式存储结构由于二叉树的每个结点最多有左右两个孩子, 因此在采用链式存储表示时, 每个结点至少需要包含三个域 : 数据域和左右指针域 lchild Data rchild 一个二叉树中所有这种形式的结点, 再加上一个指向根结点的头指针, 就构成了此二叉树的链式存储结构, 称之为二叉链表二叉链表如果想能够找到父结点, 则可以增加一个指向父结点的指针域, 则构成三叉链表

20 二叉树链表表示的示例

21 二叉链表结构定义 : template <class T> struct BiNode { T data; // 结点数据 BiNode<T> *lchild; // 左孩子的指针 BiNode<T> *rchild; // 右孩子的指针 };

22 二叉树的类定义 template <class T> class BiTree{ BiNode<T>* root; // 根指针 public: BiTree() { root=null; } BiTree(vector<T> &pre); BiTree<T>::BiTree(const BiTree<T> &tree); ~BiTree(); void PreOrder(); void InOrder(); void PostOrder(); void LevelOrder(); int Height(); BiNode<T> *Search(T e); BiNode<T> *SearchParent(BiNode<T>*child); };

23 6. 3 二叉树的遍历遍历二叉树按某条搜索路径访问树中每一个结点, 使得每个结点均被访问一次, 且仅被访问一次六种访问次序 (N-- 访问根,L-- 遍历左子树,R-- 遍历右子树 ): NLR LNR LRN NRL RNL RLN 23

24 若限定按先左后右的次序遍历, 则有如下三种遍历次序 : 先序遍历 :NLR 中序遍历 :LNR 后序遍历 :LRN

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

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

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

28 先中后序遍历的流程

29 中序遍历的递归算法 : template <class T> void BiTree<T>::InOrder(BiNode<T> *p) { if(p==null) return; InOrder(p->lchild); cout << p->data; InOrder(p->rchild); } template <class T> void BiTree<T>::InOrder() { InOrder(root) }

30 中序遍历二叉树的递归过程图解

31 层序遍历层序遍历二叉树算法的框架是若二叉树为空, 则空操作 ; 将根结点入队如队列不空, 循环 : - 做出队操作, 队头元素作为当前结点 ; - 将当前结点的左右孩子入队最后, 出队序列就是层序遍历序列遍历结果 : - + / a * e f b - c d

32 二叉树的层序遍历算法 template <class T> void BiTree<T>::LevelOrder() { queue<binode<t> *> Q; // Q 为指针队列 if(!root ) return; Q.push(root); while(!q.empty()) { BiNode<T> *p= Q.pop(); cout<<p->data; if(p->lchild) Q.push(p->lchild); if(p->rchild) Q.push(p->rchild); } }

33 7.4.3 二叉树的构造和析构算法二叉树的建立给定一棵二叉树的结点的值的序列, 建立该二叉树对应的二叉链表若给定一棵二叉树的结点的先序序列, 能建立一棵对应的二叉树吗? 33

34 1 由单个遍历序列构造二叉树 template <class T> BiNode<T> *BiTree<T>::CreateByPre() { e=getchar(); if(e=='*') return NULL; p=new BiNode<T>; p->data=e; p->lchild=createbypre(); p->rchild=createbypre(); return p; }

35 1 由单个遍历序列构造二叉树 template <class T> BiNode<T> *BiTree<T>::CreateByPre(vector<T> &pre,int &i) { e=pre[i]; i++; // 提取当前数据 if(e=='*') return NULL; p=new BiNode<T>; p->data=e; p->lchild=createbypre(pre, i); p->rchild=createbypre(pre,i); return p; } template <class T> BiTree<T>::BiTree(vector<T> &pre) { i=0; root=createbypre(pre,i); }

36 2 由二个遍历序列构造二叉树已知 : 先序序列 { ABHFDECKG },} 中序序列 { HBDFAEKCG }, 试构造相应的二叉树

37 性质 : 一棵二叉树的先序序列和中序序列可以唯一的确定这棵二叉树. 用归纳法证明 : 1 当 n = 1 时, 结论显然成立 ; 2 假定当 n <= k 时, 结论成立 ; 3 当 n = k + 1 时, 假定先序序列和中序序列分别为 : {a 1,,a k+1 } 和 {b 1,,b k+1 }

38 如中序序列中与先序序列中的 a 1 相同的元素 : 为 b j : j = 1 时, 二叉树无左子树, 由 {a 2,,a k+1 } 和 {b 2,,b k+1 } 可以唯一的确定二叉树的右子树 ; j = k+1 时, 二叉树无右子树, 由 {a 2,,a k+1 } 和 {b 1,,b k } 可以唯一的确定二叉树的左子树 ; 如 2<= j <=k, 则子序列 {a 2,,a j } 和 {b 1,,b j-1 } 唯一的确定二叉树的左子树 ; 子序列 {a j+1,,a k+1 } 和 {b j+1,,b k+1 } 唯一的确定二叉树的右子树.

39 template <class T> BiNode<T>* BiTree<T>::CreateByPreMid(vector<T> &pre, vector<t> &mid, int ipre, int imid, int n) { if(n==0) return NULL; p = new BiNode<T>; p->data = pre[ipre]; for(i=0; i<n; i++) if( pre[ipre]==mid[imid+i] ) break; p->lchild = CreateByPreMid(pre, mid, ipre+1, imid, i); p->rchild = CreateByPreMid(pre, mid, ipre+i+1,imid+i+1,n-i-1); return p; }

40 3 拷贝构造函数 template <class T> BiNode<T> * BiTree<T>::Copy(BiNode<T> *p) { if(p==null) return NULL; newp=new BiNode<T>; newp->data=p->data; newp->lchild= Copy(p->lchild); newp->rchild= Copy(p->rchild); return newp; } template <class T> BiTree<T>::BiTree(const BiTree<T> &tree) { root=copy(tree.root); }

41 4 析构函数 template <class T> void BiTree<T>::Free(BiNode<T> *p) { if(p==null) return; Free( p->lchild ); Free( p->rchild ); delete p; // 释放根结点 } template <class T> // 析构函数 BiTree<T>::~BiTree() { if(root) Free(root); }

42 7.5 二叉树的其他操作算法计算二叉树的结点数计算二叉树的高度根据关键值查找结点查找结点的父结点 42

43 例 1: 计算二叉树结点数的算法 template <class T> int BiTree<T>::Count(BiNode<T> *p) { if( p==null ) return 0; left= Count(p->lchild); right=count(p->rchild); return 1+left+right; }

44 例 2: : 求二叉树的高度 template <class T> int BiTree<T>::Height( BiNode<T> *t ) { if(t==null) return 0; } left =Height( t->lchild ); right=height( t->rchild ); if(left>right) return left+1; return right+1;

45 方法二 : 二叉树的高度为树中的结点的层次最大值 template <class T> void BiTree<T>::Height( BiNode<T> *t,int level, int& depth ) if (t){ if( level>depth) depth=level; Height(t->lchild, level+1, depth); Height(t->rchild, level+1, depth); } }

46 例 3: : 在二叉树中查找具有给定值的结点 template <class T> BiNode<T> *BiTree<T>::Search(BiNode<T> *t, T e) { if ( t == NULL) return NULL; if ( t->data == e ) return t; p= Search(t->lchild); if( p ) return p; } return Search( t->rchild) ;

47 练习题 : 设计一个算法, 在二叉树中查找关键值为 key 的结点的父结点 template <class T> BiNode<T> *BiTree<T>:: SearchParent( BiTree t, T key){ if( t == NULL) return NULL; if( t->lchild && t->lchild->data==key ) return t; if( t->rchild && t->rchild->data==key) return t; p= SearchParent(t->lchild, key); if( p ) return p; } return SearchParent( t->rchild, key) ;

48 例 4: : 查找指定结点的父结点 template <class T> BiNode<T> *BiTree<T>::SearchParent(BiNode<T> *t, BiNode<T>*child) { if( t==null child==null) return NULL; if(t->lchild==child t->rchild==child) return t; } p= SearchParent(t->lchild, child); if( p ) return p; return SearchParent(t->rchild, child) );

49 7.6 线索二叉树二叉链表结构的局限性 : 对于某个结点只能找到其左右孩子, 而不能直接得到该结点在某种遍历序列中的前趋或后继结点要想得到该信息只能通过遍历的动态过程才行怎样保存遍历过程中得到的信息呢? 解决方法 : 可利用二叉链表结点结构中的空指针域, 在空指针域中存放结点在某种遍历次序下的前驱和后继结点信息, 这种附加的指针称为线索为避免混淆, 需改变结点结构, 即增加两个标志域 49

50 enum BiThrNodePointType{LINK, THREAD} ; template <class T> struct BiThrNode{ BiThrNodePointType ltype, rtype; T data; BiThrNode<T> *lchild,*rchild; }; 标志位为 0, 表示指针指向孩子结点, 标志位为 1, 表示指针为线索

51 线索二叉树类 : template <class T> class InBiThrTree { BiThrNode<T> *root; public: BinThrTree(); ~BinThrTree(); void InThreaded(); // 中序线索化 };

52 有关概念 : 以上面结构所构成的二叉链表作为二叉树的存储结构, 叫做线索链表指向结点前驱或后继的指针叫做线索加上线索的二叉树叫线索二叉树线索化 : 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化 52

54 中序线索二叉树

55 线索化的实现 : 如何实现线索化? 只要按该某种次序 ( 先序中序后序 ) 遍历二叉树, 在遍历过程中, 用线索取代空指针如何确立结点之间的前趋与后继关系? 若指针 p 指向当前正在访问的结点, 可另外附设一个指针 pre, 并始终保持指针 pre 指向当前访问的指针 p 所指结点的前驱 55

56 // 中序线索化算法 : template <class T> void InBiThrTree<T>::InThreading( BiThrNode<T> *p, BiThrNode<T> * &pre) if( p ){ InThreading(p->lchild); // 递归左子树线索化 if(!p->lchild ) { // 没有左孩子 p->ltype=thread ; // 前驱线索 p->lchild=pre; // 左孩子指针指向前驱 } if( pre &&!pre->rchild ){ // 前驱没有右孩子 pre->rtype=thread ; // 后继线索 pre->rchild=p; // 前驱右孩子指针指向后继 } pre = p; // 保持 pre 指向 p 的前驱 InThreading(p->rchild, pre); // 递归右子树线索化 } }

57 template <class T> void InBiThrTree<T>::InThreading() { if(root==null) return; pre = NULL; InThreaded(root, pre); pre->rtype=thread; // 遍历序列中首结点的前驱为 NULL } pre->rchild=null; // 中序序列尾结点的后继为 NULL

58 问题 : 设计一个算法, 判断一棵给定的二叉树的中序遍历结点序列是否为非递减有序. 58

59 中序线索二叉树中, 查找指定结点 *p 的中序后继结点 1 若 *p 的右子树为空, 则 p->rchild 为右线索, 直接指向 *p 的中序后继结点 2 若 *p 的右子树非空, 则 *p 的中序后继必是其右子树中第一个遍历到的结点, 也就是从 *p 的右孩子开始, 沿左指针链往下查找, 直到找到一个没有左孩子的结点为止

60 对中序线索二叉树进行中序遍历的算法 : template <class T> void InBiThrTree<T>::Travese() { p=root; if(!p ) return; while( p ){ while( p->ltype==link ) p = p->lchild; cout<< p-data; while( p->rtype == THREAD &&!p->rchild){ p = p->rchild; cout<< p->data; } p = p->rchild; } }

61 中序线索二叉树中, 查找指定结点 *p 的中序前驱结点 1 若 *p 的左子树为空, 则 p->lchild 为左线索, 直接指向 *p 的中序前驱结点 2 若 *p 的左子树非空, 则从 *p 的左孩子出发, 沿右指针链往下查找, 直到找到一个没有右孩子的结点为止

62 后序线索二叉树中, 查找指定结点 *p 的后序后继结点分四种情况 : 1 若 *p 是根, 则其后继为空 ; 2 若 *p 是其双亲的右孩子, 则 *p 的后继就是其双亲结点 ; 3 若 *p 是其双亲的左孩子, 但 *p 无右兄弟时, 则 *p 的后继就是其双亲结点 ; 4 若 *p 是其双亲的左孩子, 且有右兄弟时, 则 *p 的后继是其双亲的右子树中第一个后序遍历到的结点, 它是该子树的最左下的叶结点

63 4 求父结点的算法

64 *p 和 *parent 存在如下两种情形 :

65 template <class T> BiThrNode<T> *InBiThrTree<T>::GetParent(BiThrNode<T> *p) { if(!p p==root ) return NULL; for( parent=p; parent->rtype==link; ) parent=parent->rchild; parent=parent->rchild; // parent 是 *p 的最右下方结点的后继指针 if( parent && parent->lchild==p) // 猜测 *p 是否是左孩子 return parent; for( parent=p; parent->ltype==link; ) parent=parent->lchild; } parent=parent->lchild; // parent 是 *p 的最左下方结点的前驱指针 return parent; // parent 一定是 *p 的父指针

66 7.7 树的存储结构与算法多叉链表表示法广义表表示孩子表示法双亲表示法双亲 - 孩子链表示法二叉链表表示法 66

67 1. 多叉链表表示法若树的度为 K, 则在结点结构中设置 K 个孩子指针域, 使所有结点同构

68 树的多叉链表表示

69 2. 树的广义表表示

70 3. 孩子表示法 : 1 A A 2 3 B C B C D E F G H I J D E F G G I J ^ ^ ^ ^ ^ ^

71 4. 双亲表示法 :

72 5. 双亲 - 孩子链表示 : A 1 2 A 0 B B C D 3 C 1 7 E F G H I J D 1 E 2 F 2 G 3 G 4 I 4 J 4 ^ ^ ^ ^ ^ ^

73 6. 树的二叉链表存储表示法 data firstchild nextsibling

74 森林与二叉树的转换树森林与二叉树之间有一个自然的一一对应关系转换方法 : 树二叉树兄弟结点间加连接 ( 虚线 ) 让每个结点只与最左孩子保持联系, 与其余孩子的关系去掉森林二叉树森林树二叉树 ( 添加一个虚根结点 ) 去掉虚根结点 74

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

76 (1) 森林转化成二叉树的形式化规则 : 若 F={T 1,T 2,,T n } 是森林, 则 : 若 F 为空, 即 n = 0, 0 则对应的二叉树 B 为空二叉树若 F 不空, 则对应二叉树 B 的根 root (B) 是 F 中第一棵树 T 1 的根 root (T 1 ); 其左子树为 B (T 11, T 12,, T 1m ), 其中,T, 11, T 12,, T 1m 是 root (T 1 ) 的子树 ; 其右子树为 B (T 2, T 3,, T n ), 其中,T, 2, T 3,, T n 是除 T 1 外其它树构成的森林

77 二叉树到森林的转换转换方法 : 若某结点是其双亲的左孩子, 则把该结点的右孩子右孩子的右孩子, 都与该结点的双亲结点连接起来然后去掉所有双亲结点到右孩子的连线二叉树树仅当根结点无右孩子 ; 二叉树森林仅当根结点有右孩子 77

78 (2) 二叉树转换为森林的形式化规则 : 若 B=( root, LB, RB ) 是一棵二叉树, 则 : 如果 B 为空, 则对应的森林 F 也为空如果 B 非空, 则 F 中第一棵树 T 1 的根为 root; T 1 的根的子树森林 { T 11, T 12,, T 1m } 是由 root 的左子树 LB 转换而来 ; F 中除了 T 1 之外其余的树组成的森林 { T 2, T 3,, T n } 是由 root 的右子树 RB 转换而成的森林

79 树的遍历先序遍历若树非空, 则 1 访问根结点 2 依次先序遍历树的各子树 A B C D E F G H I J 先序遍历序列 : A,B,E,F,C,G,D,H,I,J

80 后序遍历若树非空, 则 1 依次后序遍历树的各子树 2 访问根结点 A B C D E F G H I J 遍历序列 : E,F,B,G,C,H,I,J, D,A

81 层序遍历 A B C D E F G H I J 遍历序列 : A,B,C,D,E,F,G,H,I,J

82 先序遍历一棵树等价于后序遍历一棵树等价于先中序遍历该树对应的二叉树序遍历该树对应的二叉树 A A B C D E F G H I J E F B G C D H I J

83 7. 8 Huffman 树及其应用最优二叉树 (Huffman 树 ) 的概念路径长度 : 两个结点之间的路径长度是连接两结点的路径上的分支数树的路径长度 : 是树中各结点各结点到根结点的路径长度之和具有不同路径长度的二叉树 83

84 树的带权路径长度 : 是树的各叶结点叶结点所带的权值与该结点到根的路径长度的乘积的和例 : 给定 4 个叶子结点, 分别对应权值 7,5,2,4, 可以构造如下三棵二叉树 :

85 Huffman 树在权为 w 1,w 2,,w n 的 n 个叶子结点的所有二叉树中, 带权路径长度 WPL 最小的二叉树称为最优二叉树 (Huffman( 树 ) 7 5 Huffman 树 2 4 Huffman 树的特点?

86 Huffman 树的构造方法 : (1) 根据给定的 n 个权值 {w 1, w 2,, w n }, 构造 n 棵二叉树的集合 F = {T 1, T 2,, T n }, 其中每棵二叉树中均只含一个带权值为 w i 的根结点, 其左右子树为空树 ; (2) 在 F 中选取其根结点的权值为最小的两棵二叉树, 将这两棵树合并成一棵新树即添加一个新结点, 将所选的两棵树分别作为新结点的左右子树, 并置这棵新的二叉树根结点的权值为其左右子树根结点的权值之和 ; (3) 重复 (2), 直至 F 中只含一棵树为止

87 HuffmanHuffman 编码在远程通讯中, 要将待传字符串转换成二进制的 0 1 序列最简单的编码方式是采用等长编码设要传送的字符为 : 若编码为 :A 00 B 01 C 10 D---11 ABACCDA 若将编码设计为长度不等的二进制编码, 即让待传字符串中出现次数较多的字符采用尽可能短的编码, 则转换后的二进制编码串便可能缩短

88 设要传送的字符为 :ABACCDA 若编码为 :A 0 ABACCDA B 00 C 1 D---01 但 : 0000 AAAA ABA BB 重码关键 : 要设计长度不等的编码, 则必须使任一字符的编码都不是另一个字符的编码的前缀, 这种编码称之为前缀编码前缀编码

89 如何设计前缀编码 : 设要传送的字符为 : ABACCDA 0 A 0 C 规定 : 左分支用 0 表示 ; 右分支用 1 表示 B D 采用二叉树设计二进制前缀编码可编码为 :A 0 B 110 C 10 D---111

90 译码过程 : 分解接收字符串 : 遇 0 向左, 遇 1 向右 ; 一旦到达叶子结点, 则译出一个字符, 反复由根出发, 直到译码完成 0 A 0 C 1 0 B 1 1 D A B A C C D A

91 如何得到电文总长最短的前缀编码? 假设组成电文的字符集合 D={ d 1,d 2,,d n }, 每个字符 d i 在电文中出现的次数为 c i, 对应的编码长度为 l i 因此, 求电文的总长最短问题可转换为 : 以 n 种字符出现的频率作为权值, 设计一树棵 Huffman 树 91

92 设计示例 : 例 : 已知某系统在通讯时, 出现八种字符其概率分别为 :0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11, 试设计 Huffman 编码出现频率越大的字符, 其 Huffman 编码越短

93 Huffman 树的构造算法 : 当给定 n 个叶子结点构造 Huffman 树时, 共需要进行 n-1 次合并, 每次合并都要产生一个新结点, 合并过程中共产生 n-1 个新结点, 因此,Huffman 树中总的结点个数为 2n-1 个如何设计 Huffman 树的存储结构? 将 Huffman 树中的 2n-1 个结点可以存储在一个大小为 2n-1 的数组中

94 结点结构定义如下 : struct HuffmanNode { char data; // 待编码的符号 double weight; // 符号出现的频率 int parent,lchild,rchild; };

95 Huffman 树的结点结构中, 增加了一个 parent 指针域, 其作用是 : 区分结点与根结点从任一结点出发, 可直接到达其双亲结点在存储 Huffman 树结点的长度为 2n-1 的数组中, 前 n 个分量中存放的是叶子结点

96 Huffman 树的类定义如下 : class HuffmanTree{ vector<huffmannode> nodes; int n; // 叶子结点数 public: HuffmanTree(vector<HuffmanNode> &leafs); ~HuffmanTree(); };

97 构造 Huffman 树算法的流程 : 初始化 n 个叶子结点 ; 初始化 n-1 个非叶子结点 ; 执行 n-1 次合并动作 : 选取权值最小的两个根结点 ; 将两棵以它们为根的树进行合并, 使其成为新结点的左右孩子, 同时修改这两个结点的 parent 域, 并给新结点赋权值. 97

98 例 : 假设某信息系统中有 5 种符号, 分别记作 A B C D E, 它们各自出现的统计频率是 6% 14% 53% 15% 12%, 试构造 huffman 编码

99 Huffman 树初始化时的存储结构 data 域 'A' 'B' 'C' 'D' 'E' weight 域 6% 14% 53% 15% 12% parent 域 lchild 域 rchild 域

100 rchild lchild parent 100% 47% 29% 18% 12% 15% 53% 14% 6% weight 'E' 'D' 'C' 'B' 'A' data Huffman 树完建时的存储结构

101 HuffmanTree::HuffmanTree(vector<HuffmanNode> &leafs) { n=leafs.size(); // 叶子结点数 nodes.resize(2*n-1); // 为分支结点预留向量空间 ; for( i=0; i<n; ++i ){ nodes[i].weight= leafs[i].weight; nodes[i].data= leafs[i].data; nodes[i].parent = -1; nodes[i].lchild = -1; nodes[i]. rchild = -1; } for( i=n; i<2*n-1; ++i ) nodes[i].parent = -1; for(i=n; i<2*n-1; ++i) // n-1 次合并根结点 { SelectSmall( least, less, i); nodes[least].parent = nodes[less].parent = i; nodes [i].lchild=least; nodes[i].rchild=less; nodes [i].weight=nodes[least].weight+nodes[less].weight; } }

102 Huffman 树的编码算法 : // 从叶子到根逆向求第 i 个字符的 Huffman 编码 vector<int> HuffmanTree::Encode( int i ) { vector<char> code; // 第 i 个符号的编码向量 parent=nodes[i].parent; while(parent!=-1) // 只有根结点的 parent 域为 -1 { if( nodes[parent].lchild==i ) code.insert(code.begin(), 0 ); else code.insert(code.begin(), 1 ); i=parent; parent= nodes[parent].parent; // 沿父指针上溯 } return code; }

103 Huffman 树的译码算法 : string HuffmanTree::Decode( vector<int> &source ) { string target= ; // 译码的目标 : 原信息符号串 root=tree.size()-1; // 根结点下标 p=root; // 将当前结点设为根结点 for(i=0; i<source.size(); i++) { if(source[i]==0) p=nodes [p].lchild; else p=data[p].rchild; if( nodes[p].lchild==-1 && nodes [p].rchild==-1) { target= target+nodes[p].data; p=root; // 当前结点再次是根结点 } } return target; }

104 7.9 等价类问题等价关系的定义 : 如果集合 S 中的关系是自反的对称的和传递的, 则称这种关系是一个等价关系等价类 : 若 R 是集合 S 中的等价关系,x 是 S 中的任意元素, 所有与 x 存在等价关系的元素构成的集合, 称为由 x 生成的一个 R 等价类等价类划分 : 等价类划分 : 等价关系 R 可产生集合 S 的唯一划分, 即可以按 R 将 S 划分为若干不相交的子集 S 1, S 2,, 它们的并集是 S, 则这些子集 S i 称为 S 的 R 等价类 104

105 如何实现等价类划分? 假定集合 S 有 n 个元素,m 个形如 (x, y) (x, y S) 的等价偶对确定了等价关系如何求 S 的划分? 构造等价类的算法如下 : 1 令 S 中每个元素各自形成一个只含有单个成员的子集, 记作 S 1, S 2, S n 2 考察偶对 (x, y), 判断 x 和 y 所属子集, 假设 x S i, y S j 若 S i =S j, 则 x 和 y 已属同一个等价类, 无需操作 ; 若 S i S j, 则将 S i 并入 S j 3 重复执行步骤 2, 当所有偶对都处理完时, 所有剩余子集即为 S 的 R 等价类

106 集合如何表示? 数组实现链表实现树实现

107 例 : 设集合 S={a,b,c,d,e}, 等价偶对有 (a,c),(b,d),(c,e), 则构造等价类的过程如下 : (a) (b) (c) (d)

108 树的存储结构? 每棵树对应一个子集 ; 约定根结点的下标作为子集的编号 ; 整个集合是一个森林 ; 为便于操作的实现, 采用树的双亲表示法作为存储结构

109 双亲表示法的树结点结构定义 : template <class T> struct PTNode { T data; int parent; // 双亲指针域 };

110 等价类的类模板定义 template<class T> class MFSet { vector<ptnode<t> > data; public: MFSet(vector<T> &ds); ~MFSet( ); int Find(int i); void Merge(int i, int j); };

111 构造函数 : MFSet::MFSet(vector<T> &ds) { data.resize( ds.size() ); for(i=0; i<ds.size(); i++) { data[i].data=ds[i]; data[i].parent=-1; } }

112 函数 Find 的实现 : template<class T> int MFSet<T>::Find( int i ) { while(data[i].parent>=0) i = data[i].parent; return i; }

113 函数 Merge 的实现 : template<class T> void MFSet<T>::Merge( inti, intj ) { data[i].parent = j; }

114 例 : 设集合 S={a,b,c,d,e}, 等价偶对有 (a,b),(b,c),(c,d), 则构造等价类的过程如下 : (a) (b) (c) (d)

115 改进方法 : 在合并两个子集时, 将元素较少的树的根结点的 parent 域值置为元素较多的树的根结点的下标为能较容易地读取树中的结点个数, 将根结点的 parent 域值设为树中结点个数的负值负值 115

116 函数 Merge 的实现 : template<class T> void MFSet<T>::Merge( int i, int j ) { if(data[i].parent < data[j].parent ) { data[i].parent += data[j].parent; data[j].parent = i; } else { data[j].parent += data[i].parent; data[i].parent = j; } }

117 本章小结本章的主要学习要点如下 : (1) 掌握树的相关概念和基本性质 ; (2) 掌握二叉树的相关概念和基本性质 ; (3) 重点掌握二叉树的存储结构 ; (4) 重点掌握二叉树遍历算法和各种常用算法 ; (5) 掌握线索二叉树的概念结构, 及线索指针的应用算法 ; (6) 掌握树的存储结构 ; (7) 掌握 Huffman 树的概念构造方法和 Huffman 编码的产生方法 ; (8) 掌握等价类概念和构造方法

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用