家庭作業，遞歸BST插入功能C

Question

這是我第一堂課的作業。它着重於c中的動態分配，以bst的形式。

我必須有一個動態分配的BST，遞歸實現。我知道我的遍歷正常工作，並且無法插入節點。我只有根節點，並且每個其他節點似乎都設置爲NULL。我認爲我不能在遍歷時打印剩餘的節點，因爲我試圖訪問NULL結構的數據成員。到目前爲止我的代碼如下：

void insert_node(TreeNode** root, int toInsert){ 
    if(*root==NULL){ 
     TreeNode *newnode = (TreeNode *)malloc(sizeof(TreeNode)); 
     newnode->data = toInsert; 
     newnode->left = NULL; 
     newnode->right = NULL; 
    } 
    else if(toInsert > (*root)->data){ //if toInsert greater than current 
     struct TreeNode **temp = (TreeNode **)malloc(sizeof(struct TreeNode*)); 
     *temp = (*root)->right; 
     insert_node(temp, toInsert); 
    } 
    else{ //if toInsert is less than or equal to current 
     struct TreeNode **temp = (TreeNode **)malloc(sizeof(struct TreeNode*)); 
     *temp = (*root)->left; 
     insert_node(temp, toInsert); 
    } 
} 

void build_tree(TreeNode** root, const int elements[], const int count){ 
    if(count > 0){ 
     TreeNode *newroot = (TreeNode *)malloc(sizeof(TreeNode)); 
     newroot->data = elements[0]; 
     newroot->left = NULL; 
     newroot->right = NULL; 
     *root = newroot; 
     for(int i = 1; i < count; i++){ 
      insert_node(root, elements[i]); 
     } 
} 

我敢肯定，這只是衆多問題中的一個，但我得到了使用任何線路分段錯誤「（*根） - >數據」，我不知道爲什麼。作爲一個方面說明，儘管「（*根） - >數據」行出現了分段錯誤，我仍然可以打印「（* root） - > data」。如何打印該值，但仍然出現分段錯誤？

Answer 1

這很混亂。有些事情可能會有所幫助

1）不需要使用TreeNode * 指針指針作爲參數。使用樹節點。 （這裏出了點問題，因爲它是來自文本編輯器的一些功能，請考慮並在此行中的每個TreeNode之後增加*）

2）不是嚴格的規則，但作爲最佳實踐，避免使用鏈表的第一個節點存儲實際值。只用作列表的標題。原因是，如果您需要刪除此節點，則不會丟失列表。只是一個提示

3）在你的第一個函數中，如果* root == NULL，我寧願讓函數失敗而不是將它添加到一個臨時列表中（這在當前代碼中丟失，請參閱它添加值到一個不在函數外部傳遞的列表

4）那麼，如果新值大於節點，那麼實際上它會向右移動，如果它小於節點，則向左移動，但它永遠不會停止。看到這個例子： 假設你有清單1-> 3-> 4。現在你想插入2.算法會做什麼？不斷嘗試插入1節點和3節點，在它們之間切換，但從不實際插入任何內容。 解決方案：您將自下而上構建此列表，您的列表將始終進行排序（如果您正確插入節點）。所以你只需要檢查下一個節點是否更高，如果是，就插入你所在的位置。 5）如果你傳遞一個TreeNode * root作爲參數（在第二個函數上），你不應該重新創建一個新列表並且生成root = newlist。只需使用根。 所有這一切都將導致（沒有測試，可能會有一些誤差）：

void insert_node(TreeNode* root, int toInsert){ 
if(root==NULL){ 
    printf("Error"); 
    return; 
} 
TreeNode* temp = root; //I just don't like to mess with the original list, rather do this 
if(temp->right!=NULL && toInsert > temp->right->data){ //if toInsert greater than next 
    insert_node(temp->right, toInsert); 
} 
else{ //if toInsert is less or equal than next node 
    TreeNode* temp2 = temp->right; //grabbing the list after this node 
    temp->right=(TreeNode*)malloc(sizeof(TreeNode)); //making room for the new node 
    temp->right->right=temp2; //putting the pointer to the right position 
    temp->right->left=temp; //setting the left of the next node to the current 
    temp->right->data=toInsert; 
} 
} 

void build_tree(TreeNode* root, const int elements[], const int count){ 
if(count > 0){ 
    for(int i = 0; i < count; i++){ 
     insert_node(root, elements[i]); 
    } 
} 
}