一、先序中序构建树

#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) }}

---

二、扩展先序序列构建树后求中序序列和后序序列

问题描述

将二叉树的空结点用“·”补齐后，就得到原二叉树的扩展二叉树，如图所示。我请根据扩展二叉树的先序序列构建出一棵二叉树，然后输出这棵二叉树其中序和后序序列。

输入格式

一棵扩展二叉树的先序序列，字符只包含大写字母和“.”，空结点用“.”表示。总长度不超过53。

输出格式

共两行。第一行是二叉树的中序序列；第二行是二叉树的后序序列。

输入样例

ABD..EF..G..C..

输出样例

DBFEGAC
DFGEBCA

#include<iostream>
using namespace std;
struct node{
	char data;
	int left,right;
}BTree[53];
//扩展先序序列建树 
char s[53];//扩展先序序列 
int i=0;//先序遍历序列首字符下标 
int p=0;//存储结点时，可用数组的下标 
int createTree(){
	char c=s[i];
	i++;
	if(____(1)____)  return -1;
	//存储根节点 
	int t=p++;
	BTree[t].data=____(2)____;
	//构建左右子树 
	BTree[t].left=createTree();
	_______(3)__________;
	return t; 
} 
//中序遍历
void inOrder(int root){
	if(root>=0){
		inOrder(BTree[root].left);
		cout<<BTree[root].data;
		inOrder(BTree[root].right);
	}
}  
//后序遍历
void postOrder(int root){
	if(root>=0){
		postOrder(BTree[root].left);
		_______(4)__________;
		_______(5)__________;
	}
}  
int main(){
	cin>>s;
	int root=createTree();
	inOrder(root);
	cout<<endl;
	postOrder(root);
	return 0;
}

第 6 题

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

• c=='#'
• c==-1
• c=='.'
• c

---

第 7 题

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

• c
• p
• t
• i

---

第 8 题

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

• BTree[t].left=createTree()
• BTree[t].right=createTree()
• createTree()
• BTree[t].data=createTree()

---

第 9 题

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

• postOrder(BTree[root].right)
• cout<<BTree[root].data
• postOrder(BTree[root].data)
• inOrder(BTree[root].right)

---

第 10 题

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

• postOrder(BTree[root].right)
• cout<<BTree[root].data
• postOrder(BTree[root].data)
• inOrder(BTree[root].right)

---