根据先序序列和中序序列递归创建二叉树
源代码如下：
#include <iostream>
using namespace std;
//二叉树的结构
typedef struct BTNode {
char data;
struct BTNode *left;
struct BTNode *right;
}BTNode;
//根据先序序列和中序序列递归创建二叉树
BTNode * BTCreate(char a[],char b[],int n) {
int k;
if (n==0) {
return NULL;
}
int root = a[0];
BTNode *BT = (BTNode *)malloc(sizeof(BTNode));
BT->data = root; //树根的值可以确定了
for (k = 0; k < n;k++) { //在b中查找b[k]=root的根节点
if (b[k]==root) {
break;
}
}
BT->left = BTCreate(a+1,b,k); //递归创建左子树
BT->right= BTCreate(a+k+1,b+k+1,n-k-1); //递归创建右子树
return BT;
}
//对二叉树进行先序遍历
void PreOrder(BTNode *BTNode)
{
if (BTNode == NULL)
return;
cout << BTNode->data <<" ";
PreOrder(BTNode->left); //递归调用，先序遍历左子树
PreOrder(BTNode->right); //递归调用，先序遍历右子树
}
//对二叉树进行中序遍历
void InOrder(BTNode *BTNode)
{
if (BTNode == NULL)
return;
InOrder(BTNode->left); //递归调用，中序遍历左子树
cout << BTNode->data <<" ";
InOrder(BTNode->right); //递归调用，中序遍历右子树
}
int main() {
int n=0;
cout << "请输入序列个数" << endl;
cin >> n;
char *a = new char[n];
cout << "请输入先序序列" << endl;
for (int i = 0; i < n;i++) {
cin >> a[i];
}
char *b = new char[n];
cout << "请输入中序序列" << endl;
for (int i = 0; i < n; i++) {
cin >> b[i];
}
BTNode *BT =NULL;
BT=BTCreate(a,b,n);
cout << "先序遍历序列为：" << endl;
PreOrder(BT);
cout << endl;
cout << "中序遍历序列为：" << endl;
InOrder(BT);
cout << endl;
system("pause");
return 0;
}
输出：
请输入序列个数 8 请输入先序序列 a b d g c e f h 请输入中序序列 d g b a e c h f 先序遍历序列为： a b d g c e f h 中序遍历序列为： d g b a e c h f 请按任意键继续. . .
