树结构是一类重要的非线性数据结构。直观来看，树是以分支关系定义的层次结构。树结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。
树在计算机领域中也得到广泛应用，尤以二叉树最为常用。如在操作系统中，用树来表示文件目录的组织结构。在编译系统中，用树来表示源程序的语法结构。在数据库系统中，树结构也是信息的重要组织形式之一。
1、树的定义 1.1、树的定义
树(Tree)是n(n>=0)个结点的有限集，它或为空树(n= 0);,或为非空树，对千非空树T:
(1) 有且仅有一个称之为根的结点；
(2) 除根结点以外的其余结点可分为 m(m>0）个互不相交的有限集 T1, T2 , …，Tn，其中每
一个集合本身又是一棵树，并且称为根的子树(SubTree)。
1.2、树的相关术语
这里结合图1 （b）为例：
结点:树中的一个独立单元。包含一个数据元素及若于指向其子树的分支。如图 A 、 B 、 C 、 D 等。
结点的度：结点拥有的子树数称为结点的度。例如，A的度为 3, C的度为1, F的度为0。
树的度:树的度是树内各结点度的最大值。图 1 (b) 所示的树的度为3。
叶子/终端结点： 度为 0 的结点称为叶子或终端结点。结点 K 、 L 、 F 、 G 、 M 、 I 、 J都是树的叶子。
非终端结点：度不为 0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A, B的孩子有E和F。
兄弟:同一个双亲的孩子之间互称兄弟。例如，H 、 I 和J互为兄弟。
祖先:从根到该结点所经分支上的所有结点。例如， M 的祖先为 A 、 D 和 H。
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如 B 的子孙为 E 、 K 、 L和 F。
层次:结点的层次从根开始定义起，根为 第一层，根的孩子为第二层。树中任一结点的层次等千其双亲结点的层次加 1。
堂兄弟:双亲在同 一层的结点互为堂兄弟。 例如，结点 G 与E 、 F、 H 、 I 、 J互为堂兄弟。
树的深度:树中结点的最大层次称为树的深度或高度。图1 (b)所示的树的深度为4。
有序树和无序树:如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林:是 m (m>0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树。
1.3、二叉树的定义
二叉树(Binary Tree)是n(n>=0)个结点所构成的集合，它或为空树(n =0); 或为非空树，对于非空树T:
(1) 有且仅有一个称之为根的结点；
(2) 除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：
(1) 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大千2 的结点）；
(2) 二叉树的子树有左右之分，其次序不能任意颠倒。
1.4、二叉树的性质
二叉树具有下列重要特性：
性质1 二叉树第i(i≥1)层上的结点数最多为 2^i-1^。
性质2 高度为k的二叉树最多有 2^k^-1 个结点。
性质3 对任何二叉树T,设n~0~、n~1~、n~2~ 分别表示度数为 0、 1、 2 的结点个数， 则 n~0~=n~2~+1。
满二叉树和完全二叉树：
满二叉树和完全二叉树是二叉树的两种特殊情形。
一棵深度为 A 且有 2^k^ -1 个结点的二叉树称为满二叉树。
如图 3 所示是深度分别为 1、 2、 3 的满二叉树。 满二叉树的特点是每一层上的结点数都达到最大值， 即对给定的深度， 它是具有最多结点数的二叉树。 满二叉树不存在度数为 1 的结点， 每个分支结点均有两棵高度相同的子树， 且树叶都在最下一层上。
