Java二叉樹怎么根據前序和中序推出后續

本篇內容介紹了“Java二叉樹怎么根據前序和中序推出后續”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

根據前序跟中序 => 后序

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct BTreeNode
{
    int _value;
    BTreeNode*_left;
    BTreeNode*_right;
};

//解法一
BTreeNode* RebuildCode(int * PreStart, int *PreEnd, int *InStart, int *InEnd)
{
    BTreeNode *root = new BTreeNode();
    //新建節點root保存前序第一個節點為根結點
    root->_value = PreStart[0];
    root-> _left = NULL;
    root->_right  = NULL;
    if(InStart == InEnd && *InStart == *InEnd)
    {
        return root;
    }
    //據此節點找到中序遍歷此節點的位置
    int *rootIn = InStart;
    while(*PreStart != *rootIn)
    {
        rootIn++;
    }
    //左子樹的長度
    int leftlen = rootIn-InStart;
    //重建左子樹
    if(leftlen > 0)
    {
        root->_left = RebuildCode( PreStart+1, PreStart+leftlen, InStart,InStart+leftlen-1);
    }
    //重建右子樹
    if(InStart+leftlen < InEnd)
    {
        root->_right = RebuildCode( PreStart+leftlen+1, PreEnd,InStart+leftlen+1, InEnd);

    }
    return root;
}
BTreeNode* RebuildTree(int *PreOrder, int *InOrder, int len)
{
    //首先判斷邊界條件
    if(PreOrder == NULL || InOrder == NULL || len <= 0)
    {
        return NULL;
    }
    else
    {
        return RebuildCode(PreOrder, PreOrder+len-1, InOrder, InOrder+len-1);
    }
}
//后序遍歷輸出二叉樹序列
void PostOrder(BTreeNode *root)
{
    if(root->_left != NULL)
    {
        PostOrder(root->_left);
    }
     if(root->_right != NULL)
    {
        PostOrder(root->_right);
    }
    if(root != NULL)
    {
        cout<<root->_value<<" ";
    }
}
int main()
{
    int  PreOrder[8] = {1,2,4,7,3,5,6,8};
    int  InOrder[8] = {4,7,2,1,5,3,8,6};
    PostOrder(RebuildTree(PreOrder, InOrder, 8));
    cout<<endl;
    return 0;
}

根據后序跟中序 =>前序

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct BTreeNode
{
    int _value;
    BTreeNode*_left;
    BTreeNode*_right;
};

//解法一
BTreeNode* RebuildCode(int * PostStart, int *PostEnd, int *InStart, int *InEnd)
{
    BTreeNode *root = new BTreeNode();
    //新建節點root保存前序第一個節點為根結點
    root->_value = PostEnd[0];
    root-> _left = NULL;
    root->_right  = NULL;
    if(InStart == InEnd && *InStart == *InEnd)
    {
        return root;
    }
    //據此節點找到中序遍歷此節點的位置
    int *rootIn = InStart;
    while(*PostEnd != *rootIn)
    {
        rootIn++;
    }
    //左子樹的長度
    int leftlen = rootIn-InStart;
    //重建左子樹
    if(leftlen > 0)
    {
        root->_left = RebuildCode( PostStart, PostStart+leftlen-1, InStart,InStart+leftlen-1);
    }
    //重建右子樹
    if(InStart+leftlen < InEnd)
    {
        root->_right = RebuildCode( PostStart+leftlen, PostEnd-1, InStart+leftlen+1, InEnd);

    }
    return root;
}
BTreeNode* RebuildTree(int *PostOrder, int *InOrder, int len)
{
    //首先判斷邊界條件
    if(PostOrder == NULL || InOrder == NULL || len <= 0)
    {
        return NULL;
    }
    else
    {
        return RebuildCode(PostOrder, PostOrder+len-1, InOrder, InOrder+len-1);
    }
}
//后序遍歷輸出二叉樹序列
void PreOrder(BTreeNode *root)
{
    if(root != NULL)
    {
        cout<<root->_value<<" ";
    }
    if(root->_left != NULL)
    {
        PreOrder(root->_left);
    }
     if(root->_right != NULL)
    {
        PreOrder(root->_right);
    }
}
int main()
{
    int  PostOrder[8] = {7,4,2,5,8,6,3,1};
    int  InOrder[8] = {4,7,2,1,5,3,8,6};
    PreOrder(RebuildTree(PostOrder, InOrder, 8));
    cout<<endl;
    return 0;
}

“Java二叉樹怎么根據前序和中序推出后續”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！