5.1.1 什么是树

在学习二叉树的结构和行为之前，需要先给树下一个定义。数据结构中“树”的概念比较笼统，其中对树的如下递归定义最易于读者理解。

单个节点是一棵树，树根就是节点本身。设T1，T2，…，Tk是树，它们的根节点分别为n1，n2，…，nk。如果用一个新节点n作为n1，n2，…，nk的父亲，得到一棵新树，节点n就是新树的根。称n1，n2，…，nk为一组兄弟节点，它们都是节点n的子节点，称n1，n2，..，nk为节点n的子树。

一棵典型的树的基本结构如图5-1所示。

由此可见，树是由边连接起来的一系列节点，树的一个实例就是公司的组织结构图，例如图5-2所示的一家软件公司的组织结构。

图5-2展示了这家公司的结构，图中的每个方框是一个节点，连接方框的线是边。显然，由节点表示的实体（人）构成一个组织，而边表示实体之间的关系。例如，技术总监直接向董事长汇报工作，所以在这两个节点之间有一条边。销售总监和技术总监之间没有直接用边来连接，所以这两个实体之间没有直接关系。

由此可见，树是n(n≥0)个节点的有限集，作为“树”需要满足如下两个条件。

（1）有且仅有一个特定的称为根的节点。

（2）其余的节点可分为m个互不相交的有限集合T1，T2，…，Tm，其中，每个集合又都是一棵树（子树）。