删除二叉搜索树

我想删除整个二叉搜索树（树中的每个节点），你认为哪个功能会更好？删除二叉搜索树

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

删除二叉搜索树

回答

相关问题