武汉软件工程职业学院《数据结构讲义》第12讲-树和2叉树.docVIP

武汉软件工程职业学院《数据结构讲义》第12讲-树和2叉树

第四

第四章树

第

第十二讲树和二叉树

1．掌握树、二叉树的基本概念和术语，。

2．掌握二叉树的性质。

3.理解二叉树的存储结构

4.熟悉建立二叉树的二叉链表的算法。

教学重点：

二叉树的定义、二叉树的性质

教学难点：

二叉树的性质

授课内容

4.1树的定义和基本术语

前面讨论线性结构的表示及其应用实例。然而，线性结构在许多实际应用中不能明确、方便地表示数据元素之间的复杂关系。树型结构是一种应用十分广泛的非线性结构，其中以二叉树最为常用，它是以分支定义的层次结构。树型结构在客观世界中广泛存在，如家族的家谱、各种社会组织机构，一般都可以用树来形象地表示。在计算机领域中，编译系统中源程序的语法结构、数据库系统中信息的组织形式也用到树形结构。本章重点讨论二叉树的存储结构、各种操作及其应用实例。

4.1.1树的定义

1.定义

树（tree）是由n（n＞0）个结点组成的有限集合T且满足以下条件。

1）有且仅有一个特定的结点被称为该树的根（Root）。

2）除根结点之外的其余结点可分为m（m＞0）个互不相交的集合T1，T2，...，Tm，且其中每个集合又是一棵树，并称之为根的子树（Subtree）。

这是一个递归的定义，即在定义中又用到了树的概念，这也反映了树的固有特性。

图4-1-1是两棵树的示例。（a）是只有一个

为双亲结点层次值加1；树中结点的最大层次值称为树的深度或高度。图4－1－1（b）中，结点A、B、E、K的层次值分别为1、2、3、4。树T的深度为4。此外，双亲在同一层的结点互称为堂兄弟，如G和H互为堂兄弟。

4.2二叉树

4.2.1二叉树的定义

二叉树是N（N≥0）个结点的有限集合。它或为空树（N＝0），或由一个根结点和两个分别称为左子树和右子树的互不相交的子树构成。这个定义是递归的。图4-2-1中展现五种基本形态不同的二叉树。应特别注意，二叉树种左子树和右子树是严格区分的，图4-2-1（c）与（d）是两棵不同的二叉树。

图

图4-2-1二叉树的五种基本形态

?

(a)空二叉树

(b)仅有

根结点

(c)右子树为

空的二叉树

(d)左子树为

空的二叉树

(e)左右子树均非

空的二叉树

二叉树的重要性质

性质1二叉树i（i≥1）层上至多有2i－1个结点。有图4－2－2（a）可知，根结点在第1层上，这层结点数最多为1个，即20个；显然第2层上最多有2个结点，即21个；……；假设第i－1层结点最多有2i－2个，且每个结点最多有两个孩子，那么第i层上结点最多有2×2i－2＝2i－1个。

性质2深度为k（k≥1）的二叉树至多有2k－1个结点。

根据性质1，显然深度为k的二叉树的结点总数至多为：

性质3在任意二叉树中，若叶子结点（即度为零的结点）个数为n0，度为1的结点数为n1，度为2的结点个数为n2，那么有：n0＝n2＋1。

设n代表二叉树结点总数，那么

n＝n0＋n1＋n2（4.2.1）

由于有n个结点的二叉树总分支数为n－1条，于是得

n－1＝0×n0＋1×n1＋2×n2（4.2.2）

将式（4.2.1）代入式（4.2.2）,得

n0＝n2＋1

在研究后面的性质之前，先介绍两种特殊形态的二叉树：满二叉树和完全二叉树。

一棵深度为k并且含有2k－1个结点的二叉树称为满二叉树，这种数的特点是每层上的结点数都是最大结点数，如图4－2－2（a）所示。对满二叉树的结点可以从根结点开始自上向下，自左向右顺序编号，图4－2－2（a）中每个结点斜上角的数字即是该结点的编号。深度为k，含有n个结点的二叉树，当且仅当其每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时，则称此二叉树为完全二叉树，如图4－2－2（b）所示。而图4－2－2（c）则不是完全二叉树。

4567

4567

EFD

A

BC

DEFG

1

23

A

BC

DEF

1

23

456

A

BC

1

23

456

（a）满二叉树（b）完全二叉树（c）非完全二叉树

图4－2－2