题意是给出先序和中序,求出后序。
先序遍历先访问根结点,通过根结点可以在中序中把序列分为左子树部分和右子树部分,我建了一个栈,因为后序遍历最后访问根结点,所以把每次访问的根结点放入栈中。因为后序遍历先是左子树然后是右子树,所以在递归的时候就先递归右子树,然后继续递归左子树。
写完程序后有个错误,找了很久才发现,就是我原本在计算左子树个数的时候,是这样计算的,pre2=mid-pre,但是当pre>mid时,就不对了。而正确计算左子树的方法应该是下面这样的。
#include<iostream>
#include<cstring>
#include<stack>
using namespace std; char t1[], t2[];
stack<char>map;
int length; void solve(int pre, int mid, int len)
{
map.push(t1[pre]);
int i = mid;
while (t2[mid] != t1[pre]) mid++; //在中序序列中找到与前序序列相同的结点
int pre2 = mid - i; //左子树的数量
int mid2 = len - - pre2; //右子树的数量
if (mid2 >= )
solve(pre + pre2 + , mid + , mid2);
if (pre2 >= )
solve(pre + , mid - pre2, pre2);
} int main()
{
while (cin >> t1 >> t2)
{
length = strlen(t1);
solve(, , length);
while (!map.empty())
{
char s = map.top();
cout << s;
map.pop();
}
cout << endl;
}
return ;
}
后来数据结构实验的时候也要写这么的一个算法,主要部分就是
bintree buildBintree(char *pre, char *mid,int length)
{
int lch,rch;
bintree root;
root=(bintree)malloc(sizeof(binnode));
lch=;
root->data=*pre;
while(*mid!=*pre) {mid++;lch++;}
rch=length--lch;
if(rch>=) root->rchild=buildBintree(pre+lch+,mid+,rch);
else root->rchild=NULL;
if(lch>=) root->lchild=buildBintree(pre+,mid-lch,lch);
else root->lchild=NULL;
return root;
}
一开始没加11和13语句,然后就不对,看来这个指针问题得好好注意一下。