從二叉搜索樹中刪除一個葉子

-4

我已經從BST中創建了一個葉子的刪除功能。如果BST是空的，它會通知您BST是空的。否則，我有一些情況。其中之一是節點（葉）沒有孩子。因此不需要與其他節點進一步鏈接。首先，我刪除指向該葉的指針，然後將其指向null。但不幸的是，該程序崩潰。這裏是功能：從二叉搜索樹中刪除一個葉子

void BinarySearchTree :: delete_node(float deleted_key) 
{ 
    Node* deleted_node_address=return_node_address(deleted_key); 

    if(root == NULL) cout<<"The tree is empty, No thing to delete\n"; 

    else if(deleted_node_address->left_ptr==NULL && deleted_node_address->right_ptr==NULL) 
    { 
     cout<<"The element has no children, No linking required\n"; 
     delete deleted_node_address; 
     deleted_node_address=NULL; 
    } 
}

這裏是return_node_address功能：

Node* BinarySearchTree ::return_node_address(float req_key,Node *traverse_ptr) 
{ 
    if(traverse_ptr==NULL) 
    { 
     cout<<"There is no data to return its addres"; 
     return 0; 
    } 
    else if(traverse_ptr->key == req_key) 
    { 
     return traverse_ptr; 
    } 
    else if(req_key < traverse_ptr->key && traverse_ptr->left_ptr != NULL) 
    { 
     return_node_address(req_key, traverse_ptr->left_ptr); 
    } 
    else if(req_key > traverse_ptr->key && traverse_ptr->right_ptr!= NULL) 
    { 
     return_node_address(req_key, traverse_ptr->right_ptr); 
    } 
    else 
    { 
     cout<<"The Key You Entred Is Not Found in The Tree"; 
     return 0; 
    } 

}

來源

2017-09-22 Ahmed

用調試器啓動程序並逐行執行的時間。 – user0042

我正在使用QT。它的調試器不工作！ – Ahmed

讓它工作。通常它會。 – user0042

分配

deleted_node_address=NULL;

清除deleted_node_address變量，它是本地BinarySearchTree :: delete_node(float deleted_key)功能，但它是否不是清除指向刪除點的指針e從它的父節點。

因此，你使你的樹無效：它仍然有一些left_ptr或一些right_ptr非空，但指向一個非對象。因此，下次嘗試訪問指向未使用的內存時可能發生崩潰。

此外，您可以撥打return_node_address()函數搜索要刪除的節點，然後在之前測試root==NULL。你確定return_node_address方法是否爲NULL-root-proof ...？

來源

2017-09-22 17:18:49 CiaPan

你的意思是我應該使指向刪除節點的父指針指向空？我對嗎？ – Ahmed

@Ahmed是的。當您刪除子節點時，其父節點不再擁有該子節點。並且'沒有離開孩子'或'沒有正確的孩子'正好分別是'left_ptr'或'right_pttr'是'NULL'。 – CiaPan

@Ahmed可能你可能會谷歌'從BST刪除節點'，並研究一些示例實現。當您熟悉問題和可能的解決方案時，請再次瀏覽您的代碼並找出哪些部分缺失。 – CiaPan

從二叉搜索樹中刪除一個葉子

回答

相關問題