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

全栈程序员站长

发布于 2022-07-28 19:22:34

3.6K0

发布于 2022-07-28 19:22:34

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

构造二叉树结点结构

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;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/128746.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年4月1，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树