西农数据结构作业-创新互联

给定一个二叉树的中序和层序输出，重建二叉树并按先序和后序输出。

#include#includeusing namespace std;
struct TreeNode {
	int data;
	TreeNode* leftchild;
	TreeNode* rightchild;
	TreeNode(int n) {
		data = n;
	}
};
vectorceng;
vectormid;
vectorpre;
vectorpost;
TreeNode* BuildTree(int cl, int cr, int ml, int mr);
void preOrder(TreeNode* r);
void PostOrder(TreeNode* r);

int main() {
	int num;
	cin >>num;
	int temp;
	for (int i = 0; i< num; i++) {
		cin >>temp;
		ceng.push_back(temp);
	}
	for (int i = 0; i< num; i++) {
		cin >>temp;
		mid.push_back(temp);
	}
	TreeNode* root = BuildTree(0, num - 1, 0, num - 1);

	preOrder(root);
	PostOrder(root);

	for (int i = 0; i< num - 1; i++) {
		cout<< pre[i]<<" ";
	}
	cout<< pre[num - 1]<< endl;

	for (int i = 0; i< num - 1; i++) {
		cout<< post[i]<< " ";
	}
	cout<< post[num - 1]<< endl;
	
}

TreeNode* BuildTree(int cl, int cr, int ml, int mr)
{
	if(ml>mr)
		return nullptr;

	int i, j;
	int cnt = 0;
	for (i = cl; i<= cr; i++) {
		for ( j = ml; j<= mr; j++) {
			if (ceng[i] == mid[j]) {
				cnt = 1;
				break;
			}
		}
		if (cnt == 1)
			break;
	}

	TreeNode* r = new TreeNode(ceng[i]);
	r->leftchild = BuildTree(cl + 1, cr, ml, j - 1);
	r->rightchild = BuildTree(cl + 1, cr, j + 1, mr);

	return r;
	

}

void preOrder(TreeNode* r)
{
	if (r == NULL)
		return;
	pre.push_back(r->data);
	preOrder(r->leftchild);
	preOrder(r->rightchild);

}

void PostOrder(TreeNode* r)
{
	if (r == NULL)
		return;

	PostOrder(r->leftchild);
	PostOrder(r->rightchild);
	post.push_back(r->data);

}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧