[信息与通信]数据结构chapter 6 树和二叉树.ppt

《[信息与通信]数据结构chapter 6 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《[信息与通信]数据结构chapter 6 树和二叉树.ppt（117页珍藏版）》请在三一办公上搜索。

1、2-Aug-23,1,第六章 树和二叉树,树是一类重要的非线性数据结构，是以分支关系定义的层次结构典型例子：企业的管理机构计算机文件系统,2-Aug-23,2,第一节 树的定义,树(Tree)的定义树是由n(n 0)个节点组成的有限集合。如果n=0，称为空树；如果n 0，则:有且仅有一个特定的称之为根(root)的节点，它只有直接后继，但没有直接前驱；如果n1，则：除根以外的其它节点可以划分为m(m0)个互不相交的有限集合T0,T1,Tm-1，每个集合又是一棵树，并且称为根的子树(subTree)。每棵子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。特点：非空的树至少有一个根节点

2、树中各子树是互不相交的集合,2-Aug-23,3,树的示例,子树,根,2-Aug-23,4,树的基本术语,节点(node)：树中的元素。包含一个数据元素及若干指向其子树的分支节点的度(degree)：节点拥有的指向其子树的分支数目 分支(branch)节点：度不为0的节点 叶(leaf)（终端）节点：度为0的节点 树的度：树中所有节点度的最大值 孩子(child)与双亲(parent)节点：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲,2-Aug-23,5,树的基本术语（续）,兄弟(sibling)：同一个双亲的孩子之间互称兄弟。祖先(ancestor)：从根节点到某个节点所经分支上的

3、所有节点。子孙（descendant)：以某个节点为根节点的子树中的所有节点均是该节点的子孙。堂兄弟：双亲在同一个层次上的节点互为堂兄弟。节点所处层次(level)：根为第一层，根的孩子为第二层，依此类推。树的深度(depth)（高度）：树中所有节点层次的最大值。,2-Aug-23,6,树的基本术语（续）,有序树与无序树：树的各个子树从左至右的顺序不可以调换则称为有序树，否则为无序树。森林（Forest）：m(m0)棵互不相交的树的集合称为森林。对树中每个节点而言，其子树的集合就构成森林。,2-Aug-23,7,树的基本术语举例,节点A的度：3节点B的度：2节点M的度：0,叶子：K，L，F，G

4、，M，I，J,节点I的双亲：D节点L的双亲：E,树的度：3,树的深度：4,节点B，C，D为兄弟节点K，L为兄弟,节点E，G，H为堂兄弟,节点A，D，H是M的祖先,2-Aug-23,8,树的抽象数据类型,数据对象D：D是具有相同特性的数据元素的集合。数据关系R：如果D为空集，则称为空树；如果D中只有一个元素，则R为空集;否则R=H，H是满足以下条件的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-root,则存在D-root上 的一个划分D1,D2,Dm m0，对任意jk(1j,km)有DjDk=，且对任意的 i(1im)，唯一存在数据元素xi(xiDi

5、),，有H(3)对应于D-root的划分，H,有唯一的一个划分H1,H2,Hm m0，对任意jk(1j,km)有HjHk=，且对任意的i(1im)，Hi 是Di 上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。,2-Aug-23,9,树的操作,初始化 InitTree(销毁树 DestroyTree(&T)创建树 CreateTree(&T)清空树 ClearTree(&T)判断树是否为空 TreeEmtpy(T)求树的深度 TreeDepth(T)求树的根 Root(T)求树上某个节点的值 Value(T,cur_e)给树上某个节点赋值 Assign(T,Cur_e,

6、value)返回某个节点的双亲 Parent(T,Cur_e)11 求某个节点的左孩子 LeftChild(T,Cur_e)12 求某个节点的右孩子 RightChild(T,Cur_e)13 求某个节点的右兄弟 RightSibling(T,Cur_e)14 在树中插入元素 InsertChild(&T,&p,i,c)15 删除树中的元素 DeleteChild(&T,&p,i)16 遍历树中所有元素 TranverseTree(T,Visit(),2-Aug-23,10,第二节 二叉树（Binary Tree）,二叉树的定义一棵二叉树是n(n0)个节点的有限集合，该集合或者为空，或者是由一

7、个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的特点每个节点至多有二棵子树(即不存在度大于2的节点)二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树是一种度为2的有序树,2-Aug-23,11,二叉树的五种不同形态,(a)空二叉树(b)仅有根节点的二叉树(c)右子树为空(d)左子树为空(e)左右子树均非空,2-Aug-23,12,二叉树的抽象数据类型,数据对象D：D是具有相同特性的数据元素的集合。数据关系R：如果D=，则R=称为空二叉树；如果D，则 R=H，H是满足以下条件的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-r

8、oot,则存在D-root=Dl,Dr,且有DlDr=(3)如果 Dl，则Dl中存在唯一元素xl，H，且存在Dl上的关系HlH；如果 Dr，则Dr中存在唯一元素xr，H,且存在Dr上的关系HrH，并且有H=,Hl,Hr(4)(Dl,Hl)是一棵符合本定义的二叉树，称为根root的左子树。(Dr,Hr)是一棵符合本定义的二叉树，称为根root的右子树,2-Aug-23,13,二叉树的操作,二叉树的操作同普通树的操作类似二叉树的遍历操作是最重要的操作二叉树的遍历包括先序遍历中序遍历后序遍历,2-Aug-23,14,2 二叉树的重要特性,性质1 在二叉树的第 i 层上至多有 2i-1(i1)个节点证

9、明：第1层只有1个节点1=21-1=20假定第i层的节点个数为2i-1那么由于二叉树每个节点最多有两个分支，因此第i+1层最多会有：2 2i-1=2i-1+1=2(i+1)-1个节点性质2 深度为 k 的二叉树至多有 2k-1(k1)个节点证明：,2-Aug-23,15,二叉树的性质(续),性质3 对任何一棵二叉树T，如果其终端节点数为 n0，度为2的节点数为 n2，则有：n0=n2+1证明：若设度为1的节点有n1个，总节点个数为n，总分支数为B，则根据二叉树的定义，n=n0+n1+n2（1）B=2n2+n1=n 1（2）于是有：2n2+n1=n0+n1+n2-1 n2=n0 1 n0=n2+

10、1,2-Aug-23,16,几种特殊形式的二叉树,满二叉树(Full Binary Tree)定义：一棵深度为k，且有 2k-1 个节点的二叉树被称为满二叉树。特点每一层的节点数目均达到了最大值可以对其按照从上到下，从左到右的原则进行连续编号。,2-Aug-23,17,完全二叉树,完全二叉树(Complete Binary Tree)定义：深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点一一对应时，称之为完全二叉树。完全二叉树的特点：叶子节点只可能在层次最大的两层上出现；对任一节点，若其右分支下的子孙的最大层次为 L，那么其左分支下

11、的子孙的最大层次必为 L 或 L+1。,2-Aug-23,18,满二叉树与完全二叉树图示,2-Aug-23,19,进一步解释完全二叉树,完全二叉树：若共有h层，除第h层外，其它各层(1h-1)的节点数都达到最大个数，第h层从右向左连续缺若干节点，这就是完全二叉树。,2-Aug-23,20,完全二叉树的两个重要性质,性质4 具有n个节点的完全二叉树的深度为log2n+1符号x表示不大于 x 的最大整数。,证明：根据完全二叉树的定义，若深度为k,则有：,2-Aug-23,21,完全二叉树的两个重要性质,性质5 对于一棵有 n 个节点的完全二叉树（深度为 log2n+1）的节点按照层序编号（从上到下

12、，从左到右），则对于任意一个节点i(1in)有：1）如果i=1，则节点是根节点，无双亲；如果i1，则其双亲是节点是i/2。2）如果 2in，则节点 i 无左孩子，否则其左孩子为 2i 3）如果 2i+1n，则节点 i无右孩子，否则其右孩子为 2i+1性质5说明：在完全二叉树中，如果知道节点的编号就可以用简单的数学运算求出其双亲和孩子的位置。性质5的证明；可以先证明2和3，然后利用2和3的结论来证明1。,2-Aug-23,22,性质5的证明,假定第i个节点位于第k层，根据二叉树的性质，那么前面k-1层总的节点个数为:2k-1-1个节点第k层第一个节点的编号为2k-1-1+1=2k-1,由此可以知

13、道在第K层的第i个节点前面节点数目为：i-2k-1如果节点i有左孩子，根据完全二叉树的定义，那么第k层中在它前面的节点必然有左右孩子，这些孩子的总数目为：2（i-2k-1）且位于第k+1层由于第K+1层第一个节点的编号为2k，那么第i个节点的左孩子的编号必然为：2k+2（i-2k-1）=2i，它的右孩子的编号则为2i+1.,2k-1,K+1层,2i,i-2k-1,2k,2i+1,2-Aug-23,23,第三节 二叉树的存储结构,一 顺序存储结构用一组连续的存储单元依次自上而下、自左至右存储完全二叉树中的所有元素。特点：节点间关系蕴含在其存储位置中只适用于完全二叉树，对于普通的树，可能会造成严重

14、的空间浪费。,2-Aug-23,24,顺序存储示例,2-Aug-23,25,顺序存储缺点,由于完全二叉树的节点数目与树的深度是指数关系，因此如果树的深度较大，所需要的空间是惊人的。,单支树示例例：一个深度为k(k=10)的二叉树，如果用顺序存储结构来表示，需要2k-1(1023)个单元，而实际上树中的元素可能只有10个(单支树)。,2-Aug-23,26,顺序存储结构的C语言描述,#define MAX_TREE_SIZE 100TElenType SqBiTree MAX_TREE_SIZE,完全二叉树,普通二叉树,2-Aug-23,27,二 二叉树的链式存储结构,根据不同的需要，可以设计不

15、同的节点结构，从而得到不同的链式存储结构。常用的链式存储结构有两种：二叉链表，节点中有两个指针域，分别指向左右孩子三叉链表，节点中有三个指针域，分别指向左右孩子和父亲,2-Aug-23,28,二叉链表与三叉链表示例,2-Aug-23,29,二叉链表存储C描述,typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,2-Aug-23,30,第四节 遍历二叉树,在实际应用中通常要在二叉树中查找具有某些特性的节点，或是对二叉树中的所有节点作某种处理，这就需要涉及二叉树的遍历问题。所谓树的

16、遍历，就是按某种次序访问树中的节点，要求每个节点访问一次且仅访问一次。树遍历的典型例子：计算机上删除目录必须找到一种规律，将二叉树转换为一种线性结构，然后进行遍历。,2-Aug-23,31,二叉树的遍历方法,由于二叉树是由根节点、左子树、右子树三部分组成的,假定访问根节点记作 D，遍历根的左子树记作 L，遍历根的右子树记作 R那么二叉树可能的遍历次序有6种:DLR，DRL，LDR，LRD，RDL，RLD若限定先访问左子树后访问右子树，则可能有三种遍历方法：先（根）序遍历DLR，先访问根，然后是左子树和右子树 中（根）序遍历LDR，先访问左子树，然后是根和右子树 后（根）序遍历LRD，先访问左子

17、树和右子树，然后是根,2-Aug-23,32,先序遍历算法,表达式语法树,若二叉树为空，则空操作；否则访问根节点(D)；先序遍历左子树(L)；先序遍历右子树(R)。举例：先序遍历结果：-+a*b-c d/e f,2-Aug-23,33,中序遍历算法,若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根节点(D)；中序遍历右子树(R)举例：遍历结果 a+b*c-d-e/f,2-Aug-23,34,后序遍历算法,若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根节点(D)举例：遍历结果 a b c d-*+e f/-,2-Aug-23,35,三种遍历算法示例,先序遍

18、历得到的序列为：ABDEHIJKCFG中序遍历得到的序列为：DBHEJIKAFCG后序遍历得到的序列为：DHJKIEBFGCA,2-Aug-23,36,先序遍历算法的C语言描述,Status preordertranverse(BiTree T,statsus(*visit)(TelemType)if(T)visit(T-data);preorderTranverse(T-lchild,visit);preorderTranverse(T-rchild,visit);return OK;,2-Aug-23,37,C语言函数的递归调用,如果函数体中的某语句调用函数本身，那么这个函数是递归的。例：

19、定义阶乘 n!的递归函数factr(int n)与非递归fact(int n),factr(int n)int answer;if(n=1)return 1;answer=factr(n-1)*n;return anwser;fact(int n)int t,answer;answer=1;for(t=1;t=n;t+)answer=answer*t;return anwser;,2-Aug-23,38,递归程序,递归程序的主要优点是能够使某些算法更清晰简洁。编写递归函数时必须在恰当的位置放置if条件语句，让递归函数不需要继续递归而是立即返回。函数调用自己时在栈上为局部变量和参量分配存储空间，

20、从头执行函数代码，并不复制函数代码。,2-Aug-23,39,递归示例1：统计叶子节点数目,int CountLeafNum(BiTree T)if(T=NULL)return 0;if(T-lchild=NULL,2-Aug-23,40,递归示例2：计算树的高度,int ComputeTreeHeight(BiTree T)int lh;int rh;if(T=NULL)return 0;if(T-lchild=NULL,2-Aug-23,41,中序遍历非递归算法(1),status InOrderTraverse(BiTree T,Status(*Visit)(TElement e)Ini

21、tStack(S)；push(S,T);while(!StackEmpty(S)while(GetTop(S,p),2-Aug-23,42,非递归算法(1)示意图,a,Stack,b,c,null,Output:,c,e,2-Aug-23,43,中序遍历非递归算法(2),status InOrderTranverse(BiTree T，Status(*Visit)(TElement e)InitStack(S);p=T;while(p|!EmptyStack(S)if(p)push(S,p);p=p-lchild;else pop(S,p);visit(p-data);p=p-rchild;r

22、eturn OK;,2-Aug-23,44,非递归算法(2)示意图,a,Stack,b,c,Output:,c,e,两种方法的区别是（2）的处理要简洁些，空指针不需要入栈，而方法(1)有多次的空指针入栈、出栈操作。,2-Aug-23,45,先序遍历非递归算法,status PreOrderTranverse(BiTree T，Status(*Visit)(TElement e)InitStack(S);p=T;while(p|!EmptyStack(S)if(p)visit(p-data);push(S,p);p=p-lchild;else pop(S,p);p=p-rchild;return

23、 OK;,2-Aug-23,46,二叉树形态与遍历结果的关系,当二叉树的形态确定后，那么它的先序、中序和后序遍历的结果就已经确定。但是单纯根据二叉树的先序、中序或后序遍历的序列不可能完全确定二叉树的形态。如果要完全确定二叉树的形态需要知道先序和中序的结果，或是中序和后序遍历的结果,2-Aug-23,47,创建二叉树,单纯根据先序、中序或后序无法完全确定二叉树的形态因此必须在输入过程中输入特殊的字符来表示某个节点的左右子树是否为空，以便帮助建立二叉树比如：要建立右面的二叉树，则输入先序序列为：ABCDEGH特殊符号用来表示子树为空,2-Aug-23,48,按先序序列建立二叉树的C算法,Statu

24、s CreateBitree(BiTree,2-Aug-23,49,二叉树遍历C程序演示,演示如何根据插入了特殊符号的先序序列建立完整的二叉树演示如何利用递归算法实现树的先序、中序和后序遍历演示如何利用递归计算树的高度和叶子数目程序 example61.c,2-Aug-23,50,第五节 线索二叉树,二叉树遍历后得到一个节点的线性序列每个节点都有自己的前驱和后继,先序序列:A B C D E F G H K,中序序列:B D C A H G K F E,后序序列:D C B H K G F E A,2-Aug-23,51,基本概念,问题：能否利用这些空指针域来指向遍历结果中的前驱和后继？现象：

25、节点中有很多空的指针区域有n个节点的二叉树必然有n+1个空指针域赋予新用途的空指针被称为“线索”,2-Aug-23,52,线索示意图,先序序列:A B C D E F G H K,区分子树和线索的方法,为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域ltagltag=LINK lchild域指向其左子树ltag=THREAD lchild域指向其“前驱”rtagrtag=LINK rchild域指向其右子树rtag=THREAD rchild域指向其“后继”,2-Aug-23,53,如何对二叉树进行线索化,在遍历过程中修改当前结点的左、右空指针域以保存该结点的“前驱”和“后继”信息。

26、此过程称为对二叉树的线索化。遍历过程中,附设指针p指向当前访问的结点,指针pre指向它的前驱。,2-Aug-23,54,中序线索化C语言描述,void InThreading(struct BiTNode*p,struct BiTNode*pre)if(p)InThreading(p-lchild,pre);if(!p-lchild)p-ltag=THREAD;else p-ltag=LINK;if(!p-rchild)p-rtag=THREAD;else p-rtag=LINK;if(!p-lchild)p-lchild=*pre;if(!(*pre)-rchild)(*pre)-rchil

27、d=p;(*pre)=p;InThreading(p-rchild,pre);,2-Aug-23,55,先序线索化C语言描述,void PreThreading(struct BiTNode*p,struct BiTNode*pre)if(p)if(!p-lchild)p-ltag=THREAD;else p-ltag=LINK;if(!p-rchild)p-rtag=THREAD;else p-rtag=LINK;if(!p-lchild)p-lchild=*pre;if(!(*pre)-rchild)(*pre)-rchild=p;(*pre)=p;InThreading(p-lchild

28、,pre);InThreading(p-rchild,pre);,2-Aug-23,56,后序线索化C语言描述,void PostThreading(struct BiTNode*p,struct BiTNode*pre)if(p)InThreading(p-lchild,pre);InThreading(p-rchild,pre);if(!p-lchild)p-ltag=THREAD;else p-ltag=LINK;if(!p-rchild)p-rtag=THREAD;else p-rtag=LINK;if(!p-lchild)p-lchild=*pre;if(!(*pre)-rchild

29、)(*pre)-rchild=p;(*pre)=p;,2-Aug-23,57,线索化初始问题,问题：在树进行线索化之前，pre值为空左子树最左下的节点线索也为空办法人为建立一个头节点head将树T作为head的左子树 head-lchild=T初始时pre=T,2-Aug-23,58,线索化初始问题,2-Aug-23,59,线索二叉树的遍历,在线索二叉树中添加了“前驱”和“后继”的信息简化了遍历的算法：不需要堆栈不需要递归只要先找到第一个结点,然后依次找结点的后继直到后继为空时为止。只要先找到最后一个结点,然后依次找结点的前驱直到前驱为空时为止。,2-Aug-23,60,线索二叉树中序遍历示例

30、,中序遍历的第一个结点树上左子树最左下的节点（ltag=THREAD)当前结点的后继若 rtag=THREAD,则rchild指向后继否则，对将右子树设为中序遍历的第一个结点,2-Aug-23,61,2-Aug-23,62,二叉树线索化及遍历C程序演示,演示如何根据对二叉树进行线索化演示如何在线索二叉树上进行遍历程序 example62.c,2-Aug-23,63,第七节 树和森林,树的特点与二叉树不同的是，树的每个节点可能会有多个分支，因此树的表示方法与二叉树的表示方法略有不同。树的表示方法主要有以下三种：双亲表示法孩子表示法孩子兄弟表示法,2-Aug-23,64,树的应用示例 BBS,2-

31、Aug-23,65,双亲表示法,利用树中所有节点只有一个双亲的特点，用一组连续的存储单元来表示树中的每个节点，在这些存储单元中需要有一个数据域来表示该节点的双亲。,#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data;int parent;PTNode;typedef struct PTNode nodesMAX_TREE_SIZE;int n;PTree;,2-Aug-23,66,树的双亲表示法示例,数组下标,2-Aug-23,67,双亲表示法的特点,由孩子找双亲比较方便，但是由双亲找孩子需要遍历整个数据表。,2-Aug-

32、23,68,孩子表示法,在节点中给每个孩子分配一个指针域。由于树中各个节点的度不同，意味着不同的节点可能有不同数目的指针域，通常有两种解决办法：固定节点结构，即：根据树的度，为每个节点分配固定数目的指针域非固定的节点结构，即：在节点中需要增加一个域来指示该节点有多少个指针域,2-Aug-23,69,固定节点结构,固定节点结构 假定d为树的度，于是每个节点有d个指针域。特点：实现容易，但容易浪费空间，因为节点必须按照树的度来设计。,2-Aug-23,70,非固定节点结构,根据各个节点度的不同，采用不同的结构节点中有一个专门的域用来表示该节点中指针的数目。特点：节约空间但实现比较复杂,2-Aug-

33、23,71,链式孩子表示法,把每个节点的孩子节点排列起来，形成一个线性表，且以单链表作为存储结构。,普通的树,孩子表示法得到的链表,2-Aug-23,72,孩子表示法的特点,n个节点的树需要有n个单链表来表示n个头指针构成一个线性表每个节点在表中出现两次（根节点除外）采用孩子表示方法，寻找某个节点的孩子方便了，但要寻找某个节点的双亲同样需要搜寻所有的孩子链表可以在孩子链表中添加一个表示双亲位置的区域。这就得到孩子双亲表示法,2-Aug-23,73,孩子兄弟表示法,又称为二叉树表示法，或二叉链表表示法。每个节点有两个指针：一个指向该节点的第一个孩子节点，第二个指针指向该节点的下一个兄弟。C语言描

34、述的数据结构如下：typedef struct CSNode ElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,2-Aug-23,74,孩子兄弟表示法示例,普通的树,孩子兄弟法得到的二叉树,2-Aug-23,75,孩子兄弟表示法的特点,利用这种表示方法可以将普通的树变换为二叉树。注意：用二叉树表示法来表示树将得到一个右子树为空的二叉树。,2-Aug-23,76,二、森林与二叉树的转换,二叉树B由三部分构成树根root(B)左子树 LB右子树 RB普通的森林由三部分构成第一个颗树的根节点第一颗树根节点的子树森林

35、除第一颗树之外的其它树构成的森林,2-Aug-23,77,换一个角度来看树的概念,A,根节点,子树森林,2-Aug-23,78,换一个角度看森林,T1,T2,T3,根节点,子树森林,其它树构成的森林,2-Aug-23,79,森林转化成二叉树的规则,假定 F=T1,T2,Tn是森林，B=(root,LB,RB)是二叉树若F为空，即n=0，则对应的二叉树B为空二叉树。若F不空，则：对应二叉树B的根root(B)是F中第一棵树T1的根root(T1)；其左子树为LB 由T11,T12,T1m构成，其中，T11,T12,T1m是root(T1)的子树；其右子树为RB由T2,T3,Tn构成，其中，T2,

36、T3,Tn是除T1外其它树构成的森林。,2-Aug-23,80,森林转换为二叉树递归概念示意图,T1,T2,T3,根节点,子树森林,其它树构成的森林,A,二叉树,左子树,右子树,2-Aug-23,81,森林转换为二叉树示例,T1,T2,T3,B,A,F,H,2-Aug-23,82,森林转换为二叉树的非递归方法,首先将森林的每棵树用二叉树表示法转换为二叉树然后将森林中的第二棵树看成是第一棵树的兄弟，即 将第二颗树作为右子树添加到第一颗树上去以此类，直到将所有的树转换为一颗二叉树,2-Aug-23,83,森林转换为二叉树的非递归方法示例,2-Aug-23,84,二叉树转换为森林的规则,如果B为空，

37、则对应的森林F也为空。如果B非空，则：F中第一棵树T1的根为root(B)；root(B)的左子树 LB 转换为T1的子树森林 T11,T12,T1m root(B)的右子树 RB 转换成林F 中除了 T1 之外其余树组成的森林 T2,T3,Tn,2-Aug-23,85,二叉树转换森林为示例,F,H,T1,T2,T3,B,A,2-Aug-23,86,树和森林的遍历,与二叉树的遍历不相同的是，由于树可能有多个子树，因此树的遍历只有先根遍历和后根遍历两种。先根遍历就是先访问根节点，然后依次先根访问树的各个子树。后根遍历就是先依次后根遍历树的各个子树，最后访问树的根节点。,2-Aug-23,87,树

38、的遍历示例,先根遍历：后根遍历：,A,B,C,D,E,B,D,C,E,A,2-Aug-23,88,森林的遍历,根据先遍历森林中第一颗树的根结点还是先遍历第一颗树根节点的子树森林，可以将森林的遍历分为两种：先序遍历森林中序遍历森林 先序遍历森林规则若森林F为空,返回；否则访问F的第一棵树的根节点；先序遍历第一棵树的子树森林；先序遍历其它树组成的森林。中序遍历森林规则若森林F为空,返回；否则中序遍历第一棵树的子树森林；访问F的第一棵树的根节点；中序遍历其它树组成的森林。,2-Aug-23,89,先序遍历森林的示例,A,T1,T2,T3,先序森林遍历结果：,B,C,D,F,E,H,I,K,J,2-A

39、ug-23,90,中序遍历森林的示例,B,T1,T2,T3,中序森林遍历结果：,C,D,A,E,F,K,I,J,H,2-Aug-23,91,关于森林遍历的几点说明,将森林转换为二叉树后，森林的先序和中序遍历就可以通过对二叉树的先序和中序遍历来实现。,2-Aug-23,92,第八节 huffman树及其应用,基本术语：路径：从树的一个节点到另一个节点之间的所有分支构成路径路径长度(Path Length)：连接两节点的路径上的分支数目。树的路径长度:树根节点到各节点的路径长度之和节点的带权路径长度：路径长度乘以节点的权值树的带权路径长度：树的所有叶节点的权值与该节点到根的路径长度的乘积之和（带权

40、路径长度和）。WPL=wili特别注意：树的带权路径长度只计算叶节点的带权路径长度和，并不计算非终端节点,2-Aug-23,93,树的路径长度示例,0，1，1，2，2，2，2，3 PL=13,0，1，1，2，2，2，3，3 PL=14,2-Aug-23,94,树的带权路径长度示例,(a)WPL=22+42+52+72=36(b)WPL=21+42+53+73=46(c)WPL=71+52+23+43=35,2-Aug-23,95,Huffman树,带权路径长度最小的二叉树称为最优二叉树，也叫huffman 树。huffman树的特点：在叶子节点数目和权值相同的情况下，Huffman树的带权路径

41、最小权值大的节点离根最近。Huffman树在信号与信息处理领域有非常广泛的应用数据压缩视频、语音编码,2-Aug-23,96,Huffman树的应用示例,例：统计学生的成绩，检验学生的学习效果，同时评判考试题目是否合理。若设计程序对各个分数段的学生成绩进行统计，则最直观的设计思路如下图所示,2-Aug-23,97,Huffman应用示例,通常情况下学生的考试成绩是一种正态分布，也就是大部分学生处于中等水平，特别优秀或特别差的学生很少假定一般情况下学生成绩分布如下表所示如果有10000个学生，根据比例，各个分数段的学生数目应该为：500，1500，4000，3000，1000。如果采用前面的算法

42、，那么在统计过程中需要比较的次数为：采用该比较方法，统计10000个学生需要比较的次数为：5001+15002+40003+30004+10004=31500次,2-Aug-23,98,改进的统计算法,如果我们采用下面的统计方法则需要比较的次数为：5003+15003+40002+30002+10002=22000次,2-Aug-23,99,算法效率提高的原因,我们有处理对象的先念知识，即：我们知道学生成绩的分布情况。这一般需要根据经验或统计分析得到。由于大部分学生的成绩在70到90分之间，算法改进后，大部分学生的成绩只需要比较2次就可以做出判断只有成绩特别差或特别好的学生才需要多次比较。但由

43、于这些学生的人数很少，因此不会占用较多的计算时间如果我们把不同档次的学生数目看成是叶子节点的权值将每个学生成绩需要比较的次数看成是从根节点到叶子节点的路径那么要使比较的次数最小就是要使二叉树的带权路径最小，即：根据权值生成huffman树,2-Aug-23,100,如何构造一棵最优二叉树,(1)由给定的n个权值w1,w2,wn，构造n棵二叉树的森林F=T1,T2,Tn，其中每一棵二叉树Ti中只有一个带有权值wi的根节点，其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止：在F中选取两棵根节点权值最小的二叉树作为左右子树构造一棵新的二叉树，置新的二叉树的根节点的权值为其左、右子树上

44、根节点的权值之和 在F中删去这两棵二叉树 把新的二叉树加入F中,2-Aug-23,101,Huffman树构造示例,2-Aug-23,102,Huffman编码,主要用途是实现数据压缩。通信系统中传送的是一个一个的符号，每个通信系统传送的符号个数可能不同，每个符号出现的概率和编码长度也可能不同。如果我们用 Wi 表示这种符号出现的概率，路径长度Li表示该符号编码后的比特数，那么 WPL=WiLi表示每传送一个符号需要的平均比特数。显然我们总是希望平均比特数越小越好。在什么情况下比特数能够达到最小？根据各个符号的概率建立huffman树。,2-Aug-23,103,Huffman编码需要解决的问

45、题,例：有8个符号的通信系统，假设8个符号出现的概率分别为：A(0.4)，B(0.3)，C(0.1)，D(0.08)E(0.05)，F(0.04)，G(0.02)，H(0.01)如果用定长编码，显然每个码字需要3比特，比如：A000 B001 C010 D011E100 F101 G110 H111如果采用Huffman编码，显然出现概率大的符号编码后的码长比较小，而概率小的符号编码后的码长比较长由于各个符号的码长不一样，那么在接收端解码的时候会出现问题，比如：假定有三个符号A，B，C，他们编码的结果是：0，01，001，那么当接收端接收到0001时，接收端不知道发送端发送的是A，A，B还是A

46、，C。这是因为这三个符号的编码中A是B和C的前缀，B又是C的前缀。解决的办法：在编码过程中任何一个符号的码字均不能是另一个符号码字的前缀。,2-Aug-23,104,前缀码（唯一可解码）,如果各个符号编码后的码长不相同，那么每个码字的编码不能是其它码字的前缀，接收端才能进行正确的解码，这种编码称为前缀码。为了得到前缀编码，可以使用最优二叉树，并采用如下规则：约定左分支表示符号“0”，右分支表示符号“1”，从根节点到叶子节点的路径上的分支字符组成的字符串作为该叶子节点字符的编码这个过程称为Huffman编码,2-Aug-23,105,前缀码实现示例,2-Aug-23,106,Huffman编码示

47、例,对于上面的例子，根据各个符号出现概率的不同构造一颗Huffman树假定我们约定左分支表示符号0，右分支表示符号1，则可以得到各个符号的编码如下：A0 B10 C1111 D1110E1100 F11011G110101H110100,2-Aug-23,107,计算编码效率,采用定长编码每个符号要用3比特来表示采用Huffman编码后，每个符号的平均长度为：可以计算出它们的平均码长：=0.401+0.302+0.104+0.084+0.054+0.044+0.026+0.016=2.3即：平均每个符号只需要2.3个比特。那么，编码效率提高了(3.0-2.3)/3100%23%,2-Aug-2

48、3,108,Huffman树的构造过程示例,输入四个符号 A,B,C,D，它们的频率为:1/12,2/12,4/12,5/12,1,2,4,5,1,2,3,3,4,7,7,5,12,0,1,0,1,0,1,1,100,2,101,4,11,5,0,12,建立huffman树,给每个分支赋值,获得每个符号的编码,2-Aug-23,109,Huffman解码示例,假定接收到的输入为:110100101,1,2,3,4,7,5,12,0,1,0,1,0,1,1,1,C,0,D,1,0,0,A,1,0,B,1,译码后的输出:CDAB,2-Aug-23,110,Huffman编码存储C描述,typede

49、f struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char*HuffmanCode;,2-Aug-23,111,Huffman编码算法(初始化）,void HuffmanCoding(HuffmanTree,2-Aug-23,112,Huffman编码算法(建树）,for(i=n+1;i=m;i+)Select(HT,i-1,s1,s2);/从前面i-1元素中选择parent=0且权值最小的两个值 HTs1.parent=i;HTs2.parent=i;HTi.l

50、child=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;,1,2,5,3,4,2-Aug-23,113,Huffman编码算法(编码）,HC=(HuffmanCode)malloc(n+1)sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char*