THU-二叉树遍历

THU-二叉树遍历

题目链接

​​例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述:

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

输出描述:

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

示例1

输入

复制

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

输出

复制

c b e g d f a

题解：

根据题意建树，然后中序遍历即可

#include #include using namespace std;int i;struct node{ char data; struct node *rchild, *lchild; };node *create(string s){ char c = s[i++]; if(c == '#'){ return NULL; } node *root = new node(); root->data = c; root->lchild = create(s); root->rchild = create(s); return root;}void inorder(node *p){ if(p != NULL){ inorder(p->lchild); cout << p->data << " "; inorder(p->rchild); }}int main(){ string s; while(cin >> s){ i = 0; node *p = create(s); inorder(p); cout << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。