データ構造の基礎階層の遍歴と中順序の遍歴還元ツリー

【問題の説明】
階層ループと、中シーケンスループの結果文字列を指定します.
階層A B C D E F GにおけるシーケンスD B A F E G Cの対応するツリーは、A//B C//D E//F Gである
【アルゴリズム思想】
階層遍歴MID代表中序遍歴をLEVで表す.次に、ノードポインタを格納するためにHLP配列が必要です.その長さは、階層/中順遍歴文字列と同じであり、中順遍歴文字列に対応します.
(0)開始状態0 1 2 3 4 5 6 MID D D D D B A F E G C HLP 0 0 0 0 L 0 0 0 0 0 R 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0ここで、HLPはノードポインタを格納し、すべて0に初期化され、ここでL/Rはノードに左/右の子供がいるかどうかを表す.以下ではHLPとMIDの対応関係に注意する.(1)[A]BCDEFG MIDにおけるAの位置を探し,対応する位置にノードを作成し,最初に作成したノードには左右の子供がいなかった.     0  1  2  3  4  5  6 MID  D  B  A  F  E  G  C HLP  0  0  A  0  0  0  0 L    0  0  0  0  0  0  0 R    0  0  0  0  0  0  0 (2) A[B]CDEFG 0 1 2 3 4 5 6 MID D D D B A F E G C HLP 0 B A 0 0 0 L 0 0 0 0 0 R 0 0 0 0 0 0 0 0 0 0 Bの左から0以外のポインタがあるかどうか、ここでは見つからずBの右から0以外のポインタがあるかどうか、Aを見つけてAに左の子供がいないことを発見しました.BがAの左の子0 1 2 3 4 5 6 MID D D D D B A F E G C HLP 0 B A 0 0 0 L 0 X 0 0 R 0 0 0 0 0 0 0 0 0 0 0(3)AB[C]DEFGを上記の手順と同じにし、CはAの右の子0 1 2 3 4 5 6 MID D D D D D B A F E G C HLP 0 B A 0 0 C L 0 X 0 0 0 R 0 X 0 0 0 0 0 0(4)ABC[D]EFGと同等であることが分かった.発見DはBの左の子供0 1 2 3 4 5 MID D D D B A F E G C HLP D B A 0 0 C L 0 X 0 0 0 R 0 X 0 0 0 0 0 0(5)ABCD[E]FGここで少し違います.Eが左に探して発見Aの右の子供がいるので、右に探さなければなりません.その結果、EはCの左の子0 1 2 3 4 5 6 MID D D D B A F E G C HLPD B A 0 E 0 C L 0 X 0 X R 0 X 0 0 0 X 0 0 0 0(6)ABCDE[F]Gと同じで、FはAの右の子になれないことが分かった.Eの左子0 1 2 3 4 5 6 MID D D D D B A F E G C HLP D B A F E 0 C L 0 X 0 X R 0 X 0 0 X 0 0 0 0 0(7)ABCDEF[G]Gを左に探して、GがEを作ることができることを発見した右子は同じで、FがAをできない右子は、Eをした左子0 1 2 3 4 6 MID D D D D B A F E G C HLPD B A F E G C L 0 X 0 X 0 X R 0 X 0 X 0 X 0これまでABCDEFGの関係が確立されており、二叉樹還元が完了している.なぜ私たちはまず左から探して、それから右に探しなければならないのかというと、二叉木の中序がそれ自体が左から右に遍歴しているからかもしれないが、具体的には深く研究したことがない.このアルゴリズムは,前シーケンス−中シーケンス,後シーケンス−中シーケンスの二叉木還元にも同様に適用できる.しかし、このアルゴリズムを使用すると、ノードと同じ数の一時的な空間を申請する必要があることがわかります.このツリーが大きいと不便になるようです.一方,私の他の前シーケンス−中シーケンス,後シーケンス−中シーケンスのツリー還元アルゴリズムに必要な一時空間の最大数は,ツリーの層回数である.255要素のフルツリーで、階層は8で、一時的な空間は多くても8が必要で、明らかに空間的に優れています.
【ソース実装】

#include <iostream>
#include <stack>
#include <string>
#include <queue>
using namespace std;
struct TreeNode {
    char       data;
    TreeNode*   lChild;
    TreeNode*   rChild;
public:
    TreeNode(char c) : data(c), lChild(0), rChild(0) { }
};
//  -        
void Lev_Mid_Restore(string lev, string mid, TreeNode*& result) {
    const int size = lev.size();
    TreeNode* helper[size];
    for(int i = 0; i < size; i++)
        helper[i] = 0;
    /*            0  1  2  3  4  5  6  7  8
        helper    0  0  0  0  A  0  0  0  0
        lChild    0  0  0  0  0  0  0  0  0
        rChild    0  0  0  0  0  0  0  0  0
    */
    bool success = false;
    result = new TreeNode(lev[0]);
    int mi = mid.find(lev[0]);
    helper[mi] = result;
    
    for(int i = 1; i < lev.size(); i++) {
        success = false;
        mi = mid.find(lev[i]);
        helper[mi] = new TreeNode(lev[i]);  //                
        /*     X      ，       0   Y，
                     ，    ， X Y    ，        ，
                      。 
            Y       ，    X       
        */ 
        for(int p = mi - 1; p >= 0; p--) {
            if(helper[p] != 0) {
                if(helper[p]->rChild == 0) {
                    helper[p]->rChild = helper[mi];
                    success = true;
                }
                break;
            }
        }
        if(success) {
            continue;
        }
        /*     X      ，       0   Y
                    ，    ， X Y    
            Y       ，       /         
        */
        for(int p = mi + 1; p < size; p++) {
            if(helper[p] != 0) {
                if(helper[p]->lChild == 0) {
                    helper[p]->lChild = helper[mi];
                    success = true;
                }
                break;
            }
        }
        //         ，       ，       /      
        //    
        if(!success) {
            cout << "error: " << lev[i] << endl;
            break;
        }
    }
}
int main() {
    void inorderTraversal(TreeNode* pTree);
    void levelorderTraversal(TreeNode* pTree);
    void Lev_Mid_Restore(string lev, string mid, TreeNode*& result);
    /*                 A
                    /      /
                   B        C
                 /   /    /   /
                D    E    F    G
               / /  / /  / /  / /
               H I  J K  M N  O P
    */
    string Levorder1 = "ABCDEFGHIJKMNOP";
    string Midorder1 = "HDIBJEKAMFNCOGP";
    
    string Levorder2 = "ABCDEFG";
    string Midorder2 = "BDAFEGC";
    TreeNode* res = 0;
    Lev_Mid_Restore(Levorder1, Midorder1, res);
    inorderTraversal(res);  
    levelorderTraversal(res);
    
    Lev_Mid_Restore(Levorder2, Midorder2, res);
    inorderTraversal(res);  
    levelorderTraversal(res);   
    
    cin.get();
}
//     
void inorderTraversal(TreeNode* pTree) {
    stack<TreeNode*> treeStack;
    do {
        while(pTree != 0) {
            treeStack.push(pTree);
            pTree = pTree->lChild;
        }
        if(!treeStack.empty()) {
            pTree = treeStack.top();
            treeStack.pop();
            cout << pTree->data;
            pTree = pTree->rChild;
        }
    }while(!treeStack.empty() || pTree != 0);
    cout << endl;
}
//     
void levelorderTraversal(TreeNode* pTree) {
    queue<TreeNode*> treeQueue;
    treeQueue.push(pTree);
    while(!treeQueue.empty()) {
        cout << treeQueue.front()->data;
        TreeNode* lChild = treeQueue.front()->lChild;
        TreeNode* rChild = treeQueue.front()->rChild;
        if(lChild != 0) {
            treeQueue.push(lChild);
        }
        if(rChild != 0) {
            treeQueue.push(rChild);
        }
        treeQueue.pop();
    }
    cout << endl;
}