6.2 树的定义

之前我们一直在谈的是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们需要研究这种一对多的数据结构——“树”，考虑它的各种特性，来解决我们在编程中碰到的相关问题。

树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。

在任意一棵非空树中：

• 有且仅有一个特定的称为根（Root）的结点；
• 当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念，这是一种比较新的定义方法。图6-2-2的子树T 1 和子树T 2 就是根结点A的子树。当然，D、G、H、I组成的树又是B为根结点的子树，E、J组成的树是以C为根结点的子树。

对于树的定义还需要强调两点： 1.n>0时根结点是唯一的，不可能存在多个根结点。 2.m>0时，子树的个数没有限制，但它们一定是互不相交的。