什么是”树“
树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）
（2）有一个特定的结点被称为根结点或树根（root）
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
我们可以形式地给出树的递归定义如下:
单个结点是一棵树，树根就是该结点本身。
设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
相关概念：
- 节点的度：一个节点含有的子树的个数成为该节点的度
- 叶节点或终端节点：度为0的节点成为叶节点
- 非终端节点或分支节点：度不为0的节点
- 双亲节点或者父节点：若一个节点含有子节点，则这个节点成为其子节点的父节点
- 孩子节点或者子节点：一个节点含有的子树的根节点称为该节点的子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点
- 节点的层次：从根节点定义起，根节点为第一层，根节点的子节点为第二层，以此类推
- 树的高度或深度：树中最大的层次
- 堂兄弟节点：双亲在同一层的节点互称堂兄弟
- 节点的祖先：从根节点到该节点所经分支上的所有节点
- 子孙：以某节点为根的子树中任一节点都成为该节点的子孙
树的种类：
- 无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树
- 有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树
- 二叉树：每个节点最多含有两个子树的树称为二叉树
- 满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
- 完全二叉树: 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树.若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
- 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树
树的遍历：
- 先序遍历：从根节点开始，先遍历左子树，然后遍历右子树，在遍历子树的时候，依旧按照从根节点遍历左右子树的原则遍历(A,B,D,E,C,F)
- 中序遍历：从最左的叶子节点开始，先遍历左节点，然后根节点，再右节点(D,B,E,A,F,C)
- 后序遍历：从最左的叶子节点开始，先遍历左节点，然后右节点，再跟节点(D,E,B,F,C,A)
二叉树:
对树而言，需要重点掌握二叉树。二叉树是一种特殊的顺序树，它规定有左右两个孩子，即左右孩子顺序不能替换，所以二叉树是一种有序树。二叉树的结点数为大于0小于等于2。
二叉树性质：
对树而言，需要重点掌握二叉树。二叉树是一种特殊的顺序树，它规定有左右两个孩子，即左右孩子顺序不能替换，所以二叉树是一种有序树。二叉树的结点数为大于0小于等于2。对于二叉树，需要掌握以下性质：
性质1:
在二叉树的第i层上至多有
i=1，结点数为1
i=2，结点数为2
i=3，结点数为4
i=4，结点数为8
i=n, 结点数为:
性质2:
深度为K的二叉树至多有
换言之，如果二叉树的深度确定，则其最大的结点数也是确定的。
证明（可以利用性质1）
深度为K的二叉树的结点个数=二叉树中每一层结点个数的总和。即为：
（等比公式）
性质3:
二叉树中，终端结点
（注：度表示分支的个数，也指分支因子，终端结点也指叶子结点）
分析：二叉树中结点的度可以为0,1,2，也就是说需要证明结点的度为0与度为2的结点之间的关系是不变的。
证明：设二叉树中度为i的结点数为
则整棵二叉树的结点总数为：
除根结点外，每一个结点都是另一个结点的孩子，所以孩子数为(2):n-1
度为i(I = 0,1,2)的结点，有i个孩子，
孩子数 =
因为：(3) = (2),所以，
(4) – (1) ,得:
证毕.
性质1、2、3是二叉树的通用特性。
在介绍其它性质之前，先了解另一种特殊的二叉树，即满二叉树，其定义如下：
满二叉树是指深度为K，且有)2^{k}-1)个结点的二叉树。
特点：(1) 每层上结点数都达到最大
(2) 度为1的结点个数=0,即不存在分支数为1的结点
如下即为一棵满二叉树：(注意其顺序：结点层序编号方法，从根结点起从上至下逐层从左至右对二叉树的结点进行连续编号)
1
/ \
2 3
/ \ / \
4 5 6 7
完全二叉树：深度为k,结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。
1
/ \
2 3
/ \
4 5 （注意编号顺序，与满二叉树一一对应）
(向下取整)+ 1
由性质2及完全二叉树的定义有：
结点数满足：
可写成:
有:
向下取整，
性质5：在按层序编号的n个结点的完全二叉树中，任意一个结点i(1<=i<=n)有：
(1)i = 1时，结点i是树的根，否则(i> 1)，结点i的双亲为i/2(向下取整),如
2<=i=2.5<=3,取i = 2.
(2)2i > n时，结点i无左孩子，为叶结点，否则结点i的左孩子为结点2i
(3) 2i+1 > n时，结点i无右孩子，否则结点i的右孩子为结点2i +1.
性质4与性质五是针对完全二叉树而言的。性质6是针对二叉树的链式存储结构而言。
性质6: 含有n个结点的二叉链表中，有n + 1个空链域。
因为
又有
(2)-(1):
即
