数据结构 第6章 树和二叉树 什么是树和二叉树？？ 二叉树的遍历 数据结构.

Presentation on theme: "数据结构 第6章 树和二叉树 什么是树和二叉树？？ 二叉树的遍历 数据结构."— Presentation transcript:

1 数据结构 第6章 树和二叉树 什么是树和二叉树？？ 二叉树的遍历 数据结构

2 树是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。
树是一类重要的非线性结构。 树是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。 树在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。 树在计算机领域中也有着广泛的应用，例如 在编译程序中，用树来表示源程序的语法结构； 在数据库系统中，可用树来组织信息； 在分析算法的行为时，可用树来描述其执行过程。等等。 数据结构

3 树 树：是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则， 有且仅有一个特定的结点被称为根，
当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树，并称其为子树(Subtree)。 由此可以看出，树的定义是递归的。 数据结构

4 树的基本概念 分支：根和子树根之间的连线称为“分支”； 树的结点：数据元素和所有指向子树根的分支构成树中一个“结点”；
结点的度：结点拥有的子树数称为结点的度； 树的度：树中所有结点度的最大值定义为“树的度” ； 叶子：度为0的结点称为叶子或终端结点。 分支结点：度不为0的结点称为非终端结点或分支结点。 孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。 兄弟：同一个双亲的孩子之间互称。 数据结构

5 结点的祖先：是从根到该结点所经分支上的所有结点。 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。 堂兄弟：其双亲在同一层的结点互为堂兄弟。 树的深度：树中结点的最大层次称为树的深度，或高度。 有序树：如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。 森林:是m(m>=0)棵互不相交的树的集合。 数据结构

6 树的表示方法 数据结构 直观表示法：树，用于直观描述树的逻辑结构。
形式化表示法：定义树T为T=(D,R)，其中D为树T中结点的集合，R为树T中结点之间关系的集合。当树T为空树时D=EMPTY；当树T不为空树时有D={Root}U DF，其中Root为树T的根结点，DF为树T的根Root的子树集合，可由下式表示： DF = D1UD2U…Dm (1<=i,j<=m, Di/\Dj = EMPTY) 当树T中结点个数n=0或n=1时，R=EMPTY；当树T中结点个数n>1时，有： R={<Root,ri>,i = 1,2,…n-1} 其中，Root是树T的非终端结点，ri是结点Root的子树Ti的根结点，<Root,ri>表示了结点Root和结点ri的父子关系。 主要用于树的理论描述 凹入表示法：P120 图6.2(c)，主要用于屏幕显示和打印输出 集合表示法：P120图6.2(a) 广义表表示法：P120图6.2(b) 数据结构

7 树和线性结构的对比 数据结构

8 二叉树 A (a) B 空二叉树 C (b) 根和空的左右子树 (e) (c) (d) 根和左右子树 根和左子树 根和右子树
二叉树：是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树（即不存在度大于2的结点）； （2）子树有左右之分。 二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。 (a) 空二叉树 A B C (b) 根和空的左右子树 (c) 根和左子树 (d) 根和右子树 (e) 根和左右子树 数据结构

9 二叉树的性质 数据结构

10 【性质1】 在二叉树的第i层上最多有2i-1个结点（i≥1）。
假设对所有的j，1≤j<i成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。 数据结构

11 【性质2】 深度为K的二叉树最多有2K-1个结点（K≥1）。
数据结构

12 【性质3】 对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。(P124)
证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。 因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为： n=n0+n1+n （1） 再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。 又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。 将此式代入上式，得： n=n1+2n （2） 用（1）式减去（2）式，并经过调整后得到：n0=n2+1。 数据结构

13 满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。
3 4 5 7 6 满二叉树 数据结构

14 完全二叉树：对满二叉树从上到下从左到右进行从1开始的编号，则任意一棵二叉树都可以和同深度的满二叉树相对比。 　　假如一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一、一对应，则称这类二叉树为完全二叉树。 1 1 1 2 3 2 3 2 3 4 4 7 5 6 5 7 6 (a)完全二叉树 (c)非完全二叉树 (b)非完全二叉树 数据结构

15 前h-1层中的结点都是“满”的，即叶子结点只可能在层次最大的两层上出现；
且第 h 层的结点都集中在左边，即对任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。 。 显然，满二叉树本身也是完全二叉树。 数据结构

16 【性质4】 具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。
证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出： 2K-1-1<n≤2K-1 将不等式两端加1得到： 2K-1≤n<2K 将不等式中的三项同取以2为底的对数，并经过化简后得到： K-1≤log2n<K 由此可以得到：log2n =K-1。整理后得到：K= log2n+1。 数据结构

17 【性质5】 对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1≤i≤n），都有：
（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为 i/2。 （2）如果2i>n，则结点i没有左孩子；否则其左孩子结点的编号为2i。 （3）如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。 证明：利用数学归纳法证明这个性质。 首先证明（2）和（3）。 当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；若n<3，则根没有右孩子；若n<2，则根将没有左、右孩子；以上对于（2）和（3）均成立。 假设：对于所有的1≤j≤i 结论成立。即：结点j的左孩子编号为2j；右孩子编号为2j+1。 由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。 数据结构

18 可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i 的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。 又因为二叉树由n个结点组成，所以，当2(i+1)+1>n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)>n，结点i+1既没有左孩子也没有右孩子。 以上证明得到（2）和（3）成立。 下面利用上面的结论证明（1）。 对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而 2i/2=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而 (2i+1)/2 =i，由此可以得出（1）成立。 数据结构

19 二叉树的顺序存储结构 二叉树的顺序存储结构用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，以使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系，为此使用编号法。即从树根起，自上层至下层，每层自左至右的给所有结点编号。 #define MAX_TREE_SIZE 100 typedef TElemType SqBiTree[MAX_TREE_SIZE]; SqBiTree bt; 1 2 3 4 5 6 7 数据结构

20 二叉树的链式存储结构 由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表结点中至少包含三个域：数据域、左指针域及右指针域。 typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 二叉链表 数据结构

21 lchild data parent rchild
二叉链表的存储特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。 lchild data parent rchild 数据结构

22 二叉树的遍历 “遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。访问可以是输出、比较、更新、查看元素内容等等各种操作。
对于线性结构，其是一个“序列”，每个数据元素只有一个后继，因此它的遍历只有一条搜索路径，即从第一个数据元素起，顺着“后继”直到最后一个数据元素止。 而对于非线性结构，其每个数据元素可以有多个后继，为保证“遍历”成功就需要确定合适的搜索路径，使得结构中的每个数据元素都出现在这条搜索路径上，以确保每个数据元素都被访问到。 数据结构

23 由二叉树的递归定义可知，二叉树的三个基本组成单元是：根结点、左子树和右子树。
假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则遍历整个二叉树有DLR、LDR、LRD、DRL、RDL、RLD六种方案。若规定先左后右，则只有前三种情况，分别规定为： DLR——先（根）序遍历， LDR——中（根）序遍历， LRD——后（根）序遍历。 数据结构

24 1、先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。
2、中序遍历二叉树的操作定义为： （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 3、后序遍历二叉树的操作定义为： （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 数据结构

25 若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为： -+a*b-cd/ef 按中序遍历,其中序序列为：
例如图所示的二叉树表达式 (a+b*(c-d)-e/f) 若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为： -+a*b-cd/ef 按中序遍历,其中序序列为： a+b*c-d-e/f 按后序遍历,其后序序列为： abcd-*+ef/- － / ＋ f e a * b - c d 数据结构

26 遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。
（1）先序遍历递归算法 void PreOrder(BiTree BT){ if (BT) { Visit(BT); PreOrder(BT->Lchild); PreOrder(BT->Rchild); } （2）中序遍历递归算法 void InOrder(BTree BT) { if (BT) { InOrder(BT->Lchild); Visit(BT); InOrder(BT->Rchild); } （3）后序遍历递归算法 void PostOrder(BTree BT){ if (BT) { PostOrder(BT->Lchild); PostOrder(BT->Rchild); Visit(BT); } 数据结构

27 二叉树遍历举例 建立一棵二叉树 Status CreateBiTree(BiTree &T)　{ 　// 按先序次序输入二叉树中结点的值（一个字符），空格表示空树 　　scanf(&ch) ； 　　if (ch==‘ ‘) T=NULL;　　　　　　　　 　　else { 　 if(!(T=(BiNode*)malloc(sizeof(BiNode))))exit(OVERFLOW); 　　　　　　　　 T->data = ch; 　　　CreateBiTree(T->Lchild); 　　// 递归建(遍历)左子树 　　　CreateBiTree(T->Rchild); 　　// 递归建(遍历)右子树 　　} // else return OK; 　} // CreateBiTree 数据结构

28 void Leaf(BiTree T,int *count){ if (T) { Leaf(T->lchild,&count);
计算一棵二叉树的叶子结点数目 void Leaf(BiTree T,int *count){ if (T) { Leaf(T->lchild,&count); //计算左子树的叶子结点个数 if (T->lchild==NULL&&T->rchild==NULL) (*count)++; Leaf(T->rchild,&count); //计算右子树的叶子结点个数 } 数据结构

29 线索二叉树 对二叉树进行遍历的过程即为沿着某一条搜索路径对二叉树中的结点进行一次且仅仅一次的访问，换句话说，就是按一定规则将一个处于层次结构中的结点排列成一个线性序列之后进行依次访问，这个线性序列或是先序序列、或是中序序列或是后序序列，在这些线性序列中每个结点（除第一个和最后一个外）有且仅有一个直接前驱和直接后继。 数据结构

30 例如右图所示二叉树中的数据元素"E" 在先序序列中的前驱是"D"，后继是"G"；而在中序序列中的前驱是"G"，后继是"H"；在后序序列中的前驱是"H"，后继是"B"。显然，这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行"遍历"时就可以将二叉树视作线性结构进行访问操作了。 数据结构

31 lchild ltag data rtag rchild
如何保存在遍历过程中得到的前驱和后继信息？最简单的办法是在结点中增加两个指针域分别指向该结点的前驱和后继，但如此做将使存储结构的存储密度大大降低。 而另一方面，二叉链表中有大量链域的值为“NULL”，可以利用这些空的指针域存放指向前驱和后继的信息，由此得到的二叉树的存储结构称作“线索链表”，其中指向前驱或后继的指针称作“线索”。 其中: 0 lchild 域指示结点的左孩子 ltag={ lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag={ 1 rchild 域指示结点的后驱 以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树 lchild ltag data rtag rchild 数据结构

32 typedef enum PointerType{ Link=0, Thread=1 }; 　　　　// 定义指针类型，以 Link 表示指针，Thread 表示线索 　typedef struct BiThrNode{ 　　ElemType data; 　　struct BiThrNode *Lchild, *Rchild; // 左右指针 　　PointerType LTag, RTag;　// 左右指针类型标志 　} *BiThrTree; 模仿线性表的存储结构,在二叉树的线索链表上也添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;同时,令二叉树中序序列中的第一个结点lchild域指针的和最后一个结点rchild域的指针均指向头结点;就像为二叉树建立了一个双向线索链表，即可以从头结点出发，依照中序遍历的规则对二叉树中的结点依次进行"顺序"（和中序序列相同的次序）访问，或"逆序"（和中序序列相反的次序）访问。 数据结构

33 以中序线索链表为存储结构的中序遍历 以线索链表作存储结构时，由于在线索链表中已经包含有遍历得到的访问次序序列的信息，则在线索链表中进行遍历时，首先找到遍历中应该访问的“第一个”结点，而后顺每个结点的“后继”依次进行访问即可。 关键问题有二： 　　　一是如何找到访问的第一个结点？ 　　　二是如何找到每个结点在中序序列中的后继？ 以中序遍历为例，访问的第一个结点必定是 “其左子树为空”的结点。若根结点没有左子树，则根结点即为中序遍历访问的第一个结点，若根结点的左子树不空，则访问的第一个结点应该是其左子树中“最左下的结点”，即从根结点出发，顺指针 Lchild 找到其左子树直至某个结点的指针 Lchild 为“线索”止，该结点必为中序序列中的第一个结点。 若结点没有右子树，即结点的右指针类型标志 Rtag 为“Thread”，则指针 Rchild 所指即为它的后继，若结点有右子树，则它的后继应该是其右子树中访问的第一个结点。则和前面所述找二叉树的第一个结点一样，就应该从它的右子树根出发，顺指针 Lcuild 直至没有左子树的结点为止，该结点即为它的后继。 数据结构

34 Status InorderTraverse_Thr(BiThrTree T,status(*visit)(TElemType)){
//T指向头结点,头结点的lchild左链指向根结点 //中序遍历二叉线索树的非递归算法 P=T–>lchild; while(p!=T){ while(p –>LTag ==Link) p=p –>lchild; if(!visit(p –>data)) return error; while(p –>RTag= =Thread&&p –>rchild!=T){ p=p –>rchild; Visit(p –>data); } p= p–>rchild; return OK; }//InorderTraverse_Thr 数据结构

35 二叉线索树的建立 由于线索链表上保存的是“遍历”过程中得到的前驱和后继的信息，显然，线索链表应该在遍历过程中建立，即在遍历过程中改变二叉链表中结点的“空指针”以及相应的“指针类型标志”。 若结点没有左子树，则令其左指针指向它的“前驱”并将左指针类型标志改为“Thread”，若结点没有右子树，则令它的右指针指向它的“后继”并将右指针类型标志改为“Thread”。 为了获取"前驱"的信息，需要在遍历过程中添加一个指向其前驱的指针pre。 if (!pre->Rchild) { 　　　pre->RTag = Thread; 　　　pre->Rchild = p; } if (!p->Lchild) { 　　　p->LTag = Thread; 　　　p->Lchild = pre; } pre = p; 数据结构

36 Status InorderThreading(BiThrTree &Thrt,BiThrTree T){
// T为指向二叉树根结点的指针，由此二叉链表建立二叉树的中序线索链 表，Thead 指向线索链表中的头结点。 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); Thrt –>LTag =Link; Thrt –>RTag =Thread; Thrt –>rchild=Thrt; if(!T) Thrt –>lchild=Thrt; else{ Thrt –>lchild=T; pre=Thrt; InThrTreading(T); //中序遍历进行中序线索化 pre –>rchild=Thrt; pre –> RTag=Thread; Thrt –>rchild=pre; } return OK; }//InorderThreading 数据结构

37 Void InThreading(BiThrTree p){ if(p){ InThreading(p –>lchild);
if(!p –>lchild) { p –>LRag =Thread; p –>lchild=pre; } if(!pre –>rchild){ pre –>RRag =Thread; pre –>rchild=p; pre=p; InThreading(p –>rchild); 数据结构

38 树的存储结构 常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。 1. 双亲表示法
存储树中结点时，包含两个信息：结点的值data和体现结点之间相互关系的属性--该结点的双亲parent。 #define MAXSIZE typedef struct PTNode { /*结点的类型*/ datatype data; int parent; /*结点双亲的下标*/ }PTNode; typedef struct{ node nodes[MAXSIZE]; /*存放结点的数组*/ int r, n ; /* 树中实际所含结 点的个数及根结点的位置*/ }PTree; 数据结构

39 data parent root A 1 2 D B C 3 4 H G 5 E F 6 7 I J K 8 9 (a) 一棵树 10
-1 B C D E 1 F G 3 H I 6 J K root A 1 2 D B C 3 4 H G 5 E F 6 7 I J K 8 9 (a) 一棵树 10 (b) (a)图的双亲表示法 数据结构

40 双亲表示法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。
算法实现举例： int Parent(PTree T,int node) { if (node<0||node>=T.n) return -2; else return T.nodes[node].parent; } 数据结构

41 根据子女位置的实现方法不同，孩子表示法分为： 指针方式的孩子表示法； 数组方式的孩子表示法； 链表方式的孩子表示法
2. 孩子表示法 采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置，即整棵树中所有结点的相互关系是通过指明结点子女的位置来体现的。 根据子女位置的实现方法不同，孩子表示法分为： 指针方式的孩子表示法； 数组方式的孩子表示法； 链表方式的孩子表示法 树的链表方式的孩子表示法中，把每个结点的子女排列起来形成一个单链表，这样n个结点就形成n个单链表；而n个单链表的头指针又组成一个线性表，为了查找方便，使用数组加以存储。 数据结构

42 # define MAXSIZE 50 typedef struct CTNode { /*孩子结点的类型*/ int child; /*该孩子结点在数组中的编号*/ struct CTNode *next; }*ChildPtr; typedef struct { /* 树中每个结点的类型 */ TElemType data; ChildPtr firstchild; /*孩子链表头指针*/ }CTBox; typedef struct { /*树的类型*/ CTBox nodes[MAXSIZE]; int n, r； }CTree; 数据结构

43 (a)图的链表方式的孩子表示法 (a) 一棵树
∧ K J I H G F E D C B A 1 2 3 4 5 6 7 8 9 10 child next data firstchild treelist root (a)图的链表方式的孩子表示法 B C D E F G A H I K J (a) 一棵树 数据结构

44 孩子表示法的特点是寻找某个结点的孩子比较容易。
int Child(CTree T, int node, int i) { if (node<0||node>=T.n) return -2； p=T.nodes[node].firstchild; j=1; while (p&&j!=i) { p=p->next; j++;}　　　 if (!p) return -2;　　　　　　　　　　　 else return p->child; } 但寻找该结点的双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。 数据结构

45 3. 孩子兄弟表示法 采用孩子兄弟表示法表示一棵树时，在存储树中每个结点时，除了包含该结点值域外，还设置两个指针域firstchild和rightsibling，分别指向该结点的第一个子女和其右兄弟，即以二叉链表方式加以存储，因此该方法也常被称为二叉树表示法。 typedef struct CSNode {/*树中每个结点的类型*/ datatype data; struct CSNode * firstchild, *rightsibling; } CSNode,*CSTree; 数据结构

46 A B C D E F G H I J K B C D E F G A H I K J (a) 一棵树 ∧ root
data firstchild rightsibling root (a)图的孩子兄弟表示法 数据结构

47 void AllChild(CSTree T, CSTree p) //输出树中p指针所指结点的所有孩子信息 {
q=p->fisrtchild; while (q) { printf(“%c”,q->item); q=q->nextsibling; } 数据结构

48 树（森林）与二叉树的转换 1. 树、森林转换成二叉树
方法：将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可。此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。 数据结构

49 树例：P137 森林例：P138 数据结构

50 2. 二叉树转换为森林 二叉树转换为森林实际上是森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。
若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。 例： 数据结构

51 树的遍历 树的遍历问题和二叉树的遍历类似，亦为从根结点出发，对树中各个结点进行一次且仅进行一次访问。
由对根的访问时机不同可得下列两个算法： 　一、先根(序)遍历树 　　若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树； 　二、后根(序)遍历树 　　若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点； 数据结构

52 A 前序遍历的结果： ABCEFHIGD D B C 后序遍历的结果： BEHIFGCDA G E F H I 数据结构

53 void preorder(CSTree p) {/*p为指向树根结点的指针*/
1. 树的先根遍历实现（孩子兄弟表示法） void preorder(CSTree p) {/*p为指向树根结点的指针*/ if (p){ /*树不为空*/ printf("%c",p->data); preorder(p->firstchild); preorder(p->nextsibling); } } 2. 树的后根遍历实现（孩子兄弟表示法） void postorder(CSTree p){ /*p为指向树根结点的指针*/ if (p){ /*树不为空*/ postorder(p->firstchild); postorder(p->nextsibling); printf("%c",p->data); } 数据结构

54 森林的遍历 森林的遍历问题和树的遍历类似，为从第一棵树的根结点出发，对森林中各个结点进行一次且仅进行一次访问。
由对根的访问时机不同可得下列两个算法： 　一、先根(序)遍历森林　 　二、中根(序)遍历森林 数据结构

55 1.先根(序)遍历森林 若森林不空，则可依下列次序进行遍历 　　(1) 访问森林中第一棵树的根结点； 　　(2) 先序遍历第一棵树中的子树森林； 　　(3) 先序遍历除去第一棵树之后剩余的树构成的森林。 2.中序遍历森林 　若森林不空，则可依下列次序进行遍历： 　　(1) 中序遍历第一棵树中的子树森林； 　　(2) 访问森林中第一棵树的根结点； 　　(3) 中序遍历除去第一棵树之后剩余的树构成的森林。 例　 数据结构

56 赫夫曼树及其应用 赫夫曼树：带权路径长度最短的树称为赫夫曼树或最优树。 路径：树的根结点到其余结点的分支。
结点的路径长度：从根结点到该结点的路径上分支的数目。 结点的带权路径长度：从树根到该结点之间的路径长度与该结点上所带权值的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。 在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树” 数据结构

57 数据结构

58 赫夫曼树的构造 (1) 根据给定的n个权值{w1, w2, …, wn}，构造n棵二叉树的集合F = {T1, T2, …, Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树; (2) 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和; (3) 从F中删去这两棵树，同时加入刚生成的新树; (4) 重复(2)和(3)两步，直至F中只含一棵树为止。 数据结构

59 例 数据结构

60 赫夫曼树的应用 1.判定树 在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。
例如，编制一个程序，将百分制转换成五个等级输出。一种形式如下： if (socre<60) printf(“bad”); else if (socre<70) printf(“pass”) else if (score<80) printf(“general”); else if (score<90) printf(“good”); else printf(“very good”); 数据结构

61 <60 bad <70 pass <80 general <90 good very good 数据结构

62 general 70≤...≤79 80≤...≤89 good 60≤...≤69 pass <59 bad very good
数据结构

63 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：
2.赫夫曼编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则： （1）发送方传输的二进制编码，到接收方解码后必须 具有唯一性，即解码结果与发送方发送的电文完全一样； （2）发送的二进制编码尽可能地短。 数据结构

64 1. 等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列： ，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。 2. 不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列： 发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一。 数据结构

65 前缀编码 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 。 可以利用二叉树来设计二进制的前缀编码。用叶子结点表示字 符，且约定左分支表示字符‘0’，右分支表示字符‘1’，则以由 从根到叶子的路径上的分支表示的字符组成的字符串作为该叶 子结点字符的编码。 数据结构

66 赫夫曼编码 在二叉树来表示的前缀编码中，以字符出现的 次数为权，构造一棵赫夫曼树，由此得到的二 进制前缀编码便为“最优前缀编码”(赫夫曼 编码)。即以这组编码传送电文可使电文总长 最短(对所有其它前缀编码而言)。 假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，以此为例设计赫夫曼编码。 数据结构

67 （3）由此赫夫曼树生成赫夫曼编码 赫夫曼编码设计过程为：
（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}； （2）以此集合中的数值作为叶子结点的权值构造一棵赫夫曼树，如P148图6.26所示； （3）由此赫夫曼树生成赫夫曼编码 数据结构

68 赫夫曼编码的实现 typedef struct{ int weight; int parent, lchild, rchild;
}HTNode, *HuffmanTree; typedef char** HuffmanCode; 数据结构

69 void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); for (i=1; i<=n; i++) { //初始化 HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=n+1; i<=m; i++) { //初始化 HT[i].weight=0; 数据结构

70 for (i=n+1; i<=m; i++) {
printf(“\n赫夫曼树的构造过程如下所示：\n"); for (i=n+1; i<=m; i++) { // 建赫夫曼树,在HT[1..i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2。 Select(HT, i-1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } 数据结构

71 1.//--- 从叶子到根逆向求每个字符的赫夫曼编码 cd = (char *)malloc(n*sizeof(char));
cd[n-1] = '\0'; // 编码结束符。 for (i=1; i<=n; ++i) {// 逐个字符求哈夫曼编码 start = n-1; // 编码结束符位置 for (c=i, f=HT[i].parent; f!=0; c=f,f=HT[f].parent) // 从叶子到根逆向求编码 if (HT[f].lchild==c) cd[--start] = '0'; else cd[--start] = '1'; HC[i] = (char *)malloc((n-start)*sizeof(char)); strcpy(HC[i], &cd[start]); } free(cd); // 释放工作空间 } // HuffmanCoding 数据结构

72 2.//--无栈非递归遍历赫夫曼树，求赫夫曼编码 cd = (char *)malloc(n*sizeof(char));
p = m; cdlen = 0; for (i=1; i<=m; ++i) HT[i].weight = 0; // 遍历赫夫曼树时用作结点状态标志 while (p) { if (HT[p].weight==0) { // 向左 HT[p].weight = 1; if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } else if (HT[p].rchild == 0) { HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串) } 数据结构

73 else if (HT[p].weight==1) { // 向右 HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; } } else { // HT[p].weight==2，退回退到父结点，编码长度减1 HT[p].weight = 0; p = HT[p].parent; --cdlen; } // HuffmanCoding 数据结构

74 cd = (char *)malloc(n*sizeof(char)); p = m; cdlen = 0;
3.//--递归遍历赫夫曼树，求赫夫曼编码 cd = (char *)malloc(n*sizeof(char)); p = m; cdlen = 0; void printHuffCode(i, cd){ if(HT[i].parent.lchild == i) cd[cdlen++] = 0; else if(HT[i].parent.rchild == i)cd[cdlen++] = 1; if(HT[i].lchild == 0 && HT[i].rchild == 0){ HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); cd[cdlen] ='\0'; strcpy(HC[i], cd); // 复制编码(串) }else{ if (HT[i].lchild != 0) printHuffCode(HT[i].lchild, cd); if (HT[i].rchild != 0) { cdlen--;printHuffCode(HT[i].rchild, cd); } 数据结构

75 按层次遍历二叉树 遍历顺序为，为从上层到下层，每层中从左侧到右侧依次访问每个结点。 例如图所示的二叉树表达式 (a+b*(c-d)-e/f)
其按层次的遍历序列为： -+/a*efb-cd － / ＋ f e a * b - c d 数据结构

76 按层次遍历二叉树的顺序存储实现 void LevelOreder(QBTree BT) { for(i=1;i<=BT.n;i++)
if(BT[i]!=’#’) Visit(BT[i]); } 数据结构

77 按层次遍历二叉树的链式存储实现 链式存储的访问过程描述如下： 访问根结点，并将该结点记录下来；
若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。 取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。 数据结构

78 void LevelOrder(BTree *BT){ if (!BT) exit(0);
InitQueue(Q); p=BT; //初始化 Visite(p); EnQueue(&Q,p); while (!QueueEmpty(Q)) { DeQueue(&Q,&p); //出队 if (!p->Lchild){ Visit(p->Lchild); EnQueue(&Q,p->Lchild);//处理左孩子 } if (!p->Rchild) { Visite(p->Rchild); EnQueue(&Q,p->Rchild);//处理右孩子 数据结构

79 http://219.224.30.65:8080/JudgeOnline 1161号到1174号是专门为ACM新手准备的
若对一棵二叉树从0开始进行结点编号，并按 此编号把它顺序存储到一维数组a中，即编号为 0的结点存储到a[0]中，其余类推，则a[i]元素 的左子女结点为___，右子女结点为___，双亲 结点(i>=1)为___。 1161号到1174号是专门为ACM新手准备的 数据结构