第3章 非线性数据结构
第3章 非线性数据结构
3.1 树及其基本概念 3.2 二叉树
3.2.1 二叉树的定义及其性质 3.2.2 二叉树的存储结构
3.3 二叉树的遍历 3.4 树的存储结构和遍历
第3章 非线性数据结构
3.1 树及其基本概念
树型结构是一种应用十分广泛的非线性数据结构， 它很类似自然界中的树，直观地讲，树型结构是以分 支关系定义的层次结构。
第3章 非线性数据结构 A
B
C
D
E
F
G
H
I
J
图3-1 树型结构
第3章 非线性数据结构
下面结合图3-1，给出树型结构中的一些基本术语。 结点的度：一个结点拥有的子树数目。如A结点的 度为3，它有三个子树T1、T2和T3。E、F结点的度为0， 它们没有子树。 叶子：度为零的结点称叶子或终端结点。 树的度：一棵树上所有结点的度的最大值就是这 棵树的度。
第3章 非线性数据结构
3.2 二 叉 树
3.2.1 二叉树的定义及其性质 1．二叉树的定义 一个二叉树是一个有限结点的集合，该集合或者
为空，或由一个根结点和两棵互不相交的被称为该根 的左子树和右子树的二叉树组成。二叉树中每个结点 最多只能有两棵子树，并且有左右之分，即有序。 二叉树有下面两个主要特点：
第3章 非线性数据结构 A
B
C
D
E
F
G
H
I
J
图3-1 树型结构
第3章 非线性数据结构
结点的层次：根结点的层数为1，其它任何结点的 层数等于它的父结点的层数加1。
树的深度：一棵树中，结点的最大层次值就是树 的深度。图3-1中树的深度为4。
森林：森林是m(m≥0)棵互不相交的树的集合。 孩子(child)：某结点子树的根称为该结点的孩子结 点。 如B、C、D是A的孩子。
性质4：具有n个结点的完全二叉树的深度为
⌊log2n⌋+1 。
第3章 非线性数据结构
性质5：如果对一棵有n个结点的完全二叉树的结点按 层序编号(从第1层到第⌊log2n⌋+1层，每层从左到右)，则 对任一结点i(1≤i≤n)，有
(1) 如果i=1，则i是二叉树的根，无双亲；如果i>1，则 其双亲是结点i/2。
第3章 非线性数据结构
双亲(parent)：一个结点是它的那些子树的根的双 亲结点。如A是B、C、D的双亲。
兄弟(sibling)：同一个双亲的孩子之间互为兄弟。B、 C、D是A的孩子；B、C、D互为兄弟。
堂兄弟(cousins)：其双亲在同一层的结点互为堂兄 弟。如G与E、F、H、I互为堂兄弟。
k
2 i 1 = 2k−1
i1
第3章 非线性数据结构
下面介绍两种特殊形态的二叉树，满二叉树和完全二叉树。 如果一棵二叉树的深度为k，并且含有2k–1个结点，则称此
二叉树为满二叉树。图3-6是一棵深度为4的满二叉树。
A
B
C
D
E
F
G
H
I
J
K L MN O
图3-6 深度为4的满二叉树
第3章 非线性数据结构
(2) 如果2i>n，则结点i无左孩子；否则其左孩子是2i。 (3) 如果2i+1>n，则结点i无右孩子；否则其右孩子是结 点2i+1。 证明从略。
第3章 非线性数据结构 A
B
C
D
E
F
G
H
I
J
图3-1 树型结构
第3章 非线性数据结构
这是一个递归定义，即在树的定义中又用到了树， 即一棵树是由若干棵子树构成的，而子树又可由若干 棵更小的子树构成。树中的每一个结点都是该树中某 一棵子树的根。
如图3-1所示的树中，A为根结点，其余的结点分 为三个互不相交的有限集合：T1={B，E，F}，T2={C， G，J}，T3={D，H，I}。T1、T2和T3都是A的子树，而 它们本身也是一棵树。例如，T1是一棵以B为根的树， 其余结点分为互不相交的两个集合{E}和{F}，而{E}和 {F}本身又是仅有一个根结点的树。
2．二叉树的性质
二叉树具有下列重要特性。
性质1：在二叉树中，第i层的结点数最多有2i-1(i≥1)个。
例如：层次i
第i层最多结点数
1
20=1
2
21=2

22=4
k
2k−1
此性质可以用数学归纳法证明。
第3章 非线性数据结构
性质2：在深度为k的二叉树中结点总数最多有2k–1个。 由性质1可见，深度为k的二叉树的最大结点数为：
第3章 非线性数据结构
(1) 每个结点最多只能有两个孩子，即二叉树中不 存在度大于2的结点。
(2) 二叉树的子树有左、右之分，其次序不能任意 颠倒。二叉树可以有五种基本形态，如图3-2所示。
第3章 非线性数据结构
(a)
(b)
(c)
(d)
(e)
图3-2 二叉树的五种基本形态
第3章 非线性数据结构
第3章 非线性数据结构
有序树：若将树中每个结点的各子树看成是从左 到右有次序的(即不能互换的)，则称该树为有序树，否 则为无序树。作为有序树，图6.26中的两棵树是不同的， 因为结点A的两个孩子在两棵树中的左右次序不同。以 后若不特别指明，所讨论的树都是有序树。
A
A
B
CC
B
图6.26 两棵不同的有序树
树(Tree)是n(n≥0)个结点的有限集合。在树形图中， 结点常用圆圈表示，结点的名字一般写在圆圈旁边， 有时亦可写在圆圈内。当n=0时称为空树，否则在任一 非空树中：
第3章 非线性数据结构
(1) 有且仅有一个称为该树之根的结点； (2) 除根结点之外的其余结点可分为m(m≥0)个互不 相交的集合T1，T2，…，Tm，且其中每一个集合本身 又是一棵树，并且称为根的子树(SubTree)。
结点都与深度为k的满二叉树中的编号从1到n的结点一
一对应时，称之为完全二叉树。如图3-8所示是一棵深
度为4的完全二叉树。
1
2
4
5
3
6
7
8
9
10 11 12
图3-8 深度为4的完全二叉树
第3章 非线性数据结构
完全二叉树是一个十分重要的概念，在许多算法和算 法分析中，都明显或隐含地用到了完全二叉树的概念。 下面介绍完全二叉树的两个重要特性。
可以看出这种树的特点是每一层的结点数都是最大 结点数。
对满二叉树的结点进行连续编号：从根结点起，自 上而下逐层从左到右给每个结点编一个从1开始的顺序 号。图3-6就成为图3-7。
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
图3-7 深度为4的满二叉树
第3章 非线性数据结构
深度为k，有n个结点的二叉树，当且仅当其每一个