树和二叉树61树的基本概念62二叉树概念和性质63二叉树.PDF

第6章 树和二叉树 6.1 树的基本概念 6.2 二叉树概念和性质 6.3 二叉树存储结构 6.4 二叉树的遍历 6.5 二叉树的基本操作及其实现 6.6 二叉树的构造 6.7 哈夫曼树 本章小结 6.1 树的基本概念 6.1.1 树的定义 形式化定义： 树：T={D,R} 。D是包含n个结点的有穷集合（n≥0 ）。 当n=0时为空树，否则关系R满足以下条件: 有且仅有一个结点d0 ∈D，它对于关系R来说没 有前驱结点，结点d0称作树的根结点。 除结点d0外，D中的每个结点对于关系R来说都 有且仅有一个前驱结点。 D中每个结点对于关系R来说可以有零个或多 个后继结点。 递归定义： 树是由n （n≥0 ）个结点组成的有限集合（记为T ）。 如果n=0，它是一棵空树，这是树的特例； 如果n0，这n个结点中存在（且仅存在）一个结点 作为树的根结点，简称为根结点（root），其余结点 可分为m(m0)个互不相交的有限集T ,T ,…,T , 其 1 2 m 中每一个子集本身又是一棵符合本定义的树，称为根 root的子树。 root T T … T 1 2 m A A B C D E F G H I J K L M 例 左图是一棵只有根结点的树。 右图是一棵有13个结点的树，其中结点A是根, 其余结点 分成三个互不相交的子集： T1={B,E,F} ； T2={C,G,J} ； T3={D,H,I,K,L,M} 。 T1,T2,T3都是根A 的子树，且本身也是一棵树。 6.1.2 树的表示 （1）树形表示法。这是树的最基本的表示，使用一棵 倒置的树表示树结构，非常直观和形象。下图就是采用这 种表示法。 A B C D E F G H I J K L M 逻辑结构表示1 （2 ）文氏图表示法。使用集合以及集合的包含关系描述树 结构。下图就是树的文氏图表示法。 A A D H C B B C D E F G I E F G H I K J L