두 갈래 나무가 시퀀스를 훑어보는 구해

하나, 반복 서열로 두 갈래 나무를 구성한다
        
위에는 두 갈래 나무가 있는데, 그것의 역행 서열은 각각 다음과 같다는 것을 알 수 있다.
순차 반복: ABDECFG
중역: DBEAFCG
후면 순서: DEBFGCA
우리가 알아야 할 것은 두 갈래 나무의 선순 서열과 중순 서열로 유일하게 두 갈래 나무를 확정할 수 있다는 것이다.두 갈래 나무의 뒷차례 서열과 중간 서열도 유일하게 두 갈래 나무를 확정할 수 있다.그러나 선순 시퀀스와 후순 시퀀스만 알면 두 갈래 나무를 유일하게 확정할 수 없다.
둘째, 이미 알고 있는 두 갈래 나무의 선순 서열과 중순 서열, 후순 서열을 구한다.
두 갈래 나무의 선순 서열과 중순 서열로 유일하게 한 그루의 두 갈래 나무를 확정할 수 있기 때문에 유일하게 그 후순을 확정할 수 있다.선차적 역행 서열에서 첫 번째 결점은 반드시 두 갈래 나무의 뿌리 결점이다. 그러나 중차적 역행에서 뿌리 결점은 반드시 중차적 서열을 두 개의 서브 서열로 분할한다. 앞의 서브 서열은 왼쪽 서브 나무의 중차적 서열이고 뒤의 서브 서열은 오른쪽 서브 나무의 중차적 서열이다.이 두 하위 시퀀스의 길이에 따라 선행 시퀀스에서 대응하는 왼쪽 트리 선행 시퀀스와 오른쪽 트리 선행 시퀀스를 찾을 수 있습니다.반면에 왼쪽 트리 순서 서열의 첫 번째 결점은 왼쪽 트리의 뿌리 결점이고 오른쪽 트리 순서 서열의 첫 번째 결점은 오른쪽 트리의 뿌리 결점이다.이렇게 점차적으로 진행하면 유일하게 이 두 갈래 나무를 확정할 수 있다.
C++ 구현:

/*************************************************************************
	> File Name: Test.cpp
	> Author: SongLee
	> E-mail: [email protected] 
	> Created Time: 2014 03 20    17 11 31 
    > Personal Blog: http://songlee24.github.io/
 ************************************************************************/
#include<iostream>
using namespace std;

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


TreeNode* PostOrderFromOrderings(char* inorder, char* preorder, int length)
{
    if(length == 0)
    {
        return NULL;
    }
    TreeNode* node = new TreeNode;
    node->elem = *preorder;
    int rootIndex = 0;
    for(; rootIndex < length; rootIndex++)  //  
    {
        if(inorder[rootIndex] == *preorder)
            break;
    }
    node->left = PostOrderFromOrderings(inorder, preorder + 1, rootIndex);
    node->right = PostOrderFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
    cout << node->elem << " ";   //  ， 
    return node;
}


int main()
{
    char* pre = "ABDECFG";
    char* in = "DBEAFCG";
    PostOrderFromOrderings(in, pre, 7);
    cout << endl;
    return 0;
}

셋째, 이미 알고 있는 두 갈래 나무의 후차 서열과 중차 서열은 선차 서열을 구한다.
같은 이치로 두 갈래 나무의 후순 서열과 중순 서열도 유일하게 두 갈래 나무를 확정할 수 있기 때문에 유일하게 선순 역행 서열을 확정할 수 있다.후차 서열의 마지막 결점은 선차 서열의 첫 번째 결점과 같기 때문에 중차 서열을 두 개의 하위 서열로 분할한 후에 유사한 방법으로 귀속적으로 구분할 수 있다.
C++ 구현:

/*************************************************************************
	> File Name: Test1.cpp
	> Author: SongLee
	> E-mail: [email protected] 
	> Created Time: 2014 03 20    21 56 57 
    > Personal Blog: http://songlee24.github.io/
 ************************************************************************/
#include<iostream>
using namespace std;

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


TreeNode* PreOrderFromOrderings(char* inorder, char* postorder, int length)
{
    if(length == 0)
    {
        return NULL;
    }
    TreeNode* node = new TreeNode;
    node->elem = postorder[length-1];
    int rootIndex = 0;
    for(; rootIndex < length; rootIndex++)   //  
    {
        if(inorder[rootIndex] == postorder[length-1])
            break;
    }
    cout << node->elem << " ";   //  ， 
    node->left = PreOrderFromOrderings(inorder, postorder, rootIndex);
    node->right = PreOrderFromOrderings(inorder + rootIndex + 1, postorder + rootIndex, length - (rootIndex + 1));
    return node;
}


int main()
{
    char* post = "DEBFGCA";
    char* in = "DBEAFCG";
    PreOrderFromOrderings(in, post, 7);
    cout << endl;
    return 0;
}

개인 사이트:http://songlee24.github.io/