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

《数据结构树与二叉树详细解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构树与二叉树详细解析ppt课件.ppt（162页珍藏版）》请在三一办公上搜索。

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

2、,C,G,B,D,E,F,K,L,H,M,I,J,5,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的度分别为：3、2、1,叶子：K，L，F，G，

4、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)棵互不相交的树的集合.,二叉树 (Binary Tree),二叉树的五种不同形态,L,12,性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2i -1个结点。(i 1) 证明用数学归纳法性质2 深度为 k 的二叉树最多有 2k-1个结点。(h 1) 证明用求等比级数前k项和的公式 20 + 21 + + 2

5、k-1 = 2k-1,二叉树的性质,13,性质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,14,定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。除第 h

6、层外，其它各层 (0 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。(特点),15,叶结点仅在层次最大的两层出现对任一结点，若其右子树的高度为l，则其左子树的高度为l或l+1,16,性质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,上面h层结点数,包括第h层的最大结点数,17,性质5 如将一棵有n个结点的完全二叉

7、树自顶向下，同一层自左向右连续给结点编号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),18,二叉树的抽象数据类型,ADT BinaryTree is Data 是有限个结点的集合D。当D非空时，其中 有一根结点t，其余结点被分为t的左子树和 右子树。 Opera

8、tions Constructor Process: 建立一棵空二叉树 Delete Process: 删除二叉树,19,20,IsEmpty Process: 判断二叉树是否是空 Output: 若二叉树为空，则返回true, 否则返回false Size Process: 计算二叉树的结点数size Output: size Height Process: 计算二叉树的高度height Output: height Root Process: 取二叉树根结点值x Output: 根结点值x,21,Parent Input: node是二叉树中的一个结点 Process: 求node的双亲p

9、，若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, left, right PreOrder Input: Visit(

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

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

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

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

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

15、inaryTree: InOrder (BinaryTreeNode * ,41,二叉树递归的后序遍历算法void BinaryTree: postOrder (BinaryTreeNode * ,利用二叉树后序遍历计算二叉树结点个数,int Size (BinaryTreeNode *,应用二叉树遍历的事例,42,int Depth (BinaryTreeNode *,利用二叉树后序遍历计算二叉树的高度,43,以递归方式建立二叉树。递归出口：当遇到时，是空。建立根结点。建立左子树和右子树。二叉树用根字符序列和左右子树的字符序列表示，空树用空格(或某一字符表示)表示。 例如用“”或用“-1”表

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

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

18、. 结束,前序遍历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),例

19、,68,69,70,&F,71,72,73,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,算法思想 非递归后序遍历1.建立栈 stack；2.P指向根；3.当p不空或stack 不空

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

21、Push(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 ( ) /层次遍历二叉树算法 SeqQueue

24、 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);,线索的目的：利用二叉树的空指针保存遍历序列的前驱、后继信息，遍历二叉树时不需要栈。 n个结点的二叉树，有2n个指针，只用了n-1个，有n+1个是空的。用空的左指针指向遍历序列的前驱用空的右指针指向遍历序列的后继这两种指针称为线索(Thread)。,线索化二叉树 (T

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

26、索二叉链表,二叉树,thrt,线索化二叉树及其二叉链表表示,LTag=0, LeftChild为左子女指针LTag=1, LeftChild为前驱线索RTag=0, RightChild为右子女指针RTag=1, RightChild为后继指针,LeftChild,RightChild,data,LTag,RTag,91,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_tree ThrBNode *thrt;

28、 /头指针 ThrBNode *GetFirstNode(ThrBNode *); ThrBNode *GetNextNode(ThrBNode *); ThrBNode *GetNextNodePre(ThrBNode *); /求在前序序列中的后继 public: InThrBTree( ) thrt=new ThrBNode(); /创建一个带表头但不带线索的空二叉树 void CreateBTree(ThrBNode * /创建一个带表头但不带线索的二叉树,99,void MakeTree(DataType /InThrBTree,中序线索二叉树的线索给我们提供了足够的信息，对其进行中

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。,100,101,ThrBNode* GetFirstNode(ThrBNode *p) /求中序序列中的第一个结点 while (!p-lTag) p=p-lef

30、tChild; /沿左链走直到无左子女的结点 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在中序中的后继：P无右子女：则p-rightChil

31、d是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的后继; 否则P是叶：沿着p的右线索走

32、，直到头结点或一个有右子女的结点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,在中序线索二叉树上进行前序遍历的非递归算法：,void PreO

33、rder(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; /建立栈 while (t | !st

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

35、nt-leftChild else /current-lTag=0 前驱为当前结点左子树 中序下的最后一个结点,寻找当前结点在中序下的前驱,A,B,D,E,C,F,H,I,K,G,J,L,111,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(p) s.Push(p)；p=

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

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

38、tChild,nextSibling,A,B,C,D,E,F,G,123, 左子女-右兄弟表示法,森林与二叉树的转换,森林与二叉树的对应关系,124,(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 外其它树构成的森林。,12

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

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

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

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

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

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

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

46、造Huffman树（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; /NodeTypeclass Huffman int n; /待编码符号数 NodeType *tree; /tree是一个待分配的数组 String *code; /code是一个待分配的数组,每个元素存放一个编码串 void SelectMins(int k, int /在tree0.k-1中选择根权值最小和次小的二叉树,静态Huffman树的定义,148,ublic: Huffman(int m) n=m; tree=new NodeType2*n-1; /前n个元素对应叶结点，最后一个元素

48、存放根 for (k=0; kchw; treek=ch,w,-1,-1,-1; /forvoid 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.

49、rightChild=p2; treei.w=tree p1.w+treep2.w; /for /CreatHTree,151,静态建立Huffman树的过程如图所示：,n=4m=2*n-1=7,152,5,2,7,4,6,w parent lchild rchild,7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1,0123456,p1,p2,4,4,2,3,i,153,5,2,7,4,6,11,w parent lchild rchild,7 -1 -1 -1 5 -1 -1 -1 2 4 -1

50、 -1 4 4 -1 -1 6 -1 2 311 -1 -1 -1 -1 -1 -1,0123456,p1,p2,5,5,1,4,i,154,5,2,7,4,6,11,7 -1 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 311 -1 1 418 -1 -1 -1,0123456,p1,p2,6,6,0,5,i,18,w parent lchild rchild,155,求每个字符的哈夫曼编码算法,5,2,7,4,6,11,7 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 311 1 418 -1,0123456,i