3

恥ずかしすぎて聞けない、痛々しいほど愚かな質問。私は過去4時間検索し、さまざまなアルゴリズムをテストし、紙でかなりの数を試しましたが、それでも機能させることができません。

プロジェクトの実装の詳細は割愛しますが、基本的な質問は次のとおりです。「プレオーダーバイナリツリーへのノードの挿入をどのように処理しますか。

事前注文BSTとは、すべてのノードをそのような方法で挿入する必要があることを意味します。つまり、事前注文トラバーサル（印刷など）を使用してツリーをトラバースすると、ノードが昇順で印刷されます。

必要なのは単純なアルゴリズムだけです。私はここで与えられた単純な挿入アルゴリズムを試しました（stackoverflowで、しかしそれは正しくないようです（紙でも試しました））;。

ノードは基本的に次のようなものです。

typedef struct testNode{
    int key;
    struct testNode *leftChild;
    struct testNode *rightChild;
}NODE;

挿入データは、一意の整数の単なるリストです。intをキーとしてノードを作成し、そのノードをツリーに追加する必要があります。私はルートノードを持っています。これはNULLポインターとして始まります。

不明な点がある場合は申し訳ありません。

助けてくれてありがとう！

編集：以下に提供されるアルゴリズムに基づいて、これは私が思いついたものです：

void insert(NODE **tree,int key){
if(*tree){
    if ((*tree)->key >= key){
        //Insert before this .....
        NODE *temp = createNode(key);
        temp->lc = (*tree);
        (*tree) = temp;

    }
    else if(!(*tree)->rc){
        //Right Child doesn't exist ....
        insert(&(*tree)->lc,key);
    }
    else if((*tree)->rc->key < key){
        //Right child exists and is smaller than spread ... insert left ...
        insert(&(*tree)->lc,key);
    }
    else{
        //Right child exists and is greater than spread ... insert right ...
        insert(&(*tree)->rc,key);
    }
    //If the code as progressed to this point, insertion must have occured, 
            //and the code returns ......   
} else {
    //the **tree pointer points to NULL. Insert here ....
    SPREADNODE *temp = createSpreadNode(spread);
    //temp->lc = (*tree);
    (*tree) = temp;
}
}
4

1 に答える 1

2

事前注文されたBSTの定義について考えてみましょう。ルートノードは最小の要素であり、その2つの子、または右側のサブツリーのルートが左側のサブツリーのどの値よりも大きくなるように事前に注文されたツリーです。

したがって、機能する1つのアルゴリズムは次のようになります。

  1. 新しいノードがルートよりも小さい場合は、それを新しいルートにし、2つの子ノードの1つとして既存のツリーをポイントします。
  2. 新しいノードがルートよりも大きいが、右側のサブツリーのルートよりも小さい場合は、それを再帰的に左側のサブツリーに挿入します。
  3. それ以外の場合は、再帰的に右側のサブツリーに挿入します。

これは非常にバランスの取れたツリーを生成する可能性は低いですが、機能するはずです。私は少なくとも1つの他の簡単な代替案を考えることができます、そして私が読者に練習として残すことをよりバランスのとれたものにする方法は間違いありません;-)

于 2012-12-17T23:42:46.153 に答える