第六章 二叉树

    在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述，而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。

    所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构和图型就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系，如前面提到的族谱、城市交通等。在本书的第六、七、八章将重点讨论这两类非线性结构的有关概念、存储结构、在各种存储结构上所实施的一些运算以及有关的应用实例。

    本章对树型结构中最简单、应用十分广泛的二叉树结构进行讨论。

6.1  定义与性质

    6.1.1  二叉树的基本概念

    1．二叉树

    二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种基本形态，如图6.1所示。

左子树

左子树

左子树

左子树

Ф

 

  (a)      (b)              (c)                 (d)                           (e)

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

    2．二叉树的相关概念

    （1）结点的度。结点所拥有的子树的个数称为该结点的度。

    （2）叶结点。度为0的结点称为叶结点，或者称为终端结点。

    （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。

    （4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。

（5）路径、路径长度。如果一棵树的一串结点n₁,n₂,…,n_k有如下关系：结点n_i是n_i+1的父结点（1≤i）,就把n₁,n₂,…,n_k称为一条由n₁至n_k的路径。这条路径的长度是k-1。

    （6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。

    （7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。

    （8）树的深度。树中所有结点的最大层数称为树的深度。

    （9）树的度。树中各结点度的最大值称为该树的度。

    （10）满二叉树。

    在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。如图6.2所示，（a）图就是一棵满二叉树，（b）图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树。

A

B

C

D

G

E

H

F

I

1

2

5

3

6

9

8

4

A

B

C

D

E

G

F

H

I

K

J

M

L

N

O

1

5

2

3

4

6

7

8

9

10

11

12

13

14

15

7

 

           (a) 一棵满二叉树                                (b) 一棵非满二叉树

                        图6.2  满二叉树和非满二叉树示意图

    （11）完全二叉树。

    一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图6.3所示（a）为一棵完全二叉树，（b）和图6.2（b）都不是完全二叉树。

A

C

B

E

D

F

G

H

I

J

1

2

4

3

5

6

8

9

10

A

B

D

C

E

F

G

1

1

4

3

5

7

7

6

 

           (a) 一棵完全二叉树                            (b) 一棵非完全二叉树

                        图6.3  完全二叉树和非完全二叉树示意图

    6.1.2 二叉树的主要性质

    性质1  一棵非空二叉树的第i层上最多有2^i-1个结点（i≥1）。

该性质可由数学归纳法证明。证明略。

    性质2  一棵深度为k的二叉树中，最多具有2^k－1个结点。

k ∑ i=1

k ∑ i=1

    证明  设第i层的结点数为x_i（1≤i≤k），深度为k的二叉树的结点数为M，x_i最多为2^i-1，则有：

            M＝   x_i≤   2^i-1 ＝2^k-1

性质3  对于一棵非空的二叉树，如果叶子结点数为n₀，度数为2的结点数为n₂，则有:

        n₀＝n₂＋1。

    证明  设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：

            n＝n₀＋n₁＋n₂