根据先序序列和中序序列递归创建二叉树

根据先序序列和中序序列递归创建二叉树

源代码如下：

#include 
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
请按任意键继续. . .

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！