数据结构(C语言版)：第6章树

《数据结构(C语言版)：第6章树》由会员分享，可在线阅读，更多相关《数据结构(C语言版)：第6章树（116页珍藏版）》请在装配图网上搜索。

1、数据结构数据结构 第六章第六章 树和二叉树树和二叉树数据结构数据结构 第六章第六章 树和二叉树树和二叉树1、树和森林的概念（树的定义、树的术语、性质、树和森林的概念（树的定义、树的术语、性质 及运算）；及运算）； 2、二叉树的定义、性质及运算；、二叉树的定义、性质及运算； 3、二叉树的存储结构（顺序、链式表示）；、二叉树的存储结构（顺序、链式表示）； 4、遍历二叉树、遍历二叉树 5、树的存储结构；树、森林与二叉树的转换；遍、树的存储结构；树、森林与二叉树的转换；遍 历树；遍历森林历树；遍历森林 6、哈夫曼树、哈夫曼编码。、哈夫曼树、哈夫曼编码。 教学内容教学内容 数据结构数据结构 第六章第六章

2、 树和二叉树树和二叉树树型结构（非线性结构）树型结构（非线性结构） 结点之间有分支结点之间有分支 具有层次关系具有层次关系 例例 自然界：树自然界：树 人类社会人类社会 家谱家谱 行政组织机构行政组织机构 计算机领域计算机领域 编译：用树表示源程序的语法结构编译：用树表示源程序的语法结构 数据库系统：用树组织信息数据库系统：用树组织信息 算法分析：用树描述执行过程算法分析：用树描述执行过程 国务院国务院 山东省山东省 北京市北京市 西藏自治区西藏自治区 济南市济南市 青岛市青岛市 威海市威海市 历下区历下区 市中区市中区 商河县商河县 数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.1

3、 树的定义和基本术语树的定义和基本术语 定义：定义： 树树 (Tree) 是是 n (n0) 个结点的有限集。若个结点的有限集。若 n = 0，称，称 为空树；若为空树；若 n 0，则它满足如下两个条件：，则它满足如下两个条件： (1) 有且仅有一个特定的称为有且仅有一个特定的称为 (Root) 的结点；的结点； (2) 其余结点可分为其余结点可分为 m (m0) 个互不相交的有限集个互不相交的有限集 T1, T2, T3, , Tm，其中每一个集合本身又是一棵树，并称为，其中每一个集合本身又是一棵树，并称为 根的根的子树子树 (SubTree)。显然，树的定义是一个递归的定义。显然，树的定义

4、是一个递归的定义。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树树中任一结点都可以有零个或多个直接后继结点树中任一结点都可以有零个或多个直接后继结点 但至多只能有一个直接前趋结点。但至多只能有一个直接前趋结点。 T3 T2 T1 基本术语：基本术语： 结点的结点的结点拥有的子树数。结点拥有的子树数。 度度 = 0 度度 0 根结点以根结点以 外的分支外的分支 结点称为结点称为 树的树的树内各结点的度的最大值。树内各结点的度的最大值。 双亲双亲 孩子孩子 兄弟兄弟 结点的结点的从根到该结点所经分支上的所有结点。从根到该结点所经分支上的所有结点。 结点的结点的以某结点为根的子树中的任一结点

5、。以某结点为根的子树中的任一结点。 第第 1 层层 第第 2 层层 第第 3 层层 第第 4 层层 堂兄弟堂兄弟 双亲在同一层的结点双亲在同一层的结点 树的树的树中结点的最大层次。树中结点的最大层次。 树中结点的各子树从左至右有次序（最左边的为第一个孩子）。树中结点的各子树从左至右有次序（最左边的为第一个孩子）。 树中结点的各子树无次序。树中结点的各子树无次序。 数据元素数据元素+ 指向子树的分支指向子树的分支 非空树中无前驱结点的结点非空树中无前驱结点的结点 是是 m (m0) 棵互不相交的树的集合。棵互不相交的树的集合。 一棵树可以看成是一个特殊的森林。一棵树可以看成是一个特殊的森林。 把

6、根结点删除树就变成了森林。把根结点删除树就变成了森林。 给森林中的各子树加上一个双亲结点，森林就变成了树。给森林中的各子树加上一个双亲结点，森林就变成了树。 树树 森林森林 一定是一定是 不一定是不一定是 E F G H I A B C D J K L M 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 树的逻辑结构描述树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为：一棵树的逻辑结构可以用二元组描述为： Tree = (root, F )数据元素数据元素 根结点根结点 包含包含 m (m0) 棵树的森林棵树的森林 F = (T1, T2, , Tm) Ti = (ri , Fi )

7、 Ti 称做根称做根 root 的第的第 i 棵子树。棵子树。当当 m0 时，在树根和其子树森林之间存在下列关系：时，在树根和其子树森林之间存在下列关系： RF = | i = 1, 2, , m, m 0数据结构数据结构 第六章第六章 树和二叉树树和二叉树RF = , , Tree = (A, F ) F = (T1, T2, T3) T1 = (B, F1) T2 = (C, F2) T3 = (D, F3) r1F1= , r2F2= r3F3= , , E F G H I A B C D J K L M 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 树的抽象数据类型定义：树的抽

8、象数据类型定义： ADT Tree 数据对象数据对象 D： D 是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系 R：（略）：（略） 基本操作基本操作 P： InitTree (&T )； 操作结果：操作结果：构造空树构造空树 T。 CreateTree (&T, definition)； 初始条件：初始条件： definition 给出树给出树 T 的定义。的定义。 操作结果：操作结果：按按 definition 构造树构造树 T。数据结构数据结构 第六章第六章 树和二叉树树和二叉树 DestroyTree (&T )； 初始条件：初始条件：树树 T 存在存

9、在。 操作结果：操作结果：销毁树销毁树 T。 TreeEmpty (T) 初始条件：初始条件：树树 T 存在。存在。 操作结果：操作结果：若若 T 为空树，则返回为空树，则返回 TURE，否则，否则 FALSE。 TreeDepth (T) 初始条件：初始条件：树树 T 存在。存在。 操作结果：操作结果：返回返回 T 的深度。的深度。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树Root (T) 初始条件：初始条件：树树 T 存在存在。 操作结果：操作结果：返回返回 T 的根的根。 Value (T, cur_e)； 初始条件：初始条件：树树 T 存在，存在， cur_e 是是 T 中

10、某个结点中某个结点。 操作结果：操作结果：返回返回 cur_e 的值的值。 Assign (T, cur_e, value) 初始条件：初始条件：树树 T 存在，存在， cur_e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：结点结点 cur_e 赋值为赋值为 value。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 Parent (T, cur_e) 初始条件：初始条件：树树 T 存在，存在， cur_e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：若若 cur_e 是是 T 的非根结点，则返回它的双的非根结点，则返回它的双 亲，否则函数值为亲，否则函数值为

11、“空空”。 LeftChild (T, cur_e) 初始条件：初始条件：树树 T 存在，存在， cur_e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：若若 cur_e 是是 T 的非叶子结点，则返回它的的非叶子结点，则返回它的 最左孩子，否则返回最左孩子，否则返回“空空”。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树RightSibling (T, cur_e) 初始条件：初始条件：树树 T 存在，存在， cur_e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：若若 cur_e 有右兄弟，则返回它的右兄弟，有右兄弟，则返回它的右兄弟， 否则函数值为否则函数

12、值为“空空”。 TraverseTree (T, Visit() )； 初始条件：初始条件：树树 T 存在，存在，Visit 是对结点操作的函数。是对结点操作的函数。 操作结果：操作结果：按某种次序对按某种次序对 T 的每个结点调用函数的每个结点调用函数 Visit () 一次且至多一次。一旦一次且至多一次。一旦 Visit () 失败，则操作失败。失败，则操作失败。数据结构数据结构 第六章第六章 树和二叉树树和二叉树 ClearTree (&T )； 初始条件：初始条件：树树 T 存在。存在。 操作结果：操作结果：将树将树 T 清为空树。清为空树。 InsertChild (&T, &p,

13、i, c)； 初始条件：初始条件：树树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，1ip 所指结点的度所指结点的度 + 1，非空树，非空树 c 与与 T 不相交。不相交。 操作结果：操作结果：插入插入 c 为为 T 中中 p 指结点的第指结点的第 i 棵子树。棵子树。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 DeleteChild (&T, &p, i)； 初始条件：初始条件：树树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点， 1ip 所指结点的度。所指结点的度。 操作结果：操作结果：删除删除 T 中中 p 所指结点的第所指结点的第 i 棵子树。棵子

14、树。 ADT Tree 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 树的表示形式树的表示形式 1树形表示法树形表示法 A 空树空树 A B 仅含有根结点的树仅含有根结点的树 2嵌套集合（文氏）表示法嵌套集合（文氏）表示法 ABEFK LDHIMJCG E F G H I A B C D J K L M 数据结构数据结构 第六章第六章 树和二叉树树和二叉树3凹入表示法凹入表示法 A B E K L F C G D H M I J 4广义表表示法广义表表示法 E F G H I A B C D J K L M (B(E(K,L),F),C(G),D(H(M),I,J) ) 数据结构数据结

15、构 第六章第六章 树和二叉树树和二叉树6.2 二叉树二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉二叉树在树结构的应用中起着非常重要的作用，因为对二叉 树的许多操作算法简单，而任何树都可以与二叉树相互转换，这树的许多操作算法简单，而任何树都可以与二叉树相互转换，这 样就解决了树的存储结构及其运算中存在的复杂性。样就解决了树的存储结构及其运算中存在的复杂性。6.2.1 二叉树的定义二叉树的定义 二叉树是二叉树是 n (n0) 个结点的有限集，它或者是个结点的有限集，它或者是空集空集 (n = 0)，或者由一个，或者由一个根结点根结点及及两棵互不相交两棵互不相交的的 分别称作这个根的

16、分别称作这个根的左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。 定义定义 特点特点 1、每个结点最多有俩孩子、每个结点最多有俩孩子 () 。 2、子树有左右之分，其次序不能颠倒。、子树有左右之分，其次序不能颠倒。 3、二叉树可以是空集合，根可以有空的左子树或空的右子树。、二叉树可以是空集合，根可以有空的左子树或空的右子树。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 二叉树二叉树结点的子树要区分左子树和右子树，即使只有一棵子结点的子树要区分左子树和右子树，即使只有一棵子 树也要进行区分，说明它是左子树，还是右子树。树树也要进行区分，说明它是左子树，还是右子树。树当结点只有当

17、结点只有 一个孩子时，就无须区分它是左还是右的次序。（一个孩子时，就无须区分它是左还是右的次序。（也就是二叉树也就是二叉树 每个结点位置或者说次序都是固定的，可以是空，但是不可以说每个结点位置或者说次序都是固定的，可以是空，但是不可以说 它没有位置，而树的结点位置是相对于别的结点来说的，没有别它没有位置，而树的结点位置是相对于别的结点来说的，没有别 的结点时，它就无所谓左右了）的结点时，它就无所谓左右了），因此二者是不同的。，因此二者是不同的。这是二叉这是二叉 树与树的最主要的差别。树与树的最主要的差别。 二二叉叉树树树的特殊情况，它们是两个概念。树的特殊情况，它们是两个概念。 注注 A B

18、具有两个结点的树只有一种状态具有两个结点的树只有一种状态 A B A B 具有两个结点的二叉树有两种状态具有两个结点的二叉树有两种状态 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树的二叉树的 5 种基本形态种基本形态 (a)空二叉树空二叉树 (b) 根和空的根和空的 左右子树左右子树 (c) 根和左子树根和左子树 (d) 根和右子树根和右子树 (e) 根和左右子树根和左右子树 注：虽然二叉树与树概念不同，注：虽然二叉树与树概念不同， 但有关树的基本术语对二叉树都适用。但有关树的基本术语对二叉树都适用。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树的抽象数据类型定义：

19、二叉树的抽象数据类型定义： ADT BinaryTree 数据对象数据对象 D：D 是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系 R： （略）（略） 基本操作基本操作 P： InitBiTree(&T); 操作结果：操作结果：构造空二叉树构造空二叉树 T。 CreateBiTree(&T, definition); 初始条件：初始条件：definition 给出二叉树给出二叉树 T 的定义。的定义。 操作结果：操作结果：按按 definition 构造二叉树构造二叉树 T。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 DestroyBiTree(&

20、T);初始条件：初始条件：二叉树二叉树 T 存在。存在。 操作结果：操作结果：销毁二叉树销毁二叉树 T。 BiTreeEmpty(T); 初始条件：初始条件：二叉树二叉树 T 存在存在。 操作结果：操作结果：若若 T 为空二叉树，则返回为空二叉树，则返回 TRUE，否则返回，否则返回 FALSE。 BiTreeDepth(T); 初始条件：初始条件：二叉树二叉树 T 存在存在。操作结果：操作结果：返回返回 T 的深度的深度。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 Root(T); 初始条件：初始条件：二叉树二叉树 T 存在。存在。操作结果：操作结果：返回返回 T 的根。的根。

21、Value(T, e); 初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：返回返回 e 的值。的值。Parent(T, e); 初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：若若 e 是是 T 的非根结点，则返回它的双亲，的非根结点，则返回它的双亲， 否则返回否则返回“空空”。 LeftChild(T, e); 初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：返回返回 e 的左孩子。若的左孩子。若 e 无左孩

22、子则返回无左孩子则返回“空空”。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 RightChild(T, e); 初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：返回返回 e 的右孩子。若的右孩子。若 e 无右孩子则返回无右孩子则返回“空空”。 LeftSibling(T, e); 初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：返回返回 e 的左兄弟。若的左兄弟。若 e 是其双亲的左孩子或是其双亲的左孩子或 无左兄弟，则返回无左兄弟，则返回“空空”。 Righ

23、tSibling(T, e); 初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 的结点。的结点。 操作结果：操作结果：返回返回 e 的右兄弟。若的右兄弟。若 e 是其双亲的右孩子或是其双亲的右孩子或 无右兄弟，则返回无右兄弟，则返回“空空”。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树PreOrderTraverse(T, visit(); 初始条件：初始条件：二叉树二叉树 T 存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。 操作结果：操作结果： T，对每个结点调用函数，对每个结点调用函数 visit 一次一次 且仅一次。一旦且仅一次。一旦

24、visit() 失败，则操作失败。失败，则操作失败。 InOrderTraverse(T, vsit(); 初始条件：初始条件：二叉树二叉树 T 存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。 操作结果：操作结果： T，对每个结点调用函数，对每个结点调用函数 Visit 一次一次 且仅一次。一旦且仅一次。一旦 visit() 失败，则操作失败。失败，则操作失败。 PostOrderTraverse(T, visit(); 初始条件：初始条件：二叉树二叉树T存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。 操作结果：操作结果： T，对每个结点调用

25、函数，对每个结点调用函数 visit 一次一次 且仅一次。一旦且仅一次。一旦 visit() 失败，则操作失败。失败，则操作失败。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树LevelOrderTraverse(T, visit(); 初始条件：初始条件：二叉树二叉树 T 存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。 操作结果：操作结果：T，对每个结点调用函数，对每个结点调用函数 visit 一次一次 且仅一次。一旦且仅一次。一旦 visit() 失败，则操作失败。失败，则操作失败。 ClearBiTree(&T); 初始条件：初始条件：二叉树二叉树 T

26、存在。存在。 操作结果：操作结果：将二叉树将二叉树 T 清为空树。清为空树。 Assign(&T, &e, value); 初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。 操作结果：操作结果：结点结点 e 赋值为赋值为 value。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 InsertChild(&T, p, LR, c); 初始条件：初始条件：二叉树二叉树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，LR 为为 0 或或 1，非空二叉树，非空二叉树 c 与与 T 不相交且右子不相交且右子 树为空。树为空。 操作结果：操作结

27、果：根据根据 LR 为为 0 或或 1，插入，插入 c 为为 T 中中 p 所指结所指结 点的左或右子树。点的左或右子树。p 所指结点原有左或右子所指结点原有左或右子 树成为树成为 c 的右子树。的右子树。 DeleteChild(&T, p, LR); 初始条件：初始条件：二叉树二叉树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，LR 为为 0 或或 1。 操作结果：操作结果：根据根据 LR 为为 0 或或 1，删除，删除 T 中中 p 所指结点的所指结点的 左或右子树。左或右子树。 ADT BinaryTree 数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.2.2

28、二叉树的性质二叉树的性质 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2 i - 1 个结点个结点 (i 1)。 证：证：采用归纳法证明此性质。采用归纳法证明此性质。 归纳基：归纳基：当当 i = 1 时，只有一个根结点，时，只有一个根结点，2 i-1= 20 = 1，命题成立。，命题成立。 归纳假设：归纳假设：设对所有的设对所有的 j (1j i)，命题成立，即第，命题成立，即第 j 层上至多层上至多 有有2j -1 个结点。那么可以证明个结点。那么可以证明 ji 时命题也成立。时命题也成立。 归纳证明：归纳证明：由归纳假设可知，第由归纳假设可知，第 i 1 层上至多有层上至多有 2

29、 i - 2个结点。个结点。 由于二叉树每个结点的度最大为由于二叉树每个结点的度最大为 2，故在第，故在第 i 层上最层上最 大结点数为第大结点数为第 i 1 层上最大结点数的层上最大结点数的 2 倍，即：倍，即： 22 i 22 i 1。 证毕。证毕。数据结构数据结构 第六章第六章 树和二叉树树和二叉树深度为深度为 k 的二叉树至多有的二叉树至多有 2k1 个结点（个结点（k 1)。 证：证：由性质由性质 1 可知，深度为可知，深度为 k 的二叉树的最大结点数为：的二叉树的最大结点数为： 122)(111 kkiiki i 层层上上的的最最大大结结点点数数第第证毕。证毕。 数据结构数据结构

30、第六章第六章 树和二叉树树和二叉树对任何一棵二叉树对任何一棵二叉树 T，如果其叶子数为，如果其叶子数为 n0，度为，度为 2 的结点的结点 数为数为 n2，则，则 n0 = n2 + 1。 证：证：设设 n1 为二叉树为二叉树 T 中度为中度为 1 的结点数。因为二叉树中所有结点的结点数。因为二叉树中所有结点 均均2，所以其结点总数为：，所以其结点总数为： n = n0 + n1 + n2 再看二叉树中的分支数，除根结点外，其余结点都有一个分再看二叉树中的分支数，除根结点外，其余结点都有一个分 支进入，设支进入，设 B 为分支总数，则有：为分支总数，则有： n = B1 由于这些分支都是由度为

31、由于这些分支都是由度为 1 和和 2 的结点射出的，所以有：的结点射出的，所以有： B = n1 + 2n2 于是有：于是有： n = B + 1n1 + 2n2 + 1 所以有：所以有： n0 + n1 + n2 = n1 + 2n2 + 1 即：即： n0 = n2 + 1 证毕。证毕。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 满二叉树满二叉树 (Full binary tree) 特点：特点：每一层上的结点数都达到最大。每一层上的结点数都达到最大。 叶子全部在最底层。叶子全部在最底层。编号规则：编号规则：从根结点开始，自上而下，自左而右从根结点开始，自上而下，自左而右。 一

32、棵深度为一棵深度为 k 且有且有 2k- 1 个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。2453671数据结构数据结构 第六章第六章 树和二叉树树和二叉树 完全二叉树完全二叉树 (Complete binary tree) 深度为深度为 k 的具有的具有 n 个结点的二叉树，当且仅当其每一个结点的二叉树，当且仅当其每一 个结点都与深度为个结点都与深度为 k 的满二叉树中编号为的满二叉树中编号为 1 n 的结点一一的结点一一 对应时，称之为对应时，称之为完全二叉树完全二叉树。 特点：特点：叶子只可能分布在层次最大的两层上。叶子只可能分布在层次最大的两层上。 对任一结点，如果其右子树的

33、最大层次为对任一结点，如果其右子树的最大层次为 l，则其左子，则其左子 树的最大层次必为树的最大层次必为 l 或或 l + 1。 满二叉树满二叉树 完全二叉树完全二叉树 是是定定一一 不不 一一定定 是是 245361完全二叉树完全二叉树 245361非完全二叉树非完全二叉树 数据结构数据结构 第六章第六章 树和二叉树树和二叉树完全二叉树的性质完全二叉树的性质 具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n + 1。 证：假设此二叉树的深度为证：假设此二叉树的深度为 k，则根据性质，则根据性质 2 及完全二叉树的及完全二叉树的 定义得到：定义得到： 2k-1 1

34、 n2k 1 或或 2k-1n 2k 取对数得：取对数得： k 1log2n 1， 则其双亲是结点则其双亲是结点 i / 2 。 (2) 如果如果 2i n，则结点，则结点 i 为叶子结点，无左孩子；否则，其为叶子结点，无左孩子；否则，其 左孩子是结点左孩子是结点 2i。 (3) 如果如果 2i + 1 n，则结点，则结点 i 无右孩子；否则，其右孩子是无右孩子；否则，其右孩子是 结点结点 2i + 1。数据结构数据结构 第六章第六章 树和二叉树树和二叉树证：证：(1) 可以从可以从 (2) 和和 (3) 推出，所以先证明推出，所以先证明 (2) 和和 (3)。 ，由完全二叉树的定义，其左孩子

35、是，由完全二叉树的定义，其左孩子是 结点结点 2 = 2i，若，若 2 = 2i n = 1，即不存在结点，即不存在结点 2，此，此 时，结点时，结点 i 无左孩子。无左孩子。 (2) 得证得证。 i 1 结点结点 i 的右孩子也只能是结点的右孩子也只能是结点 3 = 2i + 1，若，若 3 = 2i + 1 n，即不存在结点，即不存在结点 3，此时结点此时结点 i 无右孩子。无右孩子。 (3) 得证得证。 2i 22i +1 32i 2数据结构数据结构 第六章第六章 树和二叉树树和二叉树 (1) 设第设第 j (1j log2n ) 层的层的 的编号为的编号为 i (由二叉树的由二叉树的

36、定义和性质定义和性质 2 知知 i =2 j1)，则其左孩，则其左孩 子必为第子必为第 j +1 层的第一个结点，其层的第一个结点，其 编号为编号为 2 j22 j 12i。 1 第第 j 层层 23 ，可分为两种情况：，可分为两种情况： 第第 j 1 层层 第第 j +1 层层 i 2 j-1 2i = 2j 2i+12 j-1-1 =2j-1 如果如果 2i n，则无左孩子。，则无左孩子。 (2) 得证得证。 其右孩子必定为第其右孩子必定为第 j +1 层的第二个结点，层的第二个结点， 编号为编号为2i +1。若。若 2i +1 n，则无右孩子。，则无右孩子。 (3) 得证得证。 数据结构

37、数据结构 第六章第六章 树和二叉树树和二叉树 (2) 设第设第 j (1j log2n ) 层的层的的编号为的编号为 i (2 j 1i 2 j 1)，且，且 2i +11 时：时： 如果如果 i 为左孩子，且为左孩子，且 i 的双亲为的双亲为 p，则有，则有 i = 2p， p = i / 2 = i / 2 ，即，即 i / 2 是是 i 的双亲；的双亲； i 为偶数为偶数 i 为奇数为奇数 如果如果 i 为右孩子，且为右孩子，且 i 的双亲为的双亲为 p，则有，则有 i2p +1， p = (i - 1) / 2 = i / 2 1 / 2 = i / 2 ，即，即 i / 2 是是 i

38、 的双亲。的双亲。证毕证毕。数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.2.3 二叉树的存储结构二叉树的存储结构 1、 顺序存储结构顺序存储结构 完全二叉树：完全二叉树：用一组地址连续的用一组地址连续的 存储单元依次存储单元依次存存 储结点元素，即将编号为储结点元素，即将编号为 i 的结点元的结点元 素存储在一维数组中下标为素存储在一维数组中下标为 i 1 的分的分 量中。量中。 1 2 3 4 5 6 1 2 3 4 5 6 一般二叉树：一般二叉树：将其每个结点与完将其每个结点与完 全二叉树上的结点相对照，存储在一全二叉树上的结点相对照，存储在一 维数组的相应分量中。维数组的相应

39、分量中。 这种顺序存储结构仅适用于完全二叉树这种顺序存储结构仅适用于完全二叉树 245361完全二叉树完全二叉树 245361非完全二叉树非完全二叉树 1 2 3 4 5 6 数据结构数据结构 第六章第六章 树和二叉树树和二叉树深度为深度为 k 的且只的且只 有有 k 个结点的右单支树需要个结点的右单支树需要 长度为长度为2k-1 的一维数组。的一维数组。 1 0 2 0 0 0 3 表示方式：表示方式：#define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0 号单元存

40、储根结点号单元存储根结点SqBiTree bt;231右单支树右单支树 0000数据结构数据结构 第六章第六章 树和二叉树树和二叉树 存储方式存储方式 二叉树结点的特点二叉树结点的特点 lchild data rchild结点结构结点结构 data rchild lchild data parentlchildrchild数据结构数据结构 第六章第六章 树和二叉树树和二叉树 A B C D E F G A B C D 二叉链表二叉链表 在在 n 个结点的二叉链表中，有个结点的二叉链表中，有 n + 1 个空指针域。个空指针域。ABCDEFGABCD数据结构数据结构 第六章第六章 树和二叉树树和

41、二叉树typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;C 语言的类型描述如下：语言的类型描述如下： 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 A B C D E F G 三叉链表三叉链表 ABCDEFGparentdatalchild rchild lchild data parent rchild 结点结构结点结构 数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.3 遍历二叉树和线索二叉树遍历

42、二叉树和线索二叉树 6.3.1 遍历二叉树（遍历二叉树（） 遍历概念遍历概念 顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树中的结点，使二叉树中的结点，使 得每个结点得每个结点均被访问一次均被访问一次，而且，而且仅被访问一次仅被访问一次。“”的含义很广，可以是对结点作各种处理，如：输出结的含义很广，可以是对结点作各种处理，如：输出结 点的信息、修改结点的数据值等，但要求这种访问点的信息、修改结点的数据值等，但要求这种访问。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 遍历方法遍历方法 依次遍历二叉树中的三个组成依次遍历二叉树中的三个组成 部分，便是遍历了整个二叉树部分，便是遍历了

43、整个二叉树 假设：假设：L：遍历左子树：遍历左子树 D：访问根结点：访问根结点 R：遍历右子树：遍历右子树 则遍历整个二叉树方案共有：则遍历整个二叉树方案共有： 遍历目的遍历目的 得到树中所有结点的一个得到树中所有结点的一个线性线性排列。排列。 根结点根结点 左子树左子树 右子树右子树 DLR、LDR、LRD、DRL、RDL、RLD 六种。六种。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树若规定先左后右，则只有前三种情况：若规定先左后右，则只有前三种情况： 先（根）序遍历，先（根）序遍历， 中（根）序遍历，中（根）序遍历， 后（根）序遍历。后（根）序遍历。 根结点根结点 左子树左子树

44、 右子树右子树 数据结构数据结构 第六章第六章 树和二叉树树和二叉树遍历二叉树的操作定义：遍历二叉树的操作定义： 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 (1) 访问根结点；访问根结点； (2) 先序遍历左子树；先序遍历左子树； (3) 先序遍历右子树。先序遍历右子树。 先序遍历的顺序为：先序遍历的顺序为：ABC 先序遍历的顺序为：先序遍历的顺序为：ABELDHMIJ A B C A B D E LH M I J 数据结构数据结构 第六章第六章 树和二叉树树和二叉树遍历二叉树的操作定义：遍历二叉树的操作定义： 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 (1)

45、中序遍历左子树；中序遍历左子树； (2) 访问根结点；访问根结点； (3) 中序遍历右子树。中序遍历右子树。 中序遍历的顺序为：中序遍历的顺序为：BAC 中序遍历的顺序为：中序遍历的顺序为：ELBAMHIDJ A B C A B D E LH M I J 数据结构数据结构 第六章第六章 树和二叉树树和二叉树遍历二叉树的操作定义：遍历二叉树的操作定义： 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 (1) 后序遍历左子树；后序遍历左子树； (2) 后序遍历右子树；后序遍历右子树； (3) 访问根结点。访问根结点。 后序遍历的顺序为：后序遍历的顺序为：BCA 后序遍历的顺序为：后序遍历

46、的顺序为：LEBMIHJDA A B C A B D E LH M I J 数据结构数据结构 第六章第六章 树和二叉树树和二叉树例：例：请写出下图所示二叉树的先序、中序和后序遍历顺序。请写出下图所示二叉树的先序、中序和后序遍历顺序。遍历结果：遍历结果： 先序：先序： - - + ab - - c d / e f 中序：中序： a + bc - - d - - e / f 后序：后序： a b c d - -+ e f / - - 表达式的表达式的（波兰式）（波兰式） 表达式的表达式的 表达式的表达式的（逆波兰式）（逆波兰式） 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树基本操作的

47、二叉树基本操作的算法在二叉链表上的实现：算法在二叉链表上的实现： Status PreOrderTraverse (Bitree T, Visit) / 最简单的最简单的 Visit 函数是：函数是： / Status PrintElement (TElemType e) / Printf (e); / 实用时加上格式串。实用时加上格式串。 / return OK; if (T) if (Visit (Tdata) if (PreOrderTraverse (Tlchild, Visit) if (PreOrderTraverse (Trchild, Visit) return OK; ret

48、urn ERROR; else return OK; / PreOrderTraverse lchild data rchild结点结构结点结构 A B C D E F G T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树基本操作的二叉树基本操作的算法在二叉链表上的实现：算法在二叉链表上的实现： Status InOrderTraverse (Bitree T, Visit) if (T) if (InOrderTraverse ( Tlchild, Visit ) if (Visit (Tdata) if (InOrderTraverse (Trchild, Visit) re

49、turn OK; return ERROR; else return OK; / InOrderTraverse A B C D E F G T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树基本操作的二叉树基本操作的算法在二叉链表上的实现：算法在二叉链表上的实现： Status PostOrderTraverse (Bitree T, Visit) if (T) if (PostOrderTraverse ( Tlchild, Visit ) if (PostOrderTraverse (Trchild, Visit) if (Visit (Tdata) return OK; r

50、eturn ERROR; else return OK; / PostOrderTraverse A B C D E F G T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树以中序遍历为例来说明中序遍历二叉树的递归过程以中序遍历为例来说明中序遍历二叉树的递归过程 第一次经过第一次经过第二次经过第二次经过第三次经过第三次经过 BD ABCED数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树基本操作的二叉树基本操作的算法在二叉链表上的实现：算法在二叉链表上的实现： Status InOrderTraverse (BiTree T, Visit) InitStack(S); Pus

51、h(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); / if / while return OK; / InOrderTraverse a b c d e f T p p

52、 p a + b c d e f 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树基本操作的二叉树基本操作的算法在二叉链表上的实现：算法在二叉链表上的实现： Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) InitStack(S); p = T; while ( p | !StackEmpty (S) if (p) push(S, p); p = p lchild; / 根指针进栈，遍历左子树。根指针进栈，遍历左子树。 else / 根指针退栈，访问根结点，遍历右子树。根指针退栈，访问根结点，遍历右子树。 P

53、op (S, p); if ( !Visit(p data) return ERROR; p = p rchild; / else / while return OK; / InOrderTraverse a b c d e f T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树二叉树其它操作算法举例二叉树其它操作算法举例 统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数 实现这个操作只要对二叉树实现这个操作只要对二叉树“遍历遍历”一遍，并在遍历过程中对一遍，并在遍历过程中对 “叶子结点计数叶子结点计数”即可。显然这个遍历的次序可以随意，只是为了即可。显然这个遍历的次序可以随意，只是

54、为了 在遍历的同时进行计数，需要在算法的参数中设一个在遍历的同时进行计数，需要在算法的参数中设一个“计数器计数器”。 void CountLeaf (BiTree T, int &count) / 先序遍历二叉树，以先序遍历二叉树，以 count 返回二叉树中叶子结点的数目返回二叉树中叶子结点的数目 if ( T ) if (!TLchild) & (!TRchild) / 无左、右子树无左、右子树 count + +; / 对叶子结点计数对叶子结点计数 CountLeaf ( TLchild, count); CountLeaf ( TRchild, count); / if / Count

55、Leaf 问题：问题：能否将能否将 count 设成函数中的局部变量，然后以设成函数中的局部变量，然后以 count 的值的值 作为函数值返回？作为函数值返回？ 答案：答案： 原因：原因：算法需要在递归执行的过程中对叶子算法需要在递归执行的过程中对叶子“累加计数累加计数”。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 求二叉树的深度（先序）求二叉树的深度（先序） 二叉树的深度二叉树的深度 = 叶子结点所在层次的最大值。叶子结点所在层次的最大值。 void BiTreeDepth(BiTree T, int level, int &depth) / level 为为 T 所指结点所在层

56、次，所指结点所在层次，其初值为其初值为1， / depth 为当前求得的最大层次，其初值为为当前求得的最大层次，其初值为 0。 if (T)if (level depth) depth = level; BiTreeDepth(TLchild, level + 1, depth);BiTreeDepth(TRchild, level + 1, depth); / if/ BiTreeDepth B C D E G F T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 求二叉树的深度（后序）求二叉树的深度（后序） 二叉树的深度二叉树的深度 = MAX（左子树深度，右子树深度）（左子树深度

57、，右子树深度）+ 1 。 void BiTreeDepth(BiTree T) if (!T) depth = 0; else depthleft = BiTreeDepth(TLchild); depthright = BiTreeDepth(TRchild); depth = max(depthleft, depthright) + 1; return depth; / BiTreeDepth B C D E G F T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 建立建立二叉树的存储结构二叉树的存储结构 二叉链表（先序）二叉链表（先序） Status CreateBiTree(

58、BiTree &T) scanf(&ch); if (ch=) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); Tdata = ch; / 生成根结点生成根结点 CreateBiTree(Tlchild); / 构造左子树构造左子树 CreateBiTree(Trchild); / 构造右子树构造右子树 return OK; / CreateBiTree DABEFGC 对右图所示二叉树，按下列顺序读入字符：对右图所示二叉树，按下列顺序读入字符： ABCDE GFA B C D E G F A

59、BCDEGF T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树6.3.2 线索二叉树线索二叉树 遍历结果：遍历结果： 先序：先序： - - + ab - - c d / e f 中序：中序： 后序：后序： a b c d - -+ e f / - - 为什么要研究线索二叉树为什么要研究线索二叉树 非线性结构非线性结构线性结构线性结构转转 化化 如何保存结果以避免重复遍历？如何保存结果以避免重复遍历？ 1、另辟存储空间存放遍历结果。、另辟存储空间存放遍历结果。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树遍历结果：遍历结果： 先序：先序： - - + ab - - c d / e

60、 f 中序：中序： 后序：后序： a b c d - -+ e f / - - 2、在原二叉链表的每个结点上增加两个指针域。、在原二叉链表的每个结点上增加两个指针域。 a b c d e f0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 对二叉树按某种次序遍对二叉树按某种次序遍 历使其变为线索二叉树历使其变为线索二叉树 的的。 利用利用线索化后的二叉树中的线索化后的二叉树中的线索线索就可就可 以以直接找直接找到某些结点在某种遍历序列中的到某些结点在某种遍历序列中的前趋和后继结点前趋和后继结点。 3、在原二叉链表的存储空间内反映遍历结果。、在原二叉

61、链表的存储空间内反映遍历结果。 中序线中序线 索链表索链表 中序线索二叉树中序线索二叉树 thrt 在遍历过程中用线索取代空指针在遍历过程中用线索取代空指针。 在在线索树（中序）线索树（中序）中找结点后继的方法：中找结点后继的方法： 1 、若右链是线索，则直接指示后继；若右链是线索，则直接指示后继； 2 、若右链是指针，则若右链是指针，则“右孩找左右孩找左”。 即：即：中序后继右孩找左中序后继右孩找左。 在在线索树（中序）线索树（中序）中找结点前驱的方法：中找结点前驱的方法： 1 、若左链是线索，则直接指示前驱；若左链是线索，则直接指示前驱； 2 、若左链是指针，则若左链是指针，则“左孩找右左

62、孩找右”。 即：即：中序前驱左孩找右中序前驱左孩找右。 在在线索树线索树上进行上进行遍历遍历的方法：的方法： 1 、从序列中的第一个结点起，依次找后继，直至后继为空。从序列中的第一个结点起，依次找后继，直至后继为空。 2 、从序列中的最后一个结点起，依次找前驱，直至前驱为空。从序列中的最后一个结点起，依次找前驱，直至前驱为空。 数据结构数据结构 第六章第六章 树和二叉树树和二叉树线索二叉树的存储表示线索二叉树的存储表示 typedef enum PointerTag Link, Thread ; / Link = 0：指针，：指针，Thread = 1：线索：线索 typedef struct

63、 BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针左右指针 PointerTag LTag, RTag; / 左右标志左右标志 BiThrNode, *BiThrTree; 数据结构数据结构 第六章第六章 树和二叉树树和二叉树线索链表的遍历算法（中序找后继法）：线索链表的遍历算法（中序找后继法）： Status InOrderTraverse_Thr(BiThrTree T, Visit) p = T lchild; while (p != T) while (p LTag = 0) p = p lchild

64、; if ( ! Visit(p data) return ERROR; while ( p RTag = 1 & p rchild != T) p = p rchild; Visit(p data); p = p rchild; return OK; / InOrderTraverse_Thr a b c d e f0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 T 数据结构数据结构 第六章第六章 树和二叉树树和二叉树 按中序按中序建立线索链表（建立线索链表（按中序线索化二叉树按中序线索化二叉树） 1、若结点没有左子树，则令其左指针指向它的、若

65、结点没有左子树，则令其左指针指向它的“前驱前驱”并将并将 左指针类型标志改为左指针类型标志改为 “1”； 2、若结点没有右子树，则令其右指针指向它的、若结点没有右子树，则令其右指针指向它的“后继后继”并将并将 右指针类型标志改为右指针类型标志改为 “1”； 3、为了获取、为了获取“前驱前驱” 的信息，需要在遍历过的信息，需要在遍历过 程中添加一个指针程中添加一个指针 pre， 令其始终指向刚刚访问令其始终指向刚刚访问 过的结点。若指针过的结点。若指针 p 指指 向当前访问的结点，则向当前访问的结点，则 pre 指向它的前驱。指向它的前驱。 a b c d e fT 数据结构数据结构 第六章第六

66、章 树和二叉树树和二叉树Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW); ThrtLTag = 0; ThrtRTag = 1; / 建头结点建头结点 Thrt rchild = Thrt; / 右指针回指右指针回指 if (!T) Thrt lchild = Thrt; / 若二叉树空，则左指针回指若二叉树空，则左指针回指 else Thrt lchild = T; pre = Thrt; InThreading(T); / 中序遍历进行中序线索化中序遍历进行中序线索化 pre rchild = Thrt; pre RTag = 1; / 最后一个结点线索化最后一个结点线索化 Thrt rchild = pre; return OK; / InOrderThreadingvoid InThreading(BiThrTree p) if (p) InThreading(p lchild); / 左子