二叉树遍历
大家好,我是芒果,一名非科班的在校大学生。对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
题目
描述
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: 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之前就构建好这棵树就返回了
- 点赞
- 收藏
- 关注作者
评论(0)