基础定义

树（tree）是n(n>=0)个结点的有限集。

空树

n=0的树称为空树

任意一颗非空树中

1.有且仅有一个特定称为根（ROOT）的结点

2.当n>1时，其余结点可以分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其中每一个集合本身又是一棵树，并且称为根的子树

如图

树的定义需要注意

1.n>0时，根结点是唯一的，不可能存在多个根结点。

2.m>0时，子树的个数没有限制，但他们一定是互不相交的

如图，这些不符合树的定义

结点分类

结点的度

结点拥有的子树数称为结点的度

叶节点

度为0的结点称为叶结点，也成为终端结点

分支结点

度不为0的结点，也称费终端结点

树的度

树的度是树内各结点的度的最大值

如图所示，树的度为3

结点间的关系

结点的子树称为该结点的孩子（Child）,相应的，该结点称为孩子的双亲（Parent）。

同一个结点的孩子之间互称兄弟（Sibling）。

结点的祖先是从根到该结点间所经分支上的所有结点。

以某一结点为根的树的任意结点都成为根的子孙

树的其他相关概念

结点的层次

从根开始，根为第一层，根的孩子为第二层，以此类推，如图：

树的高度（深度）

结点的最大层次数称为树的高度，也成为深度

森林

n棵互不相交的树的集合

线性结构和树结构的对比

线性结构：

第一个元素：无前驱

最后一个数据元素，无后继

中间元素，一个前驱一个后继

树结构

根结点，无双亲，唯一

叶结点，无孩子，可以多个

中间结点，一个双亲多个孩子