一、先序中序构建树

#include<iostream>
using namespace std;
string pre,mid; 
struct node{
	char data;
	int left,right;//左右孩子编号 
}BTree[30];
int p=0;
//根据先序和中序序列构造树
int getTree(int pl,int pr,int ml,int mr){
	if(pl>pr)  return -1;
	int t=p++;
	BTree[t].data=____(1)_____;
	int i=ml;
	while(i<=mr&&mid[i]!=pre[pl]) i++;
	//计算左子树的长度
	int len=____(2)_____;
	//构建左右子树
	BTree[t].left=getTree(pl+1,____(3)_____,ml,i-1);
	BTree[t].right=getTree(___(4)____,___(5)____,i+1,mr);
	return t; 
} 
int main(){
	cin>>pre>>mid;
	int n=pre.size();
	int root=getTree(0,n-1,0,n-1); 
	cout<<"二叉树的结点数："<<p; 
	return 0;
}

第 1 题

（1）处填写{{ input(1) }}

第 2 题

（2）处填写{{ input(2) }}

第 3 题

（3）处填写{{ input(3) }}

第 4 题

（4）处填写{{ input(4) }}

第 5 题

（5）处填写{{ input(5) }}

二、中序后序构建树后求先序序列

#include<bits/stdc++.h>
using namespace std;
struct node{
	char data;//结点信息
	int left,right;//左孩子、右孩子结点编号 
}BTree[30];
string mid,post;
//根据中序、后序序列构造二叉树
//pl,pr后序序列左右边界  ml,mr中序序列左右边界 
int p=0;//数组下标 
int getTree(int pl,int pr,int ml,int mr){
	if(pl>pr)  return ___(1)___; 
	int t=p++;
	//确定根节点
	BTree[t].data=___(2)___; 
	int i=ml;//i中序序列中根节点下标
	while(i<=mr&&mid[i]!=post[pr])  i++; 
	int len=___(3)___;//求左子树长度 
	//构建左子树，返回值是左子树根节点编号
	BTree[t].left=getTree(pl,___(4)___,ml,i-1);
	//构建右子树，返回值是右子树根节点编号 
	BTree[t].right=getTree(pl+len,___(5)___,i+1,mr);
	return t;//返回结点编号 
}
//对某棵二叉树进行先序遍历 
void preOrder(int root){ //root根结点在数组中编号 
	if(root>=0){
		cout<<BTree[root].data;//输入根节点的数据
		preOrder(BTree[root].left); //先序遍历左子树 
		preOrder(BTree[root].right); //先序遍历右子树 
	}
} 
int main(){
	//输入中序序列和后序序列 
	cin>>mid>>post;
	int n=mid.size();
	getTree(0,n-1,0,n-1);
	//输出先序遍历
	preOrder(0); 
	return 0;
}

第 6 题

（1）处填写{{ input(6) }}

第 7 题

（2）处填写{{ input(7) }}

第 8 题

（3）处填写{{ input(8) }}

第 9 题

（4）处填写{{ input(9) }}

第 10 题

（5）处填写{{ input(10) }}