【二叉树】二叉树遍历/根据先序创建二叉树-蒲公英云

【二叉树】二叉树遍历/根据先序创建二叉树

港控/mmm° 2023-02-19 09:27 39阅读 0赞

题目描述

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

输入

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

输出

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

样例输入

a#b#cdef#####
a##

样例输出

a b f e d c 
a
#include <cstdio>
#include <cstring>
const int maxn = 100;
struct Node{
      //结点 
 char data;
 Node *lchild,*rchild;
};
char pre[maxn]; //先序数组 
int ans,len; //ans当前指向先序序列位置，len序列长度 
//创建二叉树 
Node *create(){
 if(pre[ans] == '#'){
     //#代表空树，ans加 1 
  ans++;
  return NULL; 
 }
 if(ans == len) //序列结束 
  return NULL;
 Node *root = new Node; //创建新结点 
 root->data = pre[ans++];
 root->lchild = create(); //创建左子树 
 root->rchild = create(); //创建右子树 
 return root; 
}
//中序遍历 
void inorder(Node *root){
 if(root == NULL) //树为空 
  return;
 inorder(root->lchild); //遍历左子树 
 if(ans == len - 1)  //输出根结点 
  printf("%c",root->data); //保证一行末尾没有多余的空格 
 else
  printf("%c ",root->data);
 inorder(root->rchild); //遍历右子树 
}
int main(int argc, char** argv) {
 while(scanf("%s",pre) != EOF){
     //输入先序序列 
  ans = 0;  //更新当前指向序列位置
  len = strlen(pre);  //更新序列长度 
  inorder(create()); //中序输出创建的二叉树 
  printf("\n");
 }
 return 0;
}