第6章 树和二叉树

1、第第6章章 树和二叉树树和二叉树 6.1 树的有关概念树的有关概念 6.1 树的有关概念树的有关概念 一树的应用一树的应用 学生档案管理的组织方式学生档案管理的组织方式 组织机构图、家谱图、编译中的语法树等组织机构图、家谱图、编译中的语法树等 doswindows文件系统文件系统 6.1 树的有关概念树的有关概念 二树的定义二树的定义 树树是是n(n0)个结点的有限集合，当个结点的有限集合，当n=0时，集合为时，集合为 空集，称为空集，称为空树空树；在任意一棵非空树；在任意一棵非空树 t 中：有且仅中：有且仅 有一个称为根有一个称为根(root)的结点；当的结点；当 n1 时，除根结点外时，除

2、根结点外 的其余结点可分成的其余结点可分成 m(m0) 个互不相交的有限个互不相交的有限 t1、t2 、tm 集合，其中每一个集合本身又是一棵树，集合，其中每一个集合本身又是一棵树， 并称其为根的并称其为根的子树子树。 6.1 树的有关概念树的有关概念 ji a cbd hgfe klm a 只有根结点的树只有根结点的树 树的一般表示树的一般表示 6.1 树的有关概念树的有关概念 例如树例如树 t 如对于根如对于根a，其余结点可分为，其余结点可分为3个互不相交的集合：个互不相交的集合： t1=b, e, f, k,l，t2=c, g，t3=d, h, i, j, m， 其中的每一集合都本身又是

3、一棵树，称为根其中的每一集合都本身又是一棵树，称为根a的子树。的子树。 6.1 树的有关概念树的有关概念 ji a cbd hgfe klm 在树中：在树中： 只有根结点没有前驱；只有根结点没有前驱； 除根外，其余结点均有且仅一个前驱；除根外，其余结点均有且仅一个前驱； 结点可以有结点可以有0个或多个后继；个或多个后继； 其余结点均只有唯一条从根到该结点的路径。其余结点均只有唯一条从根到该结点的路径。 6.1 树的有关概念树的有关概念 ji a cbd hgfe klm 根：没有前驱的结点；根：没有前驱的结点； 结点：包含一个数据元素及若干指向其子树的分支；结点：包含一个数据元素及若干指向其子

4、树的分支； 双亲与孩子：结点的子树的根称为该结点的孩子，双亲与孩子：结点的子树的根称为该结点的孩子， 该结点称为孩子的双亲；该结点称为孩子的双亲； 兄弟：同一双亲的孩子之间称为兄弟；兄弟：同一双亲的孩子之间称为兄弟； 祖先：从根到该结点所经分支上的所有结点；祖先：从根到该结点所经分支上的所有结点； 子孙：以某结点为根的子树中的任一结点称为其子孙；子孙：以某结点为根的子树中的任一结点称为其子孙； 堂兄弟：其双亲在同一层的结点；堂兄弟：其双亲在同一层的结点； 三树的基本术语三树的基本术语 6.1 树的有关概念树的有关概念 ji a cbd hgfe klm 三树的基本术语三树的基本术语 结点的层次

5、：根为第一层，根的孩子为第二层结点的层次：根为第一层，根的孩子为第二层； 树的深度：树中结点的最大层次；树的深度：树中结点的最大层次； 结点的度：结点拥有的子树数；结点的度：结点拥有的子树数； 叶结点：度为叶结点：度为 0 的结点；的结点； 分支结点：度不为分支结点：度不为0的结点；的结点； 树的度：树中各结点的度的最大值；树的度：树中各结点的度的最大值； 6.1 树的有关概念树的有关概念 ji a cbd hgfe klm 三树的基本术语三树的基本术语 有序树：将树中各子树看成有次序的，称为有序树；有序树：将树中各子树看成有次序的，称为有序树； 否则称为无序树；否则称为无序树； 森林：森林：

6、m(m0) 棵互不相交的树的集合。棵互不相交的树的集合。 对树中每个节点而言，其子树的集合即为森林。对树中每个节点而言，其子树的集合即为森林。 6.1 树的有关概念树的有关概念 ji a cbd hgfe klm 第第6章章 树和二叉树树和二叉树 6.2 二叉树二叉树 6.2 二叉树二叉树 (binary tree) 一、二叉树的基本概念一、二叉树的基本概念 1. 二叉树的定义二叉树的定义 二叉树的特点是树中每个结点至多只有二棵子树，二叉树的特点是树中每个结点至多只有二棵子树， 并且二叉树的子树有左右之分，其次序不能颠倒。并且二叉树的子树有左右之分，其次序不能颠倒。 a a f f g g e

7、 e d d c c b b 说明：说明： 二叉树中结点的度二叉树中结点的度 2； 子树有左右之分子树有左右之分有序树；有序树； a a f f g g e e d d c c b b (a) 左子树有四个结点左子树有四个结点 (b) 左子树有两个结点左子树有两个结点 (a) a a g g e e d d b b c c f f (b) 6.2 二叉树二叉树 (binary tree) 2. 二叉树的基本形态二叉树的基本形态 二叉树有五种基本形态：二叉树有五种基本形态： (1)(2)(3) (4)(5) 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性质性质

8、 1 在二叉树的第在二叉树的第 i 层上至多层上至多 2i-1 个结点个结点 ( i0 ) 用数学归纳法证明：用数学归纳法证明： 当当i=1时，时，2i-1=20 =1 ，成立；，成立； 设设 i=k 时，命题成立，即第时，命题成立，即第 k 层上至多有层上至多有2k-1个结点；个结点； 因为二叉树每个结点的度因为二叉树每个结点的度2，故在第，故在第 k+1 层上最大结层上最大结 点数为第点数为第 k 层上最大结点数的层上最大结点数的2倍，即为倍，即为22k-12(k+1)-1 。 命题得到证明。命题得到证明。 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性

9、质性质 2 深度为深度为 k 的二叉树最多有的二叉树最多有 2k-1 个结点个结点( i1 ) 深度为深度为 k 的二叉树的最大结点数为：的二叉树的最大结点数为： = (第第1层的层的) + (第第2层的层的) + + (第第k层的层的) = 21-1 + 22-1 + 23-1 + + 2k-1 = 20 + 21 + 22 + + 2k-1 = 2k-1 11111111 87654321 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性质性质 3 对任何一棵二叉树，如果其叶结点数为对任何一棵二叉树，如果其叶结点数为 n0 ， 度为度为 2 的结点数为的结

10、点数为 n2 ，则，则 n0 = n2 + 1 设度为设度为1的结点数为的结点数为 n1 。 由于二叉树中所有结点的度由于二叉树中所有结点的度2，则结点总数为：，则结点总数为： n = n0 + n1 + n2 . (6-1) 二叉树中除根结点外，其余结点均有一个分支进入，二叉树中除根结点外，其余结点均有一个分支进入， 则结点总数则结点总数 n = (分支数分支数) + 1，而所有分支都是由度为，而所有分支都是由度为1和和2 的结点发出的，所以的结点发出的，所以 (分支数分支数) = n1+2*n2，从而有：，从而有： n=n1 + 2n2 + 1 . (6-2) 由式由式(6-1)和和(6-

11、2)得：得：n0 + n1 + n2 = n1 + 2*n2 + 1 n0n2 + 1 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性质性质 3 对任何一棵二叉树，如果其叶结点数为对任何一棵二叉树，如果其叶结点数为 n0 ， 度为度为 2 的结点数为的结点数为 n2 ，则，则 n0 = n2 + 1 6.2 二叉树二叉树 (binary tree) 两种特殊形态的二叉树两种特殊形态的二叉树 满二叉树满二叉树：一棵深度为：一棵深度为 k 且有且有2k-1个结点的二叉树个结点的二叉树 称为满二叉树。称为满二叉树。 特点：每一层上结点的个数都是最大结点数。特点：每

12、一层上结点的个数都是最大结点数。 6.2 二叉树二叉树 (binary tree) 两种特殊形态的二叉树两种特殊形态的二叉树 完全二叉树完全二叉树：深度为：深度为k有有n个结点的二叉树，当且仅个结点的二叉树，当且仅 当其每一个结点都与深度为当其每一个结点都与深度为k的满二叉的满二叉 树中编号从树中编号从 1 至至 n 的结点一一对应时，的结点一一对应时， 称之为完全二叉树。称之为完全二叉树。 6.2 二叉树二叉树 (binary tree) 两种特殊形态的二叉树两种特殊形态的二叉树 1 67 45 23 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性质性质

13、4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 2 1log n 设其深度为设其深度为 k ，则：，则： 2k-1-1n2k-1 2k-1n2k k-1log2nk 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性质性质 5 如果对一棵有如果对一棵有n个结点的个结点的完全二叉树完全二叉树的结点按层次的结点按层次 从左到右进行编号，则对任一结点从左到右进行编号，则对任一结点 i ( 1 i n )： 如果如果 i=1，则结点，则结点 i 为二叉树的根，无双亲；为二叉树的根，无双亲； 如果如果 i1，则结点，则结点 i 的双亲是结点的双亲是结点

14、 。2 / i i i/2 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性质性质 5 如果对一棵有如果对一棵有n个结点的个结点的完全二叉树完全二叉树的结点按层次的结点按层次 从左到右进行编号，则对任一结点从左到右进行编号，则对任一结点 i ( 1 i n )： 如果如果 2in，则结点，则结点 i 的左孩子为的左孩子为 2i； 否则结点否则结点 i 无左孩子。无左孩子。 2i i 6.2 二叉树二叉树 (binary tree) 二、二叉树性质二、二叉树性质 性质性质 5 如果对一棵有如果对一棵有n个结点的个结点的完全二叉树完全二叉树的结点按层次的结点按层次

15、 从左到右进行编号，则对任一结点从左到右进行编号，则对任一结点 i ( 1 i n )： 如果如果 2i+1n，则结点，则结点 i 的右孩子为的右孩子为 2i+1； 否则结点否则结点 i 无右孩子。无右孩子。 2i i 2i+1 6.2 二叉树二叉树 (binary tree) 1 2 j i 1 2112 22() jj i 1 21 j 结点数为结点数为 j 层层 j+1层层 j-1 层层 6.2 二叉树二叉树 (binary tree) 1 2 j i 1 2112 22() jj i 1 21 j 结点数为结点数为 j 层层 j+1层层 j-1 层层 ) 1(2i1) 1(2i 6.2

16、 二叉树二叉树 (binary tree) 结点结点 i 和和 i+1 在同一层上在同一层上 6.2 二叉树二叉树 (binary tree) 结点结点 i 和和 i+1不在同一层上不在同一层上 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 1. 顺序存储结构顺序存储结构 struct bt elemtype btmaxsize; int btnum; 将完全二叉树上编号为将完全二叉树上编号为 i 的结点元素存储在一维数的结点元素存储在一维数 组中下标为组中下标为 i 的位置上，即的位置上，即 bti。 完全二叉树完全二叉树 编号为编号为 i 的结

17、点存储在的结点存储在 bti 中中 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 1. 顺序存储结构顺序存储结构 对于一个一般的二叉树，将其对于一个一般的二叉树，将其“转化转化”为为完全二完全二 叉树叉树后，按照完全二叉树的顺序存储方式将结点存入后，按照完全二叉树的顺序存储方式将结点存入 到数组中。到数组中。 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 1. 顺序存储结构顺序存储结构 转化方法：在非完全二叉树的转化方法：在非完全二叉树的“残缺残缺”位置上增位置上增 设设“虚结点虚结点” 。 对于一个一

18、般的二叉树，将其对于一个一般的二叉树，将其“转化转化”为为完全二完全二 叉树叉树后，按照完全二叉树的顺序存储方式将结点存入后，按照完全二叉树的顺序存储方式将结点存入 到数组中。到数组中。 非完全二叉树非完全二叉树 非完全二叉树非完全二叉树 增设增设“虚结点虚结点” 非完全二叉树非完全二叉树 按照完全二叉树顺序存储按照完全二叉树顺序存储 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 1. 顺序存储结构顺序存储结构 struct bt elemtype btmaxsize; int btnum; 顺序存储结构仅适用于顺序存储结构仅适用于完全二叉树完全二

19、叉树，对于，对于 非完全二叉树会有较大的存储空间的浪费。非完全二叉树会有较大的存储空间的浪费。 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 2. 链式存储结构链式存储结构 二叉树的链式存储结构通常有二叉树的链式存储结构通常有二叉链表二叉链表 和和三叉链表三叉链表两种形式。两种形式。 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 2. 链式存储结构链式存储结构 struct btnode elemtype data; struct btnode *lchild, *rchild; ; 二叉链表二叉链表

20、6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 2. 链式存储结构链式存储结构 struct btnode elemtype data; struct btnode *lchild, *rchild, *parent; ; 三叉链表三叉链表 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 2. 链式存储结构链式存储结构 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 2. 链式存储结构链式存储结构 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储

21、结构三、二叉树的存储结构 2. 链式存储结构链式存储结构 6.2 二叉树二叉树 (binary tree) 三、二叉树的存储结构三、二叉树的存储结构 2. 链式存储结构链式存储结构 第第6章章 树和二叉树树和二叉树 6.3 遍历二叉树遍历二叉树 6.3 遍历二叉树遍历二叉树 遍历二叉树遍历二叉树 按照某条搜索路径访问树中的某个结点，使得树按照某条搜索路径访问树中的某个结点，使得树 中每个结点均被中每个结点均被访问一次访问一次，而且，而且仅被访问一次仅被访问一次。 6.3 遍历二叉树遍历二叉树 遍历二叉树遍历二叉树 按某种规律周游二叉树，对树中的每个结点访问按某种规律周游二叉树，对树中的每个结点

22、访问 一次且仅访问一次。一次且仅访问一次。 按照某条搜索路径访问树中的某个结点，使得树按照某条搜索路径访问树中的某个结点，使得树 中每个结点均被中每个结点均被访问一次访问一次，而且，而且仅被访问一次仅被访问一次。 6.3 遍历二叉树遍历二叉树 二叉树是由二叉树是由根结点根结点、左子树左子树、右子树右子树三三 个基本单元组成。个基本单元组成。 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 6.3 遍历二叉树遍历二叉树 二叉树是由二叉树是由根结点根结点、左子树左子树、右子树右子树三三 个基本单元组成。个基本单元组成。 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 遍历二叉树就是依次遍历这三

23、部分。遍历二叉树就是依次遍历这三部分。 6.3 遍历二叉树遍历二叉树 二叉树是由二叉树是由根结点根结点、左子树左子树、右子树右子树三三 个基本单元组成。个基本单元组成。 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 根据遍历二叉树的顺序不同，有三种遍根据遍历二叉树的顺序不同，有三种遍 历方法：历方法：先序先序(根根)遍历（遍历（dlr） 中序中序(根根)遍历（遍历（ldr） 后序后序(根根)遍历（遍历（lrd） d表示访问根结点表示访问根结点 l表示遍历左子树表示遍历左子树 r表示遍历右子树表示遍历右子树 遍历二叉树就是依次遍历这三部分。遍历二叉树就是依次遍历这三部分。 6.3 遍历二叉树

24、遍历二叉树 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 先序遍历序列：先序遍历序列： 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍

25、历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 先序遍历序列：先序遍历序列：a 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 先序遍历序列：先序遍历序列：a b 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。 6.3 遍历二叉

26、树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 先序遍历序列：先序遍历序列：a b d 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 先序遍历序列：先序遍历序列：a b d e 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树

27、。先序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 先序遍历序列：先序遍历序列：a b d e c 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 1. 先序先序(根根)遍历（遍历（dlr） 先序遍历序列：先序遍历序列：a b d e c f 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 访问根结点；访问根结点

28、； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。 6.3 遍历二叉树遍历二叉树 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列： 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根

29、结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列：d 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列：d b 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序

30、遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列：d b e 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列：d b e a 若二叉树为空，则空操作；否则若二叉树为空，

31、则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列：d b e a f 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列：d b e a

32、 f g 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 2. 中序中序(根根)遍历（遍历（ldr） 中序遍历序列：中序遍历序列：d b e a f g c 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 6.3 遍历二叉树遍历二叉树 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后

33、序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 3. 后序后序(根根)遍历（遍历（lrd） 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 3. 后序后序(根根)遍历（遍历（lrd） 后序遍历序列：后序遍历序列： 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 后序遍历序列：后序遍历序列：d 3. 后序后

34、序(根根)遍历（遍历（lrd） 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 后序遍历序列：后序遍历序列：d e 3. 后序后序(根根)遍历（遍历（lrd） 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 后序遍历序列：后序遍历序

35、列：d e b 3. 后序后序(根根)遍历（遍历（lrd） 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 后序遍历序列：后序遍历序列：d e b g 3. 后序后序(根根)遍历（遍历（lrd） 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树

36、的操作定义 后序遍历序列：后序遍历序列：d e b g f 3. 后序后序(根根)遍历（遍历（lrd） 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 后序遍历序列：后序遍历序列：d e b g f c 3. 后序后序(根根)遍历（遍历（lrd） 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉

37、树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 后序遍历序列：后序遍历序列：d e b g f c a 3. 后序后序(根根)遍历（遍历（lrd） 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历： 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- 中序遍历：中序遍历： 后

38、序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操

39、作定义 先序遍历：先序遍历：- + a * b 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d 中序遍

40、历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e 中序遍历：中序遍历： 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历： 后

41、序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a

42、 + b 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d

43、 / e f 中序遍历：中序遍历：a + b * c - 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、

44、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d

45、 - e / f 后序遍历：后序遍历： 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历

46、二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c d 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序

47、遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c d - 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c d - * 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c

48、 d - * + 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c d - * + e 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c d - * + e f 例：例： 6.3 遍历二叉树遍历二叉树

49、 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c d - * + e f / 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 先序遍历：先序遍历：- + a * b - c d / e f 中序遍历：中序遍历：a + b * c - d - e / f 后序遍历：后序遍历：a b c d - * + e f / - 例：例： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树

50、的操作定义 思考题：思考题： 先序遍历序列：先序遍历序列：1 2 4 5 3 6 7 中序遍历序列：中序遍历序列：4 2 5 1 6 7 3 请画出该二叉树请画出该二叉树 二叉树的遍历如下：二叉树的遍历如下： 6.3 遍历二叉树遍历二叉树 一、遍历二叉树的操作定义一、遍历二叉树的操作定义 思考题：思考题： 先序遍历序列：先序遍历序列：1 2 4 5 3 6 7 中序遍历序列：中序遍历序列：4 2 5 1 6 7 3 请画出该二叉树请画出该二叉树 二叉树的遍历如下：二叉树的遍历如下： struct btnode elemtype data; struct btnode *lchild, *rch

51、ild; ; 二叉链表的存储表示二叉链表的存储表示 二、遍历二叉树的递归算法二、遍历二叉树的递归算法 6.3 遍历二叉树遍历二叉树 回顾：回顾： 二、遍历二叉树的递归算法二、遍历二叉树的递归算法 6.3 遍历二叉树遍历二叉树 回顾：回顾： 6.3 遍历二叉树遍历二叉树 二、遍历二叉树的递归算法二、遍历二叉树的递归算法 void preorder ( struct btnode *root ) if ( root != null ) printf ( %c, root-data )； preorder ( root-lchild ); preorder ( root-rchild ); 1. 先

52、序遍历递归算法先序遍历递归算法 6.3 遍历二叉树遍历二叉树 二、遍历二叉树的递归算法二、遍历二叉树的递归算法 void inorder ( struct btnode *root ) if ( root != null ) inorder ( root-lchild ); printf ( %c , root-data ); inorder ( root-rchild ); 2. 中序遍历递归算法中序遍历递归算法 6.3 遍历二叉树遍历二叉树 二、遍历二叉树的递归算法二、遍历二叉树的递归算法 void postorder ( struct btnode *root ) if ( root !

53、= null ) postorder ( root-lchild ); postorder ( root-rchild ); printf ( %c , root-data ); 3. 后序遍历递归算法后序遍历递归算法 6.3 遍历二叉树遍历二叉树 三、遍历二叉树的非递归算法三、遍历二叉树的非递归算法 递归算法相对简明直观，清晰易懂，容易写递归算法相对简明直观，清晰易懂，容易写 出，但其效率较低，相比之下，非递归算法执出，但其效率较低，相比之下，非递归算法执 行效率更高。行效率更高。 基本思路基本思路：栈：栈 s 保存已访问过的结点；指针保存已访问过的结点；指针 p=root； 如果栈如果栈

54、s 非空或非空或 p 非空，做如下操作：非空，做如下操作： 6.3 遍历二叉树遍历二叉树 三、遍历二叉树的非递归算法三、遍历二叉树的非递归算法 1. 先序遍历非递归算法先序遍历非递归算法 基本思路基本思路：栈：栈 s 保存已访问过的结点；指针保存已访问过的结点；指针 p=root； 如果栈如果栈 s 非空或非空或 p 非空，做如下操作：非空，做如下操作： 6.3 遍历二叉树遍历二叉树 三、遍历二叉树的非递归算法三、遍历二叉树的非递归算法 1. 先序遍历非递归算法先序遍历非递归算法 若若 p 非空，则访问根结点，非空，则访问根结点，p 进栈；进栈； 令令 p 指向该结点的左子树的根，继续遍历；指

55、向该结点的左子树的根，继续遍历； 基本思路基本思路：栈：栈 s 保存已访问过的结点；指针保存已访问过的结点；指针 p=root； 如果栈如果栈 s 非空或非空或 p 非空，做如下操作：非空，做如下操作： 6.3 遍历二叉树遍历二叉树 三、遍历二叉树的非递归算法三、遍历二叉树的非递归算法 1. 先序遍历非递归算法先序遍历非递归算法 若若 p 为空，应返回到上层结点：为空，应返回到上层结点： (i) 若从左子树返回，将若从左子树返回，将 p 指向当前结点的指向当前结点的 右子树的根，继续遍历；右子树的根，继续遍历； (ii)若从右子树返回，继续出栈；若从右子树返回，继续出栈； 若若 p 非空，则访

56、问根结点，非空，则访问根结点，p 进栈；进栈； 令令 p 指向该结点的左子树的根，继续遍历；指向该结点的左子树的根，继续遍历； 基本思路基本思路：栈：栈 s 保存已访问过的结点；指针保存已访问过的结点；指针 p=root； 如果栈如果栈 s 非空或非空或 p 非空，做如下操作：非空，做如下操作： 6.3 遍历二叉树遍历二叉树 三、遍历二叉树的非递归算法三、遍历二叉树的非递归算法 1. 先序遍历非递归算法先序遍历非递归算法 如果栈如果栈 s 空且空且 p 空，则遍历结束。空，则遍历结束。 若若 p 为空，应返回到上层结点：为空，应返回到上层结点： (i) 若从左子树返回，将若从左子树返回，将 p

57、 指向当前结点的指向当前结点的 右子树的根，继续遍历；右子树的根，继续遍历； (ii)若从右子树返回，继续出栈；若从右子树返回，继续出栈； 若若 p 非空，则访问根结点，非空，则访问根结点，p 进栈；进栈； 令令 p 指向该结点的左子树的根，继续遍历；指向该结点的左子树的根，继续遍历； void preorder(struct btnode *root) p=root; initstack(s); do while(p!=null) printf(“%c ”, p-data); push(s, p); p=p-lchild; if(!empty(s) p=pop(s); p=p-rchild;

58、 while(!empty(s) | p!=null); 6.3 遍历二叉树遍历二叉树 1. 先序遍历非递归算法先序遍历非递归算法 6.3 遍历二叉树遍历二叉树 1. 先序遍历非递归算法先序遍历非递归算法 void preorder(struct btnode *root) p=root; initstack(s); do while(p!=null) printf(“%c ”, p-data); push(s, p); p=p-lchild; if(!empty(s) p=pop(s); p=p-rchild; while(!empty(s) | p!=null); 6.3 遍历二叉树遍历二

59、叉树 1. 先序遍历非递归算法先序遍历非递归算法 void preorder(struct btnode *root) p=root; initstack(s); do while(p!=null) printf(“%c ”, p-data); push(s, p); p=p-lchild; if(!empty(s) p=pop(s); p=p-rchild; while(!empty(s) | p!=null); 6.3 遍历二叉树遍历二叉树 1. 先序遍历非递归算法先序遍历非递归算法 a void preorder(struct btnode *root) p=root; initstac

60、k(s); do while(p!=null) printf(“%c ”, p-data); push(s, p); p=p-lchild; if(!empty(s) p=pop(s); p=p-rchild; while(!empty(s) | p!=null); 6.3 遍历二叉树遍历二叉树 1. 先序遍历非递归算法先序遍历非递归算法 void preorder(struct btnode *root) p=root; initstack(s); do while(p!=null) printf(“%c ”, p-data); push(s, p); p=p-lchild; if(!emp