《数据结构》课件第6章

第6章树和二叉树6.1树的基本概念6.2树的存储结构和基本操作6.3二叉树的定义和基本性质6.4二叉树的存储结构和基本操作6.5二叉树的遍历6.6树和森林与二叉树之间的关系6.7哈夫曼树及其应用本章小结习题六实训6-1树的存储结构实训6-2二叉树的遍历及应用实训6-3哈夫曼编码

【教学目标】通过对本章的学习，理解树和二叉树的基本概念及递归定义，掌握树的存储结构和基本操作，掌握二叉树的基本性质，重点掌握二叉树的各种存储结构以及链式存储结构上各种基本操作的实现，重点掌握二叉树的遍历方法，熟练掌握树、森林和二叉树之间的转换方法，熟悉哈夫曼树的建立过程和哈夫曼编码。6.1树的基本概念6.1.1树的定义树是n(n≥0)个结点的有限集合T。当n=0时，称为空树；当n>0时，该集合满足如下条件：

(1)其中必有一个称为根(Root)的特定结点，它没有直接前驱，但有零个或多个直接后继。

(2)其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根Root的子树(Subtree)。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。在现实生活中有很多树形结构的例子。例如本书的目录就是树形结构。本书共分9章，每一章又分为若干节，每一节又分为若干小节，这样就构成了一个典型的树的实例。又如家族的血缘关系，A有三个孩子B1、B2、B3；B1有三个孩子C1、C2、C3；B2有两个孩子C4、C5；C1有两个孩子D1、D2，构成了一个四世同堂的大家族，A就是这棵家族大树的根。在树的定义中要特别注意非空树的两个特点：

(1)树中至少有一个结点——根。

(2)树中各子树是互不相交的集合。结合图6.1不难了解上面提到的这些特点，同时，大家还要看到树定义的递归性。图6.1树形表示法6.1.2树的逻辑表示

1.树的逻辑结构描述树的逻辑结构可用如下形式描述：

Tree = (D，R)其中，D为具有相同性质的数据元素的集合，R为D上元素之间的关系的集合，如图6.1中有子树的那棵树:D={A,B,C,D,E,F,G,H,I,J,K,L,M}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>,<E,K>,<E,L>,<H,M>}

2.树的逻辑表示树的逻辑表示方式有很多种，常见的有以下几种：

(1)树形表示法。它像日常生活中的树木一样，整个图是一棵倒立的树，从根结点出发向下扩展，根结点在最上层，叶子结点在最下面，如图6.1所示。

(2)凹入表示法。图形的一端，所有的结点对齐，根结点用最长的矩形表示，同一层的结点用相同长度的矩形表示，层次越高，矩形长度越短，如图6.2(a)所示。

(3)嵌套表示法。类似数学中所说的文氏图表示法，如图6.2(b)所示。图6.2树的逻辑表示(a)凹入表示法；(b)嵌套表示法

(4)广义表表示法。用广义表的形式表示时根结点排在最前面，用一对圆括号把它的子树结点括起来，子树结点之间用逗号隔开。图6.1用广义表表示如下：(A(B(E(K，L)，F)，C(G)，D(H(M)，I，J))6.1.3树的基本术语结点(node)——包含一个数据元素及若干指向其它结点的分支信息。结点的度(degree)——一个结点的子树个数称为此结点的度。图6.1中，结点A的度为3，B的度为2，L的度为0。叶结点(leaf)——度为0的结点，即无后继的结点，也称为终端结点。图6.1中，结点K、L、F、G、M、I、J都是叶结点。分支结点——度不为0的结点，也称为非终端结点。图6.1中，结点A、B、C、D、E、H都是分支结点。孩子结点(child)——一个结点的直接后继称为该结点的孩子结点。图6.1中，结点B、C是A的孩子。双亲结点(parents)——一个结点的直接前驱称为该结点的双亲结点。图6.1中，结点A是B、C的双亲。兄弟结点(sibling)——同一双亲结点的孩子结点之间互称兄弟结点。图6.1中，结点H、I、J互为兄弟结点。祖先结点——一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。图6.1中，结点K的祖先是A、B、E。子孙结点——一个结点的直接后继和间接后继称为该结点的子孙结点。图6.1中，结点D的子孙是H、I、J、M。树的度——树中所有结点的度的最大值。图6.1中，树的度为3。结点的层次——从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。图6.1中，结点B、C、D在第2层，K、L、M在第4层。树的高度(深度)(depth)——树中所有结点的层次的最大值。图6.1中，树的高度为4。有序树——在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。森林(forest)——m(m≥0)棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。6.1.4树的基本概念分析以图6.1中的树为例，设结点总数为n，树的度为m，其中度为0,1,2,…,m的结点个数分别表示为n0,n1,n2,…,nm，显然

N = n0 + n1+n2+…+nm

(6-1)设树的分支总数为B，从上往下看就会发现，根据结点度的定义，度为0的结点下面没有分支，度为m的结点下面有m个分支，所以，

B=0×n0+1×n1+2×n2+…+m×nm(6-2)如果从树的最底层往上看就会发现，由于分支表示结点的父子关系，因此除了根结点之外，每一个结点只有一个分支进入，即每个结点有且仅有一个双亲结点，故

n = B + 1(6-3)即结点度数之和 = 分支总数 = 结点总数-1

例6.1

已知一棵树的度为4，其中度为1、2、3、4的结点的个数分别为6、5、4、3，求该树中叶子结点的个数。解：树的度为4，即树中结点度的最大值为4。将已知条件分别代入式(6-1)、式(6-2)：n=n0+n1+n2+n3+n4=n0+6+5+4+3=n0+18B=1×6+2×5+3×4+4×3=40将n和B代入式(6-3)有n0+18=40+1，所以n0=23。答：树中叶子结点的个数为23。6.2树的存储结构和基本操作6.2.1树的存储结构常用的树的存储结构有四种：双亲表示法；孩子表示法；带双亲的孩子链表；孩子兄弟表示法(二叉链表表示法)。

1.双亲表示法双亲表示法利用树中每个结点的双亲唯一性，在存储结点信息的同时，为每个结点附设一个指向其双亲的指针parent，唯一地表示任何一棵树。存储结构的实现：用一组连续的存储空间，即一维数组存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型。每个结点含数据域和双亲域两个域，数据域中存放结点本身信息；双亲域指示本结点的双亲结点在数组中的位置。树的双亲表示法如图6.3所示。图6.3树的双亲表示法(a)树；(b)树的双亲表示法双亲表示法的C语言描述如下：/*0号单元不用或存放结点个数，假设数据项为字符型*/typedefstructnode{chardata;intparent;}PNODE;PNODEt[M];/*用结点数组表示树*/用双亲表示法来表示树结点之间的关系，很容易找到每一个结点(根结点除外)的双亲，但是谁是该结点的孩子，如何才能找到该结点的孩子，用这种表示法却较难实现，也就是说双亲表示法找双亲容易，找孩子难。

2.孩子表示法树中的每个结点都有零个或多个孩子结点，通常采用以下几种方法来管理这些孩子结点。

1)多重链表每个结点有多个指针域，分别指向其子树的根的表叫做多重链表。由于每个结点的孩子数(即结点的度)不尽相同，因此多重链表中设置孩子结点指针域个数的方法有两种：

(1)结点同构。结点的指针个数相等，且为树的度D。

(2)结点异构。结点指针个数不等，为该结点的度d。通常都采用结点同构的多重链表。图6.3(a)所示树的多重链表如图6.4所示。图6.4结点同构时树的孩子表示法

2)孩子链表每个结点的孩子结点用单链表存储，再用含n个元素的结构体数组指向每个孩子链表。孩子表示法的存储结构包括两个部分：一部分是表头数组，表头数组中的元素是结构体数据，由一个数据项(结点数据，假设是字符型)和一个指针项(指向结点的第一个孩子)构成；另一部分是孩子单链表，每个链表结点由一个整型数据(用来存放表头数组元素的下标)和一个指针项(指向下一个孩子)构成。孩子结点的存储结构如下：

typedefstructtnode{

intchild; /*该孩子结点在表头数组中的下标*/

structtnode*next;/*指向下一个孩子结点*/

}TNODE;表头结点的存储结构如下：#defineM100 /*定义表头数组最大存储容量*/typedefstructtablenode{chardata; /*数据域*/TNODE*fchild; /*指向第一个孩子结点*/}TD;TDt[M+1]; /*t[0]单元不用*/图6.3(a)所示树的孩子链表表示法如图6.5所示。图6.5树的孩子链表表示法

3.带双亲的孩子链表用孩子表示法来表示结点之间的关系可以很容易找到结点的孩子，但是找它的双亲结点就比较困难。有没有一种表示法可以把前面两种表示法的优点都继承下来呢？为了让结点既容易找到它的双亲结点又容易找到孩子结点，可用带双亲的孩子链表来表示结点之间的存储关系。这种存储结构和孩子表示法有一点相似，只是在孩子表示法的表头数组中增加了一列来作为双亲域，用来存放该结点的双亲在表头数组中的位置。图6.3(a)所示树的带双亲的孩子链表表示法如图6.6所示。图6.6树的带双亲的孩子链表存储结构

4.孩子兄弟表示法(二叉链表表示法)图6.7树的孩子兄弟表示法的存储结构孩子兄弟表示法也称为二叉树表示法或二叉链表表示法，即用二叉链表作树的存储结构。链表中的结点由左指针域、右指针域和数据域三个部分组成，左指针指向该结点的第一个孩子结点，右指针指向该结点的下一个兄弟结点。图6.3(a)所示树的孩子兄弟表示法如图6.7所示。图6.7树的孩子兄弟表示法的存储结构孩子兄弟表示法的C语言描述如下：typedefstructtnode{chardata;structtnode*lchild;structtnode*rsibling;}TNODE;用孩子兄弟表示法表示结点之间的关系，容易实现树的各种操作。例如在图6.7中查找结点B的第三个孩子结点F。设有一指针p指向结点B，则B的第三个孩子结点F可通过下列三个操作来查找：

p = p->lchild;p = p->rsibling;p = p->rsibling;如果在每个结点中增设一个双亲域，则很容易查找一个结点的双亲结点和树的根结点。孩子兄弟表示法的特点是操作容易，但破坏了树的层次结构关系。6.2.2树的基本操作树中常用的基本操作如下：

(1) InitTree(Tree) ——将Tree初始化为一棵空树。

(2) DestoryTree(Tree) ——销毁树Tree。

(3) CreateTree(Tree)——创建树Tree。

(4) ClearTree(Tree)——清空树。

(5) TreeEmpty(Tree)——若Tree为空，则返回TRUE，否则返回FALSE。

(6) Root(Tree)——返回树Tree的根。

(7) TreeDepth(Tree)——返回树的深度。

(8) Parent(Tree，x)——树Tree存在，x是Tree中的某个结点。若x为非根结点，则返回它的双亲，否则返回“空”。

(9) FirstChild(Tree，x)——树Tree存在，x是Tree中的某个结点。若x为非叶子结点，则返回它的第一个孩子结点，否则返回“空”。

(10) NextSibling(Tree，x)——树Tree存在，x是Tree中的某个结点。若x不是其双亲的最后一个孩子结点，则返回x的下一个兄弟结点，否则返回“空”。

(11) InsertChild(Tree，p，Child)——树Tree存在，p指向Tree中的某个结点，非空树Child与Tree不相交。将Child插入Tree中，作为p所指向结点的子树。

(12) DeleteChild(Tree，p，i)——树Tree存在，p指向Tree中的某个结点，1≤i≤d，d为p所指向结点的度。删除Tree中p所指向结点的第i棵子树。

(13) TraverseTree(Tree，Visit())——树Tree存在，Visit()是对结点进行访问的函数。按照某种次序对树Tree的每个结点调用Visit()函数访问一次且最多一次。若Visit()失败，则操作失败。6.3二叉树的定义和基本性质6.3.1二叉树的定义

1.定义二叉树是n(n≥0)个结点的有限集，它或为空树(n = 0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。

2.二叉树的特点

(1)每个结点至多有二棵子树(即不存在度大于2的结点)

(2)二叉树的子树有左、右之分，且其次序不能任意颠倒。

(3)二叉树可以为空。

3.二叉树的基本形态二叉树的基本形态有五种，如图6.8所示。图6.8二叉树的五种基本形态(a)空二叉树；(b)只有根结点的二叉树；(c)右子树为空；(d)左子树为空；(e)左、右子树均非空

4.几种特殊形式的二叉树

1)满二叉树

(1)定义一棵深度为k且有2k-1个结点的二叉树称为满二叉树，如图6.9(a)所示。

(2)特点一层上的结点数都是最大结点数。满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号(1，2，…，n)。例如图6.9(a)所示的满二叉树的顺序表示为(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)。

2)完全二叉树

(1)定义深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号1至n的结点一一对应时，称为完全二叉树，如图6.9(b)所示。图6.9满二叉树与完全二叉树(a)满二叉树；(b)完全二叉树

(2)特点①叶子结点只可能在层次最大的两层上出现。②对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L + 1。满二叉树和完全二叉树是二叉树的特殊情形。满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。6.3.2二叉树的基本性质在这里介绍一下二叉树的几个重要的性质，并对部分性质进行证明。

性质1

在二叉树的第i层上至多有2i-1个节点(i≥1)。

证明用数学归纳法证明。

归纳基础：当i = 1时，整个二叉树只有一个根结点，此时2i-1 = 20 = 1，结论成立。归纳假设：假设i = k时结论成立，即第k层上结点总数最多为2k-1个。现证明当i=k+1时，结论成立。因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-１=2k，故结论成立。

性质2

深度为k的二叉树至多有2k-1个结点(k≥1)。

证明由性质1，可得深度为k的二叉树最大结点数是命题得证。

性质3

对任何一棵二叉树BT，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。

证明设n1为二叉树BT中度为1的结点数，n为二叉树T中的结点总数。因为二叉树中所有结点的度均小于或等于2，所以该二叉树中结点总数为

n = n0 + n1 + n2

(6-4)设二叉树中分支数目为B，因为除根结点外，每个结点均对应一个进入它的分支，所以

n = B + 1(6-5)又因为分支由度为1和度为2的结点射出，所以

B = n1 + 2 × n2(6-6)将式(6-4)、式(6-6)分别代入式(6-5)，得到n0 + n1 + n2 = n1 + 2 × n2 + 1所以，n0 = n2 + 1，命题得证。

性质4

具有n个结点的完全二叉树的深度为

log2n

+1。

log2n

表示取log2n的整数部分作为它的值。

证明假设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为n1 = 2k-1-1k层满二叉树的结点总数为n2 = 2k-1显然有n1<n≤n2，进一步可以推出n1+1≤n<n2+1。将n1=2k-1-1和n2=2k-1代入上式，可得2k-1≤n<2k，即k-1≤log2n<k。因为k是整数，所以k-1 =

log2n

，k = 

log2n

+1，故结论成立。

性质5

如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1≤i≤n)，有：

(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是

i/2

。

(2)如果2i > n，则结点i无左孩子；如果2i≤n，则其左孩子是2i。

(3)如果2i+1>n，则结点i无右孩子；如果2i+1≤n，则其右孩子是2i+1。

例6.2

已知完全二叉树结点总数为500，求叶子结点的数目。

分析：设完全二叉树中度为1的结点的数目为n1，如果完全二叉树的高度为k，由于k-1层满二叉树的结点总数为2k-1-1，且为奇数，因此在第k层添加1个结点时，n1 = 1，添加2个结点时，n1=0，…，所以，完全二叉树中度为1的结点的数目n1只有两种情形：解：据性质4可知n=n0+n1+n2=n0+n1+n0-1=2n0+n1-1由于n为偶数，故n1=1，得n=2n0，n0=n/2=500/2=250答：叶子结点总数为250。6.4二叉树的存储结构和基本操作6.4.1顺序存储结构二叉树的结构是非线性的，每一结点最多可有两个后继。二叉树的存储结构有两种：顺序存储结构和链式存储结构。

1.顺序存储顺序存储就是用一组连续的存储单元来存储二叉树上的数据元素，如果用C语言来实现，一般情况下就是定义一个一维数组来存储二叉树上的数据元素，因此必须把二叉树的所有结点结构转换成一种线性序列结构，使得结点在线性序列中通过它们的相对位置能反映出结点之间的逻辑关系。二叉树顺序存储结构用C语言描述如下：#defineMAXSIZE100

/*二叉树的最大结点数或者说是数组的最大容量*/charSqBiTree[MAXSIZE+1];

/*0号单元不用*/

2.顺序存储的实现为了实现二叉树的顺序存储，就要将二叉树中各结点进行编号，要求该编号与等高的完全二叉树中对应位置上的结点编号相同，并以结点编号为下标，把各结点对应地存放到一维数组中去。根据二叉树的性质5，可得根结点的编号为1，结点i的左孩子的编号为2i，右孩子的编号为2i + 1。完全二叉树的顺序存储结构如图6.10所示。图6.10完全二叉树的顺序存储结构

3.顺序存储的特点二叉树顺序存储结构有以下特点：

(1)结点之间的关系可通过数组的下标计算出来。

(2)仅适用于存储满二叉树和完全二叉树，对于一般二叉树，特别是对于那些单分支结点较多的二叉树来说是很不合适的，会造成存储空间的大量浪费，如图6.11所示。不难发现，采用顺序存储结构，实际上是对非线性的数据结构线性化，用线性结构来表示二叉树结点之间的逻辑关系。图6.11一般二叉树的顺序存储结构6.4.2链式存储结构

1.二叉链表设计要求不同，问题的解决方式不同，要用到的链式存储结构也不同。一般情况下对二叉树的链式存储采用二叉链表表示。对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子域。其中，LChild域指向该结点的左孩子，data域记录该结点的信息，RChild域指向该结点的右孩子。用C语言可以这样声明二叉树的二叉链表结点的结构：typedefstructNode{

DataTypedata;

structNode*LChild;

structNode*RChild;}BiTNode,*BiTree;在二叉链表中，每个非空的指针域对应二叉树中的一个分支。由于n个结点构成的二叉树中只有n-1个分支，因此相对应的二叉链表中只有n-1个指针域被使用，而指针总数是2n个，即还有n + 1个空指针域。从图6.12二叉树的二叉链表表示中可以看出，该二叉树有7个结点，每一个结点中有左右两个指针，在该树的二叉链表表示中总共有14个指针，其中6个指针在使用，还有8个指针是空的。图6.12二叉树的二叉链表表示(a)二叉树T；(b)二叉树T的二叉链表

2.三叉链表在二叉链表中查找某一结点的孩子结点是很方便的，而要查找其双亲结点则十分困难。为了便于找到双亲结点，可以增加一个Parent域，Parent域指向该结点的双亲结点。结点结构如下：三叉链表的存储结构用C语言描述如下：typedefstructnode{

DataTypedata;

structnode*LChild,*RChild,*Parent;}JD;用三叉链表来存储的二叉树，既容易找到结点的左右孩子结点，又容易找到其双亲结点，如图6.13所示。图6.13图6.12(a)所示二叉树的三叉链表表示6.4.3基本操作与前面所讨论的树的基本操作类似，二叉树的基本操作如下：

(1) InitBTree(bt)——将bt初始化为空二叉树。

(2) CreateBTree(bt)——创建一棵非空二叉树bt。

(3) DestoryBTree(bt)——销毁二叉树bt。

(4) EmptyBTree(bt)——若bt为空，则返回TRUE，否则返回FALSE。

(5) Root(bt)——求二叉树bt的根结点。若bt为空二叉树，则函数返回“空”。

(6) Parent(bt，x)——求双亲函数。求二叉树bt中结点x的双亲结点。若结点x是二叉树的根结点或二叉树bt中无结点x，则返回“空”。

(7) LeftChild(bt，x)——求左孩子。若结点x为叶子结点或x不在bt中，则返回“空”。

(8) RightChild(bt，x)——求右孩子。若结点x为叶子结点或x不在bt中，则返回“空”。

(9) Traverse(bt)——遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。

(10) ClearBTree(bt)——清除操作。将二叉树bt置为空树。6.5二叉树的遍历6.5.1遍历概述二叉树的遍历方法主要有以下四种：先序遍历、中序遍历、后序遍历和层次遍历。根据二叉树的递归定义，二叉树由根结点、左子树、右子树三部分组成，因此只要依次遍历这三部分，就遍历了整棵二叉树。图6.14表示二叉树结点的基本结构。从图中可以看出，如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，那么对二叉树的遍历顺序就可以有六种方式：

(1)访问根，遍历左子树，遍历右子树(记做DLR)。

(2)访问根，遍历右子树，遍历左子树(记做DRL)。

(3)遍历左子树，访问根，遍历右子树(记做LDR)。图6.14二叉树结点的基本结构

(4)遍历左子树，遍历右子树，访问根(记做LRD)。

(5)遍历右子树，访问根，遍历左子树(记做RDL)。

(6)遍历右子树，遍历左子树，访问根(记做RLD)。在以上六种遍历方式中，规定按先左后右的顺序，则只保留DLR、LDR、LRD三种遍历方式。又根据对根访问的顺序的不同分别称DLR为先序(根)遍历，LDR为中序(根)遍历、LRD为后序(根)遍历。注意：先序、中序、后序遍历是递归定义的，即在其子树中亦按上述规律进行遍历。如果从二叉树的根结点开始，按照二叉树层次从小到大依次遍历二叉树的每一层，而在遍历每层时，按从左到右的顺序依次访问各结点，这种遍历方式称为层次遍历。对于如图6.15所示的二叉树，其先序、中序、后序、层次遍历的序列如下：先序遍历：A、B、D、F、G、C、E、H。中序遍历：B、F、D、G、A、C、E、H。后序遍历：F、G、D、B、H、E、C、A。层次遍历：A、B、C、D、E、F、G、H。图6.15二叉树可以看出，二叉树的根结点总是在先序遍历序列的第一位，在后序遍历序列的最后一位，所以通过先序或后序遍历序列可以准确判定二叉树的根，但却无法判定其他结点在左子树还是右子树上。而在中序遍历序列中，如果知道了根的位置，则根前面的是左子树上的结点，根后面的是右子树上的结点，可是单独通过中序遍历序列是无法判定根结点的。所以，可以通过先序+中序或是后序+中序来唯一地确定一棵二叉树。这就是所谓“先(后)序定根，中序定左右”。例6.3已知结点的先序序列和中序序列分别如下：先序序列：ABCDEFG。中序序列：CBEDAFG.。根据给定的先序序列和中序序列求出整棵二叉树。首先由先序序列知二叉树的根结点为A，则其左子树的中序序列是(CBED)，右子树的中序序列为(FG)，反过来得知其左子树的先序序列必为(BCDE)，右子树的先序序列为(FG)，依此类推，可由左子树的先序序列和中序序列构造出A的左子树，由右子树的先序序列和中序序列构造出A的右子树，如图6.16所示。图6.16先序和中序序列构造一棵二叉树的过程6.5.2遍历算法

1.先序遍历先序遍历二叉树的基本思想：访问根结点，先序遍历左子树，先序遍历右子树。算法描述如下：

voidPreOrder(BiTreeroot)

/*先序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/

{

if(root!=NULL)

{

Visit(root->data); /*访问根结点*/PreOrder(root->LChild); /*先序遍历左子树*/PreOrder(root->RChild); /*先序遍历右子树*/}}

2.中序遍历中序遍历二叉树的基本思想：中序遍历左子树，访问根结点，中序遍历右子树。算法描述如下：voidInOrder(BiTreeroot)/*中序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/{

if(root!=NULL){InOrder(root->LChild); /*中序遍历左子树*/Visit(root->data); /*访问根结点*/InOrder(root->RChild); /*中序遍历右子树*/}}

2.后序遍历后序遍历二叉树的基本思想：后序遍历左子树，后序遍历右子树，最后访问根结点。算法描述如下：voidPostOrder(BiTreeroot)/*后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/{if(root!=NULL){PostOrder(root->LChild); /*后序遍历左子树*/PostOrder(root->RChild); /*后序遍历右子树*

Visit(root->data); /*访问根结点*/}}6.5.3遍历算法的应用

1.输出二叉树中的结点遍历算法将遍历二叉树中的每一个结点，若对输出二叉树中的结点并无次序要求，则可用三种遍历中的任何一种算法完成。下面写出用先序遍历输出结点的实现算法。voidPreOrder(BiTreeroot)/*先序遍历输出二叉树结点,root为指向二叉树根结点的指针*/{if(root!=NULL){printf(root->data); /*输出根结点*/PreOrder(root->LChild); /*先序遍历左子树*/PreOrder(root->RChild); /*先序遍历右子树*/}}

2.输出二叉树中的叶子结点输出二叉树中的叶子结点是一个有条件的输出问题，即在遍历过程中走到每一个结点时需进行测试，看是否有满足叶子结点的条件。voidPreOrder(BiTreeroot)/*先序遍历输出二叉树中的叶子结点,root为指向二叉树根结点的指针*/{

if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL) printf(root->data);

/*输出叶子结点*/PreOrder(root->LChild);

/*先序遍历左子树*/PreOrder(root->RChild);

/*先序遍历右子树*/}}

3.统计叶子结点数目

1)非递归算法只要把上面算法中对叶子结点的输出改为对全局变量LeafCount累加即可实现计数。

/*LeafCount是保存叶子结点数目的全局变量,调用之前初始化值为0*/

…

LeafCount=0; /*全局变量，在前面定义*/

voidleaf(BiTreeroot)

{if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL)LeafCount++;leaf(root->LChild);leaf(root->RChild);}}

2)递归算法采用递归算法时，如果是空树，则返回0；如果只有一个结点，则返回1；其它情况返回左右子树的叶子结点数之和。intleaf(BiTreeroot){intLeafCount;

/*局部变量，存放返回值*/if(root==NULL)

LeafCount=0;elseif((root->LChild==NULL)&&(root->RChild==NULL))LeafCount=1;elseLeafCount=leaf(root->LChild)+leaf(root->RChild);/*叶子数为左右子树的叶子数目之和*/returnLeafCount;}6.6树和森林与二叉树之间的关系6.6.1树转换成二叉树如果树的存储结构采用孩子兄弟表示法，即用二叉链表作树的存储结构，则树就可以被视为转换成了一棵二叉树。结点的左指针指向其第一个孩子，右指针指向其下一个兄弟。将树转换成二叉树的步骤为：

(1)加线就是在兄弟之间加一连线。

(2)抹线就是对树中的每个结点，只保留其与第一个孩子结点之间的连线，抹去其与其它孩子结点之间的连线。

(3)旋转是以树的根结点为轴心，将整树顺时针旋转45°。

例6.4

将图6.17(a)所示的树转换为二叉树。

解：操作过程如图6.17(b)、(c)、(d)所示。图6.17树转换成二叉树过程(a)树；(b)加线；(c)抹线；(d)旋转6.6.2森林转换成二叉树森林是若干棵树的集合。树可以转换为二叉树，森林同样也可以转换为二叉树。因此，森林也可以方便地用孩子兄弟链表表示。其基本思想就是将森林中所有树的根结点视为兄弟。所以虽然树和森林都可以转换为二叉树，但二者却有所不同：树转换成的二叉树,其根结点必然无右孩子，而森林转换后的二叉树，其根结点可以有右孩子。森林转换为二叉树的方法如下：

(1)将森林中的每棵树转换成相应的二叉树。

(2)第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。例6.5

将图6.18(a)所示的树转换为二叉树。图6.18森林转换成二叉树(a)森林；(b)森林中每棵树对应的二叉树；(c)森林对应的二叉树解：转换成二叉树的过程见图6.18(b)、(c)。例6.6

如果森林共有n个结点，其中第一棵树有n1个结点，问由该森林转换成的二叉树的根结点的左右子树上各有多少个结点。

解：在森林对应的二叉树中，第一棵树转换成了根和左子树，而其它树转换成的二叉树都在根结点的右子树上。所以，左子树上的结点数为n1-1，右子树上的结点数为n-n1。6.6.3二叉树还原成森林树和森林都可以转换为二叉树，如果是树转换成的二叉树,其根结点必然无右孩子，而如果是森林转换成的二叉树，其根结点有右孩子。将一棵二叉树还原为树或森林，具体方法如下：

(1)连线。若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。

(2)抹线。删掉原二叉树中所有双亲结点与右孩子结点的连线。

(3)整理。整理由(1)、(2)两步所得到的树或森林，使之结构层次分明。二叉树还原成森林的过程如图6.19所示。图6.19二叉树到森林的转换示例(a)连线；(b)抹线；(c)整理6.6.4树与森林的遍历1.树的遍历树的遍历方法主要有以下两种：1)先根遍历若树非空，则先根遍历方法的步骤是：(1)访问根结点。(2)从左到右，依次先根遍历根结点的每一棵子树。例如，图6.17(a)中树的先根遍历序列为ABECFHGD。

2)后根遍历若树非空，则后根遍历方法的步骤是：

(1)从左到右，依次后根遍历根结点的每一棵子树。

(2)访问根结点。例如，图6.17(a)中树的后根遍历序列为EBHFGCDA。可以证明，树的先根和后根遍历序列分别对应着由树转换成的二叉树的先序和中序遍历序列。

2.森林的遍历森林的遍历方法主要有以下三种：

1)先序遍历若森林非空，则先序遍历方法为：

(1)访问森林中第一棵树的根结点。

(2)先序遍历第一棵树的根结点的子树森林。

(3)先序遍历除去第一棵树之后剩余的树构成的森林。例如，图6.17(a)中森林的先序遍历序列为ABCDEFGHIJ。

2)中序遍历若森林非空，则中序遍历方法为：

(1)中序遍历森林中第一棵树的根结点的子树森林。

(2)访问第一棵树的根结点。

(3)中序遍历除去第一棵树之后剩余的树构成的森林。例如，图6.17(a)中森林的中序遍历序列为BCDAFEHJIG。

3)后序遍历若森林非空，则后序遍历方法为：

(1)后序遍历森林中第一棵树的根结点的子树森林。

(2)后序遍历除去第一棵树之后剩余的树构成的森林。

(3)访问第一棵树的根结点。例如，图6.17(a)中森林的后序遍历序列为BCDFHJIGEA。6.7哈夫曼树及其应用6.7.1基本概念

1.路径和路径长度路径：从树中一个结点到另一个结点之间的分支序列构成这两个结点间的路径。路径长度：路径上的分支数。树的路径长度：从树根到每一个结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。

2.结点的权和带权路径长度结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。例如用权来表示结点的重要性或使用频率等。结点的带权路径长度：结点到树根之间的路径长度与该结点权值的乘积。

3.树的带权路径长度树的带权路径长度(WeightedPathLengthofTree，WPL)：树中所有叶子结点的带权路径长度之和，即其中，n为叶子结点的个数，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。

例6.7

有4个结点A、B、C、D，权值分别为7、5、2、4，构造出不同形态的有4个叶子结点的二叉树(如图6.20所示)，分别求这些二叉树的带权路径长度。

解：三棵二叉树的带权路径长度分别为WPL(a)=7×2+5×2+2×2+4×2=36WPL(b)=4×2+7×3+5×3+2×1=46WPL(c)=7×1+5×2+2×3+4×3=35图6.20具有不同带权路径长度的二叉树(a)带权路径长度为36；(b)带权路径长度为46；(c)带权路径长度为356.7.2哈夫曼树(最优二叉树)从图6.20中四个相同的叶子结点构成的三棵不同的二叉树的带权路径长度可以知道，图6.20(c)的值最小，它所对应的二叉树具有最短带权路径长度，称为最优二叉树，即哈夫曼树。哈夫曼(Huffman)树定义：设有n个权值{w1,w2,…,wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则WPL最小的二叉树叫哈夫曼树。

1.构造哈夫曼树步骤

(1)用给定的n个权值{w1,w2,…,wn}对应的n个结点构成n棵二叉树的森林F={T1,T2,…,Tn}，其中每一棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点，其左、右子树为空。

(2)在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。

(3)在森林F中删除这两棵树，同时将新得到的二叉树加入森林中。

(4)重复(2)、(3)两步，直到森林F中只含一棵树为止，这棵树即哈夫曼树。

例6.8

已知A、B、C、D四个结点，它们的权值分别为3、6、8、12，求由这四个结点构造的哈夫曼树及其WPL。

解：由这四个结点构造哈夫曼树的过程如图6.21所示。WPL=12×1+8×2+3×3+6×3=55在图6.21中有四个叶子结点，构造出来的哈夫曼树由7个结点构成，即一棵有n个叶子结点的哈夫曼树由2n-1个结点构成。图6.21哈夫曼树的构造示意图6.7.3哈夫曼编码假设一个指令系统包括I1、I2、…、I7等7条指令，其对应的使用频率如表6-1所示。如何为其构造适当的编码系统呢。表6-1指令使用频率

分析：首先考虑使用定长编码系统，最短需3位编码，如表6-2所示。表6-2定长编码按照以上编码方式，对于编码序列001011010100，可准确解释为指令序列I2I4I3I5，且不会产生歧义。定长编码简单准确，但没有考虑指令的使用频率，将常用指令与罕用指令的长度设计成一样，就如同将五笔字型输入法中的一级、二级简码全部改成四位编码，使用起来显然效率低下且极不方便。如何根据使用频率设计变长编码系统呢？不妨先尝试设计成如表6-3所示最简单的方式。表6-3变长编码对于编码序列001011010100，却有I1I1I6I3I3I5、I1I1I3I7I3I5等多种解释。造成歧义的原因在于某些编码是另一些编码的前缀，如I2是I3～I7的前缀，I4是I7的前缀。一个合格的变长编码系统中，任一编码都不能是其他编码的前缀。符合这一条件的编码系统称为前缀编码系统。哈夫曼编码是一种很重要的数据通信二进制编码，是一种前缀编码系统。现在具体来分析一下哈夫曼编码数据通信的应用。首先要了解哈夫曼编码思想：就是根据通信数据中字符出现的频率进行编码，使电文编码总长最短。哈夫曼编码先根据字符出现频率来构造哈夫曼树，然后将树中结点左分支标为“0”，右分支标为“1”；每个字符的哈夫曼编码即为从根到每个叶子结点经过的路径而得到的0、1序列。以I1～I7的频率为权，构造的哈夫曼树如图6.22所示。图6.22哈夫曼树从图6.22中可以看出，如果编码A是编码B的前缀，则A在哈夫曼树中一定是B的祖先结点。由于哈夫曼编码对应均为叶子结点，因此任一指令的编码都不可能是其它编码的前缀，即哈夫曼编码系统是前缀编码系统。对应的哈夫曼编码如表6-4所示。表6-4哈夫曼编码可以算出该哈夫曼编码的平均码长为：其中Pi为指令使用频率，Ii为指令编码长度。可见，哈夫曼编码中虽然大部分编码的长度大于定长编码的长度3，却使得程序的总位数变小了。6.7.4哈夫曼算法由于哈夫曼树中没有度为1的结点，因此一棵有n个叶子的哈夫曼树共有2n-1个结点，那么，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个结点。每个结点包含权值、双亲结点的信息和孩子结点的信息，并采用顺序存储结构。二叉树中结点类型定义如下：typedefstruct{intweight;intparent,lchild,rchild;}HTNODE,*HUFFMANTREE; /*动态分配数组存储哈夫曼树*/typedefchar**HUFFMANCODE;/*动态分配数组存储哈夫曼编码表*/例6.8中的哈夫曼树及哈夫曼编码如图6.23所示。图6.23(a)为初始状态。森林中有4棵单结点的树。双亲为0表示是树的根结点。

1.构造哈夫曼树的算法构造一棵有n个叶子的哈夫曼树的算法如下：

(1)从已有根结点(双亲为0)中选择权值最小和次小的结点M1、M2。

(2)在已有全部结点的最后添加新结点N，其权值为M1、M2权值之和，左右孩子分别是M1、M2，双亲为0。

(3)修改M1、M2的双亲域为N。

(4)重复(1)，共进行n-1次。图6.23(b)为最终状态。此时森林中只有一棵树(1个根结点)，即为构造好的哈夫曼树。

2.形成哈夫曼编码的算法求某个叶子结点M对应的哈夫曼编码，要从叶子结点到根逆向求取，结果先存放在辅助工作空间S内，最后再复制到哈夫曼编码表中。

(1)在S中从右向左逐位存放编码，首先在最后一位存放编码结束符。

(2)从叶子M开始，逆向求取编码。设C = M。

(3)设P是C的双亲结点。

(4)从右向左向S中编码：若C是P的左孩子，加入'0'，是右孩子，加入'1'。

(5) C = P；

(6)重复(3)～(5)，直到P为空。所求得的哈夫曼编码如图6.23(c)所示。图6.23哈夫曼编码(a)初始状态；(b)最终状态；(c)哈夫曼编码本章小结本章首先介绍了树和二叉树的基本概念、存储结构及性质。树是一种一对多的非线性结构，可以采用双亲表示法、孩子表示法、带双亲的孩子链表、孩子兄弟表示法进行存储。二叉树是度数不大于2且左右子树不能互换的特殊的树，采用顺序存储和链式存储两种存储方式。遍历是二叉树最基本也最重要的操作，常用的二叉树遍历算法有先序、中序、后序和层次遍历。二叉树和树之间可以进行转换。哈夫曼树是带权路径长度最小的树。二叉树的性质及其应用、用递归方式构建和遍历二叉树的算法、哈夫曼树的构建和应用是本章的重点。习题六

一、判断题

1.二叉树是树的特殊情形。()

2.二叉树的先序遍历序列中，任意结点均处在其孩子结点之前。()

3.二叉链表是一种逻辑结构。()

4.由二叉树的先序序列和后序序列可以唯一确定一棵二叉树。()

5. n个结点的完全二叉树不唯一。()

6.树的后序遍历序列与其对应的二叉树的后序遍历序列相同。()

7.完全二叉树的某结点若无左孩子，则它必是叶子结点。()

二、选择题

1.将一棵树t转换为孩子兄弟链表表示的二叉树h，则t的后序遍历是h的()

A.先序遍历 B.中序遍历

C.后序遍历 D.层次遍历

2.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用()次序的遍历实现编号。

A.先序 B.中序

C.后序 D.从根开始的层次遍历

3.已知一棵完全二叉树中共有768个结点，则该树中共有(

)个叶子结点。

A. 383 B. 384

C. 385 D. 386

4.先序遍历和中序遍历相同的二叉树为()。

A只有根结点的二叉树

B.根结点无左孩子的二叉树

C一般二叉树

D.只有根结点的二叉树和所有结点只有右子树的二叉树

三、简答题

1.一棵树的边集为{(a,b)，(b,e)，(a,c)，(c,g)，(a,d)，(d,i)，(c,f)，(c,h)，(d,j)，(i,k)},请画出此棵树的形态，并回答下列问题：

(1)树的根是哪个结点？哪些是叶子结点？哪些是分支结点？

(2)各结点的度分别是多少？树的度是多少？

(3)各结点的层次分别是多少？树的深度是多少？以d为根的子树深度是多少？

(4)结点i的双亲是哪个结点？祖先是哪个结点？孩子是哪些结点？兄弟是哪些结点？

2.树和二叉树有哪些区别？

3.已知二叉树的后序和中序序列如下，构造出该二叉树，写出它的前序遍历序列。后序序列：ABCDEFG中序序列：ACBGDFE

4.假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成，它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}

(1)为这7个字母设计哈夫曼编码。

(2)对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码与等长编码相比，能使电文总长压缩多少？

四、算法题

1.设计算法求二叉树的高度。

2.按要求写出算法，功能为判断一棵二叉树(采用二叉链表存储结构)是否为完全二叉树。实训6-1树的存储结构【实训目的】

1.加深对树的基本概念、树的存储结构的理解。

2.掌握树的各种存储结构的实现。【实训内容】如图6.24所示的树，分别使用双亲表示法和孩子链表进行存储。【实训要求】

1.设计一个程序实现上述过程。

2.比较每种存储结构的利弊。【算法分析】

1.双亲表示法采用数组进行存储。

2.孩子链表采用表头结点数组存储结点，采用单链表表示结点之间的父子关系，链表头指针存放在父结点中。图6.24树【算法分析】

1.双亲表示法采用数组进行存储。

2.孩子链表采用表头结点数组存储结点，采用单链表表示结点之间的父子关系，链表头指针存放在父结点中。【程序清单】#include<stdio.h>#defineM20typedefstruct{chardata;intparent;typedefstruct{chardata;intparent;}NODE;

/*定义双亲表示法结点结构*/NODEpt[M+1];

/*用结点数组表示树,pt[0]单元不用*/typedefstructtnode{intchild;

/*该孩子结点在表头数组中的下标*/structtnode*next;/*指向下一个孩子结点*/}TNODE;

/*定义孩子表示法中孩子结点结构*/typedefstructtablenode{chardata; /*数据域*/TNODE*fchild; /*指向第一个孩子结点*/}TD;

/*定义孩子表示法中表头结点结构*/TDct[M+1];

/*用表头结点数组表示树，ct[0]单元不用*/voidparent_tree(chartreeData[M],intm){inti,j;charc;pt[0].data='';pt[0].parent=-1;for(i=1;i<=m;i++){pt[i].data=treeData[i];printf(“输入%c的父结点,根的父结点请输入空格\n",pt[i].data);

c=getchar();getchar();for(j=0;j<i;j++)if(pt[j].data==c)pt[i].parent=j;}printf("树的双亲表示法：\n");printf("下标dataparent\n");for(i=0;i<=m;i++)printf("%d\t%c\t%d\n",i,pt[i].data,pt[i].parent);}voidchild_tree(chartreeData[M],intm){inti,j;charc;TNODE*lc,*p;intflag;ct[0].data='';ct[0].fchild=NULL;for(i=1;i<=m;i++){ /*表头结点初始化*/ct[i].fchild=NULL;ct[i].data=treeData[i];}for(i=1;i<=m;i++){ /*建立孩子链表*/flag=1;while(flag){printf(“依次输入%c的子结点,没有子结点请输入空格\n",ct[i].data);c=getchar();getchar();if(c!=''){lc=(TNODE*)malloc(sizeof(TNODE));

/*建立子结点*/lc->next=NULL;

for(j=1;j<=m;j++) /*查找子结点编号*/if(ct[j].data==c){lc->child=j;break;}if(ct[i].fchild==NULL)

/*子结点加入孩子链表*/ct[i].fchild=lc;else{

p=ct[i].fchild;while(p->next!=NULL)p=p->next;p->next=lc;}}elseflag=0;}}printf("树的孩子表示法：\n");printf("下标datafchild\n");for(i=0;i<=m;i++){p=ct[i].fchild;printf("%d\t%c\t",i,ct[i].data);while(p!=NULL){printf("--->[%d]",p->child);p=p->next;}printf("\n");}}main(){chartreeData[M]={'','A','B','C','D','E','F','G','H','I'};intm=9;parent_tree(treeData,m);child_tree(treeData,m);}实训6-2二叉树的遍历及应用【实训目的】

1.加深对二叉树的基本概念的理解。

2.掌握二叉树遍历操作及其应用。【实训内容】创建一棵二叉树，并进行先序遍历、中序遍历、后序遍历、层次遍历，打印二叉树的叶子结点，并统计叶子结点个数和总结点个数。【实训要求】

1.设计一个程序实现上述过程。

2.采用二叉链表存储结构。【算法分析】

1.可采用输入二叉树的先序遍历序列的方式来建立二叉树。

2.采用递归方式进行二叉树的遍历。

3.判断叶子结点的条件是其左右孩子均为空。

4.层次遍历中，如果A在B之前被访问，则A的孩子必在B的孩子之前被访问。利用这一特性，借助一个先入先出的循环队列，先将根结点入队，只要队伍不为空，则反复执行如下操作：

(1)将队首元素输出并出队。

(2)将出队元素的左右孩子入队。【程序清单】#include<stdlib.h>#include<stdio.h>#definequeuesize100typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}btnode; /*定义二叉链表结点结构*/typedefbtnode*btree; /*定义二叉链表指针类型*/typedefstruct{intfront,rear;btreedata[queuesize]; /*循环队列元素类型为二叉链表结点指针*/intcount;}cirqueue; /*循环队列结构定义*/createbtree(btree*t){ /*输入二叉树的先序遍历序列，创建二叉链表*/charch;if((ch=getchar())=='')

/*如果读入空格字符，则创建空树*/*t=NULL;else{

*t=(btnode*)malloc(sizeof(btnode));

/*申请根结点*t空间*/(*t)->data=ch; /*将结点数据ch放入根结点的数据域*/createbtree(&(*t)->lchild);

/*建立左子树*/createbtree(&(*t)->rchild);

/*建立右