目录
二叉树的一些基本概念
节点的层数：根节点所在的层次规定为第1层，其孩子所在的层次为第2层，后代节点以此类推。
节点的度：一个节点拥有的子节点的个数，二叉树节点的度最大为2
叶子节点：二叉树中度为0的节点
树的深度：从根节点往下数
树的高度：从下往上数（有人认为根节点的深度为0有人认为为1具体情况具体分析，所以空树的高度可能为负一）
有序树无序树：节点有规律就是有序，没规律就是无序，二叉搜索树就是有序树
完美二叉树（满二叉树）：所有节点的度要么为0，要么为2，且所有的叶子节点都在最后一层
完全二叉树：叶子节点只会出现在最后2层，且最后一层的叶子节点都靠左对齐（如果把最后一层去掉就是满二叉树）
完满二叉树：树的每一个节点要么没有子节点，要么有两个子节点
BST（Binary Search Tree）二叉搜索树：树的每一个节点都满足小-中-大排序，任意一个节点的左孩子一定小于该节点，右孩子一定大于该节点，根节点左边的所有元素一定小于右边的所有元素，搜索树中不能出现重复元素
为什么要用二叉树：二叉树通常都是经过一些节点有固定顺序特殊排列的数据结构，这样是为了对比普通链表加快查找的效率，如果二叉树没有顺序，那就跟链表没什么区别
二叉树的遍历
利用递归方式实现，传入根节点，如果根节点不为空，则以根节点下一个需要访问的节点为根节点继续执行递归，一共有先序遍历，中序遍历，后续遍历三种遍历方式。
先序：根->左->右
代码实现：
int Before_tree(struct tree *root)
{
if (root == NULL) // 结束递归
{
return 0;
}
// 1.先访问根节点
printf("%d ", root->data);
// 2.访问左节点
Before_tree(root->left);
// 3.访问右节点
Before_tree(root->right);
}
中序：左->根->右
代码实现：
int Middle_tree(struct tree *root)
{
if (root == NULL)
{
return 0; // 结束递归
}
// 1.先访问左节点
Middle_tree(root->left);
// 2.访问根节点
printf("%d ", root->data);
// 3.访问右节点
Middle_tree(root->right);
}
后序：左->右->根
代码实现
int After_tree(struct tree *root)
{
if (root == NULL){
return 0; // 结束递归
}
// 1.先访问左
After_tree(root->left);
// 2.再访问右
After_tree(root->right);
// 3.最后访问根
printf("%d ", root->data);
}
可以看到，二叉树的先序中序和后序遍历的不同之处其实就在于下一个要访问的节点的递归的位置，通过移动这个位置就可以改变遍历方式
二叉搜索树BST
下面以BST为例进行二叉树的完整设计，包括节点设计，初始化，插入，查找，删除
节点设计
每一个二叉树节点中包含一个数据域和两个指针域，一个指向左孩子一个指向右孩子，有点类似我们的双链表
struct tree
{
int data;
struct tree *lchild;
struct tree *rchild;
}
初始化根节点
因为二叉树的根节点也作为一个值需要被遍历输出，插入的话用bst递归插入，所以头节点可以是任意的值，因为会在后面的插入中被自动排序
struct tree *create_node(int val)
{
struct tree *xnew = malloc(sizeof(struct tree));
if(xnew == NULL)
{
printf("创建节点失败");
exit(1);
}
xnew->data = val;
xnew->lchild = NULL;
xnew->rchild = NULL;
}
递归实现bst插入
struct tree *bstInsert(node *root, node *new)
{
// 若此时 BST 为空，则返回 new 使之成为二叉树的根节点
if(root == NULL)
return new;
//如果插入节点小于根节点，则把根节点变成左子节点继续递归插入，直到子节点为NULL跳出
if(new->data < root->data)
root->lchild = bstInsert(root->lchild, new);
//原理同上面
else if(new->data > root->data)
root->rchild = bstInsert(root->rchild, new);
else
{
printf("%d已存在\n", new->data);
free(new);
}
return root;
}
循环实现bst插入
void insert_node(struct tree *root, struct tree *xnew)
{
if (root == NULL){
printf("root 节点为NULL\n");
return;
}
struct tree *pos = root;
while (1)
{
// 开始比较
if (xnew->data > pos->data) // 右边
{
if (pos->right == NULL)
{
// 插入
pos->right = xnew;
return;
}
else
{
pos = pos->right; // 向右偏移
}
}
else if (xnew->data < pos->data) // 左边
{
if (root->left == NULL)
{
// 插入
root->left = xnew;
return;
}
else
{
pos = pos->left; // 向左偏移
}
}
}
}
查找节点
递归实现
struct tree *Rec_find(struct tree *root, int f_data)
{
//根节点为空直接返回空，意思是没有要找的元素
if (root == NULL)
{
return NULL;
}
//数据相同，返回该节点
if (root->data == f_data)
{
return root;
}
// 找的数据比节点大
if (f_data > root->data)
{
// 继续往右找
Rec_find(root->right, f_data);
}
//找的数据比节点小往左找
else if (f_data < root->data)
{
// 继续往左找
Rec_find(root->left, f_data);
}
}
循环实现
struct tree *find_node(struct tree *root, int f_data)
{
struct tree *pos = root; // 指向根节点
while (1)
{
if (pos == NULL)
{
printf("查无此数据\n");
return NULL;
}
if (pos->data == f_data) // 相等则找到
{
printf("找到数据%d\n", pos->data);
return pos;
}
if (f_data > pos->data)
{
// 右偏移
pos = pos->right;
}
else if (f_data < pos->data)
{
// 左偏移
pos = pos->left;
}
}
}
删除节点（重点）
二叉树的节点在删除时分为两种情况，第一种是要删除的元素是二叉树的叶子节点，此时直接将叶子节点的父亲节点置空，free掉叶子节点即可。
首先设计一个能查找要删除的节点和该节点的父节点的函数，可以由上面的查找函数修改
struct tree *Rec_find(struct tree *root, struct tree **fat, int f_data)
{
//根节点为空直接返回空，意思是没有要找的元素
if (root == NULL)
{
return NULL;
}
//数据相同，返回该节点
if (root->data == f_data)
{
return root;
}
// 找的数据比节点大
if (f_data > root->data)
{
*fat = root;
// 继续往右找
Rec_find(root->right, f_data);
}
//找的数据比节点小往左找
else if (f_data < root->data)
{
*fat = root;
// 继续往左找
Rec_find(root->left, f_data);
}
}
循环实现
struct tree *find_node_father(struct tree *root, struct tree **fat, int f_data)
{
struct tree *pos = root; // 指向根节点
while (1)
{
if (pos == NULL)
{
printf("查无此数据\n");
return NULL;
}
if (pos->data == f_data) // 相等则找到
{
return pos;
}
if (f_data > pos->data)
{
// 右偏移
*fat = pos;
pos = pos->right;
}
else if (f_data < pos->data)
{
// 左偏移
*fat = pos;
pos = pos->left;
}
}
}第一种情况：当要删除的节点是叶子节点时
void del_node(struct tree *root, int d_data)
{
struct tree *fat = NULL;
// 获取删除的节点与父亲节点
struct tree *del = find_node_father(root, &fat, d_data);
if (del == NULL)
{
printf("无此删除节点\n");
return;
}
printf("删除的节点 %p=%d\n", del, del->data);
printf("父亲的节点 %p=%d\n", fat, fat->data);
// 1.情况1 判断是否为子叶节点
if (del->left == NULL && del->right == NULL)
{
// 判断置空节点
if (d_data < fat->data) // 小于，left
{
fat->left = NULL;
}
else if (d_data > fat->data) // 大于,right
{
fat->right = NULL;
}
free(del);
return;
}
}
第二种情况，是要删除的节点并不是叶子节点，那这时候就要查找该节点的左子树的最大值或者右子树的最小值，然后直接替换掉这个要删除的节点，然后把这个节点给删除（因为左子树的最大值或者右子树的最小值肯定是一个叶子节点，所以按照情况一删除叶子节点即可）
下面是关键算法实现，可以直接添加到上面删除函数中
if (del->left != NULL)
{
// 查找左子树的最大节点
struct tree *L_MAX = del->left; // 指向左子树
struct tree *L_FAT = del;
while (L_MAX->right != NULL)
{
L_FAT = L_MAX; // 保存上一个节点的位置
L_MAX = L_MAX->right; // 不断往下找到最大
}
// 替换要删除的节点
del->data = L_MAX->data;
// 删除
free(L_MAX);
// 父节点置空
L_FAT->right = NULL;
return 1;
}
//否则向右寻找右子树的最小值
else if (del->right != NULL)
{
// 查找右子树的最小节点
struct tree *R_MIN = del->right; // 指向左子树
struct tree *R_FAT = del;
while (R_MIN->left != NULL)
{
R_FAT = R_MIN; // 保存上一个位置
R_MIN = R_MIN->left; // 不断往左走，找到最小节点
}
// 替换要删除的节点
del->data = R_MIN->data;
// 删除
free(R_MIN);
// 父节点置空
R_FAT->left = NULL;
return 1;
}
}
修改节点
如果这是一颗有序二叉树，那节点通常不能被修改，要不然二叉树就没有意义了，通过以下函数能修改二叉树
void change_tree(struct tree *root, int old_data, int new_data)
{
// 1.删除原来的数据
int ret = del_node(root, old_data);
// ret = 0，说明查无此节点，直接返回
if (ret == 0)
{
return;
}
// 2.插入新的节点
insert_node(root, create_node(new_data));
}