销毁二叉树中的节点

Question

假设我有一棵二叉树。我使用new创建节点，但现在我想在析构函数中删除它们：

void BinaryTree::recursiveDestructor(Node *& noeud){
    if (node != 0) {
        recursiveDestrutor(node->leftTree);
        recursiveDestructor(node->rightTree);
        delete node;
        node = 0;
    }
}

并且我在析构函数中使用了方法

BinaryTree::~BinaryTree(){
    recursiveDestructor(root);
}

有没有办法只在析构函数中使用 while 或 for 循环，而不是在析构函数中递归调用方法？使用循环并避免在析构函数中使用方法会更快。如果我不能使用循环，有没有办法提高性能？

Answer 1

如果您的树节点存储了它们的父节点，则可以从任何位置找到以下节点，您可以对其进行 while 循环，但它比递归形式花费更多时间（因为调用 next()将需要超过一半时间的单个节点步骤，而递归下降从不超过一个步骤来找到下一个要释放的节点。

Answer 2

为什么需要递归驱动程序？就这样

Node::~Node()
{
   delete left;  // assuming left and right are both an instance of Node
   delete right;
}

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

dtor 将在整个树的所有节点中被调用。

Answer 3

您可以广度删除具有 std::queue 的树。注意：这是在线敲定的，没有语法检查，但希望你明白了：

BinaryTree::~BinaryTree()
{
    if (!root)
        return;

    std::queue<Node*> q;
    q.push(root);
    while (!q.empty())
    {
        Node *p = q.front();
        q.pop();
        if (p->left)
            q.push(p->left);
        if (p->right)
            q.push(p->right);
        delete p;
    }
}

注意：必须节点而非子生命周期管理。 IE。一个节点不能在销毁时自动删除它的子节点。这样做会引发双重删除和大量未定义行为。

销毁二叉树中的节点

Destroying nodes in a binary tree

c++

binary-tree

destructor