二叉树输入前序遍历输出中序遍历

题目描述

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

输入描述:

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

输出描述:

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

分析

方法一：根据输入建立二叉树，再中序遍历
方法二：一个序列为前序序列，那么入栈时访问为前序，出栈时访问为中序

#include <iostream>
#include <string>

using namespace std;

int i;
string s;

struct tree_node{
	char data;
	struct tree_node *left;
	struct tree_node *right;

	tree_node(char c):data(c), left(NULL), right(NULL){}//default constructor of tree_node，初始化列表
};


tree_node* creat_tree(char c){
	char c = s[i++];
	if(c == '#') return NULL;

	tree_node *root = new tree_node(c);
	root -> left = creat_tree();
	root -> right = creat_tree();
	return root;
}

void in_order(tree_node* root){// 中序遍历
	if(!root) return;
	in_order(root -> left);
	cout << root -> data << " ";
	in_order(root -> right);
}

int main(){
	while(cin >> s){
		i = 0;
		tree_node  *root = creat_tree();
		in_order(root);
		cout << endl;
	}
	return 0;
}

方法二:使用栈转换

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main(){
    string s;
    while(cin >> s){
         stack<char> st;
         for(int i = 0; i < s.size(); i++){
            if(s[i] != '#'){// 当结点非空，压入栈
                st.push(s[i]);
            }else{// 否则就出栈并访问
                if(!st.empty()){
                    cout << st.top() << " ";
                    st.pop();
                }
            }
        }
        cout << endl;
    }
    return 0;
}