1

ノードをツリーに順番に挿入しようとしています。私の機能は正常に動作します...ノードが3つしかない場合。

私はこのコードを持っています:

typedef struct _Tnode Tnode;
struct _Tnode {
    char* data;
    Tnode* left;
    Tnode* right;
};

これに加えて：

Tnode* add_tnode(Tnode* current_node, char* value) {
Tnode* ret_value; 

if(current_node == NULL) {
    current_node = (Tnode*) malloc(sizeof(Tnode));

    if(current_node != NULL) {
      (current_node)->data = value;
      (current_node)->left = NULL;
      (current_node)->right = NULL;
      ret_value = current_node; }
    else 
        printf("no memory");    
}
else {
    if(strcmp(current_node->data,value)) {  //left for less than 

        ret_value = add_tnode((current_node->left), value);
        current_node -> left = (Tnode*) malloc(sizeof(Tnode));
        (current_node -> left) -> data = value;
    }

    else if(strcmp(current_node->data,value) > 0) {

        ret_value = add_tnode((current_node -> right), value);
        current_node -> right = (Tnode*) malloc(sizeof(Tnode));
        (current_node -> right) -> data = value;
    }

    else {
        printf("duplicate\n");
        ret_value = current_node;
    }
}

return ret_value;

}

ここで何が問題なのかはわかっていますが、それを修正する方法がわかりません。これは、ルート ノードに接続されている 2 つのノードを上書きするだけです。すなわち

         |root_node|
        /           \
|node_2|             |node_3|

ノード 4 を追加できません。入力に応じて、ノード 2 または 3 を上書きするだけです。デバッグと少しの調査の後、ここからどこに行くべきかよくわかりません...

誰かが助けてくれれば、本当に感謝しています。

4

9 に答える 9

2 
struct _Tnode {
        char* data;
        struct _Tnode * left, * right;
    };
    typedef struct _Tnode Tnode;

void addNode(Tnode ** tree, Tnode * node){

    if(!(*tree)){
        *tree = node;
        return;
    }

    if(node->data < (*tree)->val){
       insert(&(*tree)->left, node);
    }else if(node->data>(*tree)->data){
       insert(&(*tree)->right, node);
    }

}
于 2009-02-24T05:34:16.240 に答える
2

これは単なる学校のプロジェクトのように見えます。

どこから始めましょう。

1) ツリーをずっと左/右に壊しています。なぜそれらが保持されることを期待するのかわかりません: a) 常にこれらのノードに書き込みます。b) 既存のノードを返すのは、strcmp の一致時のみです。

2) 最初の比較で strcmp < 0 を確認する必要があります。

3) バランスの取れていないツリーの場合、再帰を使用する理由はありません。葉に到達してから葉をフックするまでループを使用できます。本当に再帰が必要な場合...

4) 再帰... ノードを作成する場合を除き、すべての場合に NULL を返します (つまり、現在 == NULL の最初の部分)。

5) 左/右で、一時ローカル Node* に戻り値を格納します。戻り値が NULL でない場合のみ、左/右を割り当てる必要があります。

これでも違和感がありますが、ゼロから始めたらこんな感じにはなりません。:) 「char *」値をすべての意地悪な nilly の周りにプッシュするだけで、おそらく最終的に発生するであろうメモリ リークやクラッシュについては触れません。

于 2009-02-24T05:12:13.987 に答える
2

挿入がリーフ ノード (つまり NULL) に到達する場合にのみ、mallocing を残す必要があります。それ以外の場合は、比較に応じて次のレベルに移動するだけです。あなたの場合、次のレベルにトラバースしてから、新しい malloc でそれを殺しています。このため、最初のレベルを超えることはありません。

例えば。

if (current_node == NULL) // Do initialization stuff and return current_node

if (strcmp(current_node->data, value) < 0) {
    current_node->left = add_tnode((current_node->left), value);
} else if (strcmp(current_node->data, value) > 0) {
    current_node->right = add_tnode((current_node->right), value);
}

return current_node;
于 2009-02-24T05:13:54.043 に答える
1

手始めに - 最初の strcmp

if(strcmp(current_node->data,value))

はおそらく正しくありません - これはより小さい場合とより大きい場合の両方に当てはまり、2 番目の if は意味をなさない

于 2009-02-24T05:12:28.290 に答える
0

親ノードへのポインターを構造体に追加する必要があると思います_Tnode。

于 2009-02-24T05:08:34.977 に答える
0

問題は、add_tnode への再帰関数呼び出しを行った後、左側の分岐で、malloc を使用して同じ分岐を消去していることです。malloc は、再帰呼び出しを行っているときではなく、ノードを追加するポイントまで再帰したときにのみ発生するはずです。

基本的に、特定の関数呼び出しでは、再帰呼び出しを行うか、新しいノードを malloc する必要があります。両方を行う必要はありません。

これにより、おそらくメモリリークも発生します。

于 2009-02-24T05:13:12.500 に答える
0

current_node->data が null ではないことがわかり、それを value と比較したら、まず、対応するポインター current_node->left (または ->right) が既に使用されている (!= NULL) かどうかを確認する必要があります。

null の場合はそのまま続行します。それは今うまくいくケースです。

そうでない場合は、対応するノードに対してすべてを再テストし、対応するノードで関数を再度呼び出す必要があります。ここにいくつかの擬似コードがあります:

コードを次のようにラップします。

void Add_node(Tnode* current_node) {
...
else {
        if(strcmp(current_node->data,value) < 0) {  //left for less than 
           if(current_node->left != NULL) {
                Add_node(current_node->left);
           } else {
                ret_value = add_tnode((current_node->left), value);
                current_node -> left = (Tnode*) malloc(sizeof(Tnode));
                (current_node -> left) -> data = value;
        } else if(strcmp(current_node->data,value) > 0) {
                Add_node(current_node->right);
           } else {
           ...
}

これは再帰 (関数呼び出し自体) と呼ばれ、ツリーをウォークスルーします。ノードを読み取るには、再帰関数を再度実行する必要があります。それらが終了することに注意してください（ここで、ある時点で左または右のポインターがnullになり、再帰呼び出しが終了します）。

于 2009-02-24T05:15:31.170 に答える
0

これを自分の教育のために実装していない場合は、libavlを使用します。

于 2009-02-24T05:18:07.310 に答える
0

ノードの親を知る必要はありません。現在のノードの値のみ。

擬似コード:

add_treenode(root, value)

{

 //check if we are at a leaf  
 if root == null
     allocate space for new node.
     set children to null
     save root->value = value
     return root // if you need to return something, return the node you inserted.
 //if not, this node has a value
 if root->value < value  //use strcmp since value is a string
       add_tnode(root->left, value)
 else
       add_tnode(root->right, value)
 return NULL

}

これは、新しいツリー ノードを挿入するときと同じくらいきれいです。挿入したいノードのルートと値を渡すと、あとはそれが行います。

于 2009-02-24T05:22:31.980 に答える