1、本章中主要介绍下列内容：树的逻辑定义和存储结构 二叉树的逻辑定义、存储结构 二叉树的基本操作算法 树和二叉树的转换 哈夫曼树及其应用,第六章 树和二叉树,本章学习要求掌握：树和二叉树的性质，有关术语及基本概念。掌握：二叉树的两种存储方法，重点是链式存储。掌握：各种次序的遍历算法，能灵活运用遍历算法实现二叉树的各种运算。掌握：几种建立二叉树的方法。了解：二叉树的线索化及其实质，了解在各种线索树中查找给定结点的前趋和后继的方法。了解：树、森林与二叉树之间的转换方法。了解：树的各种存储结构及其特点；树和森林的二种次序的遍历。掌握：哈夫曼树的基本概念，最优二叉树和哈夫曼编码方法。,6.1 树基本概念6
2、.2 二叉树的基本操作与存储实现6.3 二叉树的遍历6.4 线索二叉树6.5 二叉树的应用6.6 树的定义与相关术语6.7 树的基本操作与存储6.8 树、森林与二叉树的转换6.9 树和森林的遍历,6.1 树的基本概念,1.树的定义 树是一种常非线性结构树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。,递归定义的,树的几种形态,2.树的特点,（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点（2）树中所有结点可以有零个或多个后继结点,树结构
3、和非树结构的示意 图,3.树的表示方法：,(b)凹入表,（a）树形表示,A,B,C,D,E,F,I,J,G,H,(A(B(D)(E(I)(J)(C(G)(H)(d)嵌套括号表示法,C,D,E,I,J,F,G,H,A,B,(c)文氏图,4.基本术语结点(node)表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(leaf)度为0的结点,也叫终端结点分支结点度0的结点，也叫非终端结点结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层树的度一棵树中最大的结点度数树的深度(depth)树中结点的最大层次有序树、无序树 如果树中每棵子树从左向右
4、的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。森林 是m（m0）棵互不相交的树的集合。,在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子(child)结点子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点兄弟(sibling)同一双亲的孩子祖先、子孙如果有一条路径从结点M到结点N，那么M就称为N的祖先，N成为M的子孙堂兄弟 双亲在同一层的结点互为堂兄弟。,叶子：K，L，F，G，M，I，J,结点B，C，D为兄弟结点K，L为兄弟,结点A的度：结点B的度：结点M的度：,结点A的孩子：结点B的孩子：,结点I的双亲：结点L的双亲：,树的度：,结点A的层次：结点
5、M的层次：,树的深度：,结点F，G为堂兄弟结点A是结点F，G的祖先,其它术语:有序树和无序树、森林,3,2,0,D,E,4,1,4,3,B，C，D,E，F,术语,结点A的度：2结点B的度：2结点M的度：0,叶子：K，L，F，M，J,结点A的孩子：B，D结点B的孩子：E，F,结点J的双亲：D结点L的双亲：E,结点B，D为兄弟结点K，L为兄弟,树的度：2,结点A的层次：1结点M的层次：4,树的深度：4,结点F，H为堂兄弟结点A是结点F，H的祖先,5.树的基本运算常用操作：（1）构造一个树 CreateTree(T)（2）清空以T为根的树 ClearTree(T)（3）判断树是否为空 TreeEmp
6、ty(T)（4）获取给定结点的第i个孩子 Child(T,node,i)（6）获取给定结点的双亲 Parent(T,node)（6）遍历树Traverse(T)对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依后序遍历方法依次访问每棵子树，最后访问根结点。,6.2 二叉树,6.2.1 二叉树的定义1.定义 二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个
7、作为右子集，每个子集又是一个二叉树。二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。,递归定义的,二叉树结构的图形表示示例,G H,D E F,B C,A,2.二叉树的5种形态：,3.二叉树的基本运算（1）构造一棵二叉树 CreateBTree(BT)（2）清空以BT为根的二叉树 ClearBTree(BT)（3）判断二叉树是否为空 BTreeEmpty(BT)（4）获取给定结点的左孩子和右孩子 LeftChild(BT,node)，RightChild(BT,node)（5）给定结点的左孩子和右孩子 LeftChild(BT,node)，Ri
8、ghtChild(BT,node)（5）获取给定结点的双亲 Parent(BT,node)（6）遍历二叉树Traverse(BT),6.2.2 二叉树性质,性质1：,第i层上最大结点数是第i-1层的2倍，即 故命题得证,证明：用归纳法证明之,假设对所有j(1ji)命题成立，即第j层上至多有 个结点,那么，第i-1层至多有 个结点,又二叉树每个结点的度至多为2,性质2：深度为k的二叉树至多有 个结点(k1),证明：由性质1，可得深度为k 的二叉树最大结点数是,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1,证明：n1为二叉树T中度为1的结点数 因为：二
9、叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个 分支进入 设B为分支总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,几种特殊形式的二叉树,满二叉树定义：,特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+
10、1,证明：根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有,2 k-1-1n2k-1,2 k-1 n 2k,K-1 log2n k,性质4：,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2(2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,2i+2,2i 2i+1 2i+2 2i+3 i+1 2i 2i+1,i,i i+1,6.2.3 二叉树的存储结构 二叉树
11、也可以采用两种存储方式：顺序存储结构和链式存储结构。1.顺序存储结构 其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。,完全二叉树的存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中,1.顺序存储结构:用一组连续的存储单元按照完全二叉树的 每个结点编号的顺序存放结点内容。,6.2.3 二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。,一般二叉树的顺序存储：将一般二叉树添加虚结点转为完全二叉树，然后进行存储,特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树,在C语言中
12、，这种存储形式的类型定义如下所示：#define MaxTreeNodeNum 100typedef struct datatype dataMaxTreeNodeNum;/*根存储在下标为1的数组单元中*/int n;/*当前完全二叉树的结点个数*/QBTree;,（1）构造一棵完全二叉树void CreateBTree(QBTree*BT,DataType data,int n)if(n=MaxTreeNodeNum)n=MaxTreeNodeNum-1;for(i=1;idatai=datai;BT-n=n;,（2）获取给定结点的左孩子 int LeftCHild(QBTree BT,i
13、nt node)if(2*nodeBT.n)return 0;else return 2*node;RightChild(BT,node)与这个操作类似，读者可试着自行完成。,（3）获取给定结点的双亲 int Parent(QBTree BT,int node)if(1node,2.链式存储结构 在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：其中，lchild和rchild是分别指向该结点左孩子和右孩子的
14、指针，data是数据元素的内容。,data,2.链式存储结构二叉链表,typedef struct BiTNode datatype data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,在n个结点的二叉链表中，有n+1个空指针域,头指针bt,带头结点的二叉链表,三叉链表:二叉链表寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。,头指针bt,6.2.4 二叉树的基本操作及实现,建立一棵带头结点的空二叉树 Initiate(bt)创建二叉树 Create(x,lbt,rb
15、t)插入左孩子 InsertL(bt,x,parent)插入右孩子 InsertR(bt,x,parent)删除只有一个结点的左子树 DeleteL(bt,parent)删除右子树 DeleteR(bt,parent)查找 Search(bt,x)遍历 Traverse(bt),typedef struct BiTNode datatype data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,6.3 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍
16、历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。,6.3.1按根、左子树和右子树的遍历,按根、左子树和右子树三部分进行遍历二叉树的顺序存在下面6种可能：,其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。,二叉树的遍历方法先序遍历：
17、若二叉树为空，则结束遍历操作；否则访问根结点；然后分别先序遍历左子树、右子树中序遍历：若二叉树为空，则结束遍历操作；否则先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：若二叉树为空，则结束遍历操作；先后序遍历左、右子树，然后访问根结点,D L R,先序遍历序列：A B D C,先序遍历:先访问根结点,然后分别先序遍历左子树、右子树,L D R,中序遍历序列：B D A C,中序遍历:先中序遍历左子树，然后访问根结点，最后中序遍历右子树,L R D,后序遍历序列：D B C A,后序遍历:先后序遍历左、右子树，然后访问根结点,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,
18、-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,下面我们再给出两种遍历二叉树的方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。,D G B A E C H F,G H,D E F,B C,A,任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。,G H,D E F,B C,A,遍历算法：由此可以
19、看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。递归算法,void PreOrder(BiTree bt)if(bt=NULL)return；printf(%dt,bt-data);PreOrder(bt-lchild);PreOrder(bt-rchild);,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,6.3.2二叉树遍历的非递归算法,（1）先序遍历的非递归实现,可利用堆栈将递归算法改写成非递归的形式Bi
20、Tree stackMAXNODE;,非递归先序遍历二叉树的主要操作：p=bt;while(1)while(p不空)visit(p-data);/进栈之前访问p结点；push(p,stack);p=p-lchild;if(栈空)return;p=pop(stack);p=p-rchild;,访问：A,访问：AB,访问：ABC,访问：ABCD,while(p不空)visit(p-data);push(p,stack);p=p-lchild;,p=pop(stack);p=p-rchild;,访问：ABCDE,访问：ABCDEG,访问：ABCDEGF,栈空结束,p=bt;while(1)while
21、(p不空)push(p,stack);p=p-lchild;if(栈空)return;p=pop(stack);visit(p-data);/出栈时访问p结点；p=p-rchild;,（2）中序遍历的非递归实现,（3）后序遍历的非递归实现,Typedef struct BiTree link;int flag=0;/进栈的次数 stacktype;stacktype stackMAXNODE;/顺序栈stacktype XP；,结点要入两次栈，出两次栈，在第二次出栈时访问。,p=bt;while(1)while(p不空)XP.link=p；XP.flag=1；push(XP,stack);/第
22、一次进栈 p=p-lchild;if(栈空)return;XP=pop(stack);p=XP.link;sign=XP.flag;if(sign=2)/第二次出栈 visit(p-data);p=NULL;else/第一次出栈 XP.link=p；XP.flag=2；push(XP,stack);/第二次进栈 p=p-rchild;,while(p不空)XP.link=p；XP.flag=1；push(XP,stack);/第一次进栈 p=p-lchild;,XP=pop(stack);p=XP.link;sign=XP.flag;if(sign=2)/第二次出栈 visit(p-data)
23、;p=NULL;else/第一次出栈 XP.link=p；XP.flag=2；push(XP,stack);/第二次进栈 p=p-rchild;,C第一次出栈,C第二次进栈,C第二次出栈访问C,B第一次出栈第二次进栈,访问C G,访问C G E,访问C G E F D B,访问C G E F D B A,6.3.3 按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。,按层次遍历该二叉树的序列为：ABCDEFGH,二叉树用顺序存储结构表示时，按层遍历的算法实现,(a)完全二叉树,(b)非完全二叉树,图
24、5-20,void LevelOreder(QBTree BT)for(i=1;i=BT.n;i+)if(BT.datai!=#)Visite(BT.datai);,算法实现,二叉树用链式存储结构表示时，按层遍历的算法实现 访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。,在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下
25、列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；,void LevelOrder(BTree*BT)if(!BT)exit;InitQueue(Q);p=BT;/初始化 Visite(p);EnQueue(/处理右孩子,6.3.4 二叉树遍历算法的应用,二叉树是递归定义，可以写出它的递归遍历算法，同时借助遍历算法可以实现一些基本的应用，如：节点计数、创建二叉树、计算二叉树的高度等等,1.先序遍历查找数据元素,BiTree Search(BiTree bt,
26、datatype x)if（空树）return NULL；if(bt-data=x)return bt;P为查找左子树的结果；if（找到）return p；else P为查找右子树的结果；return p；,2.统计二叉树中叶子结点个数算法,int countleaf(BiTree bt)if（空树）return 0；if(bt-lchild=NULL return(countleaf(bt-lchild)+countleaf(bt-right)；,这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍
27、历实现的。,void Leaf(BTree BT,int*count)if(BT)Leaf(BT-child,/计算右子树的叶子结点个数,3.输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，#。在算法中，需要对每个输入的字符进行判断，如果对应的字符是#，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。,按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABC00DE0G00F00
28、0,#typedef char datatype;void createBinTree(BiTree*t)输入一个字符ch;if(ch=#)*t=NULL;return;*t=(BiTNode*)malloc(sizeof(BiTNode);(*t)-data=ch;createBinTree(,4.由中序和先序遍历序列建立二叉树的二叉链表,已知先序序列为：ABCDEGF 中序序列为：CBEGDFA,设先序序列的序号范围为ij（初始情况为1n），中序序列的序号范围为kh（初始情况为1n）；,算法过程：创建根结点；找到先序序列的i对应的中序序列中的位置m；划定左、右子树的范围；创建左子树；创建右
29、子树；,5.交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。void change_left_right(BTree BT)if(BT)change_left_right(BT-lchild);change_left_right(BT-rchild);BT-lchildBT-rchild;,6.求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子
30、树较大的高度值加1。int hight(BTree BT)/h1和h2分别是以BT为根的左右子树的高度 if(BT=NULL)return 0;else h1=hight(BT-lchild);h2=hight(BT-right);return maxh1,h2+1;,问题的提出：二叉树中有很多闲置的指针，能否利用它们为访问二叉树提供便利，如下图所示：,如：求解某结点在某种遍历次序下的前驱或后继结点,6.4线索二叉树,6.4.1 线索的概念,求前驱和后继的方法：,遍历通过指定次序的遍历发现结点的前驱或后继，费时间，低效增设前驱和后继指针在每个结点中增设两个指针，分别指示该结点在指定次序下的前驱
31、或后继。增加空间开销利用二叉链表中的空指针域（n个结点的二叉树有n+1个空指针域），将二叉链表中的空的指针域改为指向其前驱和后继：空的左孩子指针指向其前驱，空的右孩子指针指向其后继称这种新的指针为（前趋或后继）线索，所得到的二叉树被称为线索二叉树，将二叉树转变成线索二叉树的过程被称为线索化。线索二叉树根据所选择的次序可分为先序、中序和后序线索二叉树。,比较好的方法,线索化,为什么？,？,（a）未加区分标志的先序线索二叉树的二叉链表示例,然而，仅仅按照这种方式简单地修改指针的值还不行，因为这将导致难以区分二叉链表中各结点的孩子指针和线索。例如，图6.15中结点C的lchild指针域所指向的结点是
32、其左孩子还是其前趋？为此，在每个结点中需再引入两个区分标志ltag和rtag，并且约定如下：ltag=0：lchild指示该结点的左孩子。ltag=1：lchild指针该结点的前趋。rtag=0：rchild指示该结点的右孩子。rtag=1：rchild指针该结点的后继。,线索二叉链表结构描述如下：typedef char datatype；/*不妨设数据类型为字符型*/typedef struct Threadnode int ltag,rtag;datatype data;struct Threadnode*lchild,*rchild;Threadnode,*Thread_Tree;,图
33、6.15 b 线索二叉树的二叉链表形式示例,0,0,0,0,1,1,1,1,1,1,先序线索二叉树,0,0,0,0,1,1,1,1,1,1,中序线索二叉树,0,0,0,0,1,1,1,1,1,1,后序线索二叉树,头结点：ltag=0,lchild指向根结点rtag=1,rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点,带头结点的中序线索二叉树,6.4.2 线索的算法实现,对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚已访问过的结点，即若指针t指向当前结点，则pre指向它的前驱，以便增设线索。,1.建立一棵中序线索化二叉树,BiThree pre;int Inorder(Bi
