洛谷P1030 求先序排列

一时失言乱红尘 2022-05-28 01:46 195阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

输入格式：

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

输出格式：

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

![70][]

参考博客：

[https://blog.csdn.net/emmaczw/article/details/72822267][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;
    }*/

[70]: /images/20220528/17fbe3649911428ebc6d4e9f19638525.png
[https_blog.csdn.net_emmaczw_article_details_72822267]: https://blog.csdn.net/emmaczw/article/details/72822267