二叉搜索樹碼

想寫的二叉搜索樹析構函數（它應該刪除在樹中的所有節點）這是我走到這一步，二叉搜索樹碼

virtual ~BST() { 
    BSTNode<Data>* node = root; 
    if (node == NULL){ 
    return; 
    }else if (node->left) { 
     while(node->left){ 
     delete node; 
     } 
    }else if (node->right){ 
     while(node->right) 
     delete node; 
    } 
     isize = 0; 
}

我知道但是有一些錯誤代碼，我該如何解決它

來源

2013-04-11 cloud9resident

向我們展示了BST類和BSTNode類。 – 2013-04-11 22:15:31

當你做eg

while(node->left){ 
    delete node; 
}

您刪除節點，但實際上並沒有循環到下一個節點。因此下一次在循環中node將不會是NULL，因此您解除引用未分配的數據結構未定義的行爲，並可能導致崩潰。然後您嘗試刪除相同的node再次這仍然是未定義的行爲，並且可能會導致崩潰。

您也不會刪除這兩個左右節點，其中只有一個是因爲else。

我建議你把正確的析構函數中刪除自己的孩子BSTNode：

template<typename T> 
BSTNode<T>::~BSTNode() 
{ 
    delete left; 
    delete right; 
}

然後樹的析構函數將僅僅是：

BST::~BST() 
{ 
    delete root; 
}

來源

2013-04-11 22:10:57

失去else秒。否則，如果樹有left。 right將不會被刪除。

失去while。節點應該有自己的析構函數，並且應該遞歸地刪除。

最後丟失if s。因爲刪除NULL是有效的。

virtual ~BST() { 
    BSTNode<Data>* node = root; 
    if (node == NULL){ 
    return; 
    } 
    delete node->left; 
    delete node->right; 
    isize = 0; 
}

來源

2013-04-11 22:11:58

這可能只會刪除根直接的孩子，讓樹的其餘部分「在風中」這麼說。 – 2013-04-11 22:31:28

沒錯，那正是我在想的，但是我需要一個刪除所有節點 – cloud9resident 2013-04-11 22:34:46

@JoachimPileborg Ya他不太清楚他是如何實現BST和BSTNode之間的關係的。我讓他出示，但他沒有。我在這裏假設，既然他在節點中有左和右，那些節點也有左和右。我的意思是BST只是實際樹形結構的包裝。但後來我不確定。這可能是錯誤的。這就是爲什麼我向他提到節點應該有自己的析構函數並遞歸刪除。 – 2013-04-11 22:37:19

void BST::deleteNode(BSTNode<Data> *node) { 
    if (node) { 
     deleteNode(node->left); 
     deleteNode(node->right); 
     delete node; 
    } 
} 

BST::~BST() { 
    deleteNode(root); 
}

來源

2013-04-11 22:15:16 Archie

這是否會遞歸刪除所有節點，而不僅僅是直接節點？ – cloud9resident 2013-04-11 22:36:26

@ cloud9resident是的，這看起來好像會正確刪除所有的孩子。 – 2013-04-11 22:45:15

二叉搜索樹碼

回答

相關問題