数据结构树与二叉树详细解析ppt课件

1、1,树的概念 二叉树 二叉树遍历 线索化二叉树 树与森林 Huffman树,第4章 树与二叉树,2,树形结构是一种非线性结构，应用十分广泛。 如：行政机构、磁盘目录、家谱等,3,磁 盘 目 录,4,树和森林的概念,树的定义 树是由 n (n 0) 个结点组成的有限集合。如果 n = 0，称为空树；如果 n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其他结点划分为 m (m 0) 个 互不相交的有限集合T0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树,5,树的特点,每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后

2、继,A,C,G,B,D,E,F,K,L,H,M,I,J,6,例5.1: Tree=(D, R) D=Book, C1, C2, C3, S1.1, S1.2, S2.1, S2.2, S2.3, S2.1.1, S2.1.2 R=, , , , , , , , ,树是一种层次结构 （hierarchy structure,7,基本术语：主要来源于家谱和树 双亲、子女（parent, child）： 若 R，则称a是b的双亲，b是a 的子女(孩子); 结点度（degree）： 结点所拥有的子女数； 叶（leaf）： 度为0的结点； 分枝结点（branch node）： 度大于0的结点； 树的度：

3、树中最大的结点度,8,结点所在的层次（level）： 根在第1层，其它任一结点所在的层是其双亲的层加1； 深度或高（depth）： 结点所在的层次的最大层数； 兄弟（sibling)： 具有同一双亲的结点互称兄弟； 堂兄弟（cousin）： 双亲在同层的非兄弟结点互称堂兄弟,9,祖先、子孙（ancestor）： 一个结点是它所有子树中的结点的祖先,这些结点是它的子孙; 路径（path）： 是一结点序列n1,n2,n3,nk， 并且前1个结点是后1个结 点的双亲；它的长度是k-1; 有序树（ordered tree）： 每个结点的子女由左到右是有次序的；否则是无序树,10,结点A、B、C的度分别

4、为： 3、2、1,叶子： K，L，F，G，M，I，J,结点A的孩子： B，C，D 结点B的孩子： E，F,结点I的双亲： D 结点L的双亲： E,结点B，C，D为兄弟 结点K，L为兄弟,树的度： 3,结点A的层次： 0 结点M的层次： 3,树的深度： 3,结点F，G为堂兄弟 结点A是结点F，G的祖先,11,森林（Forest）: m(m 0)棵互不相交的树的集合,12,二叉树 (Binary Tree,二叉树的五种不同形态,L,13,性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2i -1个结点。(i 1) 证明用数学归纳法 性质2 深度为 k 的二叉树最多有 2k-1个结点

5、。(h 1) 证明用求等比级数前k项和的公式 20 + 21 + + 2k-1 = 2k-1,二叉树的性质,14,性质3 对任何一棵二叉树, 如果其叶结点有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0n21 证明：若设度为1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,15,定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete

6、 Binary Tree) 若设二叉树的高度为h，则共有h+1层。除第 h 层外，其它各层 (0 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。(特点,16,叶结点仅在层次最大的两层出现 对任一结点，若其右子树的高度为l，则其左子树的高度为l或l+1,17,性质4 具有 n (n 0) 个结点的完全二叉树的高度为 log2(n+1) -1 证明：设完全二叉树的高度为 h，则有 2h - 1 n 2h+1 - 1 变形 2h n+1 2h+1 取对数 h log2(n+1) h+1 有 log2(n+1) = h+1 h = log2(n+1) -1,上面

7、h层结点数,包括第h层的最大结点数,18,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, , n-1，则有以下关系： 若i = 0, 则 i 无双亲 若i 0, 则 i 的双亲为(i -1)/2 若2*i+1 n, 则 i 的左子女为 2*i+1，若 2*i+2 n, 则 i 的右子女为2*i+2 若 i 为偶数, 且i != 0, 则其左兄弟为i-1, 若 i 为奇数, 且i != n-1, 则其右兄弟为i+1 结点i所在的层次为 log2(i+1,19,二叉树的抽象数据类型,ADT BinaryTree is Data 是有限个结点的集合D。当

8、D非空时，其中 有一根结点t，其余结点被分为t的左子树和 右子树。 Operations Constructor Process: 建立一棵空二叉树 Delete Process: 删除二叉树,20,IsEmpty Process: 判断二叉树是否是空 Output: 若二叉树为空，则返回true, 否则返回false Size Process: 计算二叉树的结点数size Output: size Height Process: 计算二叉树的高度height Output: height Root Process: 取二叉树根结点值x Output: 根结点值x,21,Parent Inpu

9、t: node是二叉树中的一个结点 Process: 求node的双亲p，若node 是根，则p为空 Output: p CreateBinaryTree Input: 二叉树的某种形式的定义definition Process: 根据此定义definition构造二叉树 MakeTree Input: data是根结点值，left是左子树，right是右子树 Process: 创建二叉树，data是根结点值，left是其左子树， right是其右子树,22,BreakTree Process: 拆分二叉树，data是根结点数据，left是左子树， right是右子树 Output: data

10、, left, right PreOrder Input: Visit()是结点访问函数 Process: 按前序遍历对二叉树中每个结点调用Visit( )1次且仅1次 Output: 根据Visit( )，按前序遍历序列得到结果 InOrder Input: Visit()是结点访问函数 Process: 按中序遍历对二叉树中每个结点调用Visit( ) 1次且仅1次 Output: 根据Visit( )，按中序遍历序列得到结果,23,PostOrder Input: Visit()是结点访问函数 Process: 按后序遍历次序对二叉树中每个结点调用Visit( ) 1次且 仅1次 Out

11、put: 根据Visit( )，按后序遍历序列得到结果 LevelOrder Input: Visit()是结点访问函数 Process: 按层次对二叉树中每个结点调用Visit( )1次且仅1次 Output: 根据Visit( )，按层次遍历序列得到结果 / BinaryTree,24,完全二叉树 一般二叉树 的顺序表示 的顺序表示,二叉树的顺序表示,25,极端情形: 只有右单支的二叉树,26,二叉树的链表表示,二叉链表,27,二叉树的链表表示,三叉链表,28,二叉树链表表示的示例,二叉树 二叉链表 三叉链表,29,二叉链表中结点定义如下： class BinaryTreeNode Dat

12、aType data; BinaryTreeNode *leftChild, *rightChild; /左指针,右指针 public : BinaryTreeNode(DataType /BinaryTreeNode,二叉树的链表式实现,30,class BinaryTree BinaryTreeNode *root; /根结点指针 public : BinaryTree( ) root = NULL; /创建一个空的二叉树 bool IsEmpty( ); /如果二叉树为空，则返回true，否则返回false bool Root(DataType /通过扩充二叉树的前序遍历序列，创建二叉树

13、,二叉链表定义如下,31,void MakeTree(DataType /逐层遍历,其中，Visit作为遍历的过程参数，负责对结点的访问,32,void Delete(BinaryTreeNode *,33,bool Root(DataType /创建新二叉树,34,二叉树遍历,二叉树的遍历是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V， 遍历根的左子树记作 L， 遍历根的右子树记作 R,35,可能的遍历次序,前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV,36,前序遍历： 若BT非空，则： 1.访问根； 2.前序遍历左

14、子树； 3.前序遍历右子树,中序遍历： 若BT非空，则： 1.中序遍历左子树； 2.访问根 3.中序遍历右子树,后序遍历： 若BT非空，则： 1.后序遍历左子树； 2.后序遍历右子树； 3.访问根,遍历算法,37,遍历结果 中序： a + b * c - d - e / f 前序：- + a * b - c d / e f 后序： a b c d - * + e f /,38,练习,给出上述二叉树的前序、中序和后序的遍历序列,前序遍历序列：ABDGCEFH 中序遍历序列：DGBAECHF 后序遍历序列：GDBEHFCA,39,前序遍历的二叉树递归算法 void BinaryTree: preO

15、rder (BinaryTreeNode *,40,二叉树递归的中序遍历算法 void BinaryTree: InOrder (BinaryTreeNode *,41,二叉树递归的后序遍历算法 void BinaryTree: postOrder (BinaryTreeNode *,42,利用二叉树后序遍历计算二叉树结点个数,int Size (BinaryTreeNode *,应用二叉树遍历的事例,43,int Depth (BinaryTreeNode *,利用二叉树后序遍历计算二叉树的高度,44,以递归方式建立二叉树。 递归出口：当遇到时，是空。 建立根结点。 建立左子树和右子树。 二

16、叉树用根字符序列和左右子树的字符序列表示，空树用空格(或某一字符表示)表示。 例如用“”或用“-1”表示字符序列或正整数序列空结点,利用二叉树前序遍历建立二叉树,45,如图所示的二叉树的前序遍历顺序为 A B C D E G F 序列是扩充二叉树的前序遍历序列。 是扩充的叶结点，它代表空指针,46,建立二叉树(二叉链表）算法: void CreateBinaryTree(BinaryTreeNode* CreateBinaryTree,47,遍历二叉树的非递归算法,我们先观察一下三种遍历行走的路线 前序遍历,48,中序遍历,49,后序遍历,50,三种遍历的访问位置对比,三种遍历的路线是完全一样

17、的，每个结点都被经过三次但访问时间是不同的,前序：第一次经过时访问,中序：第二次经过时访问,后序：第三次经过时访问,51,算法思想 非递归中序遍历Binary Tree 建立栈 stack； P指向根； 当p不空 或 stack 不空时反复做： 若 p不空 ,p 入 栈; p指向左子女； 否则： 出栈顶元素到p中； 访问p； p指向右子女； 4. 结束,52,思考：非递归的前序遍历算法,中序遍历BinaryTree算法思想 : 建立栈 Stack； p指向根； 当p不空 或 Stack 不空时反复做： 若 p不空，p 入 栈； p指向左子女； 否则： 出栈顶元素到p中； 访问p； p指向右子女

18、； 4. 结束,前序遍历BinaryTree的非递归算法思想 : 建立栈 Stack； p指向根； 当p不空 或 Stack 不空时反复做： 若 p不空，访问p ，p 入 栈； p指向左子女； 否则： 出栈顶元素到p中； p指向右子女； 结束,53,例,A,root,54,例,55,A,B,C,3,例,56,57,5,例,58,6,例,P=NULL,59,60,61,62,A,D,E,访问：C B,P=NULL,10,例,63,A,D,访问：C B E,p,11,例,64,G,65,66,14,例,67,A,D,访问：C B E G,P=NULL,15,例,68,69,70,F,71,72,7

19、3,74,75,前序遍历的非递归算法： void PreOrder(BinaryTreeNode *p=root) BinaryTreeNode *p; Stack stack; /建立栈 while (p | !stack.IsEmpty() while(p) stack.Push(p); coutp-data; p=p-leftChild; /向左走 else p=stack.Pop(); p=p-rightChild; /向右走 /while /InOrder,76,算法思想 非递归后序遍历 1.建立栈 stack； 2.P指向根； 3.当p不空或stack 不空时反复做： 若p不空 ：

20、(p,L) 入 栈; p向左走一步； 否则： 出栈顶元到p和tag中； 若tag=R : 访问p；p置空； 否则 （p,R）入栈；并 p向右走一步； 4. 结束,后序遍历时，访问一个结点的时间是： 第3次经过时； 第2次返回时； 从右边返回时； 如何区分从左还是右返回的呢？ P入栈时带一标记: 向左走时带L 向左走时带R,77,void PostOrder(void Visit(BinaryTreeNode *) /后序遍历 BinaryTreeNode *t=root; Stack stack; /建立栈 while (t | !stack.IsEmpty() if (t) stack.Pu

21、sh(t, L); /(t,L)入栈 t=t-leftChild; / t向左走,后序遍历二叉树非递归算法（基于二叉链表存储结构,78,else e=stack.Pop(); /出栈顶元素到e中 t=e.t; tag=e.tag; if (tag=R) t-data; t=NULL; else stack.Push(t,R); t=t-rightChild; /t向右走 /if /while /postOrder,79,例,B,E,A,C,root,A.L) 入栈 (A.L) (B.L) 入栈 (A.L)(B.L) (B.L)退栈 (A.L) (B.R)入栈 (A.L) (B.R) (E.L)

22、入栈 (A.L) (B.R) (E.L) (E.L)退栈 (A.L) (B.R) (E.R)入栈 (A.L) (B.R) (E.R) (E.R)退栈 (A.L) (B.R) 访问E (B.R)退栈 (A.L) 访问B (A.L)退栈 (A.R)入栈 (A.R) (C.L)入栈 (A.R) (C.L) (C.L)退栈 (A.R) (C.R)入栈 (A.R) (C.R) (C.R)退栈 (A.R)访问C (A.R)退栈 访问A,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,80,已知二叉树

23、的前序遍历序列和中序遍历序列 或二叉树中序遍历序列和后序遍历序列， 如何确定一棵二叉树,例：已知一棵二叉树的 前序遍历序列：HDACBGFE 中序遍历序列：ADCBHFEG 试画出满足以上序列的二叉树,81,例：已知一棵二叉树的 中序遍历序列：ADCBHFEG 后序遍历序列：ABCDEFGH 试画出满足以上序列的二叉树,课堂练习: 前序遍历序列：ABDGHJKECFIM 中序遍历序列：GDJHKBEACFMI 试画出满足以上序列的二叉树,82,考虑层次遍历算法LevelOrder ,层次遍历序列：ABCDEFGH,83,void BinaryTree:LevelOrder ( ) /层次遍历二

24、叉树算法 SeqQueue qu; BinTreeNode *p=root; qu.Enter(p); while(!qu.IsEmpty( ) p=qu.Leave( ); coutdata; if(p-leftChild) qu. Enter(p-leftChild); if(p-rightChild) qu. Leave(p-rightChild);,84,线索的目的：利用二叉树的空指针保存遍历序列的前驱、后继信息，遍历二叉树时不需要栈。 n个结点的二叉树，有2n个指针，只用了n-1个，有n+1个是空的。 用空的左指针指向遍历序列的前驱 用空的右指针指向遍历序列的后继 这两种指针称为线索

25、(Thread,线索化二叉树 (Threaded Binary Tree,线索 (Thread,85,例,n个结点的二叉链表中，有2n个指针，只用了n-1个指针，有n+1个指针是空的,86,给二叉树加线索的过程是线索化（穿线）； 按前序遍历序列线索化的二叉树是前序线索二叉树； 按中序遍历序列线索化的二叉树是中序线索二叉树； 按后序遍历序列线索化的二叉树是后序线索二叉树； 中序线索二叉树简称线索二叉树,87,增加 Pred 指针和 Succ 指针的二叉树,88,B,thrt,前序序列：ABCDE 前序线索二叉链表,二叉树,89,B,中序序列：BCAED 中序线索二叉链表,二叉树,thrt,90,

26、B,后序序列：CBEDA 后序线索二叉链表,二叉树,thrt,91,线索化二叉树及其二叉链表表示,LTag=0, LeftChild为左子女指针 LTag=1, LeftChild为前驱线索 RTag=0, RightChild为右子女指针 RTag=1, RightChild为后继指针,LeftChild,RightChild,data,LTag,RTag,92,0,0,0,0,1,1,1,1,1,1,二叉树,thrt,93,0,0,0,0,1,1,1,1,1,1,二叉树,thrt,94,0,0,0,0,1,1,1,1,1,1,二叉树,thrt,95,D,B,F,E,A,C,NIL,NIL,

27、例,中序）线索化二叉树,中序遍历序列：DBFEAC,96,后序线索二叉树,前序线索二叉树,后序遍历序列：DBECA,前序遍历序列：ABDCE,97,class ThrBNode DataType data; bool lTag, rTag; ThrBNode *leftChild, *rightChild; public: ThrBNode(DataType d) data=d; leftChild= rightChild=NULL; lTag=rTag=false; ;/ThrBNode,中序线索二叉链表的类定义,98,class InThrBTree / Thread_Binary_tre

28、e ThrBNode *thrt; /头指针 ThrBNode *GetFirstNode(ThrBNode *); ThrBNode *GetNextNode(ThrBNode *); ThrBNode *GetNextNodePre(ThrBNode *); /求在前序序列中的后继 public: InThrBTree( ) thrt=new ThrBNode(); /创建一个带表头但不带线索的空二叉树 void CreateBTree(ThrBNode * /创建一个带表头但不带线索的二叉树,99,void MakeTree(DataType /InThrBTree,100,中序线索二叉

29、树的线索给我们提供了足够的信息，对其进行中序遍历时，既不需要递归（使用了系统栈）也不需要栈,1) 找到序列的第一个结点p,2)当p非空时： 访问p; 找出p的后继r； p=r,算法思想,关键问题1 沿着根的左链走直到无左子女的结点r，即中序序列中的第一个结点 p=root; While (!p-ltag) p=p-lchild,关键问题2，有如下两种情况： P无右子女:则p-rchild是p的后继； P有右子女：则p的右子树的中序序列下第一个结点是p的后继，方法同关键问题1,101,ThrBNode* GetFirstNode(ThrBNode *p) /求中序序列中的第一个结点 while

30、(!p-lTag) p=p-leftChild; /沿左链走直到无左子女的结点 return p; / GetFirstNode,中序遍历线索二叉链表中基本操作的实现,求中序序列中的第一个结点： 沿着根的左链走,直到无左子女的结点p，即中序序列中的第一个结点,102,ThrBNode*GetNextNode(ThrBNode *p ) /求p在中序中的后继 if (p-rTag) return p-rightChild; /P无右子女 r=p-rightChild; /r指向p的右子树的根 r=GetFirstNode(r); /求右子树的第一个结点 return r;,求p在中序中的后继：

31、P无右子女：则p-rightChild是p的后继； P有右子女：则p的右子树的中序序列下 一个结点是p的后继,103,void InOrder(void Visit(ThrBNode *) p=thrt-leftChild;/取根结点 if(p=thrt) return; p=GetFirstNode(p); while (p!=thrt) Visit(p); p=GetNextNode(p); /InOrder,104,找到前序序列中的第一个结点: 根就是第一个结点,找出给定结点p在前序序列中的后继结点: 有如下3种情况： P有左子女：则p左子女是p的后继；否则 P有右子女：则p的右子女是p

32、的后继; 否则 P是叶：沿着p的右线索走，直到头结点或一个有右子女的结点r为止，若到头结点，则p无后继，否则r的右子女是p 的 后继,在中序线索二叉树上进行前序遍历的非递归算法,105,ThrBNode *GetNextNodePre(ThrBNode *p ) /求p在前序序列中的后继结点 if (!p-lTag) return p-leftChild; /p有左子女 if (!p-rTag) return p-rightChild; /p有右子女 r=p-rightChild; /p是叶结点 while (r!=thrt /GetNextNodePre,106,在中序线索二叉树上进行前序遍

33、历的非递归算法,void PreOrder(void Visit(ThrBNode *) p=thrt-leftChild; while (p!= thrt) Visit(p); p=GetNextNodePre(p); /PreOrder,107,0,0,0,0,0,0,0,0,0,0,二叉树,thrt,通过中序遍历建立中序线索化二叉链表的算法,108,0,0,0,0,1,1,1,1,1,1,二叉树,thrt,109,中序遍历的非递归算法(回忆) void InOrder(BinaryTreeNode *p=root) BinaryTreeNode *t=p; Stack stack; /建

34、立栈 while (t | !stack.IsEmpty() if(t) stack.Push(t); t=t-leftChild; /t向左走 else t=stack.Pop(); coutt-data; t=t-rightChild; /t向右走 /while /InOrder,通过中序遍历建立中序线索化二叉链表,110,if (current-rTag =1) 后继为current-rightChild else /current-rTag != 1 后继为当前结点右子树 的中序下的第一个结点,寻找当前结点在中序下的后继,A,B,D,E,C,F,H,I,K,G,J,111,if (cu

35、rrent-lTag=1) 前驱为current-leftChild else /current-lTag=0 前驱为当前结点左子树 中序下的最后一个结点,寻找当前结点在中序下的前驱,A,B,D,E,C,F,H,I,K,G,J,L,112,void InOrderThreading(ThrBNode * prebt,通过中序遍历建立中序线索化二叉链表的算法,if(p=bt) pre-leftChild=thrt; pre-lTag=true; pre-rightChild=thrt; pre-rTag=true; return;,113,while(p | !s.IsEmpty() while

36、(p) s.Push(p)；p=p-leftChild;/向左走到尽头 if(s.IsEmpty() /访问结点，向右一步 p=s.Pop()； if (!p-leftChild) p-leftChild=pre; p-lTag=true; if (pre!=bt,114,0 A 0,0 B 0,0 C 0,0 D 0,0 E 0,root,pre = NULL,current,115,0 A 0,1 B 0,0 C 0,0 D 0,0 E 0,root,pre = NULL,current,116,0 A 0,1 B 0,0 C 0,1 D 0,0 E 0,root,pre,current,

37、117,0 A 0,1 B 0,0 C 0,1 D 1,0 E 0,root,pre,current,118,0 A 0,1 B 0,0 C 0,1 D 1,1 E 0,root,pre,current,119,0 A 0,1 B 0,0 C 0,1 D 1,1 E 1,root,pre,current,120,0 A 0,1 B 0,0 C 1,1 D 1,1 E 1,root,pre,后处理,121,双亲表示,A,B,C,D,E,F,G,树的存储表示,树与森林,122,A,B,C,D,E,F,G,空链域2n+1个,子女表示法,123,第二种解决方案,data,firstChild,next

38、Sibling,A,B,C,D,E,F,G,左子女-右兄弟表示法,124,森林与二叉树的转换,森林与二叉树的对应关系,125,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 外其它树构成的森林,126,2) 二叉树转换为森林的

39、规则 如果 B 为空，则对应的森林 F 也为空。 如果 B 非空，则 F 中第一棵树 T1 的根为 root； T1 的根的子树森林 T11, T12, , T1m 是由 root 的左子树 LB 转换而来，F 中除了 T1 之外其余的树组成的森林 T2, T3, , Tn 是由 root 的右子树 RB 转换而成的森林,127,树的二叉树表示,树的遍历,深度优先遍历 先根次序遍历 后根次序遍历 广度优先遍历,128,树的先根次序遍历,当树非空时 访问根结点； 依次先根遍历根的各棵 子树。 树先根遍历 ABEFCDG。 对应二叉树前序遍历 ABEFCDG。 树的先根遍历结果与其对应二叉树 表示

40、的前序遍历结果相同。 树的先根遍历可以借助对应二叉树的前序遍历算法实现,129,树的后根次序遍历,当树非空时 依次后根遍历根的各棵 子树； 访问根结点。 树后根遍历 EFBCGDA。 对应二叉树中序遍历 EFBCGDA。 树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。 树的后根遍历可以借助对应二叉树的中序遍历算法实现,130,3) 广度优先(层次次序)遍历,按广度优先次序遍历树的结果。 ABCDEFG,131,森林的遍历,森林的二叉树表示 ABCDE FG HIKJ,1) 先根次序遍历的规则： 若森林 F 为空, 返回；否则 访问 F 的第一棵 树的根结点； 先根次序遍历第 一棵树的子

41、树森林； 先根次序遍历其 它树组成的森林,132,森林的二叉树表示 EDCB GKJIHFA,2) 后根次序遍历的规则： 若森林 F 为空， 返回；否则 后根次序遍历第 一棵树的子树森林； 后根次序遍历其 它树组成的森林； 访问 F 的第一棵 树的根结点,133,森林的二叉树表示 AFHBCDGIJEK,3) 广度优先遍历(层次 序遍历) ： 若森林 F 为空， 返回；否则 依次遍历各棵树 的根结点； 依次遍历各棵树 根结点的所有子女； 依次遍历这些子 女结点的子女结点,134,Huffman树,路径长度 (Path Length) 两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。

42、 树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和 EPL。 树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和 IPL。 树的路径长度是根结点到各结点的路径长度之和 PL = EPL + IPL,135,1,2,3,4,5,6,7,8,树的路径长度 PL = 0+1*2+ +2*4+3*1 = 13,136,n 个结点的二叉树的路径长度不小于 下述数列前 n 项的和，即,其路径长度最小者为,137,带权路径长度 (Weighted Path Length, WPL) 树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和,扩充二叉树 各叶结点带有权值,1

43、38,具有不同带权路径长度的扩充二叉树,WPL = 7*1+ 5*2+2*3+ 4*3 = 35,139,Huffman树,带权路径长度达到最小的扩充二叉树即为Huffman树。 在Huffman树中，权值大的结点离根最近,Huffman算法 (1) 由给定的 n 个权值 w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林 F = T0, T1, T2, , Tn-1 ，其中每棵扩充二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空,140,2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子

44、树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F,141,Huffman树的构造过程,142,Huffman编码,主要用途是实现数据压缩,设给出一段报文： 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,143,若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 各

45、字符出现概率为 2/18, 7/18, 4/18, 5/18 ,化整为 2, 7, 4, 5 。以它们为各叶结点上的权值, 建立Huffman树。左分支赋 0，右分支赋 1，得Huffman编码(变长编码,144,A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于Huffman树的带权路径长度WPL。 Huffman编码是一种无 前缀编码。解码时不会混 淆,145,设字符集为 c1 , c2 , cn , 看作叶结点 出现概率为 w1 , w2 , wn , 叶结点的权 （1）构造H

46、uffman树 （2）左分支标0，右分支标1 （3）根到叶结点ci的路径上的二进制编码就是ci的编码 设编码长度为 l1 , l2 , ln 是叶结点的路径长度, 则树的带权路径长度WPL是,146,采用静态链表建立Huffman树,用n个叶结点构造出的最优二叉树共有几个结点,构造最优树时共执行n-1次循环，每次增加一个新 结点，共增加了n-1个结点，所以结点总数一定 是n+n-1=2n-1,因为n0=n2+1, 所以n2=n0-1, 又由于在最优二叉树中 没有度为1的结点,所以在最优二叉树中总的结点数为 n+n-1=2n-1,147,class NodeType char ch;/待编码符号

47、 float w; /权值 int parent, leftChild, rightChild; ; /NodeType class Huffman int n; /待编码符号数 NodeType *tree; /tree是一个待分配的数组 String *code; /code是一个待分配的数组,每个元素存放一个编码串 void SelectMins(int k, int /在tree0.k-1中选择根权值最小和次小的二叉树,静态Huffman树的定义,148,public: Huffman(int m) n=m; tree=new NodeType2*n-1; /前n个元素对应叶结点，最后

48、一个元素存放根 for (k=0; kchw; treek=ch,w,-1,-1,-1; /for void CreatHTree(); /构造Huffman树 void GetCode(); /得到每个叶结点的编码 /Huffman,149,void SelectMins(int i, int,150,void CreatHTree() for (i=n; i2*n-1; i+) SelectMins(i, p1, p2); /在tree0.k-1中选最小的2棵树 treep1.parent= treep2.parent=i; /p1,p2作k的子女 treei.leftChild=p1; treei.rightChild=p2; treei.w=tree p1.w+treep2.w; /for /CreatHTree,151,静