c语言建立二叉树的算法代码(C语言数据结构二叉树实现)

大家好，又见面了，我是你们的朋友全栈君。

构造二叉树结点结构

typedef struct BT
{
    char data;
    struct BT *l_chrild;
    struct BT *r_chrild;
}BT;

• 创建二叉树

BT* Create_tree()// 创建二叉树
{
    BT *bt;
    char x;
    scanf("%c",&x);
    getchar();

    if (x == '0')
    {
        bt = NULL;
    }
    else
    {
        bt = (BT *)malloc(sizeof(BT));
        bt->data = x;

        printf("请输入 %c 的左子树\n", bt->data);
        bt->l_chrild = Create_tree();   // 

        printf("请输入 %c 的右子树\n",bt->data);
        bt->r_chrild = Create_tree();
    }
    return bt;

}

先序遍历二叉树：思路，

• 当二叉树不为空时
• 访问根节点
• 遍历根节点左子树
• 遍历根节点右子树
• 其他遍历类似

void pre_order(BT *bt)  // 先序遍历
{
    // 体会递归思想：是如何执行的分两次结束，一次是左右孩子为空，或者此程序执行结束。
    if (bt == NULL)
        return;
    else
    {
        printf("%c ", bt->data);   // 根
        pre_order(bt->l_chrild);   // 左
        pre_order(bt->r_chrild);  // 右
    }
}

中序遍历：

void ln_order(BT *bt)  // 中序遍历
{
    if (bt == NULL)
    return ;
    else
    {
        ln_order(bt->l_chrild);   // 左
        printf("%c ", bt->data); // 根
        ln_order(bt->r_chrild); // 右
    }
}

后序遍历：

void post_order(BT *bt)  // 后序遍历
{
    if (bt == NULL)
        return;
    else
    {
        post_order(bt->l_chrild);  // 左
        post_order(bt->r_chrild); // 右
        printf("%c ", bt->data); // 根
    }
}

层次遍历：
遍历从二叉树的根节点开始，首先将根节点指针入队，然后从队头取出一个元素，每取一个元素，执行下面的操作
1>访问该元素所指结点(就是输出)
2> 若该元素所指结点的，左，右孩子节点非空，则将该元素所指结点的左孩子指针和右孩子指针一次入队

void lever_order(BT * bt)  // 层次遍历
{
    //入队顺序，跟，左，右，左子树的左孩子，左子树的右孩子，右子树的左孩子，右子树的右孩子，出对顺序就是这
    int i, j;
    BT *q[100], *p;
    p = bt;

    if (p != NULL)    // 若二叉树非空，则跟根结点地址入队
    {
        i = 1;      // i指向对头
        q[i] = p;  
        j = 2;    // j指向对尾
    }

    while (i != j)  // 当队列不为空时执行循环
    {
        p = q[i];
        printf("%c ",p->data);    // 访问首结点的数据域
        if (p->l_chrild != NULL)  // 将出队结点的左孩子的地址入队
        {
            q[j] = p->l_chrild;
            j++;
        }
        if (p->r_chrild != NULL)
        {
            q[j] = p->r_chrild;  // 将出队结点的右孩子的地址入队
            j++;
        }
        i++;
    }
}

求叶子结点数:

// 思想：从根节点开始，当根节点的左右孩子都为空，则count+1，递归便历
void leaf_num(BT *bt, int *count)  // 求叶子结点数
{
    if (bt != NULL)  // 当结点为空时返回调用处
    {
        //当左右孩子都为空时，说明已该节点为叶子节点
        if (bt->l_chrild == NULL && bt->r_chrild == NULL)
        {
        // (*count)++; // 计数器
            ++*count;  // 两个都行注意运算符优先级
        }

        leaf_num(bt->l_chrild, count);
        leaf_num(bt->r_chrild, count);

    }
}

求结点个数:

// 与叶子节点类似，如果根节点不为空，node+1 递归遍历
void node_num(BT  *bt, int *node) //结点个数
{
    if (bt != NULL) // 当该节点为空时，返回调用处
    {
        (*node)++;
        node_num(bt->l_chrild, node); // 便历左右子树
        node_num(bt->r_chrild, node);
    }
}

求二叉树深度：
这个一定要好好想想
思路：

• 从二叉树的根节点开始：
• 若二叉树根节点为空，返回0，
• 否则：
• 递归统计左子树的深度，
• 递归统计右子树的深度。
• 递归结束，返回左右子树深度的较大值，即二叉树的深度

int tree_depth(BT *bt) // 二叉树深度，就是最大层数
{
    int l_dep, r_dep;  //定义两个变量，存放左，右子树的深度

    if (bt == NULL)
        return 0;
    else
    {
        l_dep = tree_depth(bt->l_chrild); //左右子树的深度标记
        r_dep = tree_depth(bt->r_chrild);

        if (l_dep > r_dep)  // 比较来个深度，较大的加1返回,值得注意的是当此程序呢每一次调用自然执行到最后(而不是bt==NULL)返回的值到调用处 进行自增
            return l_dep+1;
        else
            return r_dep+1;
    }

}

• 镜像二叉树,又称翻转二叉树：

// 就是所有节点对换, 也可以用非递归用栈实现，与此类似
//这里是递归实现
void reversal(BT *bt) // 镜像二叉树
{
    BT *p;
    if (bt == NULL) 
    {
        return ;
    }
    //交换两个节点，相当于t=a;a=b;b=t;
    p = bt->l_chrild;
    bt->l_chrild = bt->r_chrild;
    bt->r_chrild = p;

    if (bt->l_chrild)  // 遍历左子树，此时的左子树应给是，原来的右子树（原来左右都不为空时）
        reversal(bt->l_chrild);
    if (bt->r_chrild)
        reversal(bt->r_chrild);
}

括号二叉树：

void kuohao(BT *bt) //括号显示二叉树
{
    if (bt != NULL)
    {
        printf("%c", bt->data);
        if (bt->l_chrild || bt->r_chrild)
        {
            printf("(");
            kuohao(bt->l_chrild);
            if (bt->r_chrild)
                printf(",");
            kuohao(bt->r_chrild);
                printf(")");
        }
    }
}

凹入法显示二叉树：

void print_space(BT *bt, int t)  // 凹入法显示二叉树,利用中序遍历，也可以先，后序遍历，就是在输出时加上一个循环
{
    int i;
    if (bt)
    {
        print_space(bt->l_chrild, t+3); 
        for (i = 0; i < t; i++)
        {
            printf("*");
        }
        printf("%10c\n",bt->data);
        print_space(bt->r_chrild, t+3);
    }
}

源代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct BT
{
char data;
struct BT *l_chrild;
struct BT *r_chrild;
}BT;
void show_fun()
{
printf(" 二叉树子系统 \n");
printf("*******************************************\n");
printf("* 1-------建二叉树 *\n");
printf("* 2-------先序遍历 *\n");
printf("* 3-------中序遍历 *\n");
printf("* 4-------后序遍历 *\n");
printf("* 5-------层次遍历 *\n");
printf("* 6-------求叶子数 *\n");
printf("* 7-------求结点数 *\n");
printf("* 8-------求深度 *\n");
printf("* 9-------镜像二叉树 *\n");
printf("* 10-------括号显示 *\n");
printf("* 11-------凹入显示 *\n");
printf("* 0-------返回 *\n");
printf("*******************************************\n");
}
BT* Create_tree()// 创建二叉树
{
BT *bt;
char x;
scanf("%c",&x);
getchar();
if (x == '0')
{
bt = NULL;
}
else
{
bt = (BT *)malloc(sizeof(BT));
bt->data = x;
printf("请输入 %c 的左子树\n", bt->data);
bt->l_chrild = Create_tree();   // 
printf("请输入 %c 的右子树\n",bt->data);
bt->r_chrild = Create_tree();
}
return bt;
}
void pre_order(BT *bt)  // 先序遍历
{
// 体会递归思想：是如何执行的分两次结束，一次是左右孩子为空，或者此程序执行结束。
if (bt == NULL)
return;
else
{
printf("%c ", bt->data);   // 根
pre_order(bt->l_chrild);   // 左
pre_order(bt->r_chrild);  // 右
}
}
void ln_order(BT *bt)  // 中序遍历
{
if (bt == NULL)
return ;
else
{
ln_order(bt->l_chrild);   // 左
printf("%c ", bt->data); // 根
ln_order(bt->r_chrild); // 右
}
}
void post_order(BT *bt)  // 后序遍历
{
if (bt == NULL)
return;
else
{
post_order(bt->l_chrild);  // 左
post_order(bt->r_chrild); // 右
printf("%c ", bt->data); // 根
}
}
// 
void lever_order(BT * bt)  // 层次遍历
{
//入队顺序，跟，左，右，左子树的左孩子，左子树的右孩子，右子树的左孩子，右子树的右孩子，出对顺序就是这
int i, j;
BT *q[100], *p;
p = bt;
if (p != NULL)    // 若二叉树非空，则跟根结点地址入队
{
i = 1;      // i指向对头
q[i] = p;  
j = 2;    // j指向对尾
}
while (i != j)  // 当队列不为空时执行循环
{
p = q[i];
printf("%c ",p->data);    // 访问首结点的数据域
if (p->l_chrild != NULL)  // 将出队结点的左孩子的地址入队
{
q[j] = p->l_chrild;
j++;
}
if (p->r_chrild != NULL)
{
q[j] = p->r_chrild;  // 将出队结点的右孩子的地址入队
j++;
}
i++;
}
}
// 思想：从根节点开始，当根节点的左右孩子都为空，则count+1，递归便历
void leaf_num(BT *bt, int *count)  // 求叶子结点数
{
if (bt != NULL)  // 当结点为空时返回调用处
{
//当左右孩子都为空时，说明已该节点为叶子节点
if (bt->l_chrild == NULL && bt->r_chrild == NULL)
{
// (*count)++; // 计数器
++*count;  // 两个都行注意运算符优先级
}
leaf_num(bt->l_chrild, count);
leaf_num(bt->r_chrild, count);
}
}
// 与叶子节点类似，如果根节点不为空，node+1 递归遍历
void node_num(BT  *bt, int *node) //结点个数
{
if (bt != NULL) // 当该节点为空时，返回调用处
{
(*node)++;
node_num(bt->l_chrild, node); // 便历左右子树
node_num(bt->r_chrild, node);
}
}
int tree_depth(BT *bt) // 二叉树深度，就是最大层数
{
int l_dep, r_dep;  //定义两个变量，存放左，右子树的深度
if (bt == NULL)
return 0;
else
{
l_dep = tree_depth(bt->l_chrild); //左右子树的深度标记
r_dep = tree_depth(bt->r_chrild);
if (l_dep > r_dep)  // 比较来个深度，较大的加1返回,值得注意的是当此程序呢每一次调用自然执行到最后(而不是bt==NULL)返回的值到调用处 进行自增
return l_dep+1;
else
return r_dep+1;
}
}
// 就是所有节点对换, 也可以用非递归用栈实现，与此类似
//这里是递归实现
void reversal(BT *bt) // 镜像二叉树
{
BT *p;
if (bt == NULL) 
{
return ;
}
//交换两个节点，相当于t=a;a=b;b=t;
p = bt->l_chrild;
bt->l_chrild = bt->r_chrild;
bt->r_chrild = p;
if (bt->l_chrild)  // 遍历左子树，此时的左子树应给是，原来的右子树（原来左右都不为空时）
reversal(bt->l_chrild);
if (bt->r_chrild)
reversal(bt->r_chrild);
}
void kuohao(BT *bt) //括号显示二叉树
{
if (bt != NULL)
{
printf("%c", bt->data);
if (bt->l_chrild || bt->r_chrild)
{
printf("(");
kuohao(bt->l_chrild);
if (bt->r_chrild)
printf(",");
kuohao(bt->r_chrild);
printf(")");
}
}
}
void print_space(BT *bt, int t)  // 凹入法显示二叉树,利用中序遍历，也可以先，后序遍历，就是在输出时加上一个循环
{
int i;
if (bt)
{
print_space(bt->l_chrild, t+3); 
for (i = 0; i < t; i++)
{
printf("*");
}
printf("%10c\n",bt->data);
print_space(bt->r_chrild, t+3);
}
}
int main()
{
int i;
BT * bt = NULL;
while (1)
{
show_fun();
printf("请输入一个数字\n");
scanf("%d",&i);
getchar();
if (i == 1)
{
printf("请输入一课二叉树\n");
bt = Create_tree();
printf("二叉树创建成功\n");
}
else if (i == 2)
{
printf("该二叉树先序遍历为：\n");
pre_order(bt);  
printf("\n");
}
else if (i == 3)
{
printf("改二叉树中序遍历为：\n");
ln_order(bt);
printf("\n");
}
else if (i == 4)
{
printf("该二叉树后序遍历为：\n");
post_order(bt);
printf("\n");
}
else if (i == 5)
{
printf("该二叉树层次遍历为：\n");
lever_order(bt);
printf("\n");
}
else if (i == 6)
{
int count = 0;
leaf_num(bt, &count);
printf("该二叉树叶子数为：%d\n", count);
}
else if (i == 7)
{
int node = 0;
node_num(bt, &node);
printf("该二叉树结点个数为: %d\n", node);
}
else if (i == 8)
{
int depth;
depth = tree_depth(bt);
printf("该二叉树深度为：%d\n",depth);
}
else if (i == 9)
{
reversal(bt);
printf("已转换成镜像二叉树\n");
}
else if (i == 10)
{
printf("括号显示二叉树: \n");
kuohao(bt);
printf("\n");
}
else if (i == 11)
{
printf("空格显示二叉树: \n");
print_space(bt, 3); // 传多少都可以
}
else if (i == 0)
return 0;
else 
return 0;
}
return 0;
}