本章先对二叉树的相关理论知识进行介绍，然后给出C语言的详细实现。
关于二叉树的学习，需要说明的是：它并不难，不仅不难，而且它非常简单。初次接触树的时候，我也觉得它似乎很难；而之所产生这种感觉主要是由于二叉树有一大堆陌生的概念、性质等内容。而当我真正的实现了二叉树再回过头来看它的相关概念和性质的时候，觉得原来它是如此的简单！因此，建议在学习二叉树的时候：先对二叉树基本的概念、性质有个基本了解，遇到难懂的知识点，可以画图来帮助理解；在有个基本的概念之后，再亲自动手实现二叉查找树(这一点至关重要!)；最后再回过头来总结一下二叉树的理论知识时，你会发现——它的确很简单！在代码实践中，我以"二叉查找树，而不是单纯的二叉树"为例子进行说明，单纯的二叉树非常简单，实际使用很少。况且掌握了二叉查找树，二叉树也就自然掌握了。
树是一种数据结构，它是由n（n>=1）个有限节点组成的一个具有层次关系的集合。
树的特点：
- 每个节点有0个或多个子节点
- 没有父节点的节点成为根节点
- 每一个非根节点的节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
若一个节点有子树，那么该节点成为该子树根的双亲，子树的根是该节点的孩子，有相同双亲的节点互为兄弟，一个节点的所有子树上的任何节点都是该节点的后裔，从根节点到某个节点路径上的所有节点都是该节点的祖先。
- 节点的度：节点拥有子树的数目
- 叶子：度为0的节点
- 分支节点：度不为0的节点
- 树的度：树中节点最大的度
- 层次：根节点的层次为1，其余节点的层次等于该节点的双节点的层次加1
- 树的高度：树中节点的最大层次
- 无序树：树中节点的各子树之间的次序是不重要的，可以互相交换位置
- 有序树：树中节点的各子树之间的次序是重要的，不可以互相交换位置
- 森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树，删去根，树即成为森林
二叉树是每个节点最多有两个子树的树结构。它有5种基本形态：
- 空集
- 根有空的左子树或者右子树
- 两者都为空
- 两者都不为空
- 二叉树的第i层上的节点数组最多为
$$2^{i-1}，i>=1$$ - 深度为k的二叉树至多有
$$2^k-1，k>=1$$ 个节点 - 包含n的节点的二叉树的高度至少为
$$log_2(n+1)$$ - 在任意一棵二叉树中，若终端节点的个数为$$n_0$$，度为2的节点树为$$n_2$$，则
$$n_0=n_2+1$$
证明：
证明：下面用"数学归纳法"进行证明。 (01) 当i=1时，第i层的节点数目为$$2^{i-1}=2^{0}=1$$。因为第1层上只有一个根结点，所以命题成立。 (02) 假设当i>1，第i层的节点数目为$$2^{i-1}$$。这个是根据(01)推断出来的！ 下面根据这个假设，推断出“第(i+1)层的节点数目为$$2^{i}$$”即可。 由于二叉树的每个结点至多有两个孩子，故"第(i+1)层上的结点数目“最多是”第i层的结点数目的2倍"。即，第(i+1)层上的结点数目最大值=$$2×2^{i-1}=2^{i}$$。 故假设成立，原命题得证！
证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用"性质1"可知，深度为k的二叉树的结点数至多为：
证明：根据"性质2"可知，高度为h的二叉树最多有$$2^{h}–1$$个结点。反之，对于包含n个节点的二叉树的高度至少为$$log_2(n+1)$$。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)="0度结点数(n0)" + "1度结点数(n1)" + "2度结点数(n2)"。由此，得到等式一。
(等式一)
定义：高度为h，且有$$2^h-1$$个节点的二叉树。
定义：一棵二叉树中，只有最下的两层节点的度可以小于2，并且最下面一层的叶子节点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。
特点：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。显然，一棵满二叉树一定是一个完全二叉树，而完全二叉树未必是满二叉树。
定义：二叉查找树（Binary Search Tree），又称为二叉搜索树。设x为二叉查找树的的一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y]<key[x]，如果y是x右子树的一个节点，则key[y]>key[x]。
在二叉查找树中：
- 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的值
- 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的值
- 任意节点的左右值树也为二叉查找树
- 没有键值相等的节点（no duplicate nodes）
在实际应用中，二叉查找树用的比较多。
struct BSTreeNode {
int key;
struct BSTreeNode *left;
struct BSTreeNode *right;
struct BSTreeNode *parent;
} Node;二叉查找树的节点包含基本信息：
- key：它是关键字，是用来对二叉查找树的节点进行排序的
- left：它指向当前节点的左孩子
- right：它指向当前节点的右孩子
- parent：它指向当前节点的双亲
static Node* create_node(int key, Node* parent, Node* left, Node* right)
{
Node* p;
if((P = (Node *)malloc(sizeof(struct Node))) == NULL)
return NULL;
p->key = key;
p->left = left;
p->right = right;
p->parent = parent;
return p;
}若二叉树非空，则执行以下操作：
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
void preorder_bstree(Node* root)
{
if(root != NULL)
{
printf("%d ", root->key);
preorder_bstree(tree->left);
preorder_bstree(tree->left);
}
}若二叉树非空，则执行以下操作：
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
void inorder_bstree(Node* root)
{
if(root != NULL)
{
inorder_bstree(tree->left);
printf("%d ", root->key);
inorder_bstree(tree->left);
}
}若二叉树非空，则执行以下操作：
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
void postorder_bstree(Node* root)
{
if(root != NULL)
{
postorder_bstree(tree->left);
postorder_bstree(tree->left);
printf("%d ", root->key);
}
}
对上面的二叉树而言
- 前序遍历结果：3 1 2 5 4 6
- 中序遍历结果：1 2 3 4 5 6
- 后序遍历结果：2 1 4 6 5 3
递归版本的代码
Node* bstree_search(Node* root, int key)
{
if(root == NULL || root->key == key)
return root;
if(key < root->key)
return bstree_search(root->left, key);
else
return bstree_search(root->right, key);
}非递归版本的代码
Node* iterative_bstree_search(Node* root, int key)
{
while((root != NULL) && (root->key != key))
{
if(key < root->key)
root = root->left;
else
root = root->right;
}
return root;
}查找最大值的代码
Node* bstree_max(Node* x)
{
if(x == NULL)
return NULL;
while(x->right != NULL)
x = x->right;
return x;
}查找最小值的代码
Node* bstree_min(Node* x)
{
if(x == NULL)
return NULL;
while(x->left != NULL)
x = x->left;
return x;
}前驱：该节点的左子树中最大节点
后继：该节点的右子树中最小节点
查找前驱节点的代码
Node* bstree_predecessor(Node* x)
{
// 如果x存在左孩子，则x的前驱结点为以其左孩子为根的子树的最大结点
if(x->left != NULL)
return bstree_max(x->left);
// 如果x没有左孩子。则x有以下两种可能：
// (1) x是一个右孩子，则x的前驱结点为它的父结点。
// (2) x是一个左孩子，则查找x的最低的父结点，使得x为它的右孩子
Node* y = x->parent;
while((y != NULL) && (y->left == x))
{
x = y;
y = y->parent;
}
return y;
}查找后继节点的代码
Node* bstree_predecessor(Node* x)
{
// 如果x存在右孩子，则x的前驱结点为以其右孩子为根的子树的最小结点
if(x->right != NULL)
return bstree_min(x->right);
// 如果x没有右孩子。则x有以下两种可能：
// (1) x是一个左孩子，则x的后继结点为它的父结点。
// (2) x是一个右孩子，则查找x的最低的父结点，使得x为它的左孩子
Node* y = x->parent;
while((y != NULL) && (y->right == x))
{
x = y;
y = y->parent;
}
return y;
}插入节点的代码
static Node* bstree_insert(Node* tree, Node* z)
{
Node* y = NULL;
Node* x = tree;
// 查找z插入的位置
while(x != NULL)
{
y = x;
if(z->key < x->key)
x = x->left;
else
x = x->right;
}
// y就是要插入的节点的父节点
z->parent = y;
if(y == NULL)
tree = z;
else if(z->key < y->key)
y->left = z;
else
y->right = z;
return tree;
}注：本文实现的二叉查找树是允许插入相同键值的节点的！若用户不希望插入相同键值的节点，将bstree_insert()修改为以下代码即可。
while(x != NULL)
{
y = x;
if(z->key < x->key)
x = x->left;
else if(z->key > x->key)
x = x->right;
else
{
free(z);
return tree; //不修改，直接返回
}
}现有如下一棵二叉查找树
若要删除上图1中的任意节点，需要考虑以下三种情况：
- 需要删除的节点没有子节点
- 需要删除的节点只有一个子节点（左儿子或右儿子）
- 需要删除的节点右两个子节点（既有左儿子也有右儿子）
第一种情况直接删除即可。
下面讨论第二种情况：
若我们要删除的是3号节点，由图1可以看到，它下面还有一个4号子节点。由下图2，可以看出，对于这种办法，我们只需要想办法，让5号节点的左子树的指针指向4就可以了。
下面讨论第三种情况：
如果我们要删除的（例如3）的节点下，有2个子节点。如图3，我们先在需要删除的节点的右子树中，找到一个最小的值（因为右子树中的节点的值一定大于根节点）。然后，用找到的最小的值与需要删除的节点的值替换。然后，再将最小值的原节点进行删除（图4）
删除节点的代码
static Node* bstree_delete(Node* tree, Node* z)
{
Node* x = NULL;
Node* y = NULL;
// 如果要删除的节点是个叶子节点
if((z->left == NULL) && (z->right == NULL))
{
// 直接删除
// 如果要删除的是根节点
if(z->parent == NULL)
{
free(z);
return NULL;
}
else
{
if(z->parent->left == z)
{
z->parent->left = NULL;
free(z);
}
else
{
z->parent->right = NULL;
free(z);
}
}
return tree;
}
// 如果要删除的节点有1个子节点
else if((z->left == NULL) || (z->right == NULL))
{
// 记录要删除的节点的子节点
if(z->left != NULL)
y = z->left;
else
y = z->right;
// 如果要删除的是根节点
if(z->parent == NULL)
{
free(z);
return y;
}
else
{
// 要删除的节点的父节点原来的指向改为y
if(z->parent->left == z)
{
z->parent->left = y;
free(z);
}
else
{
z->parent->right = y;
free(z);
}
}
}
// 如果要删除的节点有2个子节点
else
{
y = bstree_successor(z); // 寻找后继节点
// 将要删除的节点的值改为后继节点的值
z->key = y->key;
// 删除y
return bstree_delete(tree, y);
}
}