将节点添加到二叉搜索树

免责声明：这是作业。我没有要求明确的代码答案，只有帮助理解为什么我的代码不工作。将节点添加到二叉搜索树

我想实现一个基本的二叉搜索树，但我有我的_addNode(...)函数的问题。

这是问题所在。当我用调试器浏览我的代码时，我注意到叶节点是在创建根的同时在两侧（左侧和右侧）无限创建的，当叶节点为NULL时，从来没有任何点。问题是，我要求我的程序创建一个新的节点，只要它找到一个叶子所在的值即NULL。因此，如果没有任何NULL值，则永远不会创建任何新叶子，对吧？

我遇到的另一个问题是我的compare(...)函数。在调试器中逐句通过它显示它遍历函数多次，从不实际返回值。当它返回到调用函数时，它将回退到函数并无限循环。再次，我不知道为什么会发生这种情况，因为我在每个if声明中都有有效的声明。

以下是您可能需要的所有代码。如果我遗漏了一些东西，请告诉我，我会发布它。

struct Node { 
    TYPE   val; 
    struct Node *left; 
    struct Node *right; 
}; 

struct BSTree { 
    struct Node *root; 
    int   cnt; 
}; 

struct data { 
    int number; 
    char *name; 
}; 

int compare(TYPE left, TYPE right) 
{ 
    assert(left != 0); 
    assert(right != 0); 

    struct data *leftData = (struct data *) left; 
    struct data *rightData = (struct data *) right; 

    if (leftData->number < rightData->number) { 
     return -1; 
    } 
    if (leftData->number > rightData->number) { 
     return 1; 
    } else return 0; 
} 

void addBSTree(struct BSTree *tree, TYPE val) 
{ 
    tree->root = _addNode(tree->root, val); 
    tree->cnt++; 
} 

struct Node *_addNode(struct Node *cur, TYPE val) 
{ 
    assert(val != 0); 

    if(cur == NULL) { 
     struct Node * newNode = malloc(sizeof(struct Node)); 
     newNode->val = val; 
     return newNode; 
    } 
    if (compare(val, cur->val) == -1) { 
     //(val < cur->val) 
     cur->left = _addNode(cur->left, val); 
    } else cur->right = _addNode(cur->right, val); 

    return cur; 
}

编辑：添加下面的功能（S）

int main(int argc, char *argv[]) 
{ 
    struct BSTree *tree = newBSTree(); 

    /*Create value of the type of data that you want to store*/ 
    struct data myData1; 
    struct data myData2; 
    struct data myData3; 
    struct data myData4; 

    myData1.number = 5; 
    myData1.name = "rooty"; 
    myData2.number = 1; 
    myData2.name = "lefty"; 
    myData3.number = 10; 
    myData3.name = "righty"; 
    myData4.number = 3; 
    myData4.name = "righty"; 

    /*add the values to BST*/ 
    addBSTree(tree, &myData1); 
    addBSTree(tree, &myData2); 
    addBSTree(tree, &myData3); 
    addBSTree(tree, &myData4); 

    /*Print the entire tree*/ 
    printTree(tree); 
    /*((1 (3)) 5 (10))*/ 
    return 1; 
}

来源

2012-11-29 idigyourpast

你可以发布执行这些功能的代码吗？ – Griffin

@Griffin你去 – idigyourpast

它是typedef结构数据*类型？（我假设它只是看代码）。 – Griffin

也许你可以malloc后立即尝试设置左，右，以NULL：

struct Node * newNode = malloc(sizeof(struct Node)); 
newNode->left = NULL; 
newNode->right = NULL;

来源

2012-11-29 20:18:46 cnicutar

不知道为什么我没有想到..谢谢。这个问题似乎来自“比较（...）”。 – idigyourpast

~~检查这条线在这里（或相应的左侧）：~~

~~cur-> right = _addNode（cur-> right，val）;~~

~~如果cur-> right == 0，没关系。但是，如果cur-> right！= 0，那么坐在那里的节点将被_addNode的返回值替换，该返回值最终不是整个分支，而只是一个节点。~~

我喜欢在使用memset（newNode，0，sizeof（struct Node））的malloc之后显式地在结构中输出0值。其他人可能会不同意。

来源

2012-11-29 20:26:50 Griffin

但是'if（cur == NULL）'操作是否处理？ '_addNode（...）'应该认识到'cur-> right'为NULL，然后根据前面的'if'语句分配一个新节点。 ...对？ – idigyourpast

是的，我认为你是对的。我只是看更多，意识到我可能在这里错了。 – Griffin

将节点添加到二叉搜索树

回答

相关问题