利用递归思想,慢慢分解。
过程中就输出了,所以不需要再重新建立新的二叉树再输出。
思路如下:

如图:假设如下输入
01.png

根据二叉树创建的规律,那么我们可以得到第一个根节点,即先序遍历的第一个节点。

先序:根左右 中序:左根右 后序:左右根

02.png

再根据中序遍历,我们可以判断出根节点的左儿子所有的节点和右儿子所有的节点
03.png

然后把它们拿出来单独看
04.png

之后同样的做法
即B为根节点(即A的左孩子),F D 为B的右孩子组成,B无左孩子
…………
递归操作

上代码:

#include <iostream>
#include <cstring>

using namespace std;


void solveIt(char *in, char *pre, int length)
{
    if (length <= 0)
    {
        return;
    }
    char *p;
    for (p = in; p < in + length; p++)  //找到中序中的头部在第几个位置
    {
        if (*p == *pre)
        {
            break;
        }
    }

    solveIt(in, pre + 1, p - in);    //左
    solveIt(p + 1, pre + (p - in) + 1, length - (p - in) - 1);  //右
    cout << *pre;  //根
}

int main()
{
    char in[200];
    char pre[200];
    cin >> in >> pre;

    solveIt(in, pre, strlen(in));


    system("pause");
    return 0;
}

中序,后序输出先序也是一样的思路

代码:

#include <iostream>
#include <cstring>

using namespace std;

void solveIt(char *in, char *post, int len)
{
    //root = post+len-1
    //中左右
    if (len <= 0)
    {
        return;
    }
    char *p;
    for (p = in;p<in+len;p++)
    {
        if (*p == post[len - 1])
        {
            break;
        }
    }
    cout << post[len - 1];
    solveIt(in, post, p - in);
    solveIt(p+1, post + (p-in), len - (p-in) - 1);
}

int main()
{
    char in[200];
    char post[200];
    cin >> in >> post;
    solveIt(in, post, strlen(in));
    return 0;
}
最后修改:2019 年 03 月 31 日 10 : 58 PM
如果觉得我的文章对你有用,请随意赞赏