AcWing 3384. 二叉树遍历    原题链接    简单

作者： 作者的头像   yxy. ,  2021-04-22 11:16:03 ,  所有人可见 ,  阅读 644

0


编写一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。

例如如下的先序遍历字符串： abc##de#g##f### 其中 # 表示的是空格，空格字符代表空树。

建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入格式
共一行，包含一个字符串，表示先序遍历字符串。

输出格式
共一行，输出将输入字符串建立二叉树后中序遍历的序列，字符之间空格隔开。
注意，输出中不用包含 #。

数据范围
输入字符串长度不超过 100，且只包含小写字母和 #。

输入样例：

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

输出样例：

c b e g d f a

#include<iostream>
using namespace std;

const int N=110;
int n;
typedef struct Node{
    Node *left,*right;
    char data;
}*Tree;
char c;

void build(Tree &T)
{
    cin>>c;
    if(c=='#'){T=NULL;return;}

    T=new Node;

    T->data=c;
    build(T->left);
    build(T->right);
}

void inorder(Tree &T)
{
    if(T==NULL) return;

    inorder(T->left);
    cout<<T->data<<" ";
    inorder(T->right);
}

int main()
{
    Tree T;
    build(T);
    inorder(T);
}

2 评论

用户头像
王德发   2022-02-19 20:14         踩      回复

为啥我这么写就无法输出

#include<iostream>
using namespace std;

const int N=110;
int n;

struct Node{
    Node *left,*right;
    char data;
};
char c;

void build(Node *T)
{
    cin>>c;
    if(c=='#'){
        T=nullptr;
        return;
    }

    T=new struct Node;

    T->data=c;
    build(T->left);
    build(T->right);
}

void inorder(Node *T)
{
    if(T==nullptr) return;

    inorder(T->left);
    cout<<T->data<<" ";
    inorder(T->right);
}

int main()
{
    struct Node* T;
    build(T);
    inorder(T);
}
用户头像
皇GG   2022-02-24 15:43         踩      回复

楼主定义的是Tree, Tree T定义的是一个地址，你这个struct Node T想把T定义成Node的地址，但系统要求定义Node，所以build（T）的时候就会报错，说T未定义，个人理解。