NOIP高中信息技术竞赛资料 - -数据结构(7)

第4章 队列

第5章 树和二叉树

第5章 树和二叉树

树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。

树型结构在客观世界中是大量存在的，在计算机领域中也有着广泛的应用，如在编译程序中，用树来表示源程序的语法结构；在数据库系统可用树来组织信息。

5.1树的概念

1.树的递归定义

树是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

①有且仅有一个特定的称为根(Root)的结点；

②其余的结点可分为m(m≥0)个互不相交的有限子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。

注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。

2.树结构的基本术语

（1）结点的度

①结点的度：一个结点拥有子树的个数称为该结点的度。 例如图5.1表示的树中结点A的度为3，其它结点的度都为2或0。 ②树的度：该树中结点的最大度数称为该树的度。 例如图5.1表示的树的度为3。

③叶子结点：度为零的结点称为叶子结点或终端结点。 例如图5.1表示的树中结点C、E、G、H、I、J都是叶子结点。

④分支结点：度不为零的结点称分支结点或非终端结点。即除叶子结点外的结点均为分支结点。

例如图5.1表示的树中结点A、B、D、F都是分支结点。 ⑤内部结点：除根结点之外的分支结点统称为内部结点。 ⑥开始结点：根结点又称为开始结点。 例如图5.1表示的树中结点A是开始结点。 （2）结点之间的关系

①孩子结点：树中某个结点的子树的根称为该结点的孩子结点。

例如图5.1表示的树中结点B、C、D都是结点A的孩子结点，结点E、F都是结点B的孩子结点，结点G、H都是结点D的孩子结点。

②双亲结点：孩子结点的根称为该结点的双亲。

第5章 树和二叉树

例如图5.1表示的树中结点A是结点B、C、D的双亲结点，结点B是结点E、F的双亲结点，结点D是结点G、H的双亲结点。

③兄弟结点：同一个双亲的孩子互称为兄弟结点。

例如图5.1表示的树中结点B、C、D互为兄弟结点，结点E、F互为兄弟结点，而结点F和G非兄弟结点。

④堂兄弟：在后面介绍。 ⑤祖先和子孙：在后面介绍。 （3）路径

①路径或道路：若树中存在一个结点序列k1,k2,…,kj,使得ki是ki+1的双亲(1≤i

②路径的长度：指路径所经过的边的数目。

注意：若一个结点序列是路径，则在树的树形图表示中，该结点序列“自上而下”地通过路径上的每条边。从树的根结点到树中其余结点均存在一条惟一的路径。

例如图5.1表示的树中结点序列ABFI是结点A到I的一条路径，因为自上而下A是B的双亲，B是F的双亲，F是I的双亲。该路径的长度为3。而结点B和G之间不存在路径，因为既不能从B出发自上而下地经过若干个结点到达G，也不能从G出发自上而下地经过若干个结点到达B。

③祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先，ks是k的子孙。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。

约定：结点k的祖先和子孙不包含结点k本身。 （4）结点的层数和树的深度

①结点的层数：根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。

②堂兄弟：双亲在同一层的结点互为堂兄弟。 ③树的深度：树中结点的最大层数称为树的深度。 要注意结点的度、树的度和树的深度的区别。 （5）有序树和无序树

若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。

若不特别指明，一般讨论的树都是有序树。 （6）森林

森林是m(m≥0)棵互不相交的树的集合。

删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变

第5章 树和二叉树

为一棵树。

5.2 二叉树

二叉树是树型结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树的特点是每个结点最多只能有两棵子树，且有左右之分。

1.二叉树的定义 （1）二叉树的递归定义

二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

（2）二叉树的五种基本形态

二叉树可以是空集；可以有空的左子树或空的右子树；或者左、右子树皆为空。

二叉树的五种基本形态如图5.3。 (a)

(b)

(c)

(d)

(e)

图5.3 二叉树的五种基本形态

图中(a)为空二叉树，(b)是仅有一个根结点的二叉树，(c)是右子树为空的二

叉树，(d) 是左子树为空的二叉树，(e)是左右子树均非空的二叉树。

2. 二叉树的性质

性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)个。 证明：假设树非空，用数学归纳法证明。

当i=1时，因为第1层上只有一个根结点，而2i-1=20=1。所以命题成立。 假设对所有的j(1≤j

根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2?2i-2=2i-1个结点，故命题成立。

性质2 深度为k的二叉树至多有2k-1(k≥1)个结点。

第5章 树和二叉树

证明：由性质1，第i层至多有2i-1个(1≤i≤k)结点，所以深度为k的二叉树的结点总数至多为20+21+…+2k-1=2k-1个。

性质3 在任意一棵非空二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

证明：因为二叉树中所有结点的度数均不大于2，所以结点总数（记为n）应等于0度结点数n0、1度结点数n1和2度结点数n2之和：

n=n0+n1+n2

另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：nl+2?n2，而树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：

n=n1+2?n2+1

综合以上两个式子得到：

n0=n2+1

性质3说明：在任意非空二叉树中叶子结点数总比度为2的结点数多1个。 例如，如图5.4所示的二叉树中

叶子结点数为6，度为2的结点数为5，叶子结点数正好比度为2的结点数多1个。

（1）满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。 满二叉树的特点：

①每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。

②满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层。

例如，如图5.5所示的二叉树

图5.4

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(7)在线全文阅读。