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

构造二叉树结点结构typedefstructBT{chardata;structBT*l_chrild;structBT*r_chrild;}BT;创建二叉树BT*Create_tree()//创建二叉树{BT*bt;charx;scanf(“%c”,&x);getchar();if(x

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

构造二叉树结点结构

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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/128746.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • sql注入之报错注入「建议收藏」

    sql注入之报错注入「建议收藏」报错注入报错注入在没法用union联合查询时用,但前提还是不能过滤一些关键的函数。报错注入就是利用了数据库的某些机制,人为地制造错误条件,使得查询结果能够出现在错误信息中。这里主要记录一下xpath语法错误和concat+rand()+group_by()导致主键重复xpath语法错误利用xpath语法错误来进行报错注入主要利用extractvalue和updatexml两个函数。使用…

  • php addslashes函数已经没用了_JAVA substring

    php addslashes函数已经没用了_JAVA substringPHP为了安全性,所以引入了个magic_quotes_gpc=On的功能,可以不需要做任何处理就能直接把单引号插入数据库中,那么对于Off时,则需要考虑单引号的问题了,而不是一味地信任运行环境。当magic_quotes_gpc=On时,使用了addslashes()处理后的数据在数据库中将以\’形式保存,如果此时直接输出的话,就会发现比自己期待的内容多了个\,因此stripslashe…

  • 一些能用的 BT Tracker 服务器地址【不定时更新】[通俗易懂]

    一些能用的 BT Tracker 服务器地址【不定时更新】[通俗易懂]不定时更新可用的BTTracker服务器列表(BTTrackerList);相关工具BEncodeEditor:https://sites.google.com/site/ultimasites/bencode-editorTrackerEditor:https://github.com/GerryFerdinandus/bittorrent-tracker-editor/releases可以将服务器列表写入TrackerEditor程序同目录下的add_trackers.txt

  • 启动 Eclipse 弹出“Failed to load the JNI shared library jvm.dll”错误的解决方法

    启动 Eclipse 弹出“Failed to load the JNI shared library jvm.dll”错误的解决方法

  • golang2021 7.13 激活码【中文破解版】

    (golang2021 7.13 激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • JS 定义全局变量[通俗易懂]

    JS 定义全局变量[通俗易懂]JavaScript声明全局变量三种方式的异同JavaScript中声明变量格式:var(关键字)+变量名(标识符)。方式1vartest;vartest=5;需注意的是该句不能包含在function内,否则是局部变量。这是第一种方式声明全局变量。方式2test=5;没有使用var,直接给标识符test赋值,这样会隐式的声明了全局变量test。即使该语句是在一个func…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号