[编程题]二叉树遍历
- 热度指数：56098 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串：
ABC##DE#G##F###
其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述:
输入包括1行字符串，长度不超过100。
输出描述:
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
示例1
输入
abc##de#g##f###
输出
c b e g d f a
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *lchild;
struct TreeNode *rchild;
}TreeNode;
// 前序遍历建立二叉树
void createTree(TreeNode **T, char *data, int *index)
{
char ch = data[*index];
*index += 1;
if (ch == '#')
{
*T = NULL;
}
else
{
*T = (TreeNode*)malloc(sizeof(TreeNode));
(*T)->data = ch;
createTree(&((*T)->lchild), data, index);
createTree(&((*T)->rchild), data, index);
}
}
void preOrder(TreeNode* T)
{
if (T == NULL)
{
return;
}
else
{
printf("%c ", T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
void inOrder(TreeNode* T)
{
if (T == NULL)
{
return;
}
else
{
inOrder(T->lchild);
printf("%c ", T->data);
inOrder(T->rchild);
}
}
int main()
{
char s[110];
scanf("%s", &s);
TreeNode *T;
int index = 0;
createTree(&T, s, &index);
inOrder(T);
printf("\n");
return 0;
}
发表于 2024-03-15 12:19:10
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char* BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType val;
} BTNode;
//初始化二叉树
BTNode* InitTree()
{
BTNode* treenode = (BTNode*)malloc(sizeof(BTNode));
if(treenode == NULL)
{
perror("malloc fail");
exit(-1);
}
treenode->right = NULL;
treenode->left = NULL;
treenode->val = NULL;
return treenode;
}
//用前序遍历构建二叉树
void PrevTreePush(char* ch,BTNode** root,int* i,size_t len)
{
if(*i > len)
{
return;
}
if(*(ch+(*i)) == '#')
{
(*i)++;
return;
}
*root = InitTree();
(*root)->val = ch+(*i);
(*i)++;
PrevTreePush(ch, &(*root)->left,i,len);
PrevTreePush(ch, &(*root)->right,i,len);
}
void InOrderTraversal(BTNode * root)
{
if(root == NULL)
return;
InOrderTraversal(root->left);
printf("%c ",*(root->val));
InOrderTraversal(root->right);
}
int main()
{
char ch[100] = "\0";
BTNode *root;
while (fgets(ch,100,stdin) != NULL)
{
int i = 0;
size_t len = strlen(ch);
len = len - 1;
PrevTreePush(ch,&root,&i,len);
InOrderTraversal(root);
}
return 0;
}
发表于 2023-10-24 19:32:11
回复(0)
非递归创建二叉树
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BT {
char val;
struct BT* left;
struct BT* right;
} BT;
//创建节点
BT* getBT(char c) {
BT* tree = (BT*)malloc(sizeof(BT));
tree->val = c;
tree->left = tree->right = NULL;
return tree;
}
BT* setBT(char arr[],int len) {
//记录回去的路
BT* Stack[len];
//指向栈顶元素下一位置
int top = 0;
//创建root节点
BT* root = getBT(arr[0]);
//用于探路
BT* cmp = root;
//状态标记，为0创建左子树、为1创建右子树
//并用来记录遇到了几个空子树
int index = 0;
//从root的左子树开始构建
for (int i = 1; arr[i] != '\0';) {
//不为空就创建节点
if (arr[i] != '#') {
if (index == 0) {
cmp->left = getBT(arr[i]);
Stack[top++] = cmp;
cmp = cmp->left;
}
else if (index == 1) {
cmp->right = getBT(arr[i]);
Stack[top++] = cmp;
cmp = cmp->right;
index = 0;
}
i++;
}
else {
//统计沿途遇到了几个空子树
while (arr[i] == '#') {
index++;
i++;
}
//如果只是<=1，说明此根的左子树为空，就转去构建右子树
//如果>1，说明此根为叶子节点，就开始跳转
//该语句块的作用是：使cmp回到还没构建右子树的根处
if (index > 1) {
//减去左子树为空的计数后
//index此时的值表示遇到了几个空右子树
index--;
//开始往回走
while(index>0){
//遇到空子树就计数减1
if (cmp->right == NULL) {
index--;
}
cmp = Stack[--top];
}
//出循环了再来判断是否回到了右子树为空的根
//没有就继续往回走
while (top > 0 && cmp->right != NULL) {
cmp = Stack[--top];
}
}
//保证程序构建的是右子树
index = 1;
}
}
return root;
}
//递归实现中序遍历
void zx(BT* root) {
if (!root)
return;
zx(root->left);
printf("%c ", root->val);
zx(root->right);
}
int main() {
char arr[101]={0};
scanf("%s",arr);
if (arr[0] == '#')
printf(" ");
else {
int len = strlen(arr) - 1;
BT* root=setBT(arr, len);
zx(root);
}
return 0;
}
发表于 2023-05-16 15:29:21
回复(0)
#include<stdio.h>
#include<stdlib.h>
typedef struct BTNode
{
char val;
struct BTNode* left;
struct BTNode* right;
}BTNode;
struct BTNode* BinaryTreeCreate(char* p,int* k)
{
if(p[*k] == '#')
{
(*k)++;
return NULL;
}
BTNode* tmp=(BTNode*)malloc(sizeof(BTNode));
if(tmp == NULL)
{
exit(-1);
}
tmp->val=p[*k];
(*k)++;
tmp->left=BinaryTreeCreate(p,k);
tmp->right=BinaryTreeCreate(p,k);
return tmp;
}
void Inorder(struct BTNode* root)
{
if(root == NULL)
return;
Inorder(root->left);
printf("%c ",root->val);
Inorder(root->right);
}
int main()
{
char c[101];
while(scanf("%s",c) != EOF)
{
int k=0;
BTNode* root=BinaryTreeCreate(c,&k);
Inorder(root);
}
return 0;
}
发表于 2022-09-04 23:19:39
回复(0)
#include<stdio.h>
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
char val;
}TNode;
TNode* CreateTree(char* str,int* i)
{
if(str[*i]=='#')
{
(*i)++;
return NULL;
}
TNode* root=(TNode*)malloc(sizeof(TNode));
if(root==NULL)
{
exit(-1);
}
root->val=str[*i];
(*i)++;
root->left=CreateTree(str,i);
root->right=CreateTree(str, i);
return root;
}
void InOrder(TNode* root)
{
if(root==NULL)
{
return;
}
InOrder(root->left);
printf("%c ",root->val);
InOrder(root->right);
}
int main()
{
char str[100]={0};
scanf("%s",str);
int i=0;
TNode* root=CreateTree(str,&i);//字符串前序遍历二叉树
InOrder(root);//对二叉树进行中序遍历，输出遍历结果。
return 0;
}
发表于 2022-05-08 17:04:30
回复(0)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct TreeNode
{
char val;
struct TreeNode* left;
struct TreeNode* right;
}TNode;
TNode* BuildTree(char tree[],int* pi)
{
if(tree[*pi] == '#')
{
(*pi)++;
return NULL;
}
TNode* root = (TNode*)malloc(sizeof(TNode));
if(root == NULL)
{
printf("malloc fail\n");
exit(-1);
}
root->val = tree[*pi];
(*pi)++;
root->left = BuildTree(tree, pi);
root->right = BuildTree(tree, pi);
return root ;
}
void InOrder(TNode* root)
{
if(root == NULL)
return;
InOrder(root ->left);
printf("%c ",root ->val);
InOrder(root ->right);
}
int main()
{
char tree[100] = {0};
scanf("%s",tree);
int i = 0;
TNode* node = BuildTree(tree,&i);
InOrder(node);
return 0;
}
发表于 2022-03-23 15:58:55
回复(0)
- 中序遍历的访问步骤：
- （1）沿着根的左孩子，依次入栈，直到左孩子为空。
- （2）此时，栈顶元素出栈并访问：如果栈顶元素的右孩子为空，继续弹栈；如果右孩子不为空，则将右孩子入栈，继续执行（1）。
- 先序遍历只是在元素入栈时访问，其他步骤与中序遍历相同。
- 于是将先序序列的每个元素入栈，某个元素后面是#号时，表明它的左孩子为空，将其弹栈访问，如果后面还有#号，表明它的右孩子也为空，继续弹栈。整个过程中的弹栈访问序列即中序序列。
#include <cstdio>
#include <cstring>
#include <stack>
char pre[101];
int main()
{
while (scanf("%s", pre) != EOF)
{
std::stack<char> s;
for (size_t i = 0; i < strlen(pre); i++)
{
if (pre[i] != '#')
s.push(pre[i]);
else
{
if (!s.empty())
{
printf("%c ", s.top());
s.pop();
}
}
}
printf("\n");
}
return 0;
}
发表于 2022-03-10 23:55:56
回复(0)
//参考了题解
#include<stdio.h>
#include <stdlib.h>
const int N1=1e8+5;
const int N2=1e2+5;
int pos,len,t;//pos记录的是树的编号，t记录的是字符串的位置
char tree[N1];
char str[N2];
void create(int pos){
char c=str[t++];
if(c=='#'){
return ;
}
tree[pos]=c;
create(2*pos);//递归创建左子树
create(2*pos+1);
}
void order(int root){
if(tree[root]==0)
return ;
order(2*root);
printf("%c",tree[root]);
order(2*root+1);
}
int main(){
while(scanf("%s",str)!=EOF){
t=0;
create(1);
inorder(1);
}
return 0;
}
//或者用指针
#include <stdio.h>
#include <stdlib.h>
const int N=1e3+5;
int pos;
char str[N];
typedef struct treenode{
char data;
struct treenode* leftchild;
struct treenode* rightchild;
//treenode(char c):data(c),leftchild(NULL),rightchild(NULL){};
}treenode;
treenode *create(){
char c=str[pos++];
if(c=='#'){
return NULL;
}
treenode *root=(treenode*)malloc(sizeof(treenode));
root->data=c;
root->leftchild=create();
root->rightchild=create();
return root;
}
void inorder(treenode *root){
if(root==NULL){
return ;
}
inorder(root->leftchild);
printf("%c ",root->data);
inorder(root->rightchild);
}
int main(){
while(scanf("%s",&str)!=EOF){
pos=0;
treenode *root=(treenode*)malloc(sizeof(treenode));
root=create();
inorder(root);
}
return 0;
}
发表于 2022-03-04 10:48:44
回复(0)
#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
char string[maxsize];
int i=0;
typedef struct tnode{
struct tnode*left;
struct tnode*right;
char ch;
}tnode;
int build(tnode*Node){
tnode *node;
int tag1=0,tag2=0;
i++;
if(string[i-1]=='\0')
exit(0);
if(string[i-1]!='#'){
Node->ch=string[i-1];
Node->left=(tnode*)malloc(sizeof(tnode));
tag1=build(Node->left);
if(tag1==-1) Node->left=NULL;
Node->right=(tnode*)malloc(sizeof(tnode));
tag2=build(Node->right);
if(tag2==-1) Node->right=NULL;
return 0;
}
else
return -1;
}
void midspan(tnode*Node){
if(Node!=NULL){
midspan(Node->left);
printf("%c ",Node->ch);
midspan(Node->right);
}
else return;
}
int main(){
tnode *Node;
int j=0,tag;
char c;
Node=(tnode*)malloc(sizeof(tnode));
while(scanf("%c",&c)!=EOF){
string[j++]=c;
while((c=getchar())!='\n')
string[j++]=c;
string[j]='\0';
tag=build(Node);
midspan(Node);
printf("\n");
}
}
发表于 2022-02-07 19:25:41
回复(0)
#include<stdio.h>
#include<stdlib.h>
char *g;//全局变量，指针g用来遍历字符串
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//递归建树，利用指针g读取字符并写入根结点数据域然后返回根结点
BiTree TreeBuild(){
if(*g=='#'){//读到#返回NULL
g++;//指针后移
return NULL;
}
else{//读到其它值
BiTNode *s=(BiTNode*)malloc(sizeof(BiTNode));//创建空节点
s->data=*g;//写入数据
g++;//指针后移
s->lchild=TreeBuild();//创建左子树
s->rchild=TreeBuild();//创建右子树
return s;//返回根结点
}
}
//递归打印中序遍历
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild);
printf("%c ",T->data);
InOrder(T->rchild);
}
}
int main(){
char Q[100];
int n;
scanf("%s",Q);//输入字符串
g=Q;//指针归零
BiTree T=TreeBuild();//建树
InOrder(T);//遍历输出
printf("\n");
return 0;
}
发表于 2021-12-16 15:26:39
回复(0)
#include<stdio.h>
#include<stdlib.h>
typedef struct BinTreeNode
{
char val;
struct BinTreeNode* left;
struct BinTreeNode* right;
}BTNode;
BTNode* BinTreeCreate(char* str,int* i)
{
if(str[*i]=='#')
{
(*i)++;
return NULL;
}
BTNode* root=malloc(sizeof(BTNode));
root->val=str[*i];
(*i)++;
root->left=BinTreeCreate(str,i);
root->right=BinTreeCreate(str,i);
return root;
}
void InOrder(BTNode* root)
{
if(!root)
return;
InOrder(root->left);
printf("%c ",root->val);
InOrder(root->right);
}
int main()
{
char str[100]={0};
while(~scanf("%s",str))
{
int i=0;
BTNode* root=BinTreeCreate(str,&i);
InOrder(root);
}
return 0;
}
发表于 2021-11-12 10:05:50
回复(0)
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode*left;
struct TreeNode*right;
}TNode;
void CreateTree(char*a, int* pi,TNode**root)
{
if (a[*pi] != '#')
{
TNode*p = (TNode*)malloc(sizeof(TNode));
p->val = a[*pi];
++(*pi);
*root = p;
}
else
{
++(*pi);
*root = NULL;
return;
}
CreateTree(a, pi,&(*root)->left);
CreateTree(a, pi, &(*root)->right);
}
void Inorder(TNode*root)
{
if (root == NULL)
return;
Inorder(root->left);
printf("%c ", root->val);
Inorder(root->right);
}
int main()
{
char str[100];
scanf("%s", str);
int i = 0;
TNode*root=NULL;
CreateTree(str, &i, &root);
Inorder(root);
return 0;
}
发表于 2021-10-08 23:02:04
回复(0)
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct TreeNode {
ElemType data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode, *BT;
// =============== function prototype ==============
void CreateTree(BT* bt);
void InOrderTraversal(BT bt, void (*visit) (TreeNode*));
// =============== function prototype ==============
void output(TreeNode* node) {
fprintf(stdout, "%c ", (*node).data);
}
int main(const int argc, const char** const argv) {
BT bt = NULL;
CreateTree(&bt);
InOrderTraversal(bt, output);
return 0;
}
// 只有深入理解二叉树及扩展二叉树, 二级指针和堆栈内存等知识。才能写出这短小精悍的函式！
void CreateTree(BT* bt) {
char ch;
fscanf(stdin, "%c", &ch);
if (ch == '#') {
*bt = NULL;
return;
}
*bt = (TreeNode*) malloc(sizeof(TreeNode));
(*bt)->data = ch;
CreateTree(&(*(*bt)).left);
CreateTree(&(*(*bt)).right);
}
void InOrderTraversal(BT bt, void (*visit) (TreeNode*)) {
if (!bt) return;
InOrderTraversal(bt->left, visit);
output(bt);
InOrderTraversal(bt->right, visit);
}
发表于 2021-07-25 15:42:49
回复(0)
问题信息
难度：
15条回答
498收藏
25877浏览
通过挑战的用户
查看代码-
2023-03-14 16:46:21
-
2023-03-14 15:01:02
-
2023-03-13 19:12:25
-
2023-03-13 11:45:16
-
2023-03-12 17:58:02
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
