1

我正在尝试按顺序将节点插入树中。我的功能工作正常......当只有三个节点时。

我有这个代码：

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;

}

我知道这里出了什么问题，我只是不知道如何解决它。这只是覆盖连接到根节点的两个节点。IE

         |root_node|
        /           \
|node_2|             |node_3|

我无法添加节点 4。它只是根据输入覆盖节点 2 或 3。经过调试和一些研究，我不太确定从这里去哪里......

如果有人可以提供帮助，我将不胜感激。

4

9 回答 9

2

这似乎只是一个学校项目。

从哪里开始。

1）你一直在树下左右摇摆。我不确定您为什么希望它们被保留，因为：a）您总是写入这些节点。b）您返回现有节点的唯一时间是在 strcmp 匹配上。

2）您确实需要在第一次比较时检查 strcmp < 0 。

3）对于非平衡树，没有理由使用递归 - 您可以使用循环直到到达叶子然后钩住叶子。如果你真的想要递归......

4）递归...在所有情况下都返回NULL，除非您创建一个节点（即：您拥有当前== NULL的第一部分）。

5）在左/右，将返回值存储在临时本地节点*中。仅当返回值不为 NULL 时才应分配左/右。

即使这对我来说也不合适，但如果我从头开始，它看起来根本不会像这样。:) 我们甚至不会陷入内存泄漏/崩溃中，你可能会通过随意推动'char *'值来结束所有的事情。

于 2009-02-24T05:12:13.987 回答
2

您应该只在插入到达叶节点（即NULL）的情况下进行分配。在其他情况下，您应该做的就是根据您的比较遍历到下一个级别。在您的情况下，您将遍历到下一个级别，然后使用新的 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 回答
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 回答
1

对于初学者 - 第一个 strcmp

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

可能是不正确的 - 这对于小于和大于都是正确的，然后第二个 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）。

如果它为空，则照常进行。这就是现在工作正常的情况。

如果没有，您必须针对相应节点重新测试整个事情，在相应节点上再次调用您的函数。这里有一些伪代码：

用以下代码包装代码：

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

这称为递归（一个函数调用本身）并遍历树。要读取某个节点，您必须再次执行递归函数。小心它们终止（这里在某些时候左或右指针将为空，从而终止递归调用）。

于 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 回答