バイナリ検索ツリーへの挿入

Question

したがって、私はBSTにiを挿入する破壊関数BST insertbst（int i、BST t）を定義する必要があります。つまり、iを含むようにtを変更し、結果のツリーを返します。実行時間はO（高さt）でなければなりません。

私は私のコードで使用される他の機能はで見つけることができ、このバージョンを思い付く...しかし

BST insertbst(int i, BST t) { 
    if (t == NULL) { 
     return BSTmake(i, NULL, NULL); 
    } else if (i < BSTkey(t)) { 
     return BSTmake(BSTkey(t), insertbst(i ,BSTleft(t)), BSTright(t)); 
    } else { 
     return BSTmake(BSTkey(t), BSTleft(t), insertbst(i ,BSTright(t))); 
    } 
} 

私に次のエラーのideone.com/xhxb6を与えている

：任意の提案を行うためにhttp://pastebin.com/TVYRE4Nd それは破壊的な、または私のヒープエラーを避けるためにそれを変更する？

.hファイル：http://ideone.com/QeSTl

テストファイル：http://pastebin.com/9ca5i4My

Answer 1

あなたは間違いなくそれを確認することができますよう、それが呼ばれる新しいBST node毎回、作成しているとして、あなたが今やっているようにあなたがBSTmake()を使用することはできません新しいノードは挿入ごとに1回だけ作成する必要があります。 main

BST x = BSTmake(2, (BSTmake(1, NULL, NULL)), (BSTmake(3, NULL,NULL))); 
BST y = insertbst(4, x); 

で次の2つのステートメントのために今

私はyが指しすべき場所についてのあなたの仮定を知りません。一般に、BSTの実装では、insertを単独で呼び出し、nodeを挿入し、root nodeを渡します。このアプローチを使用すると、コードをより簡単に理解できるようになります。このパターンを使用するには、2行目をinsertbst(4, &x)に変更する必要があります。

その後、以下のようにあなたのinsertbstの実装を変更する必要があります：

• がnewnodeの親を表すノードポインタへのポインタとして二番目の引数を渡します。
• BST *tがnullの場合は、新しいノードを作成し、それを指すようにノードにポインタを割り当てます。
• i < BSTkey(t)またはi > BSTKey(t)の場合、ポインタを左のサブツリーまたは右のサブツリーのいずれかに第2引数として渡して、insertbst（）を再帰的に呼び出す必要があります。

これは、ように見えるかもしれないものです：割り当てられたメモリチャンクにvoid *たポイントを返しmalloc()また

BST insertbst(int i, BST *t) { 
    if (*t == NULL) { 
     *t = BSTMake(i, NULL, NULL); 
    } 
    else if (BSTkey(newnode) < BSTkey(*t)) { 
     insertbst(i, &t->left); 
    } 
    else { 
     insertbst(i, &t->right); 
    } 
} 

。私はBSTがのようなものをtypedefと書かれていると仮定しています。したがって、newnode宣言をBST newnode = (BST)malloc(sizeof(struct bst_node));と変更する必要があります。