c - 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;