6-树和二叉树

1、第六章第六章 树和二叉树树和二叉树四类基本结构：四类基本结构：1.1.线性结构线性结构2.2.树形结构树形结构3.3.图状结构图状结构 4.4.集集 合合数据结构数据结构 第六章第六章 树和二叉树树和二叉树树形结构：非线性结构树形结构：非线性结构&非线性结构：非线性结构：至少存在一个数据元素有两个或两个以上的至少存在一个数据元素有两个或两个以上的直接后继直接后继（或（或直接前驱直接前驱）元素的数据结构。）元素的数据结构。&树形结构：树形结构：以分支关系定义的层次结构以分支关系定义的层次结构。 例如：例如：人类的族谱、各种社会关系、各类分类编码；人类的族谱、各种社会关系、各类分类编码；操作系统的

2、文件系统；操作系统的文件系统；Internet中的中的DNS（域名系统）（域名系统）数据结构数据结构 第六章第六章 树和二叉树树和二叉树本章主要内容本章主要内容6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 树与等价问题树与等价问题6.6 Huffman 树及其应用树及其应用数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.1 树的定义和基本术语树的定义和基本术语数据结构数据结构 第六章第六章 树和二叉树树和二叉树树的定义树的定义树树是是n(n=0)个结点的有限集。在一颗非个结点的有限集。

3、在一颗非空树中：空树中：1）有且仅有一个特定的称为）有且仅有一个特定的称为根根(root)的结点；的结点；2）当）当n1时，其余结点可分为时，其余结点可分为m(m0)个互不个互不相交的有限集相交的有限集T1，T2,Tm，其中每个集合，其中每个集合本身又是一颗树，并且称为本身又是一颗树，并且称为根的子树根的子树(subtree)。数据结构数据结构 第六章第六章 树和二叉树树和二叉树ABCDEFGHIJMKL一个树的例子一个树的例子数据结构数据结构 第六章第六章 树和二叉树树和二叉树树的四种表示方法树的四种表示方法1 1）树型）树型 2 2）广义表）广义表 3 3）嵌套集合）嵌套集合4 4）凹入表

4、示法）凹入表示法数据结构数据结构 第六章第六章 树和二叉树树和二叉树ABCDEFGHIJMKL(A( B(E(K, L), F), C(G), D(H(M), I, J) )T1T3T2树根树型表示法树型表示法广义表表示法（广义表表示法（括号表示法括号表示法）数据结构数据结构 第六章第六章 树和二叉树树和二叉树嵌套集合表示法（嵌套集合表示法（文氏图表示法文氏图表示法）KLGFMIJABDHCE数据结构数据结构 第六章第六章 树和二叉树树和二叉树凹入表示法：凹入表示法：使用线段的伸缩描述树结构使用线段的伸缩描述树结构KLFCGDHMIJEBA数据结构数据结构 第六章第六章 树和二叉树树和二叉树基

5、基 本本 术术 语语数据结构数据结构 第六章第六章 树和二叉树树和二叉树树结构中的基本术语树结构中的基本术语1. 1. 结点的度：结点的度：结点具有的子树数称为该结点的度结点具有的子树数称为该结点的度(Degree)(Degree)。 叶子结点叶子结点：度为度为0 0的结点，即没有子树的结点。的结点，即没有子树的结点。 分支结点分支结点：度大于零的结点。：度大于零的结点。 内部结点内部结点：除根结点外的分支结点。：除根结点外的分支结点。 树的度树的度：一棵树中各个结点度数的最大值。：一棵树中各个结点度数的最大值。 2. 2. 儿子结点儿子结点和和父亲结点父亲结点：一个结点的子树的根称为该结点的

6、：一个结点的子树的根称为该结点的儿子结点；儿子结点； 反之，该结点则称为其孩子结点的父亲结点。反之，该结点则称为其孩子结点的父亲结点。 兄弟结点兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。：同一个结点的儿子结点之间互称为兄弟结点。数据结构数据结构 第六章第六章 树和二叉树树和二叉树3.3.路径路径：从树中一个结点到另一个结点之间的分支构成：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。这两个结点之间的路径。 子孙结点子孙结点：一个结点的子树中所有结点均称之为：一个结点的子树中所有结点均称之为该结点的子孙结点。该结点的子孙结点。祖先结点祖先结点：反之，从根结点到达一个结点的

7、路径：反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。上的所有结点，都叫做该结点的祖先结点。4.4.树的深度树的深度：树是一种层次结构，树中结点的层次：树是一种层次结构，树中结点的层次（LevelLevel）是从根结点算起的。根结点为第一层，其儿子）是从根结点算起的。根结点为第一层，其儿子结点为第二层。其余各结点的层数逐层由上而下计算。结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。一棵树中结点的最大层数叫做此树的深度或高度。数据结构数据结构 第六章第六章 树和二叉树树和二叉树5.5.有序树和无序树有序树和无序树：若将树中每个结

8、点的各子树看成是从：若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。左到右有次序的，则称该树为有序树；否则称为无序树。6. 6. 森林森林(Forest)(Forest)： 是是m m（m0m0）棵互不相交的树的集合）棵互不相交的树的集合 。任何一棵非空树是一个任何一棵非空树是一个二元组二元组 Tree = （root，F）其中：其中：root 被称为根结被称为根结点点F 被称为子树森林。被称为子树森林。ArootBCDEFGHIJMKLF数据结构数据结构 第六章第六章 树和二叉树树和二叉树树形结构的逻辑特征树形结构的逻辑特征可用树中结点之间的父子关系来描述：

9、可用树中结点之间的父子关系来描述：树中任一结点都可以树中任一结点都可以有零个或多个直接后有零个或多个直接后继结点继结点（即儿子结点），但至多只能有（即儿子结点），但至多只能有一一个直接前趋结点个直接前趋结点（即父亲结点）。树中只（即父亲结点）。树中只有有根结点无前趋根结点无前趋，它是开始结点；，它是开始结点；叶结点叶结点无后继无后继，它们是终端结点。，它们是终端结点。数据结构数据结构 第六章第六章 树和二叉树树和二叉树对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点数据结构数据结构 第六章第六章 树和二叉树树和二叉树线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素

10、(无前驱无前驱) 根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、 一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、 多个后继多个后继)数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.2 二叉树二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树 二叉树或为空树，或是由一个根结点加二叉树或为空树，或是由一个根结点加上两棵分别称为上两棵分别称为左子树左子树和和右子树右子树的、的、互不互不交的交的二叉树组成。二叉树组成。ABCDEFGHK根结点根结点

11、左子树左子树右子树右子树二叉树中不存在度大于二叉树中不存在度大于2的的结点，并且二叉树的子树有结点，并且二叉树的子树有左子树和右子树左子树和右子树之分！之分！数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树的性质二叉树的性质数据结构数据结构 第六章第六章 树和二叉树树和二叉树 性质性质1 ：在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点个结点

12、(i1) 。用归纳法证明：用归纳法证明： 归纳基础：归纳基础：i = 1 层时，只有一个根结点：层时，只有一个根结点： 2i-1 = 20 = 1；归纳假设：归纳假设：假设对所有的假设对所有的 j，1 j i， 命题成立；命题成立；归纳证明：归纳证明：二叉树上每个结点至多有两棵二叉树上每个结点至多有两棵 子树，则第子树，则第 i 层的结点数层的结点数 =2i-2 2 = 2i-1 。数据结构数据结构 第六章第六章 树和二叉树树和二叉树性质性质 2 ：深度为深度为 k 的二叉树至多含的二叉树至多含 2k-1 个结点（个结点（k1）。）。证明：证明：基于上一条性质，深度为基于上一条性质，深度为 k

13、 的二叉树上的二叉树上的结点数至多为的结点数至多为 20+21+ +2k-1 = 2k-1 。数据结构数据结构 第六章第六章 树和二叉树树和二叉树 性质性质 3 ：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶个叶子结点、子结点、n2 个度为个度为 2 的结点，则必存的结点，则必存在关系式：在关系式：n0 = n2+1。证明：证明：设设 二叉树上结点总数二叉树上结点总数 n = n0 + n1 + n2又又 二叉树上分支总数二叉树上分支总数 b = n1+2n2 而而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。数据结构数据结构

14、第六章第六章 树和二叉树树和二叉树两类两类特殊特殊的二叉树：的二叉树：满二叉树：满二叉树：指的是指的是深度为深度为k且含有且含有2k-1个结点的二叉树。个结点的二叉树。123456789 10 11 12 13 14 15结点编号：结点编号：从上到下，从左到右按自然数从上到下，从左到右按自然数编号。编号。特点：特点：每一层上都有含有最大结点数每一层上都有含有最大结点数。数据结构数据结构 第六章第六章 树和二叉树树和二叉树两类两类特殊特殊的二叉树：的二叉树：完全二叉树：完全二叉树：深度为深度为k的的二叉树中所含的二叉树中所含的 n 个结点和深度为个结点和深度为k的满二叉树中的满二叉树中编号为编号

15、为 1 至至 n 的结点的结点一一对应。一一对应。abcdefghij数据结构数据结构 第六章第六章 树和二叉树树和二叉树完全二叉树特点：完全二叉树特点：abcdefghij&除最后一层外，每一层都取最大结点数，最后除最后一层外，每一层都取最大结点数，最后一层结点都集中且连续分布在该层最左边的若一层结点都集中且连续分布在该层最左边的若干位置。干位置。&叶子结点只可能在层次最大的两层出现。叶子结点只可能在层次最大的两层出现。&对任一结点，若其右分支下的子孙的最大层次对任一结点，若其右分支下的子孙的最大层次为为L，则其左分支下的子孙的最大层次为，则其左分支下的子孙的最大层次为L 或或L+1。满二叉

16、树必为完全二满二叉树必为完全二叉树，而完全二叉树叉树，而完全二叉树不一定是满二叉树！不一定是满二叉树！数据结构数据结构 第六章第六章 树和二叉树树和二叉树 具有具有 n 个结点的完全二叉树的深个结点的完全二叉树的深度为度为 log2n +1 。证明：设完全二叉树的深度为证明：设完全二叉树的深度为 k 则根据第二条性质得则根据第二条性质得 2k-1 -1 n 2k -1 则则 2k-1 n 2k 即即 k-1 log2 n n，则该结点无左孩子，否则，编号，则该结点无左孩子，否则，编号为为 2i 的结点为其的结点为其左孩子左孩子结点；结点；(1)若若 2i+1n，则该结点无右孩子结点，否则，则该

17、结点无右孩子结点，否则，编号为编号为2i+1 的结点为其的结点为其右孩子右孩子结点。结点。数据结构数据结构 第六章第六章 树和二叉树树和二叉树先证性质先证性质5之（之（2）、（）、（3），由此可反推），由此可反推出（出（1）。）。而（而（2）、（）、（3）可归结为：对于完全二叉）可归结为：对于完全二叉树的结点树的结点i，若其存在左孩，则该左孩必，若其存在左孩，则该左孩必为为 ，若存在右孩，则该右孩必，若存在右孩，则该右孩必为为 。nii22nii1212后续用归纳法证明性质（后续用归纳法证明性质（2）（）（3）性质性质5 的证明：的证明：数据结构数据结构 第六章第六章 树和二叉树树和二叉树归纳

18、基础：归纳基础：i = 1 时，成立；时，成立；归纳假设：归纳假设：假设对所有的假设对所有的m，1 m i+1，命题成立；，命题成立；归纳证明：归纳证明：分两种情况：分两种情况：(1) 设结点设结点i+1为第为第j层（层（ ）的）的第一个结点。第一个结点。(结点结点 i 和和 i1不在同一层不在同一层)(2) 设结点设结点i+1为第为第j层（层（ ）上）上的除第一个结点外的其他结点。的除第一个结点外的其他结点。(结点结点 i 和和 i1 在同一层在同一层)nj2log1nj2log1数据结构数据结构 第六章第六章 树和二叉树树和二叉树 j-1 j j+12j-1-12j-12j.k k-1 2

19、k 2k+1 k+1 2k+2 2k+32j-12j-2数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树的顺序存储二叉树的顺序存储二叉树的链式存储二叉树的链式存储二叉树的存储结构二叉树的存储结构数据结构数据结构 第六章第六章 树和二叉树树和二叉树所谓二叉树的顺序存储，就是用一所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左一般是按照二叉树结点从上至下、从左到右的顺序存储。到右的顺序存储。 1. 二叉树的顺序存储二叉树的顺序存储 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树的顺序存储表

20、示可描述为：二叉树的顺序存储表示可描述为：#define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点号单元存储根结点SqBiTree bt;即将即将 bt 定义为含有定义为含有MAX_TREE_SIZE个个 TElemType 类型元素的一维数组。类型元素的一维数组。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树A B C D E F G HIJ K L 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树完全二叉树J12345678910

21、1112EFHIKLABDCG数据结构数据结构 第六章第六章 树和二叉树树和二叉树一般二叉树一般二叉树12345711ABCEGFDA B C D EFG 1 2 3 4 5 6 7 8 9 10 11编号规则：编号规则：根结点的编号为根结点的编号为1；对于；对于编号为编号为i的结点，左孩子的结点，左孩子如果存在，则编号为如果存在，则编号为2i，右孩子如果存在则编号右孩子如果存在则编号为为2i+1。数据结构数据结构 第六章第六章 树和二叉树树和二叉树单支二叉树单支二叉树137ABCABCD 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15D15顺序存储只适用于完全二顺序存

22、储只适用于完全二叉树和满二叉树叉树和满二叉树在最坏情况下，深度为在最坏情况下，深度为 k 的右单支二叉树需要的右单支二叉树需要 2k- -1 个存储空间。个存储空间。数据结构数据结构 第六章第六章 树和二叉树树和二叉树 二叉链表二叉链表 三叉链表三叉链表2. 二叉树的链式存储二叉树的链式存储ACEFGBD数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉链表类型表述如下：二叉链表类型表述如下：typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 B

23、iTNode, *BiTree;结点结构结点结构:lchild data rchild数据结构数据结构 第六章第六章 树和二叉树树和二叉树AFDE root结点结构结点结构:二叉链表二叉链表lchild data rchildG CB ACEFGBD数据结构数据结构 第六章第六章 树和二叉树树和二叉树结论结论1：在含有在含有n个结点的二叉链表中有个结点的二叉链表中有n1个空链域。（提示：个空链域。（提示： n0 = n2+1 ）两个结论两个结论结论结论2：在含有在含有n个结点的度为个结点的度为k的树的树中必有中必有n(k-1)+1 个空链域。个空链域。 （结论（结论1的推广）的推广）数据结构数

24、据结构 第六章第六章 树和二叉树树和二叉树三叉链表类型表述如下：三叉链表类型表述如下：typedef struct TriTNode DataType data; struct TriTNode *parent; struct TriTNode *lchild; struct TriTNode *rchild; TriTNode, *TriTree; 结点结构结点结构:lchild data rchildparent数据结构数据结构 第六章第六章 树和二叉树树和二叉树AFDE root三叉链表三叉链表G CB ACEFGBD 结点结构结点结构:lchild data rchildparent数

25、据结构数据结构 第六章第六章 树和二叉树树和二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.3.1 遍历二叉树遍历二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树遍历：遍历：顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树中二叉树中的每个结点，使得每个结点均被的每个结点，使得每个结点均被访问一次访问一次，而且而且仅被访问一次仅被访问一次。“访问访问”的含义可以很广，如：输出结点的含义可以很广，如：输出结点的信息等。的信息等。1. 基本概念基本概念非线性非线性线性化线性化结点访问序列结点访问序列遍历遍历遍历目的遍历目的

26、数据结构数据结构 第六章第六章 树和二叉树树和二叉树 “二叉树二叉树”由三个基本单元组成：由三个基本单元组成：根结点、根结点、左子树和右子树左子树和右子树。若能依次遍历这三部分，就。若能依次遍历这三部分，就遍历了整个二叉树。遍历了整个二叉树。设用设用L、D、R分别表示遍历左子树、访分别表示遍历左子树、访问根结点、遍历右子树，则可有以下问根结点、遍历右子树，则可有以下 ? 种遍历种遍历二叉树的方案：二叉树的方案：DLR、LDR、LRDDRL、RDL、RLD先左后右先左后右先右后左先右后左6数据结构数据结构 第六章第六章 树和二叉树树和二叉树前前（根）序的遍历算法（根）序的遍历算法中中（根）序的遍

27、历算法（根）序的遍历算法后后（根）序的遍历算法（根）序的遍历算法2. 先左后右先左后右的遍历算法的遍历算法 DLR：LDR：LRD：数据结构数据结构 第六章第六章 树和二叉树树和二叉树ABCDEFG先序遍历结果：先序遍历结果：ABDGCEF 若二叉树为空树，则空操作；若二叉树为空树，则空操作； 否则否则:（1）D：访问根结点；访问根结点；（2）L：前序遍历前序遍历左子树；左子树；（3）R：前序遍历前序遍历右子树。右子树。2.1 前（根）序的遍历算法前（根）序的遍历算法A B D G C E F数据结构数据结构 第六章第六章 树和二叉树树和二叉树void preorder (NODE *p) /

28、 前序遍历二叉树前序遍历二叉树 if (p!=NULL) visit(p-data); preorder(p-lchild); preorder(p-rchild); 2.1前（根）序的遍历算法前（根）序的遍历算法printf(“%c”,p-data);数据结构数据结构 第六章第六章 树和二叉树树和二叉树ABCDEFG中序遍历结果：中序遍历结果：ABDGCEFABD GCEF 若二叉树为空树，则空操作；若二叉树为空树，则空操作； 否则否则:（1）L：中序遍历中序遍历左子树；左子树； （2）D：访问根结点；访问根结点；（3）R：中序遍历中序遍历右子树。右子树。2.2 中（根）序的遍历算法中（根）

29、序的遍历算法数据结构数据结构 第六章第六章 树和二叉树树和二叉树void inorder (NODE *p) / 中序遍历二叉树中序遍历二叉树 if (p!=NULL) inorder(p-lchild); visit(p-data); inorder(p-rchild); 2.2 中（根）序的遍历算法中（根）序的遍历算法printf(“%c”,p-data);数据结构数据结构 第六章第六章 树和二叉树树和二叉树ABCDEFG后序遍历结果：后序遍历结果：ABDGCEFABDGCE F若二叉树为空树，则空操作；若二叉树为空树，则空操作；否则否则:（1）L：后序遍历后序遍历左子树；左子树； （2）

30、R：后序遍历后序遍历右子树。右子树。（3）D：访问根结点；访问根结点；2.3 后（根）序的遍历算法后（根）序的遍历算法数据结构数据结构 第六章第六章 树和二叉树树和二叉树void postorder (NODE *p) / 后序遍历二叉树后序遍历二叉树 if (p!=NULL) postorder(p-lchild); postorder(p-rchild); visit(p-data); 2.3 后（根）序的遍历算法后（根）序的遍历算法printf(“%c”,p-data);数据结构数据结构 第六章第六章 树和二叉树树和二叉树三种遍历算法的比较三种遍历算法的比较void preorder (

31、NODE *p) / 前序遍历二叉树前序遍历二叉树 if (p!=NULL) visit(p-data); preorder(p-lchild); preorder(p-rchild); void inorder (NODE *p) / 中序遍历二叉树中序遍历二叉树 if (p!=NULL) inorder(p-lchild); visit(p-data); inorder(p-rchild); void postorder (NODE *p) / 后序遍历二叉树后序遍历二叉树 if (p!=NULL) postorder(p-lchild); postorder(p-rchild); vis

32、it(p-data); 语句都是一样的，语句都是一样的，只是顺序不同！只是顺序不同！数据结构数据结构 第六章第六章 树和二叉树树和二叉树进行前序、中序和后序遍历都是从根结点进行前序、中序和后序遍历都是从根结点A A开始的，开始的，且在遍历过程中且在遍历过程中经过结点的路线是一样的经过结点的路线是一样的，只是，只是访问的时访问的时机不同机不同而已。而已。数据结构数据结构 第六章第六章 树和二叉树树和二叉树如表达式：如表达式：a+b*(c-d)-e/f3. 表达式的二叉树表示表达式的二叉树表示-+/a*efcdb-先序序列：先序序列：中序序列：中序序列：后序序列：后序序列： + a * b c d

33、 / e fa + b * c d e / fa b c d* + e f / 前缀前缀(波兰式波兰式)中缀表示中缀表示后缀后缀(逆波兰式逆波兰式)数据结构数据结构 第六章第六章 树和二叉树树和二叉树4. 遍历算法的应用举例遍历算法的应用举例1）输出二叉树中的结点）输出二叉树中的结点(先序遍历先序遍历)2）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数 (先序遍历先序遍历)3）求二叉树的深度（）求二叉树的深度（后序遍历后序遍历）数据结构数据结构 第六章第六章 树和二叉树树和二叉树void Preorder (BiTree root) if (root!=NULL) visit(root

34、-data); Preorder(root-lchild); Preorder(root-rchild); 4.1 输出二叉树的结点输出二叉树的结点printf(root-data);数据结构数据结构 第六章第六章 树和二叉树树和二叉树4.2 统计二叉树中叶子结点的数目统计二叉树中叶子结点的数目算法基本思想算法基本思想: 先序先序(或中序或后序或中序或后序)遍历二叉树，在遍遍历二叉树，在遍历过程中查找叶子结点，并计数。历过程中查找叶子结点，并计数。 由此，由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数的参数，并将算法中，并将算法中“访问结点访问结点”的操作的操作改为：改为

35、：若是叶子，则计数器增若是叶子，则计数器增1。数据结构数据结构 第六章第六章 树和二叉树树和二叉树int LeafCount=0;void LeafNum(BiTree bt) /先序遍历先序遍历 if (bt!=NULL) visit(root-data); LeafNum(bt-LChild); LeafNum(bt-RChild); 4.2 统计二叉树中叶子结点的数目（统计二叉树中叶子结点的数目（算法一算法一）if(bt-LChild=NULL&bt-RChild=NULL)LeafCount+;数据结构数据结构 第六章第六章 树和二叉树树和二叉树int leaf (BiTree roo

36、t) int LeafCount2; if (root=NULL) LeafCount2 =0; else if(root-LChild=NULL)&(root-RChild=NULL) LeafCount2 =1; else LeafCount2= leaf(root-LChild)+leaf(root-RChild);/* 叶子数为左右子树的叶子数目之和叶子数为左右子树的叶子数目之和 */return LeafCount2;4.2 统计二叉树中叶子结点的数目（统计二叉树中叶子结点的数目（算法二算法二）数据结构数据结构 第六章第六章 树和二叉树树和二叉树4.3 求二叉树的深度（后序遍历）求二

37、叉树的深度（后序遍历）算法基本思想算法基本思想: 首先分析二叉树的深度和它的左、右子树首先分析二叉树的深度和它的左、右子树深度之间的关系。深度之间的关系。 从二叉树深度的定义可知，二叉树的深度从二叉树深度的定义可知，二叉树的深度应为其应为其左、右子树深度的最大值加左、右子树深度的最大值加1。 由此，需先分别求得左、右子树的深度，由此，需先分别求得左、右子树的深度，算法中算法中“访问结点访问结点”的操作为：求得左、右的操作为：求得左、右子树深度的最大值，然后加子树深度的最大值，然后加 1。数据结构数据结构 第六章第六章 树和二叉树树和二叉树int PostTreeDepth(BiTree bt)

38、 int hl,hr,max; if (bt!=NULL) hl=PostTreeDepth(bt-LChild); hr=PostTreeDepth(bt-RChild); max=hlhr?hl:hr; return(max+1); else return(0); /* 如果是空树，则返回如果是空树，则返回0 */4.3 求二叉树的高度（后序遍历）求二叉树的高度（后序遍历）数据结构数据结构 第六章第六章 树和二叉树树和二叉树5. 二叉树遍历的非递归实现二叉树遍历的非递归实现-中序遍历中序遍历首先回顾一下中序算法的递归描述。首先回顾一下中序算法的递归描述。数据结构数据结构 第六章第六章 树和

39、二叉树树和二叉树void Inorder (BiTree root) / 中序遍历二叉树中序遍历二叉树 if (root!=NULL) Inorder(root-lchild); /L:中序遍历左子树中序遍历左子树 visit(root-data); /D:访问根结点访问根结点 Inorder(root-rchild); /R:中序遍历右子树中序遍历右子树 中序算法的递归描述中序算法的递归描述abcdeT中序序列：中序序列： dbac e数据结构数据结构 第六章第六章 树和二叉树树和二叉树算法算法6.26.2的思路：的思路：（1 1）指向根结点的指针进栈；）指向根结点的指针进栈；（2 2）栈顶

40、指针非空则其左孩子指针进栈；直到栈顶指）栈顶指针非空则其左孩子指针进栈；直到栈顶指针为空；针为空；（3 3）弹出栈顶空指针，若栈非空，再弹出栈顶指针并）弹出栈顶空指针，若栈非空，再弹出栈顶指针并访问该指针指向的结点；该指针指向结点的右孩子指针访问该指针指向的结点；该指针指向结点的右孩子指针入栈；入栈；（4 4）继续第（）继续第（2 2）步的操作，直到栈为空。）步的操作，直到栈为空。 5. 二叉树遍历的非递归实现二叉树遍历的非递归实现-中序遍历中序遍历数据结构数据结构 第六章第六章 树和二叉树树和二叉树Status InOrderTraverse(BiTree T, Status (*Visit

41、)(ElemType) InitStack(S); Push(S, T); / 根指针进栈根指针进栈while (!StackEmpty(S) / 向左走到尽头向左走到尽头while (GetTop(S, p) & p) Push(S, p-lchild); Pop(S, p); / 空指针退栈空指针退栈if (!StackEmpty(S) / 访问结点，向右一步访问结点，向右一步Pop(S, p); if (!Visit(p-data) return ERROR;Push(S, p-rchild);return OK; / InOrderTraverse算法算法6.2 中序遍历二叉树中序遍历

42、二叉树T的非递归算法的非递归算法数据结构数据结构 第六章第六章 树和二叉树树和二叉树算法算法6.3的思路：的思路：（1）指向根结点的指针非空则进栈；）指向根结点的指针非空则进栈；（2）栈顶的指针的左孩子指针非空则进栈；直到栈顶指）栈顶的指针的左孩子指针非空则进栈；直到栈顶指针左孩子指针为空；针左孩子指针为空；（3）若栈非空，弹出栈顶指针并访问该指针指向的结点；）若栈非空，弹出栈顶指针并访问该指针指向的结点；该指针指向结点的右孩子指针若非空则入栈；该指针指向结点的右孩子指针若非空则入栈；（4）继续第（）继续第（2）步的操作，直到栈为空。）步的操作，直到栈为空。与算法与算法6.2没有质的区别，只是

43、没有质的区别，只是6.3在指针非空入栈，在指针非空入栈，6.2是入栈后判断其是否非空是入栈后判断其是否非空5. 二叉树遍历的非递归实现二叉树遍历的非递归实现-中序遍历中序遍历数据结构数据结构 第六章第六章 树和二叉树树和二叉树Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) InitStack(S); p = T; while (p | !StackEmpty(S) / 非空指针进栈，继续左进非空指针进栈，继续左进 if (p) Push(S, p); p = p-lchild; else / 指针退栈，访问其所指结点，再向右

44、进指针退栈，访问其所指结点，再向右进 Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse算法算法6.3 中序遍历二叉树中序遍历二叉树T的非递归算法的非递归算法数据结构数据结构 第六章第六章 树和二叉树树和二叉树所谓所谓二叉树的层次遍历二叉树的层次遍历，是指从二叉树的第一层（根，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。到右的顺序对结点逐个访问。 在进行在进行层次遍历层

45、次遍历时，可设置一个时，可设置一个队列结构队列结构，遍历从二，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：头取出一个元素，每取一个元素，执行下面两个操作：6. 二叉树的层次遍历二叉树的层次遍历（1 1）访问该元素所指结点；访问该元素所指结点；（2 2）若该元素所指结点的左、右孩子结点非空，则将该元素若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。此过

46、程不断进行，当队列为空时，二叉树的层次遍历结束。 层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头树根结点A入队层次层次遍历序列:层次遍历层次遍历GFCDAB队列队头A层序层序遍历序列:A出队n先根，后子树；先左子树，后右子树层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头根结点B、C入队A的子树层序层序遍历序列: A层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头BB出队C层序层序遍历序列: A层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头C根结点入队B的子树层序层序遍历序列: AB层次遍历层次遍历n先

47、根，后子树；先左子树，后右子树GFCDAB队列队头CC出队层序层序遍历序列: AB层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头根结点入队C的子树层序层序遍历序列: ABC层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头DED出队层序层序遍历序列: ABC层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头E根结点入队D的子树层序层序遍历序列: ABCD层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头EE出队层序层序遍历序列: ABCD层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头根结

48、点F、G入队E的子树层序层序遍历序列: ABCDE层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头FGF出队层序层序遍历序列: ABCDE层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头G根结点入队F的子树层序层序遍历序列: ABCDEF层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头GG出队层序层序遍历序列: ABCDEF层次遍历层次遍历n先根，后子树；先左子树，后右子树GFCDAB队列队头根结点入队G的子树层序层序遍历序列: ABCDEFG数据结构数据结构 第六章第六章 树和二叉树树和二叉树void LevelOrder（B

49、iTree bt） BiTree QueueMAXNODE; /一维数组用以实现队列一维数组用以实现队列 int front,rear; /队首元素和队尾元素队首元素和队尾元素 if (bt = = NULL) return; front= -1; rear=0; queuerear= bt; while(front!=rear) front+; Visit ( queuefront-data ); /*访问队首结点的数据域访问队首结点的数据域*/ if (queuefront-lchild!=NULL) /*左孩子结点入队左孩子结点入队*/ rear+; queuerear= queuefr

50、ont-lchild; if (queuefront-rchild!=NULL) /*右孩子结点入队列右孩子结点入队列*/ rear+; queuerear=queuefront-rchild; 层次遍历二叉树层次遍历二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树7.1 由结点序列恢复二叉树由结点序列恢复二叉树在对一棵二叉树进行遍历，只要遍在对一棵二叉树进行遍历，只要遍历的策略已确定，就可以得到一个唯一历的策略已确定，就可以得到一个唯一的结点序列。的结点序列。那么，给定一个遍历的结点序列，那么，给定一个遍历的结点序列，能否唯一的确定一棵二叉树？能否唯一的确定一棵二叉树？答案：答案：

51、不能！不能！7. 建立二叉树建立二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树先序序列：先序序列：A B C结点序列确定二叉树的不唯一性结点序列确定二叉树的不唯一性ABCABCABCABC数据结构数据结构 第六章第六章 树和二叉树树和二叉树关于二叉树的先序、中序和后序遍历序列确定二叉树关于二叉树的先序、中序和后序遍历序列确定二叉树的问题。的问题。l任何任何n(n0)个不同结点的二又树个不同结点的二又树,都可由它的都可由它的中序中序序序列和列和先序先序序列唯一地确定。序列唯一地确定。证明：证明：先序序列是先序序列是a1a2an中序序列是中序序列是b1b2bn根结点：根结点：a1。在中

52、序序列中与在中序序列中与a1相同的结点为：相同的结点为：bj。 b1bj-1bjbj+1bn a1a2akak+1an数据结构数据结构 第六章第六章 树和二叉树树和二叉树l任何任何n(n0)个不同结点的二又树个不同结点的二又树,都可由它的都可由它的中序中序序序列和列和后序后序序列唯一地确定。序列唯一地确定。证明：证明：后序序列是后序序列是a1a2an中序序列是中序序列是b1b2bn根结点：根结点：an。在中序序列中与在中序序列中与an相同的结点为：相同的结点为：bj。 b1bj-1bjbj+1bn a1a2akak+1an-1an数据结构数据结构 第六章第六章 树和二叉树树和二叉树由结点序列恢

53、复二叉树由结点序列恢复二叉树可可恢复二叉树的结点序列组合：恢复二叉树的结点序列组合：（1）先序先序序列和序列和中序中序序列序列（2）中序中序序列和序列和后序后序序列序列不可不可恢复二叉树的结点序列组合：恢复二叉树的结点序列组合：先序先序序列和序列和后序后序序列序列数据结构数据结构 第六章第六章 树和二叉树树和二叉树由由先序先序和和中序中序序列恢复二叉树序列恢复二叉树二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根数据结构数据结构 第六章第六章 树和二叉树树和二叉树由由先序先序和和中序中序序列恢复二叉树序列恢复二叉树举例举

54、例先序序列：先序序列：A B C D E F G中序序列：中序序列：C B D A E G F左子树左子树右子树右子树ABCDEFGACB C D E F GB D A E G F数据结构数据结构 第六章第六章 树和二叉树树和二叉树7.2 由扩展的结点序列恢复二叉树由扩展的结点序列恢复二叉树在前面讲述的结点序列中，我们忽略在前面讲述的结点序列中，我们忽略了空子树的输出。假如了空子树的输出。假如在遍历二叉树时，在遍历二叉树时，我们使用某个特定的符号表示空子树，则我们使用某个特定的符号表示空子树，则称得到的序列为扩展的结点序列称得到的序列为扩展的结点序列。如：。如：扩展的先序序列：扩展的先序序列：

55、AB # C # # DE # # #ADBEC数据结构数据结构 第六章第六章 树和二叉树树和二叉树建立一棵二叉树建立一棵二叉树算法基本思想算法基本思想: :首先首先读入当前根结点数据，读入当前根结点数据，如果是如果是，则表示当前树根置为空，则表示当前树根置为空，否则否则申请申请一个新结点一个新结点，存入当前根结点的数据，存入当前根结点的数据，分别分别用当前根结点的左子域和右子域进用当前根结点的左子域和右子域进行递归调用，行递归调用，创建左、右子树创建左、右子树。数据结构数据结构 第六章第六章 树和二叉树树和二叉树BiTree CreateBiTree() char ch; BiTreeNod

56、e *p; ch=getchar(); if (ch=#) return NULL; else p=(BiTreeNode *) malloc(sizeof(BiTreeNode); p-data=ch; p-LChild=CreateBiTree(); p-RChild=CreateBiTree(); return (p); 创建二叉树创建二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.3.2 线索二叉树线索二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树 在具有在具有 N N 个结点的二叉树中，有个结点的二叉树中，有 N+1N+1个是空指个是空指针域针域，这些空指针

57、域可以用来存放结点的前驱和，这些空指针域可以用来存放结点的前驱和后继；后继；即用左指针域存放其前驱，用右指针域存即用左指针域存放其前驱，用右指针域存放其后继放其后继。在二叉链表的结点中增加两个标志，在二叉链表的结点中增加两个标志，用以区别是用以区别是孩子指针孩子指针还是还是前驱或后继指针前驱或后继指针。结点的结构为：结点的结构为： lchildLTagdataRTagrchild0 lchild域指示结点的左孩子域指示结点的左孩子lchild域指示结点的遍历前驱域指示结点的遍历前驱0 rchild域指示结点的右孩子域指示结点的右孩子1 rchild域指示结点的遍历后继域指示结点的遍历后继 LT

58、ag=RTag=数据结构数据结构 第六章第六章 树和二叉树树和二叉树以上述结点结构构成的二叉链表作为二以上述结点结构构成的二叉链表作为二叉树的存储结构，叫做叉树的存储结构，叫做线索链表线索链表。指向前驱。指向前驱和后继的指针叫和后继的指针叫线索线索。具有线索的二叉树称。具有线索的二叉树称为为线索二叉树线索二叉树。对二叉树以某种次序遍历使。对二叉树以某种次序遍历使其变为线索二叉树的过程称其变为线索二叉树的过程称线索化线索化。数据结构数据结构 第六章第六章 树和二叉树树和二叉树ABCDEFGH(a) 二叉 树ABCDEFGH(b )先序线索二叉 树ACDEFGH(c) 中序线索二叉树ABCDEFG

59、H(d ) 后序线索二叉 树BN U LLN U LLN U LLN U LLABDGCEHFDGBAEHCFGDBHEFCA数据结构数据结构 第六章第六章 树和二叉树树和二叉树typedef enum PointerTag Link,Thread;typedef struct BiThrNode TElemType data; PointerTag LTag,RTag; struct BiThrNode *lchild,*rchild; BiThrNode , *BiThrTree ; 二叉树的二叉线索存储表示二叉树的二叉线索存储表示数据结构数据结构 第六章第六章 树和二叉树树和二叉树线索化

60、的思路线索化的思路对二叉树线索化，对二叉树线索化，实质上就是遍历一棵二叉树实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，结点或后继结点的线索。为实现这一过程，设指针设指针prepre始终指向刚刚访问过的结点，即若指针始终指向刚刚访问过的结点，即若指针p p指向当前结点，指向当前结点，则则prepre指向它的前驱指向它的前驱，以便增设线索。，以便增设线索。 数据结构数据结构 第六章第六章 树和