本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍

历算法。树和二叉树的各种存结构以及建立在各种存储结构上的操作及应用等。

1.树的定义

树(Tree)是 n(n≧0)个结点的有限集合 T，若 n=0 时称为空树，否则：

⑴ 有且只有一个特殊的称为树的根(Root)结点；

⑵ 若 n＞1 时，其余的结点被分为 m(m＞0)个互不相交的子集 T1, T2, T3…Tm，其中每个

子集本身又是一棵树，称其为根的子树。这是树的递归定义，即用树来定义树，而只有一个

结点的树必定仅由根组成，如图所示。

2.树的基本术语

(1) 结点(node)：一个数据元素及其若干指向其子树的分支。

(2) 结点的度(degree) 、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最

大值称为树的度。

图(b)中结点 A 的度是 3 ，结点 B 的度是 2 ，结点 M 的度是 0，树的度是 3