01链式二叉树+遍历问题：求先序遍历

[NOIP2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。

输入格式

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

输出格式

共一行一个字符串，表示一棵二叉树的先序。

样例 #1

样例输入 #1

BADC
BDCA

样例输出 #1

ABCD

提示

【题目来源】

NOIP 2001 普及组第三题

以下为正文：

这道题本蒟蒻居然去建树，真的是太垃圾了我太菜了，但好在也学习了一下怎么建树，也是比较好的。

本题思路与大佬代码：

模拟了好久，终于找出了套路，用的是DFS，其实就是递归；

我说一下这题的主要的方法（要点），

1.后序遍历中，最后一个节点一定是根节点（对于每一颗子树也成立）；

2.既然这题要求先序遍历，那么我们只需一次输出访问的父节点即可；

这样的话，我们只要递归将一棵大树分成两颗子树，让后找他们的父节点，不断递归输出；

3.那么难点就在这了，如何通过一个中序和后序遍历中找出两段子树的后序遍历序列（后序，因为只有后序我们才方便找到父节点）呢？

自己可以拿几个样例做一做，耐性点就会发现它的套路，我这里简单说一下：

在中序遍历中找到当前父节点后，我们可以分别求出他的左子树节点数和右子树节点数，因为中序遍历访问的顺序是左子树，父节点，右子树，所以可以直接计算出；

然后，由于我们对结点的访问一定是先访问一颗子树，在访问另一颗，所以在我们的原后序遍历串右边界中减掉右子树节点个数再减一即为新的左子树右边界，在原后序遍历串左边界加上左子树节点个数即为新的右子树左边界；

当然右子树右边界和左子树左边界这个非常好确定，就不在多说，自己看代码吧

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char s1[10];
char s2[10];
int len;
inline int find(char ch)
{
    for(int i=0;i<len;i++)
    {
        if(s1[i]==ch) return i;
    }
}
void dfs(int l1,int r1,int l2,int r2)
{
    int m=find(s2[r2]);
    cout<<s2[r2];
    if(m>l1) /*具有左子树*/dfs(l1,m-1,l2,r2-r1+m-1);//r1-m为右子树结点数 
    if(m<r1) /*具有右子树*/dfs(m+1,r1,l2+m-l1,r2-1);//m-l1为左子树节点数
}
int main()
{
    cin>>s1;
    cin>>s2;
    len=strlen(s1);
    dfs(0,len-1,0,len-1);
}

然而本蒟蒻的传统型建树代码效率也很高，也是AC捏

#include<iostream>
#include<cstdlib>
#include<string>

using namespace std;
string mid,post;
typedef struct bit{//二叉树结构体
    char content;
    bit* lchild;
    bit *rchild;
}bitree;

void freebypostertraversal(bitree* root)//释放内存空间函数
{
    if(root)
    {

        freebypostertraversal(root->lchild );
        freebypostertraversal(root->rchild );
        free(root);
    }
}
void preordertraversal(bitree* root)//前序遍历函数
{
    if(root)
    {
        cout<<root->content;
        preordertraversal(root->lchild );
        preordertraversal(root->rchild );

    }
}
bitree* mptopre(char inp,int start,int end,int startp,int endp)
{//m=中序遍历，p=后续遍历，to=到，pre=前序遍历
    int start1,start2,end1,end2,trans,start4,start3,end3,end4;
    bitree *root=(bitree*)malloc(sizeof(bitree));//建立一个节点的内存 
    root->content =inp;
        for (int i=start;i<=end ;i++)
        {
            if(mid[i]==inp)
            {
                trans=i; break;
            }
        }//这个循环是在中序遍历中找后序遍历的最后一项的根
        start1=start;
        start2=trans+1;
        end1=trans-1;
        end2=end;
        start3=startp;
        end3=start3+end1-start1;
        start4=end3+1;
        end4=endp-1;
        if (end3<start3)// 判断非空 
        {
            root->lchild =NULL;
        }
        else{
            root->lchild=mptopre(post[end3],start1,end1,start3,end3);
        }
        if (end4<start4)// 判断非空 
        {
            root->rchild =NULL;
        }
        else{
            root->rchild =mptopre(post[end4],start2,end2,start4,end4); 
        }
    return root;//返回指针实现连接 

}
int main()
{
    cin>> mid>>post;
    bitree *root=mptopre(post[post.length() -1],0,mid.length() -1,0,post.length() -1);
    preordertraversal(root);
    freebypostertraversal(root);
    return 0;
}

完结撒花！