【华科考研机试题】二叉树遍历（递归版 详细注释）

题意

输入前序遍历序列字符串a，中序遍历字符串b，输出后序遍历字符串。

解题思路

1.已知前序遍历，中序遍历求后序遍历，常规做法是建立一棵树。
2.用手算的话很简单，将字符串a遍历一遍，依次插入到树中。

插入关键代码如下

for(a[i] in a){
	//插入a[i]
	int flag = 1;// 标志位为1表示a[i]还未插入
	设置p指针指向根结点 
	while(flag){
		if(a[i]比p指向的结点的字母 在b字符串 中的索引小){
			if(p->left为空){
				将a[i]插入到p->left位置 
				flag = 0; //a[i]插入完成，跳出循环 
			}else{
				p指向p->left 
			}
		} else{//a[i]比p指向的结点的字母 在b字符串 中的索引大 
			if(p->right为空){
				将a[i]插入到p->right位置 
				flag = 0; //a[i]插入完成，跳出循环 
			}else{
				p指向p->right 
			}
		}
	} 
}

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
	char val;
	node* left;
	node* right;
};
node* root;
string a,b;

//如果c在x左边，返回1 
bool InLeft(char x, char c){
	for(int i = 0;b[i]; ++i){
		if(b[i] == x){
			return 0;
		}
		if(b[i] == c){
			return 1;
		}
	}
	return 0; //此句理解起来可忽略，删掉牛客网编译器会报错。 
}

void insert(char c){
	node* p = root;
	//flag为1表示c未插入到树中 
	int flag = 1;
	//为即将插入的结点申请空间 
	node* newNode = (node*)malloc(sizeof(node));
	newNode->left = NULL;
	newNode->right = NULL;
	newNode->val = c;
	
	while(flag){
		//如果c 在当前结点p的左边（在b中的相对位置） 
		if(InLeft(p->val, c)){
			//如果当前结点p的左子树不为空 
			if(p->left){
				p = p->left;
			}else{
				p->left = newNode;
				flag = 0;
			}
		}else{
			if(p->right){
				p = p->right;
			}else{
				p->right = newNode;
				flag = 0;
			}
		}
	}
}


//后续遍历的递归（偷懒）写法，非递归得用栈 
void dfs(node* root){
	if(!root) return;
	if(root->left) dfs(root->left);
	if(root->right) dfs(root->right);
	cout << root->val;
}

int main() {
	ios::sync_with_stdio(false);
	while(cin >> a >> b){
		root = (node*)malloc(sizeof(node));	
		//如果a字符串不为空，将第一个字母设置为根结点字母 
		if(a[0]) root->val = a[0], root->left = NULL, root->right = NULL;
		//遍历a字符串后续字母，依次插入到树中 
		for(int i = 1;a[i]; ++i){
			insert(a[i]);
		}
		//后序遍历输出树 
		dfs(root);
		cout << endl;
	}
	return 0;
}