1、第六章 树和二叉树 第六章 树和二叉树 6.1 6.1 树的有关概念树的有关概念1.1. 树的概念树的概念2. 2. 树的应用树的应用3.3. 树的表示树的表示4. 树的有关术语树的有关术语5 树的基本操作树的基本操作6.1 树的有关概念1树的定义树的定义 定义：树是定义：树是n个结点的个结点的集合。在任一棵非空树中：集合。在任一棵非空树中： （1）有且仅有一个称为根的结点；。）有且仅有一个称为根的结点；。 （2）其余结点可分为）其余结点可分为m个个有限集合，而且这些集合有限集合，而且这些集合中的每一集合本身又是一棵树，称为根的子树。中的每一集合本身又是一棵树，称为根的子树。树是递归结构，在树
2、的定义中又用到了树的概念树是递归结构，在树的定义中又用到了树的概念J JI IA AC CB BD DH HG GF FE E 树结构树结构 （除了一个称为根的结点外）每个元素都有且仅有（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。一个直接前趋，有且仅有零个或多个直接后继。6.1 树的有关概念从逻辑结构看：从逻辑结构看： 1）树中只有根结点没有前趋；）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在）除根外的
3、其他结点，都存在条从根到该结点的路径；条从根到该结点的路径；5）树是一种分枝结构）树是一种分枝结构J JI IA AC CB BD DH HG GF FE E6.1 树的有关概念2树的应用树的应用1）树可表示具有分枝结构关系的对象）树可表示具有分枝结构关系的对象例例1家族族谱家族族谱例例2单位行政机构的组织关系、系统功能模块图单位行政机构的组织关系、系统功能模块图6.1 树的有关概念2）树是常用的数据组织形式）树是常用的数据组织形式 有些应用中数据元素之间并不存在间分支结构关系，但是有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。为了便于管理和
4、使用数据，将它们用树的形式来组织。例例3 计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件是文件系统，所有的文件是用树的形式来组织的。用树的形式来组织的。My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic 6.1 树的有关概念3 、树的基本术语、树的基本术语1 1）结点的度：）结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。2 2）树的度：）树的度：树中各结点度的最大值。树中各结点度的最大值。CGBDEFKLHMIJA 6.1 树的有关概念3 3）叶子结点：）叶子结点：度
5、为度为0的结点，也称为终端结点。的结点，也称为终端结点。4 4）分支结点：）分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFKLHMIJA 6.1 树的有关概念5 5）孩子、双亲：）孩子、双亲：树中结点的子树的根结点称为这个结树中结点的子树的根结点称为这个结点的点的孩子结点孩子结点，这个结点称为它孩子结点的，这个结点称为它孩子结点的双亲结点双亲结点；6 6）兄弟：）兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。 CGBDEFKLHMIJA 6.1 树的有关概念7）路径：）路径：如果树的结点序列如果树的结点序列n1, n2,
6、 , nk有如下关系：结有如下关系：结点点ni是是ni+1的双亲，则把的双亲，则把n1, n2, , nk称为一条由称为一条由n1至至nk的的路径；路径上经过的边的个数称为路径；路径上经过的边的个数称为路径长度路径长度。 CGBDEFKLHMIJA 6.1 树的有关概念8 8）祖先、子孙：）祖先、子孙：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到结点到结点y，那么，那么x就称为就称为y的祖先，而的祖先，而y称为称为x的子孙。的子孙。CGBDEFKLHMIJA 6.1 树的有关概念9 9）结点所在层数：）结点所在层数：根结点的层数为根结点的层数为1 1；对其余任何结点，；对其余任
7、何结点，若某结点在第若某结点在第k k层，则其孩子结点在第层，则其孩子结点在第k+1k+1层。层。1010）树的深度：）树的深度：树中所有结点的最大层数，也称树中所有结点的最大层数，也称高度高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJC 6.1 树的有关概念1111）有序树、无序树：）有序树、无序树：如果一棵树中结点的各子树如果一棵树中结点的各子树从左到右是有次序的（即不能互换），称这棵树为从左到右是有次序的（即不能互换），称这棵树为有序树；反之，称为无序树。有序树；反之，称为无序树。ACBGFEDACBGFED数据结构中讨论的一般都是有序树数据结构中讨论的一般都是
8、有序树 6.1 树的有关概念12）森林：）森林：m (m0)棵互不相交的树的集合。棵互不相交的树的集合。 CBDEFKLHJA 6.1 树的有关概念树结构和线性结构的比较树结构和线性结构的比较线性结构线性结构树结构树结构第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个）无前驱无前驱无双亲无双亲最后最后一一个数据元素个数据元素叶子结点叶子结点(可以有可以有多多个个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子一对一一对一 一对多一对多6.1 树的有关概念4、树的基本操作、树的基本操作 树的应用很
9、广，应用不同基本操作也不同。下面列举了树树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：的一些基本操作： 1）InitTree(&T); /构造空树T 2）DestroyTree(&T); /销毁树T 3）CreateTree(&T, definition); /按definition构造树T 4）ClearTree(&T); /将树T清为空树 5）TreeEmpty(T); /判断树T是否为空树 6）TreeDepth(T); /求树的深度 7） Root(T); /返回树T的根值 6.1 树的有关概念 8） Value(T, &cur_e); /求树T中结点cur_e的值
10、 9） Assign(T, cur_e, value); /把value赋值给树T的cur_e结点 10）Parent(T, cur_e); /求树T中非根结点cur_e的双亲 11）LeftChild(T, cur_e); /求树T中非叶子结点cur_e的左孩子 12）RightSibling(T, cur_e); /求树T中cur_e结点的右兄弟 13）InsertChild(&T, &p, i, c); /在树中插入一个结点 14）DeleteChild(&T,&p, i); /删除树中某一个结点 15）TraverseTree(T, Visit( ); /按某种次序访问树中每个结点6
11、2 二 叉 树 树是一种分枝结构的对象，在树的概念中，对每一个结点树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树讨论一种最简单的树二叉树。二叉树。6.2 二 叉 树一一 二叉树的概念二叉树的概念1 1 二叉树的定义二叉树的定义二叉树：二叉树： 或为空树，或由根及两或为空树，或由根及两颗不相交的左子树、右子树构成，颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。并且左、右子树本身也是二叉树。说明：说明：1 1）二叉树中每个结点最多有两颗子树；二叉树每个结点
12、度小于等于）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2;2 2）左、右子树不能颠例）左、右子树不能颠例有序树有序树; ;3 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念; ;ABCDEFG6.2 二 叉 树 2 二叉树的基本形态二叉树的基本形态空二叉树空二叉树只有一个根结点只有一个根结点右子树右子树根结点只有右子树根结点只有右子树左子树左子树根结点只有左子树根结点只有左子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树6.2 二 叉 树二、二叉树性质 性质1 在二叉树的第i 层上最多有2
13、i-1个结点（i=1）证明：证明： 当当i=1时时，第，第1层只有一个根结点，结点数层只有一个根结点，结点数=20 =1，结论显然成立。，结论显然成立。假设假设j=i-1时时，结论正确，即第，结论正确，即第j层最多有层最多有2i-2， 所以当所以当j=i时时，第，第i层最多有层最多有2*2i-2=2i-1；结论正确；结论正确6.2 二 叉 树 性质性质2 一棵深度为一棵深度为k的二叉树中，最多有的二叉树中，最多有2k- -1个结个结点，最少有点，最少有k个结点。个结点。 证明：由性质证明：由性质1可知，深度为可知，深度为k的二叉树中结点个数最多的二叉树中结点个数最多= =2k-1；kii1)(
14、层上结点的最大个数第 每一层至少要有一个结点，因此深度为每一层至少要有一个结点，因此深度为k k的二叉树，的二叉树，至少有至少有k k个结点。个结点。6.2 二 叉 树证明证明: 设设n为二叉树的结点总数，为二叉树的结点总数，n1为二为二叉树中度为叉树中度为1的结点数，则有：的结点数，则有： nn0n1n2 在二叉树中，在二叉树中，除了根结点外，其余结点都有唯一除了根结点外，其余结点都有唯一的一的一个分枝进入，由于这些分枝是由度为个分枝进入，由于这些分枝是由度为1和度为和度为2的结点射出的结点射出的，一个度为的，一个度为1的结点射出一个分枝，一个度为的结点射出一个分枝，一个度为2的结点射的结点
15、射出两个分枝，所以有：出两个分枝，所以有： nn12n21因此可以得到：因此可以得到：n0n21 。A152346789 10BCDEFGHIJ性质性质3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为，度为2的结点数为的结点数为n2，则有，则有: n0n21。 6.2 二 叉 树两种特殊的二叉树两种特殊的二叉树满二叉树：如果深度为满二叉树：如果深度为k k的二叉树，有的二叉树，有2 2k k-1-1个结点则称为满二叉树；个结点则称为满二叉树；A15234678910BCDEFGHIJKLM NO1112 13 14 15满二叉树的特点满二叉树的特点：1. 叶子只能
16、出现在最下一层；叶子只能出现在最下一层；2. 只有度为只有度为0和度为和度为2的结点。的结点。满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中结点结点个数最多个数最多满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中叶子结点叶子结点个数最多个数最多6.2 二 叉 树 完全二叉树完全二叉树 深度为深度为K，有，有n个结点的个结点的二叉树，当且仅当其每一个二叉树，当且仅当其每一个结点都与深度为结点都与深度为K的满二叉树的满二叉树中编号从中编号从1至至n的结点都一一的结点都一一对应时，称之为完全二叉树对应时，称之为完全二叉树。A15234678910BCDEFGHIJA15234678
17、910BCDEFGHIJKLM NO1112 13 14 156.2 二 叉 树在满二叉树中，从最后在满二叉树中，从最后一个结点开始，一个结点开始，连续连续去去掉掉任意任意个结点，即是一个结点，即是一棵完全二叉树。棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是完全二叉树，结点不是完全二叉树，结点10与满二叉树中的结点与满二叉树中的结点10不是同一个结点不是同一个结点6.2 二 叉 树完全二叉树的特点完全二叉树的特点1. 叶子结点只能出现在最下两层；叶子结点只能出现在最下两层；2. 完全二叉树中如果有度为完全二
18、叉树中如果有度为1的结的结点，只可能有一个，且该结点，只可能有一个，且该结点只有点只有左孩子。左孩子。 3. 深度为深度为k的完全二叉树在的完全二叉树在k-1层层上一定是满二叉树。上一定是满二叉树。A1523467910BCDEFGHIJK11L12M13N14O1586.2 二 叉 树性质性质4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 A15234678910BCDEFGHIJ6.2 二 叉 树性质性质5 对一棵具有对一棵具有n个结点的完全二叉树中从个结点的完全二叉树中从1开始按层序编号，开始按层序编号，则对于任意的序号为则对于任意的序号为i（1i
19、n）的结点，有：）的结点，有： （1）如果）如果i1，则结点，则结点i的双亲结点的序号为的双亲结点的序号为 i/2（取整）；如（取整）；如果果i1，则结点，则结点i是根结点，无双亲结点。是根结点，无双亲结点。 A15234678910BCDEFGHIJ6.2 二 叉 树（2）如果）如果2in，则结点，则结点i的左孩子的序号为的左孩子的序号为2i； 如果如果2in，则结点，则结点i无左孩子。无左孩子。 A15234678910BCDEFGHIJ6.2 二 叉 树（3）如果）如果2i1n，则结点，则结点i的右孩子的序号为的右孩子的序号为2i1； 如果如果2i1n，则结点，则结点 i无右孩子。无右孩
20、子。 A15234678910BCDEFGHIJ6.2 二 叉 树 对一棵具有对一棵具有n个结点的个结点的完全二叉树中从完全二叉树中从1开始按层开始按层序编号，则序编号，则l 结点结点i的双亲结点为的双亲结点为 i/2；l 结点结点i的左孩子为的左孩子为2i；l 结点结点i的右孩子为的右孩子为2i1。 18910456723性质性质5表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。6.2 二 叉 树三二叉树存贮结构三二叉树存贮结构 1 1 二叉树的顺序结构二叉树的顺序结构 二叉树的顺序存储结构就是用一维数组存储二叉树中
21、二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的的结点，并且结点的存储位存储位置置（下标）应能体现结点之（下标）应能体现结点之间的间的逻辑关系逻辑关系父子关系。父子关系。 如何利用数组下标来反映结点之间的逻辑关系如何利用数组下标来反映结点之间的逻辑关系? ?完全二叉树完全二叉树和和满二叉树满二叉树中结点的序号可以唯一中结点的序号可以唯一地反映出结点之间的逻辑关系地反映出结点之间的逻辑关系 。6.2 二 叉 树完全二叉树的顺序存储完全二叉树的顺序存储A15234678910BCDEFGHIJ以编号以编号为下标为下标 A B C D E F G H I J数组下标数组下标 1 2
22、3 4 5 6 7 8 9 106.2 二 叉 树二叉树的顺序存储二叉树的顺序存储ABCDFGE按照完全按照完全二叉树编号二叉树编号ABCDFGE123561013ABC DE F G数组下标数组下标 1 2 3 4 5 6 7 8 9 10 11 12 13以编号以编号为下标为下标6.2 二 叉 树6.2 二 叉 树 2 2 二叉树的链式存储结构二叉树的链式存储结构1）基本思想：）基本思想：令二叉树的每个结点对应一个链表结令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信点，链表结点除了存放与二叉树结点有关的数据信息息外，还要设置指示左右孩子的指针。外，还要设置指示
23、左右孩子的指针。 结点结构：结点结构： lchild data rchild其中，其中，data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针；：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。：右指针域，存放指向右孩子的指针。 6.2 二 叉 树二叉树的二叉链表存储表示：二叉树的二叉链表存储表示：Typedef struct BiNode TElemType data; struct BiNode *lchild, *rchild;/ 左右孩子指针左右孩子指针BiNode, *BiTree;6.2
24、 二 叉 树 2 2）二叉链表）二叉链表 二叉链表中每个结点至少包含三个域：数据域、左指针域、二叉链表中每个结点至少包含三个域：数据域、左指针域、 右指针域右指针域 ABCDEFGGFEDBAC在在n n个结点的二叉树中，有个结点的二叉树中，有n+1n+1个空链域。个空链域。6.2 二 叉 树3 ）三叉链表三叉链表 三叉链表中每个结点至少包含四个域：数据域、双亲指针三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域域、左指针域、右指针域结点结构：结点结构： lchild data parent其中，其中，data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信
25、息； parent:双亲指针域，存放指向指向双亲节点的指针；双亲指针域，存放指向指向双亲节点的指针； lchild：左指针域，存放指向左孩子的指针；：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。：右指针域，存放指向右孩子的指针。 rchild6.2 二 叉 树ABCDEFGABDEFCG第六章第六章 树和二叉树树和二叉树 6.3 二叉树的遍历一、二叉树的遍历方法一、二叉树的遍历方法 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点被访问一次访问二叉树中的所有结点，使得每个结点被访问一次且
26、仅被且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 二叉树的遍历方式：二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种：前序前序：DLR中序中序：LDR后序后序：LRD层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问
27、各结点。 考虑二叉树的组成：考虑二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树6.3 二叉树的遍历1 1、先序（根）遍历、先序（根）遍历若二叉树为空，则空操作返回若二叉树为空，则空操作返回；否则：；否则：访问根结点；访问根结点；先序先序遍历遍历根根结点的左子树；结点的左子树；先序先序遍历遍历根根结点的右子树。结点的右子树。先序遍历序列：先序遍历序列：A B D G C E FABCDEFG6.3 二叉树的遍历6.3 二叉树的遍历2、中序（根）遍历、中序（根）遍历若二叉树为空，则空操作返回；若二叉树为空，则空操作返回；否则：否则：中序中序遍历遍历根根结点的左子树；结点的左子
28、树；访问根结点；访问根结点；中序中序遍历遍历根根结点的右子树。结点的右子树。 中序遍历序列：中序遍历序列：D G B A E C FABCDEFG6.3 二叉树的遍历3、后序（根）遍历、后序（根）遍历若二叉树为空，则空操作返回；若二叉树为空，则空操作返回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序遍历遍历根根结点的右子树；结点的右子树；访问根结点。访问根结点。后序遍历序列：后序遍历序列：G D B E F C AABCDEFG4、层序遍历、层序遍历二叉树的层次遍历是指从二二叉树的层次遍历是指从二叉树的第一层（即根结点）叉树的第一层（即根结点）开始，开始，从上至下从上至
29、下逐层遍历，逐层遍历，在同一层中，则按在同一层中，则按从左到右从左到右的顺序对结点逐个访问。的顺序对结点逐个访问。 层序遍历序列：层序遍历序列：A B C D E F GABCDEFG6.3 二叉树的遍历6.3 二叉树的遍历ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A6.3 二叉树的遍历void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍历二叉树先序遍历二叉树 if (T!=NULL)
30、 visit(T-data); / 访问结点访问结点 Preorder(T-lchild, visit); / 遍历左子树遍历左子树 Preorder(T-rchild, visit);/ 遍历右子树遍历右子树 1 1先序遍历递归算法先序遍历递归算法6.3 二叉树的遍历二叉树前序遍历的非递归算法的二叉树前序遍历的非递归算法的关键关键：在前序遍历过：在前序遍历过某结点的整个左子树后，如何找到该结点的某结点的整个左子树后，如何找到该结点的右子树右子树的的根指针。根指针。解决办法：解决办法：在访问完该结点后，将该结点的指针保存在访问完该结点后，将该结点的指针保存在在栈栈中，以便以后能通过它找到该结点
31、的右子树。中，以便以后能通过它找到该结点的右子树。 先序遍历先序遍历非递归算法非递归算法AGBCDFE先序遍历先序遍历算法的执行轨迹算法的执行轨迹栈内容1.栈栈s初始化；初始化；2.循环直到循环直到root为空或栈为空或栈s为空为空 2.1 当当root不空时循环不空时循环2.1.1 输出输出root-data;（可将输出变为任何处理）（可将输出变为任何处理） 2.1.2 将指针将指针root的值保存到栈中；的值保存到栈中； 2.1.3 继续遍历继续遍历root的左子树的左子树2.2 如果栈如果栈s不空，则不空，则2.2.1 将栈顶元素弹出至将栈顶元素弹出至root；2.2.2 准备遍历准备遍
32、历root的右子树；的右子树； 6.3 二叉树的遍历void Preorder (BiTree T, void( *visit)(TElemType& e) InitStack(&S) ; p=T; while (p!=NULL|!StackEmpty(S) if (p!=NULL) visit(p-data); / 访问结点访问结点 Push(&S,p); p=p-lchild else Pop(&S,&p); p=p-rchild 先序遍历非递归算法（伪代码）先序遍历非递归算法（伪代码）6.3 二叉树的遍历2 中中序遍历递归算法序遍历递归算法void Inorder (BiTree T,
33、void( *visit)(TElemType& e) / 中序遍历二叉树中序遍历二叉树 if (T!=NULL) Preorder(T-lchild, visit); / 遍历左子树遍历左子树 visit(T-data); / 访问结点访问结点 Preorder(T-rchild, visit);/ 遍历右子树遍历右子树 6.3 二叉树的遍历中中序遍历非递归算法：序遍历非递归算法：void Inorder (BiTree T, void( *visit)(TElemType& e) InitStack(&S) ; p=T; while (p!=NULL|!StackEmpty(S) if (
34、p!=NULL) Push(&S,p); p=p-lchild else Pop(&S,&p); visit(T-data); / 访问结点访问结点 p=p-rchild 6.3 二叉树的遍历3 后后序遍历递归算法序遍历递归算法void Postorder (BiTree T, void( *visit)(TElemType& e) / 后序遍历二叉树后序遍历二叉树 if (T!=NULL) Preorder(T-lchild, visit); / 遍历左子树遍历左子树 Preorder(T-rchild, visit);/ 遍历右子树遍历右子树 visit(T-data); / 访问结点访问
35、结点 若已知一棵二叉树的前序序列和中序序列，能否唯若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？一确定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的先序遍历序列和中序遍历序列例如：已知一棵二叉树的先序遍历序列和中序遍历序列分别为分别为ABCDEFGHI 和和BCAEDGHFI，如何构造该二叉如何构造该二叉树呢树呢? ? 6.3 二叉树的遍历先序：先序：A B C D E F G H I中序：中序：B C A E D G H F I先序：先序：B C中序：中序：B C B C D EF GH IA先序：先序： D E F G H I中序：中序： E D G H F
36、IABCDEFGHI6.3 二叉树的遍历先序：先序：F G H I中序：中序：G H F I先序：先序： D E F G H I中序：中序： E D G H F IABCDEFGHIABCDEFIGH6.3 二叉树的遍历第六章 树和二叉树 6.4 遍历的应用 遍历二叉树是二叉树各种操作的基础遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的是多种形式及多个操作，根据遍历算法的框架，框架，适当修改访问操作的内容适当修改访问操作的内容，可以派，可以派生出很多关于二叉树的应用算法。生出很多关于二叉树的应用算法。
37、6.4 6.4 遍历的应用遍历的应用例例1 编写编写 求二叉树的叶子结点个数的算法求二叉树的叶子结点个数的算法输入：二叉树的二叉链表输入：二叉树的二叉链表结果：二叉树的叶子结点个数结果：二叉树的叶子结点个数基本思想：遍历操作访问二叉树的每个结点，而且每个结点仅被访问基本思想：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。所以可在二叉树遍历的过程中，统计叶子结点的个数。一次。所以可在二叉树遍历的过程中，统计叶子结点的个数。void leaf(BiTree T) /n计数二叉树的叶子结点的个数，初值计数二叉树的叶子结点的个数，初值n=0if(T) if(T-lchild=null&T-r
38、child=null) n=n+1; leaf(T-lchild); leaf(T-rchild); /if/leafABCDEFG例例2 2 求二叉树的结点个数。求二叉树的结点个数。 void Count(BiNode *root) /n为全局量并已初始化为为全局量并已初始化为0 if (root) Count(root-lchild); n+ +; Count(root-rchild); 6.4 遍历的应用遍历的应用例例3 3 、求二叉树的深度。、求二叉树的深度。 int Depth(BiNode *root) if (root= =NULL) return 0; else hl= Dep
39、th(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; 6.4 遍历的应用遍历的应用二叉树的深度应为二叉树的深度应为其左、右子树深度其左、右子树深度的最大值加的最大值加1 1。6.4 遍历的应用 例例4 为二叉树建立二叉存储链表为二叉树建立二叉存储链表 输入：二叉树的先序序列输入：二叉树的先序序列 结果：建立二叉树的二叉存储链表结果：建立二叉树的二叉存储链表 按先序编历的顺序输入按先序编历的顺序输入先序序列（设每个元素是先序序列（设每个元素是一个一个字符），建立二叉链表的所有结点并完成相应结点的链接字符），建立二叉链表的所
40、有结点并完成相应结点的链接。 为了建立一棵二叉树，将二叉树中每个结点的空指针为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如引出一个虚结点，其值为一特定值如“#”“#”，以标识其为，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。空，把这样处理后的二叉树称为原二叉树的扩展二叉树。 扩展二叉树的先序遍历序列扩展二叉树的先序遍历序列:A B # D # # C # #DBAC#DBAC#6.4 遍历的应用6.4 遍历的应用Status CreateBiTree(BiTree &T) /假设扩展二叉树的先序遍历序列由键盘输入，假设扩展二叉树的先序遍历序列由键
41、盘输入，T为指向根结点的指针为指向根结点的指针 scanf (&ch); if (ch= = #) T=NULL; / 若若ch= = # 则则T=NULL返回返回 else / 若若ch! = if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 建立（根）结点建立（根）结点 CreateBiTree(T-lchild); /构造左子树，并将左子树根结点指针构造左子树，并将左子树根结点指针 /赋赋 给（根）结点给（根）结点 的左孩子域的左孩子域 CreateBiTree(T-rchild); /构
42、造右子树，并将右子树根结点指针构造右子树，并将右子树根结点指针 /赋给（根）结点赋给（根）结点 的右孩子域的右孩子域 return OK;/CreateBiTree 小小 结结1 1 二叉树：二叉树： 或为空树，或由根及两颗不相交的左子树、或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；右子树构成，并且左、右子树本身也是二叉树；2 2 二叉树即可以用顺序结构存储，也可用链式结构存储；二叉树即可以用顺序结构存储，也可用链式结构存储；3 3 遍历：按某种搜索路径访问二叉树的每个结点，每个结遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。点仅被访问一次
43、。 二叉树的遍历可以分解为：访问根，遍二叉树的遍历可以分解为：访问根，遍历历左子树和左子树和遍历遍历右子树，本课程介绍了三种遍历算法：右子树，本课程介绍了三种遍历算法：先先序遍历、中序遍历、后序遍历；序遍历、中序遍历、后序遍历；第六章 树和二叉树 6.6.5 5 线索二叉树线索二叉树 1. 1. 线索二叉树的概念线索二叉树的概念 2 2 线索链表线索链表 3. 3. * * 线索二叉树的遍线索二叉树的遍历历6.5 线索二叉树一、一、 线索二叉树线索二叉树遍历的目的：遍历的目的：将二叉树中的结点按一定规律（先、中、后序）线性化的将二叉树中的结点按一定规律（先、中、后序）线性化的过程。过程。问题：
44、问题：当以二叉链表作为存储结构时，只能找到某结点的左、右当以二叉链表作为存储结构时，只能找到某结点的左、右孩子信息，不能得到结点在某种遍历序列中的前驱和后继信息。孩子信息，不能得到结点在某种遍历序列中的前驱和后继信息。解决办法：解决办法： 重新遍历，在遍历过程中得到前驱、后继信息。但这种动态重新遍历，在遍历过程中得到前驱、后继信息。但这种动态 访问浪费时间。访问浪费时间。 充分利用二叉链表的空链域，将遍历过程中结点的前驱、后充分利用二叉链表的空链域，将遍历过程中结点的前驱、后 继信息保留下来。继信息保留下来。 ltag lchild data rchild rtag0: lchild指向该结点
45、的左孩子指向该结点的左孩子1: lchild指向该结点的前驱结点指向该结点的前驱结点0: rchild指向该结点的右孩子指向该结点的右孩子1: rchild指向该结点的后继结点指向该结点的后继结点ltag=rtag=结点结构结点结构6.5 线索二叉树线索：线索：将二叉链表中的空指针域指向前驱结点和后继结点的指将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；针被称为线索；线索化：线索化：使二叉链表中结点的空链域存放其前驱或后继信息的使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；过程称为线索化；线索二叉树：线索二叉树：加上线索的二叉树称为线索二叉树。加上线索的二叉树称
46、为线索二叉树。ABCDEFGABCDEFGABCDEFGABCDEFGABDGCEFABDGCEFDGBAECFDGBAECFGDBEFCAGDBEFCANULLNULLNULLNULLNULLNULLNULLNULL先序先序中序中序后序后序ABCDEFGDGBAECFDGBAECFNULLNULLNULLNULL中序中序找前驱结点1 1、PLtag=1,PLchildPLtag=1,PLchild为为前驱前驱2 2、“根根”P P的前驱结点是中的前驱结点是中序遍历序遍历P P的左子树时访问的的左子树时访问的最后一个结点最后一个结点找后继结点1 1、PRtag=1,PRchildPRtag=1
47、,PRchild为为后继驱后继驱2 2、“根根”P P的后继结点是其的后继结点是其右子树的右子树的“最左下端最左下端”的结的结点点A头指针头指针BCDEFG00000000000000中序线索链表的建立过程中序线索链表的建立过程已经建立起二叉链表已经建立起二叉链表A头指针头指针BCDEFG00000000000000中序线索链表的建立过程中序线索链表的建立过程中序遍历二叉链表中序遍历二叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点p1A头指针头指针BCDEFG00000000000000中序线索链表的建立过程中序线索链表的建立过程中序遍历二叉链表中序遍历二
48、叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点pre1p1A头指针头指针BCDEFG00000000000000中序遍历二叉链表中序遍历二叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点pre11p1中序线索链表的建立过程中序线索链表的建立过程A头指针头指针BCDEFG00000000000000中序遍历二叉链表中序遍历二叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点pre11p11中序线索链表的建立过程中序线索链表的建立过程A头指针头指针BCDEFG00000000000000中序
49、遍历二叉链表中序遍历二叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点pre11p111中序线索链表的建立过程中序线索链表的建立过程A头指针头指针BCDEFG00000000000000中序遍历二叉链表中序遍历二叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点pre11p1111中序线索链表的建立过程中序线索链表的建立过程A头指针头指针BCDEFG00000000000000中序遍历二叉链表中序遍历二叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点pre11p11111中序线索链表的建立
50、过程中序线索链表的建立过程A头指针头指针BCDEFG00000000000000中序遍历二叉链表中序遍历二叉链表p p为正在访问的结点为正在访问的结点prepre为刚访问的结点为刚访问的结点pre11111111中序线索链表的建立过程中序线索链表的建立过程 6.6 6.6 树和森林树和森林 一一. . 树的存储结构树的存储结构 二二. . 树和二叉树的转换树和二叉树的转换 三三. . 树的遍历树的遍历 四四. . 森林森林 6.6 6.6 树和森林树和森林 一树的存贮结构一树的存贮结构 1、双亲表示法基本思想：基本思想：用一维数组来存储树的各个结点（一般用一维数组来存储树的各个结点（一般按按层
