输入

先序和中序
例如

ABCDEGF
CBEGDFA
第二次输入中序和后序
例如
HLDBEKAFCG
LHDKEBFGCA

输出

这棵树的先序中序和后序

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <stack>
using namespace std;
#define md 1000000007;
struct  tree
{
	tree * lson;
	tree * rson;
	char c;
}mytr;
string p,m,a;
int len;
tree * head;
int prepos=0,aftpos;
void fun_pre_mid(int left,int right,tree * father){
	char ch;int midpos;
	if(prepos<=len-1){
        ch=p[prepos++];
        father->c=ch;
        for(int i=left;i<=right;i++)
            if(m[i]==ch){midpos=i;break;}
        tree * tmp=NULL;
        tmp=(tree *)malloc(sizeof(tree));
        tmp->lson=NULL;tmp->rson=NULL;tmp->c='#';
        if(midpos==right&&left<right){
            father->rson=NULL;
            father->lson=tmp;
            fun_pre_mid(left,right-1,tmp);
        }
        else if(midpos==left&&left<right){
            father->lson=NULL;
            father->rson=tmp;
            fun_pre_mid(left+1,right,tmp);
        }
        else if(midpos<right&&midpos>left){
            tree * tmp1=NULL;
            tmp1=(tree *)malloc(sizeof(tree));
            tmp1->lson=NULL;tmp1->rson=NULL;tmp1->c='#';
            father->lson=tmp;
            fun_pre_mid(left,midpos-1,tmp);
            father->rson=tmp1;
            fun_pre_mid(midpos+1,right,tmp1);
        }
	}
} 
void fun_aft_mid(int left,int right,tree * father){
    char ch;int midpos;
    if(aftpos>=0){
        ch=a[aftpos--];
        father->c=ch;
        for(int i=left;i<=right;i++)
            if(m[i]==ch){midpos=i;break;}
        tree * tmp=NULL;
        tmp=(tree *)malloc(sizeof(tree));
        tmp->lson=NULL;tmp->rson=NULL;tmp->c='#';
        if(midpos==right&&left<right){
            father->rson=NULL;
            father->lson=tmp;
            fun_aft_mid(left,right-1,tmp);
        }
        else if(midpos==left&&left<right){
            father->lson=NULL;
            father->rson=tmp;
            fun_aft_mid(left+1,right,tmp);
        }
        else if(midpos<right&&midpos>left){
            tree * tmp1=NULL;
            tmp1=(tree *)malloc(sizeof(tree));
            tmp1->lson=NULL;tmp1->rson=NULL;tmp1->c='#';
            father->rson=tmp1;
            fun_aft_mid(midpos+1,right,tmp1);
            father->lson=tmp;
            fun_aft_mid(left,midpos-1,tmp);
        }
    }
}
void preorder(tree * tt){
	cout<<tt->c<<" ";
	if(tt->lson!=NULL)preorder(tt->lson);
	if(tt->rson!=NULL)preorder(tt->rson);
}
void midorder(tree * tt){
	if(tt->lson!=NULL)midorder(tt->lson);
	cout<<tt->c<<" ";
	if(tt->rson!=NULL)midorder(tt->rson);
}
void aftorder(tree * tt){
	if(tt->lson!=NULL)aftorder(tt->lson);
	if(tt->rson!=NULL)aftorder(tt->rson);
	cout<<tt->c<<" ";
}
int main()
{
	cout<<"pre order"<<endl;
	cin>>p;len=p.length();
	cout<<"mid order"<<endl;
	cin>>m;
    head = new tree;
	fun_pre_mid(0,len-1, head);
    cout<<"pre:"<<endl;
	preorder( head);puts("");
    cout<<"mid:"<<endl;
	midorder( head);puts("");
    cout<<"aft:"<<endl;
    aftorder( head);puts("");
    puts("------------------------------");
    cout<<"mid order"<<endl;
    cin>>m;
    cout<<"aft order"<<endl;
    cin>>a;len=a.length();aftpos=len-1;
    head = new tree;
    fun_aft_mid(0,len-1, head);
    cout<<"pre:"<<endl;
    preorder( head);puts("");
    cout<<"mid:"<<endl;
    midorder( head);puts("");
    cout<<"aft:"<<endl;
    aftorder( head);
	return 0;
}