C中的二叉樹

Question

我試圖按順序將節點插入樹中。我的功能很好......當只有三個節點時。

我有這樣的代碼：

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; 

}

我知道什麼是錯在這裏，我只是不知道如何解決它。這隻會覆蓋連接到根節點的兩個節點。即

  |root_node| 
     /   \ 
|node_2|    |node_3| 

我不能添加節點四。它只是根據輸入覆蓋節點2或3。經過調試和一點研究，我不太確定該從哪裏出發......

如果有人能幫忙，我會非常感激。

Answer 1

您應該僅在插入到達葉節點（即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; 

Answer 2

我想你需要將一個指向父節點的指針添加到_Tnode結構中。

Answer 3

這似乎只是一個學校項目。

從哪裏開始。

1）你正在向左/向右翻轉樹。我不確定爲什麼你會期望它們被保留，因爲： a）你總是寫這些節點。 b）您返回現有節點的唯一時間是在strcmp匹配上。 2）你真的需要在第一次比較時檢查strcmp < 0。

3）對於一個非平衡樹，沒有理由使用遞歸 - 你可以直接使用一個循環，直到你到達葉子然後鉤住葉子。如果你真的想遞歸...

4）遞歸...除了當你創建一個節點（例如：你有當前的== NULL的第一部分）的所有情況下返回NULL。

5）在左側/右側，將返回值存儲在臨時本地節點*中。只有在返回值不是NULL的情況下，纔可以向左/右分配。

即使這對我來說並不合適，但如果我從頭開始，它根本就不會看起來像這樣。 :)我們甚至不會進入內存泄漏/崩潰，你可能會通過在所有威爾遜周圍推「char *」值來結束。

Answer 4

對於初學者 - 第一的strcmp

如果（的strcmp（current_node->數據，值））

可能是不正確的 - 這是真的兩者小於和大於，然後第二如果沒有意義

Answer 5

問題是，在你的遞歸函數調用add_tnode之後，在左邊的分支上說，你用你的malloc去掉了同一個分支。只有當您遞歸到您要添加節點的位置時，纔會發生malloc，而不是在進行遞歸調用時。

本質上，在一個特定的函數調用中，你應該做一個遞歸調用或malloc一個新節點，而不是兩個。

這可能也會產生內存泄漏。

Answer 6

一旦你發現了，那current_node->數據不爲空，並與值進行比較，你首先要檢查相應的指針是否current_node->左（或 - >右）已在使用（ ！= NULL）。

如果它爲空，則按照原樣繼續。現在情況正好。

如果不是，則必須重新測試對應節點的整個事情，再次在cooresponding節點上調用您的函數。這裏是一些僞代碼：

裹的代碼：

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 { 
      ... 
} 

這就是所謂recoursion（功能呼喚本身），並通過樹行走。要讀取某個節點，您必須再次執行遞歸函數。請小心，它們會終止（在某些時候，左側或右側指針將爲空，從而終止遞歸調用）。

Answer 7

如果不實現這個爲自己的薰陶，我只想用libavl

Answer 8

你不需要知道節點的父節點。只是當前節點的值。

僞代碼：

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 

}

這是乾淨的，因爲它得到當談到插入一個新的樹節點。傳遞你想要插入的節點的根和值，剩下的就完成了。

Answer 9

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); 
    } 

}