根据树的前序遍历、中序遍历、后序遍历中的两种遍历求第三种遍历结果

63 阅读 0 评论 42 点赞

我是靠谱客的博主粗犷树叶，最近开发中收集的这篇文章主要介绍根据树的前序遍历、中序遍历、后序遍历中的两种遍历求第三种遍历结果，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

学过数据结构，都知道二叉树有四种遍历手段，前序遍历、中序遍历、后序遍历以及层序遍历，而前三种遍历存在较强的关联，即：知道中序遍历及另外两种遍历中的一种时，可以求第三种，简单的讲就是根据中序遍历和前序遍历、后序遍历中的一种，可以求第三种。
是不是有些绕了，自己慢慢理解吧！我们这里要讲一下实现代码。
遇见这种问题，我听说好像可以用栈来实现，但是今天要说的是通过建树来实现的。
分为两种情况：
1、知道前序遍历和中序遍历，求后序遍历。
                这个相对比较简单，因为我们可以通过查找根结点在中序遍历的位置来对两种遍历序列切割，分成子序列，这样通过递归可以实现建树，并且在递归函数尾加上一条输出语句即可实现后序遍历。
2、知道后序遍历和中序遍历，求前序遍历。
                这个就有些难了，对三种遍历没有教深入理解的人是无法理解透这个算法的，其实和前边的算法大致一样，只是有些许的细节差别，我们同样是要查找根结点在中序遍历中的位置，但是我们不能用同样的手段分隔，我们知道，中序遍历，根结点的左边的都是左子树，右边的都是右子树，而后序遍历中的根结点在尾部，所以想要分隔必须对中序遍历进行以根结点为中心左右分割（不留下根结点），对后序遍历进行的分割要保证前半段的长度和中序遍历的前半段长度一致，后半段去除根结点的部分，这样分成了两段同样也是左右子树，另外输出语句也要提前，因为这是前序遍历，所以输出语句需要在递归函数调用自身前就进行输出。

大致的思路就是这样，先看第一种的代码（代码C++）：

#include <iostream>
#include <fstream>
#include <string>

struct TreeNode
{
   struct TreeNode* left;
   struct TreeNode* right;
   char  elem;
};

void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
{
    if(length == 0)
    {
       //cout<<"invalid length";
       return;
    }
    TreeNode* node = new TreeNode;//Noice that [new] should be written out.
    node->elem = *preorder;
    int rootIndex = 0;
    for(;rootIndex < length; rootIndex++)
    {
        if(inorder[rootIndex] == *preorder)
           break;
    }
    //Left
    BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
    //Right
    BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
    cout<<node->elem<<endl;
    return;
}

int main(int argc, char* argv[])
{
    printf("Hello World!n");
    char* pr="GDAFEMHZ";
    char* in="ADEFGHMZ";

    BinaryTreeFromOrderings(in, pr, 8);

    printf("n");
    return 0;
}

接着，是第二种情况的代码（代码C）：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef char TElemType;
#define MAX_TREE_SIZE 100

typedef struct BiTNode  //结点结构
{
    TElemType data; //结点数据
    struct BiTNode *lchild, *rchild;    //左右孩子指针
} BiTNode, *BiTree;

//建树并前序遍历
void BinaryTreeFromOrderings(char *mid, char *last, int len)
{
    //长度为0则返回空
    if (len == 0)
    {
        return ;
    }
    BiTree node = (BiTree)malloc(sizeof(BiTNode));  //分配结点空间
    node->data = last[len - 1];
    //mid中寻找根结点
    int rootIndex = 0;
    for (; rootIndex < len; rootIndex++)
    {
        if (mid[rootIndex] == last[len - 1])
        {
            break;
        }
    }
    //前序遍历，则在建一个节点打印一次
    printf("%c", node->data);
    //Left
    BinaryTreeFromOrderings(mid, last, rootIndex);
    //Right
    BinaryTreeFromOrderings(mid + rootIndex + 1, last + rootIndex, len - (rootIndex + 1));  //后段为右子树
    return ;
}

int main(int argc, const char * argv[])
{
    char mid[100], last[100], len;
    scanf("%s %s", mid, last);
    len = (int)strlen(mid);

    BinaryTreeFromOrderings(mid, last, len);

    printf("n");
    return 0;
}