删除二叉搜索树

Question

我正在尝试删除整个二进制搜索树(树中的每个节点)，您认为这些函数中的哪一个会工作得更好？

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;
    }

Answer 1

建议的析构函数~BST()和class BST的建议函数destroyTree()都不会删除BST实例，并且会比其他方法更好。

解释1 -析构函数~BST()在做什么？

建议的源是简单的delete root->left;，然后是delete root->right;，它将只删除BinarySearchTree的2个节点。

1. 节点root不是check with NULL，否则永远不会删除，
2. 节点root->left也不是check with NULL，
3. 节点root->right也不是check with NULL，<代码>H219<代码>G220

解释2 -函数destroyTree()在做什么？

两个while循环来尝试探索树，一个用于左分支，另一个用于右分支。条件(tree != NULL)的存在只是为了退出循环，而不是检查当前节点是否可以删除。

1. 使用左侧循环时，将只删除root->left的->left节点，直到tree->left == NULL和在尝试delete tree;时崩溃，

H136即使在添加了D37以退出循环之后，在右侧循环中调用新的delete tree; E240，

1. 和最后一个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;
    }
}