C语言实现二叉树：从基础到应用
C语言实现二叉树：从基础到应用
二叉树（binary tree）是树（tree）的一种特殊形式，树（tree）的节点后面可以有任意多个后继，而二叉树 (binary tree) 每个节点后面最多两个后继。这种结构更容易实现也更有实际意义。
二叉树的简介
每个节点后面最多两个子树，还具有位置关系，分别是左子树（left）和右子树（right）。所以在实现时，二叉树的节点结构也就有了两个指针分别指向左子树（left）和右子树（right）。实现二叉树用的最多的方法就是递归（简单来理解就是套娃(￣▽￣)*）。
二叉树的节点结构
typedef struct bitree {
char date;
struct bitree* lch, *rch;
}bitree;
定义一个int类型data来容纳节点元素（还可以根据需要来定义元素类型例如int，double等）还有定义指向左右子节点的指针。
二叉树的初始化
本文实现中用了‘#’来代表节点内容为空。先初始化节点在依次遍历左节点和右节点就是先序遍历初始化，所以在后面输入元素时要按照先序遍历的顺序输入元素节点。
void bitree_init(bitree **bt)
{
char ch;
ch = getchar();
if (ch =='#')
{
*bt= NULL;
return;
}
else {
(*bt) = (bitree*)malloc(sizeof(bitree));
(*bt)->date = ch;
bitree_init(&(*bt)->lch);
bitree_init(&(*bt)->rch);
}
}
二叉树的中序遍历输出
在这里就只介绍中序遍历，后面先序遍历以及后序遍历各位应该看的出来了，就是取决于实现一步骤的位置。后面可以用这些先序，中序，后序的实现来完成数据结构后面的习题和加深对遍历的理解
void bitree_inorder(bitree* bt)
{
if (bt)
{
bitree_inorder(bt->lch);
printf("%c", bt->date);
bitree_inorder(bt->rch);
}
}
遍历计算二叉树的叶子数
通过二叉树的结构，我们知道叶子节点的特征是叶子节点的左右指针应该都是空，我们可与通过遍历查找和运用int函数返回累加值来计算二叉树的叶子总数
int bitree_count(bitree* bt)
{
if (bt == NULL)
{
return 0;
}
else if (bt->lch == NULL && bt->rch == NULL)
{
return 1;//如果满足二叉树叶子节点特征就返回1，累加到int函数
}
else
{
return bitree_count(bt->lch) + bitree_count(bt->rch);
}
}
遍历计算二叉树得深度
同样用int函数来实现累加，分别遍历左右子树来实现对深度计算，最后还比较左右子树的输出的深度打大小，来决定输出最大的深度就是函数的深度。
int bitree_depth(bitree* bt)
{
if (bt == NULL)
{
return 0;
}
else
{
int rdepth = bitree_depth(bt->rch);
int ldepth = bitree_depth(bt->lch);
return (rdepth > ldepth) ? rdepth + 1 : ldepth + 1;//三元运算表示法
}
}
三元表示法的结构是（return+（表达式1>表达式2）？返回式1：返回式2），意思是如果return后面的比较式子成立就返回式1，否知就返回式2可以用于代替if-else语句，结构上更简洁容易阅读
二叉树的复制
利用先序遍历将树的元素复制到另一个新建的二叉树上。
void copy(bitree* bt, bitree** s)
{
if (bt == NULL)//先判断树是否为空
{
*s = NULL;
return;
}
else
{
*s = (bitree*)malloc(sizeof(bitree));//分配空间给新树接收节点元素
(*s)->date = bt->date;
copy(bt->lch, &(*s)->lch);
copy(bt->rch, &(*s)->rch);
}
}
代码实现和验证
实现使用的例子如下图，实现例子先序遍历输入元素是ABD###CE#G##FH##J##，后面实现中的先序遍历输出和后序遍历没有在前面写出来但是通过同构中序遍历修改顺序就可以实现对应的不同顺序输出
int main()
{
bitree* bt;
bitree_init(&bt);
printf("中序遍历\n");
bitree_inorder(bt);
printf("\n");
printf("先序遍历\n");
bitree_preorder(bt);
printf("\n");
printf("后序遍历\n");
bitree_postorder(bt);
printf("\n");
printf("树的叶子数：%d", bitree_count(bt));
printf("\n");
printf("树的深度：%d", bitree_depth(bt));
printf("\n");
bitree* s;
copy(bt,&s);
printf("以下是复制的二叉树\n");
printf("先序遍历\n");
bitree_preorder(s);
printf("\n");
printf("中序遍历\n");
bitree_inorder(s);
printf("\n");
printf("后序遍历\n");
bitree_postorder(s);
printf("\n");
printf("树的叶子数：%d", bitree_count(bt));
printf("\n");
printf("树的深度：%d", bitree_depth(bt));
printf("\n");
return 0;
}
先对图例的二叉树进行一套操作，在复制到另一个树上再次实现，就不多赘述太多了，有图有真相，我们直接上图吧
如果有错请各位看官直接指出，小的虚心请教捏