洛谷P1030 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入输出格式

输入格式：

2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式：

1行，表示一棵二叉树的先序。

参考博客：

https://blog.csdn.net/emmaczw/article/details/72822267

这里也有前序和中序确定二叉树的代码

举例说明：根据已知求解二叉树

中序序列 HLDBEKAFCG
后序序列 LHDKEBFGCA

1、在后序序列LHDKEBFGCA中最后出现的元素为A，HLDBEK|A|FCG
2、在后序序列LHDKEB中最后出现的元素为B，HLD|B|EK|A|FCG
3、在后序序列LHD中最后出现的元素为D，HL|D|B|EK|A|FCG
4、在后序序列LH中最后出现的元素为H，H|L|D|B|EK|A|FCG
5、在后序序列KE中最后出现的元素为E，H|L|D|B|E|K|A|FCG
5、在后序序列FGC中最后出现的元素为C，H|L|D|B|E|K|A|F|C|G
6、所有元素都已经定位，二叉树求解完成。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

typedef struct node* Btree;

struct node
{
	char data;
	Btree lchild;
	Btree rchild;
};

char mid[10];
char post[10];


/*  利用后序中序序列创建树
*        i: 子树的后序序列字符串的尾字符在post[]中的下标
*        j: 子树的中序序列字符串的首字符在mid[]中的下标
*      len: 子树的字符串序列的长度
*/

Btree MidPosGetBtree(int i,int j,Btree T,int len)
{
	if (len <= 0) return NULL;

	T = (Btree)malloc(sizeof(struct node));
	T->data = post[i];
	T->lchild = T->rchild = NULL;

    //根再中序遍历数组里的下标
	int index;
	for (index = 1; mid [index]!= post[i]; index++);
	

	int len_left = index - j;
	int len_right = len-1-len_left;

	T->lchild = MidPosGetBtree(i-1-len_right,j,T->lchild,len_left);
	T->rchild = MidPosGetBtree(i-1,index+1,T->rchild,len_right);

	return T;
}

void pre(Btree t)
{
	if (t)
	{
		cout << t->data;
		pre(t->lchild);
		pre(t->rchild);
	}
}



int main()
{
	//freopen("1.txt", "r", stdin);
	scanf("%s", mid + 1);
	scanf("%s", post + 1);
	int len;
	for (len = 1; mid[len]; len++);
	len--;

	Btree root=NULL;
	root = MidPosGetBtree(len, 1, root, len);

	pre(root);
	return 0;
}

/*#include <iostream>  
#include <cstring>  
using namespace std;
typedef struct _Node
{
	char v;
	struct _Node *left;
	struct _Node *right;
}Node, *PNode;

char mid[10];
char post[10];

int Position(char c)
{
	return strchr(mid, c) - mid;
}

void PostMidCreateTree(PNode &pn, int i, int j, int len)
{
	if (len <= 0)
		return;

	pn = new Node;
	pn->v = post[i];
	pn->left = pn->right = NULL;
	int m = Position(post[i]);
	PostMidCreateTree(pn->left, i - 1 - (len - 1 - (m - j)), j, m - j);//注意参数:m-j左子树的长度,len-1-(m-j)右子树的长度  
	PostMidCreateTree(pn->right, i - 1, m + 1, len - 1 - (m - j));
}

void PreTravelTree(PNode pn)        //前序递归遍历  
{
	if (pn)
	{
		cout << pn->v ;
		PreTravelTree(pn->left);
		PreTravelTree(pn->right);
	}
}

int main()
{
	//freopen("1.txt", "r", stdin);
	PNode root2 = NULL;
	scanf("%s", mid);
	scanf("%s", post);
	PostMidCreateTree(root2, strlen(post) - 1, 0, strlen(mid));
	PreTravelTree(root2);

	return 0;
}*/