二叉树遍历

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

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

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

描述

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

输入描述：

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

输出描述：

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

示例1

输入：

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

复制

输出：

c b e g d f a 

复制

思路

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

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

  

  • 所以可以写成：

  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之前就构建好这棵树就返回了