第7章树和二叉树1树的基本概念7.2二叉树概念和性质7.3二叉树存储结构7.4 二叉树的遍历7.5二叉树的基本运算及其实现7.6二叉树的构造7.7线索二叉树7.8哈夫曼树本章小结
1 第7章 树和二叉树 7.1 树的基本概念 7.2 二叉树概念和性质 7.3 二叉树存储结构 7.4 二叉树的遍历 7.5 二叉树的基本运算及其实现 7.6 二叉树的构造 7.8 哈夫曼树 7.7 线索二叉树 本章小结
7.1树的基本概念7.1.1树的定义形式化定义：树：T=D,R。D是包含n个节点的有穷集合（n≥0）当n=0时为空树，否则关系R满足以下条件：有且仅有一个节点d.ED，它对于关系R来说没有前驱节点，节点d.称作树的根节点除节点d.外，D中的每个节点对于关系R来说都有仅有一个前驱节点。D中每个节点对于关系R来说可以有零个或多个后继节点
2 7.1.1 树的定义 形式化定义： 树：T={D,R}。D是包含n个节点的有穷集合（n≥0）。 当n=0时为空树，否则关系R满足以下条件: ⚫ 有且仅有一个节点d0∈D，它对于关系R来说没有 前驱节点，节点d0称作树的根节点。 ⚫ 除节点d0外，D中的每个节点对于关系R来说都 有且仅有一个前驱节点。 ⚫ D中每个节点对于关系R来说可以有零个或多个 后继节点。 7.1 树的基本概念
递归定义：树是由n（n≥0）个节点组成的有限集合（记为T）。其中：如果n=0，它是一棵空树，这是树的特例；如果n>0，这n个节点中存在（有仅存在）一个节点作为树的根节点，简称为根节点（root），其余节点可分为m（m>0）个互不相交的有限集Ti,T2....,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树rootTiT2Tm3
3 递归定义： 树是由n（n≥0）个节点组成的有限集合（记为T）。其中： ⚫ 如果n=0，它是一棵空树，这是树的特例； ⚫ 如果n>0，这n个节点中存在（有仅存在）一个节点 作为树的根节点，简称为根节点（root），其余节点 可分为m （m>0）个互不相交的有限集T1 ,T2 ,.,Tm,其 中每一棵子集本身又是一棵符合本定义的树，称为 根root的子树。 root T1 T2 Tm
7.1.2 树的表示（1）树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。下图就是采用这种表示法。H逻辑结构表示1
4 7.1.2 树的表示 （1）树形表示法。这是树的最基本的表示，使用一棵倒置 的树表示树结构，非常直观和形象。下图就是采用这种表示 法。 A B C D E F G J H I K L M 逻辑结构表示1
（2）文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。D临BCH福逻辑结构表示25
5 （2）文氏图表示法。使用集合以及集合的包含关系描述树结 构。下图就是树的文氏图表示法。 A B C D E F G J H I K L M 逻辑结构表示2 A E F B C G J D H K L M I