数据结构电子教案ch6.docx

1、数据结构电子教案ch6第六章 .二叉树数据结构教程 在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述，而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。 所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构和图型就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系，如前面提到的族谱、

2、城市交通等。在本书的第六、七、八章将重点讨论这两类非线性结构的有关概念、存储结构、在各种存储结构上所实施的一些运算以及有关的应用实例。 本章对树型结构中最简单、应用十分广泛的二叉树结构进行讨论。6.1 定义与性质 6.1.1 二叉树的基本概念 1二叉树 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子

3、树。因此二叉树具有五种基本形态，如图6.1所示。左子树左子树左子树左子树 (a) (b) (c) (d) (e) 图6.1 二叉树的五种基本形态 2二叉树的相关概念 （1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点。度为0的结点称为叶结点，或者称为终端结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（5）路径、路径长度。如果一棵树的一串结点n1,n2,nk有如下关系：

4、结点ni是ni+1的父结点（1ik）,就把n1,n2,nk称为一条由n1至nk的路径。这条路径的长度是k-1。 （6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。 （7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 （8）树的深度。树中所有结点的最大层数称为树的深度。 （9）树的度。树中各结点度的最大值称为该树的度。 （10）满二叉树。 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。如图6.2所示，（a）图就是一棵满二叉树，（b）图则不是满二叉

5、树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树。11A A2B323 C BC45677654 G F E DDEGF H IKJHIONML8914151312111098 (a) 一棵满二叉树 (b) 一棵非满二叉树 图6.2 满二叉树和非满二叉树示意图 （11）完全二叉树。 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子

6、结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图6.3所示（a）为一棵完全二叉树，（b）和图6.2（b）都不是完全二叉树。11AA3132CBC B6547654EFDFGED7GJIH10 89 (a) 一棵完全二叉树 (b) 一棵非完全二叉树 图6.3 完全二叉树和非完全二叉树示意图 6.1.2 二叉树的主要性质 性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i1）。该性质可由数学归纳法证明。证明略。 性质2 一棵深度为k的二叉树中，最多具有2k1个结点。 ki=1 ki=1 证明 设第i层的结点数为xi（1ik），深度为k的二叉树的结点

7、数为M，xi最多为2i-1，则有： M xi 2i-1 2k-1性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有: n0n21。 证明 设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： nn0n1n2 （6-1）在二叉树中，除根结点外，其余结点都有唯一的一个进入分支。设B为二叉树中的分支数，那么有： Bn1 （6-2）这些分支是由度为1和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出两个分支，所以有： Bn12n2 （6-3）综合（6-1）、（6-2）、（6-3）式可以得到： n0n21 性质4 具有n个结点的完全二叉树的深度

8、k为log2n+1。 证明 根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有 2k11n2k-1即 2k1n2k对不等式取对数，有 k1log2n1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i1，则序号为i的结点是根结点，无双亲结点。 （2）如果2in，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。（3）如果2i1n，则序号为i的结点的右孩子结点的序号为2i1；如果2i1n，则序号为i的结点无右孩子。此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i1）/2，左孩子的编号为2i1

9、，右孩子的编号为2i2。此性质可采用数学归纳法证明。证明略。6.2 基本操作与存储实现 6.2.1 二叉树的存储 1顺序存储结构所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结

10、点之间的关系。图6.4 给出的图6.3(a)所示的完全二叉树的顺序存储示意。 对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图6.5给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图6.6 所示，一棵深度为k的右单支树，只有k个结点，却需分配2k

11、1个存储单元。 A B C D E F G H I J数组下标 0 1 2 3 4 5 6 7 8 9 图6.4 完全二叉树的顺序存储示意图AACBCBEDDEGFFG (a) 一棵二叉树 (b) 改造后的完全二叉树 A B C D E F G (c) 改造后完全二叉树顺序存储状态 图6.5 一般二叉树及其顺序存储示意图AABBCCDD (a) 一棵右单支二叉树 (b) 改造后的右单支树对应的完全二叉树 A B CD (c) 单支树改造后完全二叉树的顺序存储状态 图6.6 右单支二叉树及其顺序存储示意图 二叉树的顺序存储表示可描述为： #define MAXNODE /*二叉树的最大结点数*/

12、 typedef elemtype SqBiTreeMAXNODE /*0号单元存放根结点*/ SqBiTree bt;即将bt定义为含有MAXNODE个elemtype类型元素的一维数组。 2链式存储结构 所谓二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式。 （1）二叉链表存储链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为： lchild rchild data 其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指

13、针，当左孩子或右孩子不存在时，相应指针域值为空（用符号或NULL表示）。 图6.7(a)给出了图6.3(b)所示的一棵二叉树的二叉链表示。二叉链表也可以带头结点的方式存放，如图6.7(b)所示。头指针bt 头结点指针btAACBCBFEDFEDGG (a) 带头指针的二叉链表 (b) 带头结点的二叉链表 图6.7 图6.3(b)所示二叉树的二叉链表表示示意图 （2）三叉链表存储每个结点由四个域组成，具体结构为： parent rchild lchild data其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查

14、找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。 图6.8给出了图6.3(b)所示的一棵二叉树的三叉链表示。ACBFEDG 图6.8 图6.3(b)所示二叉树的三叉链表表示示意图 尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。本书后面所涉及到的二叉树的链式存储结构不加特别说明的都是指二叉链表结构。 二叉树的二叉链表存储表示可描述为： typedef struct BiTNode elemtype data; struct BiTNode

15、*lchild;*rchild; /*左右孩子指针*/ BiTNode,*BiTree;即将BiTree定义为指向二叉链表结点结构的指针类型。 6.2.2 二叉树的基本操作及实现 1二叉树的基本操作 二叉树的基本操作通常有以下几种：（1） Initiate（bt）建立一棵空二叉树。 （2）Create（x，lbt，rbt）生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。 （3）InsertL（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结

16、点作为结点x的左孩子结点。 （4）InsertR（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的右孩子结点。如果结点parent原来有右孩子结点，则将结点parent原来的右孩子结点作为结点x的右孩子结点。 （5）DeleteL（bt，parent）在二叉树bt中删除结点parent的左子树。 （6）DeleteR（bt，parent）在二叉树bt中删除结点parent的右子树。 （7）Search（bt，x）在二叉树bt中查找数据元素x。（8）Traverse（bt）按某种方式遍历二叉树bt的全部结点。 2算法的实现 算法的实现依赖于具体的存储结构，当

17、二叉树采用不同的存储结构时，上述各种操作的实现算法是不同的。下面讨论基于二叉链表存储结构的上述操作的实现算法。 （1）Initiate（bt）初始建立二叉树bt，并使bt指向头结点。在二叉树根结点前建立头结点，就如同在单链表前建立的头结点，可以方便后边的一些操作实现。 int Initiate (BiTree *bt) /*初始化建立二叉树*bt的头结点*/ if(*bt=(BiTNode *)malloc(sizeof(BiTNode)=NULL) return 0; *bt-lchild=NULL; *bt-rchild=NULL; return 1;算法 6.1 （2）Create（x，

18、lbt，rbt）建立一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。 BiTree Create（elemtype x，BiTree lbt，BiTree rbt） /*生成一棵以x为根结点的数据域值以lbt和rbt为左右子树的二叉树*/ BiTree p; if (p=(BiTNode *)malloc(sizeof(BiTNode)=NULL) return NULL; p-data=x; p-lchild=lbt; p-rchild=rbt; return p;算法 6.2 （3）InsertL（bt，x，

19、parent） BiTree InsertL（BiTree bt，elemtype x，BiTree parent） /*在二叉树bt的结点parent的左子树插入结点数据元素x*/ BiTree p; if (parent=NULL) printf(“n插入出错”)； return NULL; if (p=(BiTNode *)malloc(sizeof(BiTNode)=NULL) return NULL; p-data=x; p-lchild=NULL; p-rchild=NULL; if (parent-lchild=NULL) parent-lchild=p; else p-lchi

20、ld=parent-lchild; parent-lchild=p; return bt;算法 6.3 （4）InsertR（bt，x，parent）功能类同于（3），算法略。 （5）DeleteL（bt，parent）在二叉树bt中删除结点parent的左子树。当parent或parent的左孩子结点为空时删除失败。删除成功时返回根结点指针；删除失败时返回空指针。 BiTree DeleteL（BiTree bt，BiTree parent） /*在二叉树bt中删除结点parent的左子树*/ BiTree p; if (parent=NULL|parent-lchild=NULL) pri

21、ntf(“n删除出错”)； return NULL p=parent-lchild; parent-lchild=NULL; free(p); /*当p为非叶子结点时，这样删除仅释放了所删子树根结点的空间，*/ /*若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。*/ return br;算法 6.4 （6）DeleteR（bt，parent）功能类同于（5），只是删除结点parent的右子树。算法略。 操作Search（bt，x）实际是遍历操作Traverse（bt）的特例，关于二叉树的遍历操作的实现，将在下一节中重点介绍。6.3 二叉树的遍历 6.3.1 二叉树的遍历方法及递归实现

22、二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。由二叉树的定义可知，一棵由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：D

23、LR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。 1先序遍历（DLR） 先序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1） 访问根结点；（2） 先序遍历根结点的左子树；（3） 先序遍历根结点的右子树。 先序遍历二叉树的递归算法如下：void PreOrder（BiTree bt）/*先序遍历二叉树bt*/ if (bt=NULL) return; /*递归调用的结束条件*/ Visite（bt-data）; /*访问结点的数据域*/ PreOrder（bt-lchild）; /*

24、先序递归遍历bt的左子树*/ PreOrder（bt-rchild）; /*先序递归遍历bt的右子树*/ 算法 6.5对于图6图6.3(b)所示的二叉树，按先序遍历所得到的结点序列为： A B D G C E F 2中序遍历（LDR）中序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。中序遍历二叉树的递归算法如下：void InOrder（BiTree bt）/*中序遍历二叉树bt*/ if (bt=NULL) return; /*递归调用的结束条件*/ InOrder（bt-lchild）; /*中序递归遍历bt的

25、左子树*/ Visite（bt-data）; /*访问结点的数据域*/ InOrder（bt-rchild）; /*中序递归遍历bt的右子树*/ 算法 6.6对于图6.3(b)所示的二叉树，按中序遍历所得到的结点序列为： D G B A E C F 3后序遍历（LRD）后序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树。（3）访问根结点；后序遍历二叉树的递归算法如下：void PostOrder（BiTree bt）/*后序遍历二叉树bt*/ if (bt=NULL) return; /*递归调用的结束条件*/ PostOrder（b

26、t-lchild）; /*后序递归遍历bt的左子树*/ PostOrder（bt-rchild）; /*后序递归遍历bt的右子树*/ Visite（bt-data）; /*访问结点的数据域*/算法 6.7对于图图6.3(b)所示的二叉树，按先序遍历所得到的结点序列为： G D B E F C A 4层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于图6.3(b)所示的二叉树，按层次遍历所得到的结果序列为： A B C D E F G下面讨论层次遍历的算法。 由层次遍历的定义可以推知，在进行层次遍历时，对一层结

27、点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：（1） 访问该元素所指结点；（2） 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。 在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组QueueMAXNODE用以实现队列，变量front和rear分别表示当前对首元素

28、和队尾元素在数组中的位置。 void LevelOrder（BiTree bt） /*层次遍历二叉树bt*/ BiTree QueueMAXNODE; int front,rear; if (bt=NULL) return; front=-1; rear=0; queuerear=bt; while(front!=rear) front+; Visite(queuefront-data); /*访问队首结点的数据域*/ if (queuefront-lchild!=NULL) /*将队首结点的左孩子结点入队列*/ rear+; queuerear=queuefront-lchild; if (queuefront-rchild!=NULL) /*将队首结点的右孩子结点入队列*/ rear+; queuerear=queuefront-rchild; 算法 6.8 6.3.2 二叉树遍历的非递归实现 前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。当给出二叉树的链式存储结构以后，用具有递归功能的程序设计语言很方便就能实现上述算法。然而，并非所有程序设计语言都允许递归；另一方面，递归程序虽然简洁