8

二分探索木での順序通りの走査（VISIT LEFT、VISIT ROOT、VISIT RIGHT）により、ソートされた結果が得られることを知っています。しかし、バイナリツリーでポストオーダートラバーサル（VISIT LEFT、VISIT RIGHT、VISIT ROOT）を実行する必要があり、その結果、ソートされた値が得られるはずです。

それを達成するために、どのように二分木を構築する必要がありますか？

4

5 に答える 5

12

ルートは最後にアクセスされるため、最大のアイテムが含まれている必要があります。左側のサブツリーは右側のサブツリーの前にアクセスされるため、左側のサブツリーのすべてのアイテムは、右側のサブツリーのどのアイテムよりも小さくなければなりません。

したがって、このようなツリーを構築するには、次のように進めることができます: ルートより大きいアイテムを挿入すると、そのアイテムが新しいルートになります。ルートより小さいが左サブツリーのルートより大きいアイテムを挿入する場合、それを右サブツリーに挿入します。それ以外の場合は、左のサブツリーに挿入します。

于 2010-02-07T13:35:08.203 に答える
1

このサブルーチンは、ツリー構造が存在するツリーに挿入するためのものです。

struct tree

{

int data;
tree * left;
tree *right;

tree(int n)  // constructor 

{
       data = n;
       left = right = NULL;
    }
};

アルゴリズムは次のとおり
です。1。ツリーが空の場合は、新しいノードを挿入します。
2.新しいノードのデータがルートノードのデータよりも大きい場合は、新しいノード
をツリーのルートにします。
3.それ以外の場合は、ツリーの左側のサブツリーに新しいノードを挿入します。

tree * insert(tree *root,int n)

{

if(root == NULL)
{

    root = new tree(n);

    return root;
}
else
{

    if(n > root -> data)
    {
        tree * t = new tree(n);

        t -> left = root;

        return t;
    }

    else


    {

        root -> left = insert(root -> left,n);

        return root;
    }
    }
}
于 2011-03-13T13:51:06.567 に答える
1

ツリーの各ノードで次のことを確認する必要があります。

  • ノードの値は、左サブツリーと右サブツリーのすべての値より大きくなければなりません。
  • 左のサブツリーの値は、右のサブツリーの値より小さくなければなりません。
于 2010-02-07T13:36:33.487 に答える
0

現在受け入れられている答えは、優れたオンラインアルゴリズムを提供します。やや簡単な解決策---オンラインではないため、不正行為の可能性があります---は、ソートされたリンクリストを親ポインタに格納することです。

言い換えると、データを並べ替えます。最大のアイテムをルートに配置し、そのサブツリーの1つを空にして、残りのn-1アイテムのポストオーダーソートされたツリーを他のサブツリーに再帰的に構築します。

ツリーの高さはnで、単一の葉がリストの先頭になり、ルートが最後尾の要素になります。葉から根までツリーを歩くと、要素は増加するシーケンスを形成し、このパスはポストオーダートラバーサルに正確に対応します。

于 2012-10-29T10:20:51.093 に答える