一、树
1、 树的定义：
树(tree)是n(n>0)个节点的有限集，在任意一棵树中，(1)有且仅有一个特定的称为根(root)的节点，(2)当n>1时，其余节点可分为m(m>0)个互不相交的有限集，而每个集合本身又是一棵树，称为根的子树(subtree)。
从上面树的定义中可以看到，这是一个递归的定义，即树的定义中又用到了树的概念。
2、 树结构中的基本术语：
树的结点包含一个数据元素及若干只指向其子树的分支。
结点拥有的子树数称为结点的度(degree)。
如图6.1(b)中，A的度为3，C的度为1，F的度为0。度为0的结点称为叶子(leaf)或终端结点。如图6.1(b)中，结点K, L, F, G, M, I, J度都为0，都是叶子。
度不为0的结点为非终端结点或分支结点，除根结点之外，分支结点也称内部结点。
树的度是数内各结点的度的最大值，如图6.1(b)中，树的度为3。
结点的子树的根称为该结点的孩子(Child)，该结点称为孩子的双亲(parent)，如图6.1(b)中，D为A的孩子，A是D的双亲，同一个双亲的孩子之间称为兄弟(sibling)，如H, I, J互为兄弟。
结点的层次(level)从跟开始定义，根为第一次，根的孩子为第二层，双亲在同一层的结点互为堂兄弟，如图6.1(b)中，结点G, E, F, H, I, J互为堂兄弟。
树种结点的最大层次为树的深度(depth)或高度，如图6.1(b)中，树的深度为4。
如果树中结点的各子树是有次序的不能互换的，此树为有序树，否则称为无序树。
森林(forest)是m(m≥0)棵互不相交的树的集合。
二、二叉树
1、二叉树的定义：
二叉树(binary tree)的特点：每个结点至多只有2棵子树，且子树有左右之分，次序不能颠倒。
3、 二叉树的性质：
(1) 在二叉树的第i层上至多有2i-1个结点(i≥1)
(2) 深度为k的二叉树至多有2k-1个结点(k≥1)
(3) 对任意一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4、 完全二叉树和满二叉树：
这是两种特殊形态的二叉树。
一棵深度为k且有2k-1个结点的二叉树称为满二叉树，每一层上的结点数都是最大。
对满二叉树的结点进行连续编号，当二叉树的每个结点都与相同深度的满二叉树中编号从1~n的结点一一对应时，此二叉树称为完全二叉树。
非完全二叉树：
5、 二叉树的存储结构：
(1) 顺序存储结构：
使用数组存储，如上面的完全二叉树，可以使用数组bt[12]，将编号为i的结点的数据元素存放在bt[i]中。
根据完全二叉树的特性，结点在向量中的相对位置蕴含着结点之间的关系，如bt[5]的双亲在bt[2]，他的左右孩子在bt[10]，bt[11]。但这种顺序存储结构仅适合于完全二叉树。如果一般的二叉树也按照这种方式存储，不存在的结点也需要占位。如对于下面的二叉树：
他的顺序存储结构如下：
这样非常浪费空间。
(2) 链式存储结构：
表示二叉树的链表至少包含三个域：数据域和左、右指针域（二叉链表），有时为了便于找到结点的双亲，还可以在结点结构中增加一个指向其双亲结点的指针域（三叉链表）。
//二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
三、遍历二叉树
1、 遍历的概念
二叉树是由三个基本单元组成：根结点，左子树，右子树，因此依次遍历这三部分，就遍历了整个二叉树，按遍历的顺序可划分为：前(根)序遍历（根->左子树->右子树），中(根)序遍历（左子树->根->右子树），后(根)序遍历（左子树->右子树->根）。
如图所示的二叉树：
前序遍历：A B D H I E J C F K G
中序遍历：H D I B E J A F K C G
后序遍历：H I D J E B K F G C A
前序遍历二叉树递归算法：
void PreOrderTraverse(BiTree T, int level)
{
if (T == NULL)
return;
PreOrderTraverse(T->lchild, level + 1);
PreOrderTraverse(T->rchild, level + 1);
}
2、 遍历的考题
(1) 根据前序、中序遍历的结果，求后序遍历
例：
前序遍历：G D A F E M H Z
中序遍历：A D E F G H M Z
A． 根据前序遍历的特点，我们知道根结点为G
B． 观察中序遍历A D E F G H M Z。其中根节点G左侧的A D E F必然是根结点的左子树，G右侧的H M Z必然是根结点的右子树。
C． 观察左子树A D E F，左子树中的根节点必然是根的左孩子。在前序遍历中，根结点的左孩子位于根结点G之后，所以左子树的根节点为D，根据中序遍历的结果D的左侧A是左子树，D的右侧E F是右子树，以此类推。
D． 同样的道理，根结点的右子树节点H M Z中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把根结点和根结点的所有左子树节点遍历完之后才会遍历右子树，并且遍历的右子树的第一个节点就是右子树的根节点。所以根据前序遍历的结果，右子树节点H M Z的排序是M H Z，因此M是右子树的根结点，按照中序遍历的结果M的左侧H是左子树，M的右侧Z是右子树，以此类推。
E． 观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。
F． 那么这棵树就是这样的
(2) 根据中序、后序遍历的结果，求前序遍历
例：
中序遍历：A D E F G H M Z
后序遍历：A E F D H Z M G
A. 根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G.
B. 观察中序遍历A D E F G H M Z。其中根结点G左侧的ADEF必然是根结点的左子树， G右侧的H M Z必然是根结点的右子树。
C. 观察左子树A D E F，左子树的根节点必然是根结点的左孩子。在后序遍历中，根结点是最后一个遍历的，根据后续遍历的结果，D是左子树最后一个遍历的结点，因此D就是左子树的根节点，按照中序遍历的结果D的左侧A是左子树，D的右侧E F是右子树，以此类推。
D. 同样的道理，根结点的右子树H M Z中的根节点也可以通过后序遍历求得。在后序遍历中，一定是最后才遍历根结点，根据后续遍历的结果，M是右子树的根结点，按照中序遍历的结果M的左侧H是左子树，M的右侧Z是右子树，以此类推。
E. 上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了
