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

港控/mmm° 2023-02-19 09:27 63阅读 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;
    }