3

プレオーダー、インオーダー、ポストオーダーのトラバーサルを知っています。BST を再構築するアルゴリズムは何ですか?

4

4 に答える 4

12

BSTなので、または<1>in-orderからソートできます。実際には、またはのみが必要です....pre-orderpost-orderpre-orderpost-order

<1>比較関数が何であるかを知っている場合

pre-orderとからin-order、二分木を構築する

BT createBT(int* preOrder, int* inOrder, int len)
{
    int i;
    BT tree;
    if(len <= 0)
        return NULL;
    tree = new BTNode;
    t->data = *preOrder;
    for(i = 0; i < len; i++)
        if(*(inOrder + i) == *preOrder)
            break;
    tree->left = createBT(preOrder + 1, inOrder, i);
    tree->right = createBT(preOrder + i + 1, inOrder + i + 1, len - i - 1);
    return tree;
}

この背後にある理論的根拠:

予約注文では、最初のノードがルートです。順序でルートを見つけます。すると、木を左右に分けることができます。再帰的に実行します。

post-orderと についても同様ですin-order。

于 2011-03-20T08:50:47.660 に答える
0

二分木の再構築には、preorder+inorder または postorder+inorder が必要です。BST について既に指摘したように、事前注文または事後注文のいずれかを使用して再構築することができます。

@brainydexter によって与えられたコードを変更した次の関数を使用して、静的変数を使用せずにツリーを再構築できます。

struct node* buildTree(char in[],char pre[], int inStrt, int inEnd,int preIndex){

    // start index > end index..base condition return NULL.
    if(inStrt > inEnd)
        return NULL;

    // build the current node with the data at pre[preIndex].
    struct node *tNode = newNode(pre[preIndex]);

    // if all nodes are constructed return. 
    if(inStrt == inEnd)
        return tNode;

    // Else find the index of this node in Inorder traversal
    int inIndex = search(in, inStrt, inEnd, tNode->data);

    // Using index in Inorder traversal, construct left and right subtress
    tNode->left = buildTree(in, pre, inStrt, inIndex-1,preIndex+1);
    tNode->right = buildTree(in, pre, inIndex+1, inEnd,preIndex+inIndex+1);

    return tNode;
}
于 2011-03-22T05:01:24.550 に答える
0

私は個人的にダンテの答えを理解するのが少し難しいと感じました。私は解決策を試してみましたが、ここに投稿されたものと似ていることがわかりましたhttp://geeksforgeeks.org/?p=6633

複雑さは O(N^2) です。

ポストオーダー トラバーサルを使用してツリーを構築するための別のアプローチを次に示します。

お役に立てれば

于 2011-03-22T03:29:00.053 に答える