將節點添加到二叉搜索樹

免責聲明：這是作業。我沒有要求明確的代碼答案，只有幫助理解爲什麼我的代碼不工作。將節點添加到二叉搜索樹

我想實現一個基本的二叉搜索樹，但我有我的_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

將節點添加到二叉搜索樹

回答

相關問題