二叉树遍历

举报
芒果_Mango 发表于 2022/07/31 23:17:07 2022/07/31
【摘要】 大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助!如果有错误请大佬们指正!共同学习交流作者简介:CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog掘金LV3用户 https://juejin.cn/us...

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助!如果有错误请大佬们指正!共同学习交流

作者简介:


题目

二叉树遍历牛客题霸牛客网 (nowcoder.com)

描述

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

输入描述:

输入包括1行字符串,长度不超过100。

输出描述:

可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。

示例1

输入:

abc##de#g##f###

复制

输出:

c b e g d f a 

复制


image-20220209214745995


image-20220209214758841


思路

这是一个IO型的OJ题->要我们自己写main,自己写头文件


  • 用数组存放字符串 ->数组大小?

    image-20220209214805778

    • 所以可以写成:
    char str[100];
    

  • 二叉树的结构体

    • 注意存放的是字符:char类型
struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val; //结点中 :存放的是字符
};

  • 后面要中序遍历打印这棵树

    • 中序遍历
//中序遍历
void InOrder(struct TreeNode* root)
{
    //空树直接返回
    if(root == NULL)
    {
        return ;
    }
    //中序遍历-左子树 根 右子树
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);  
}

  • 整体架构
#include<stdio.h>
#include<stdlib.h>//二叉树结构体
struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val; //结点中 :存放的是字符
};//中序遍历
void InOrder(struct TreeNode* root)
{
    //空树直接返回
    if(root == NULL)
    {
        return ;
    }
    //中序遍历-左子树 根 右子树
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);  
}
//构建二叉树
struct TreeNode* CreateTree(char* str,int* pi)
{
    
}
​
int main()
{
    char str[100];
    scanf("%s",str);//数组名本身就是首元素地址,所以不用加&
    int i = 0;//标志字符串下标
    struct TreeNode* root = CreateTree(str,&i);
    InOrder(root);
    return 0;
}

因为有多组测试数据,所以也可以写成,不写多组输入也能通过,因为后台会多次执行

多组数据的输入:
//写法1
while(scanf("%s",str)!=EOF)
{}
//写法2
while(~scanf("%s",str))
{}

注意点:要传下标的地址过去!!!如果不是地址,每次递归都不是对同一个i进行++,而是开辟新的栈帧空间,i不是同一个。有bug


  • 二叉树的构建
  • 如果i指向的字符是# ->说明是空树,返回NULL,且i要++往后走
  • 如果不是#,创建一个结点(malloc),其值为现在下标指向的值,然后i++往后走

//构建二叉树
struct TreeNode* CreateTree(char* str,int* pi)
{
    if(str[*pi] =='#')
    {
        (*pi)++;//是下标i ++,而不是指针pi++。  
        return NULL;
    }
    //不是#,就创建结点,进行链接
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    //结点存放的是现在i指向的字符,然后i++往后走
    root->val  =  str[(*pi)++];
    //链接左子树和右子树
    //创建左树 链接到左边   
    //创建右树 链接到右边
    root->left = CreateTree( str, pi);
    root->right = CreateTree( str, pi);
    return root;
}

错误写法

if(str[(*pi)++] == '#')
{
    return NULL;
}

写成这样是错误的,进行判断时候,不是# 也++了。

我们的本意是:如果i指向的是# ,i往后走,然后返回空


代码

#include<stdio.h>
#include<stdlib.h>//二叉树结构体
struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val; //结点中 :存放的是字符
};//中序遍历
void InOrder(struct TreeNode* root)
{
    //空树直接返回
    if(root == NULL)
    {
        return ;
    }
    //中序遍历-左子树 根 右子树
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);  
}
//构建二叉树
struct TreeNode* CreateTree(char* str,int* pi)
{
    if(str[*pi] =='#')
    {
        (*pi)++;//是下标i ++,而不是指针pi++。  
        return NULL;
    }
    //不是#,就创建结点,进行链接
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    //结点存放的是现在i指向的字符,然后i++往后走
    root->val  =  str[(*pi)++];
    //创建左树 链接到左边   
    //创建右树 链接到右边
    root->left = CreateTree( str, pi);
    root->right = CreateTree( str, pi);
    return root;
}
​
int main()
{
    char str[100];
    scanf("%s",str);//数组名本身就是首元素地址,所以不用加&
    int i = 0;//标志字符串下标
    struct TreeNode* root = CreateTree(str,&i);
    InOrder(root);
    return 0;
}

字符串末尾的\0不需要考虑

这里是用#来标记左右子树是否存在了,在外层给的时候一般就直接给一个字符串 \0一般是处在字符串的末尾了,而现在要在字符串中用#标记左右子树的情况


在\0之前就构建好这棵树就返回了

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。