刪除二叉搜索樹

我想刪除整個二叉搜索樹（樹中的每個節點），你認爲哪個功能會更好？刪除二叉搜索樹

private: 
    struct Node { 
     string value; 
     Node* left; 
     Node* right; 
    }; 
    Node* root; 

public: 
    BST() { 
     root = NULL; 
    } 

    ~BST() { 
     delete root->left; 
     delete root->right; 
    }

或：

... 
    void destroyTree (Node*& tree) { 
     while (tree != NULL) { 
      tree = tree->left; 
      delete tree; 
     } 
     while (tree != NULL) { 
      tree = tree->right; 
      delete tree; 
     } 
     delete tree; 
    }

來源

2017-03-07 farah

請添加標記** 'C' **最大化的觀衆人數。 –

@ J.Piquard如果你可以識別你自己的語言，你可以自己加上標籤 – Bergi

@Bergi，實際上標籤**'C++'**是帶有部分'class BST'聲明的正確標籤。 –

無論是提出的析構函數~BST()也不建議功能class BST的destroyTree()將刪除BST實例，會比其他的更好。

說明1 - 什麼是析構函數~BST()正在做什麼？

提議的源是簡單接着delete root->right;delete root->left;和將只刪除2 BinarySearchTree的節點。

節點root不與NULL檢查和否則永遠不會被刪除，
root->left不與NULL檢查過的節點，
節點root->right沒有與空檢查過，

說明2 - 功能destroyTree()正在做什麼？

兩個while循環嘗試樹的探索，一個用於左邊的分支，另一個用於右邊的分支。條件(tree != NULL)爲僅用於退出循環，但不檢查當前的節點是否可以刪除。

以左循環，只有->left的root->left的節點都將被刪除，直到tree->left == NULL和CRASH試圖delete tree;時，
即使添加if (tree==NULL) break;來調用delete tree;之前從環退出後一個新的CRASH在右邊的循環，
而最後delete tree;是一個無意義，因爲在這個位置，tree總是'== NULL'。

加成解 - 基於到功能destroyTree()的變形例。

遞歸函數將是最簡單的方法來刪除所有創建的和插入的節點。但請注意BinarySearchTree 的大小，尤其是最深的分支。

void destroyTree(Node *cur_node) { 
    if (cur_node!=NULL) { 
     // explore and delete on left 
     destroyTree(cur_node->left); // recursive-call 
     // explore and delete on right 
     destroyTree(cur_node->right); // recursive-call 
     // delete each node 
     delete cur_node; 
    } 
}

來源

2017-03-08 22:08:07

刪除二叉搜索樹

回答

相關問題