二叉搜索樹刪除指針的問題

Question

我想實現二叉搜索樹操作並被卡住刪除。

11 
/\ 
10 14 

使用序遍歷作爲樹的表示初始輸出是10 11 14

刪除節點10，期望輸出是11 14但我正在逐漸0 11 14

刪除節點14，輸出預計只是11，但我越來越0 11 67837.

請解釋爲什麼我得到錯誤的輸出。我不尋找任何代碼:)。

typedef struct _node{ 
    int data; 
    struct _node *left; 
    struct _node *right; 
} Node; 

Node* bstree_search(Node *root, int key) 
{ 
    if(root == NULL){ 
    return root; 
    } 
    // Based on binary search relation, key can be found in either left, 
    // right, or root. 
    if(key > root->data) 
    return bstree_search(root->right, key); 
    else if(key < root->data) 
    return bstree_search(root->left, key); 
    else 
    return root; 
} 
void bstree_insert(Node **adroot, int value) 
{ 
    // since address of address(root is itself address) is passed we can change root. 
    if(*adroot == NULL){ 
    *adroot = malloc(sizeof(**adroot)); 
    (*adroot)->data = value; 
    (*adroot)->right = (*adroot)->left = NULL; 
    return; 
    } 
    if(value > (*adroot)->data) 
    bstree_insert(&(*adroot)->right, value); 
    else 
    bstree_insert(&(*adroot)->left, value); 
} 

void bstree_inorder_walk(Node *root) 
{ 
    if(root != NULL){ 
    bstree_inorder_walk(root->left); 
    printf("%d ",root->data); 
    bstree_inorder_walk(root->right); 
    } 
} 
void bstree_delete(Node **adnode) 
{ 
    //Node with no children or only one child 
    Node *node, *temp; 
    node = temp = *adnode; 
    if((*adnode)->right == NULL || (*adnode)->left == NULL){ 
    if((*adnode)->right == NULL){ 
     *adnode = (*adnode)->left; 
    }else{ 
     *adnode = (*adnode)->right; 
    } 
    }else{ // Node with two children 

    } 
    free(temp); 
} 

int main() 
{ 
    Node *root = NULL; 
    Node *needle = NULL; 
    int i,elems[] = {11,10,14}; 

    for(i = 0; i < 3; ++i) 
    bstree_insert(&root,elems[i]); 

    bstree_inorder_walk(root); 
    printf("\n"); 

    needle = bstree_search(root, 10); 
    bstree_delete(&needle); 
    bstree_inorder_walk(root); 
    printf("\n"); 

    needle = bstree_search(root, 14); 
    bstree_delete(&needle); 
    bstree_inorder_walk(root); 
    printf("\n"); 
} 

Answer 1

請解釋爲什麼我收到錯誤 輸出。

您的delete函數還必須更改已刪除節點的父節點。例如，當您刪除保存10的節點時，必須將根Node的left子設置爲NULL。既然你不這樣做，當你稍後遍歷樹時，你會打印出已經被釋放的數據。

我沒有看到除delete以外的任何代碼，因此一旦進行此更改，我無法對其進行任何保證。

Answer 2

因爲你的刪除代碼有問題（好的，也許這就是明顯的），你會得到錯誤的輸出。

要從二叉搜索樹中刪除，首先找到要刪除的節點。如果它是葉節點，則將其父節點中的指針設置爲NULL，並釋放該節點。如果它是而不是葉節點，則取兩個葉節點之一（或者是右子樹中最左邊的子節點，或者是左子樹中最右邊的子節點），然後插入該節點以代替您需要刪除的節點，將指向其上一個父節點的指針設置爲NULL，並刪除您現在「拼接出」樹的節點。

Answer 3

幾件事情的真快，

當你分配節點首先，你真的應該做對的sizeof的類型的malloc（即節點）。第二，如果你有兩個孩子，看起來你並沒有真的刪除這個節點，並且通過宣傳一個孩子來重建搜索樹。

其他人已經讓你其他明顯的錯誤。