例题10.1二叉树遍历（清华）

通过字符串建立二叉树，然后中序遍历输出二叉树

关键字：构建二叉树、中序遍历二叉树

#include<vector>
using namespace std;

typedef struct TreeNode {
	char data;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char x) :data(x), left(nullptr), right(nullptr){}
}TreeNode;

TreeNode* build(int &position, string s) {
	char c = s[position++];
	if (c == '#')
		return nullptr;
	TreeNode* root = new TreeNode(c);
	root->left = build(position, s);
	root->right = build(position, s);
	return root;
}

void inOrder(TreeNode* root, vector<char>& res) {
	if (root == NULL)
		return ;
	if (root->left != NULL) 
		inOrder(root->left,res);
	res.push_back(root->data);
	if (root->right != NULL)
		inOrder(root->right,res);
	return;
}

int main()
{
	string s;
	while (cin >> s) {
		//1.构建二叉树
		int position = 0;
		TreeNode* root = build(position, s);
		//2.中序遍历输出
		vector<char> res;
		inOrder(root, res);
		for (int i = 0; i < res.size(); i++)
			cout << res[i] << " ";
		cout << endl;
	}

}