数据结构《第6章-树和二叉树》.pdfVIP

第 6 章 树和二叉树 本章学习要点 ◆熟悉树的递归定义、相关术语以及基本概念 ◆熟悉二叉树的递归定义、二叉树的有关术语以及基本概念 ◆掌握二叉树的基本性质以及相应的证明方法 ◆了解二叉树的两种存储结构、各种存储方法的特点和适用范围 ◆熟练掌握二叉树的各种遍历算法，能通过应用二叉树的遍历操作实现二叉树的其它基本操作 ◆了解线索二叉树的实质和目的，掌握在中序线索化的二叉树中，查找给定结点的前驱和后继的方法 ◆掌握树、森林与二叉树之间的关系和转换方法 ◆掌握树的各种存储结构的特点、适应范围以及树和森林的遍历算法 树型结构是一种应用非常广泛的非线性结构，其中以二叉树最为常用。树型结构反映了元素之间 的层次关系和分支关系，它非常类似于自然界中的树。树型结构在电脑领域中广泛应用。比方，在电 脑操作系统中对文件的目录管理就是采用树型结构；在编译程序中，使用树来表示程序的语法结构； 在数据库系统中，树型结构也是信息的重要组织形式之一。 本章将详细讨论二叉树的逻辑结构、各种存储结构及其基本操作的实现，研究树、森林和二叉树 之间的转换关系，最后介绍一个二叉树的应用实例 ____Huffman 树及其应用。 6.1 树的定义和基本术语 6.1.1 树的定义 树 T 〔Tree 〕是 n(n=0) 个数据元素〔结点〕的有限集合 D ，如果 D 为空集，则称 T 为 空树 ；否 则有下面的定义： 〔1 〕在 D 中有且仅有一个特定的结点，称为 根结点 ； 〔2 〕当 n1 时，其余的结点可分成 m(m0) 个互不相交的有限集： T 1 2 m ,T ,…,T ，期中每个集合又都是 一棵树，并称它们为树 T 的根结点的 子树 。 树是以递归的方式来定义的，即在表达树的定义的过程中又用到了树的概念。树的这种递归定义 方式反映了树型结构的层次特性。直观地讲，树是由根结点和假设干棵子树组成，其中的每棵子树又 都是由一个根结点和它自己的假设干棵子树组成，依此类推。 例如， 图 6.1 是用 图形表示法 表示的一棵树 T 。根据树的定义， T 的数据元素集合 D 中一共包含有 1 2 3 10 个结点： D={A,B,C,D,E,F,G,H,I,J} ，其中结点 A 为 T 的根结点。根结点 A 有三棵子树 T ,T ,T ，子 树的根结点分别为 B、C、D 均为 A 的孩子结点，每棵子树中所含数据元素的集合分别为 D1、D2 、D3 ， 1 2 3 它们互不相交且为： D ={B,E,F},D ={C,G} 和 D ={D,H,I} 。 树的表示方法还有 广义表表示法 、集合表示法 和 凹入表示法 等。图 6.2 分别给出图 6.1 中所表示 的树 T 的其它三种表示方法。 6.1.2 树结构中的基本术语 〔1 〕结点〔 Node 〕树的结点包含一个数据元素以及假设干个指向其子树的分支指针。 〔2 〕结点的度〔 Degree 〕结点所拥有的子树个数称为该结点的度。 例如，在图 6.1 所示的树 T 中，度为零的结点有 E 、F、G、H 、 I、J，度为 1 的结点有 C，度为 2 的结点有 B ，度为 3 的结点有 A 、B 。 〔3 〕叶子结点〔 Leaf 〕度为 0 的结点称为叶结点或终端结点。 例如，树 T 中，其叶结点为 E、F、G、H 、 I、J。 〔4 〕分支结点〔 Offshoot-Node 〕度不为 0 的结点称为分支结点或非终端结点。 例如，树 T 中，分支结点有 A 、B 、C 、D 。 〔5 〕树的度〔 Tree-D