是否需要遍历一颗General Tree来销毁树（析构函数）？

Question

销毁（对象超出范围时）General Tree是否需要像双向链表一样遍历每个节点并删除它们？我正在写的 General Tree 是一个循环，以便可以在恒定时间内完成插入。如果有人可以帮助我修复错误，那将非常有帮助。下面的析构函数目前导致堆栈溢出（我认为是因为树是循环的）。

这是 2 个析构函数

~Node()
         {
        if(left){delete left;}
                if(next){delete next;}
                if(parent){delete parent;}
          }

一般树

 ~Gen()
       {
           if (head)
                 delete head; //call destructor on node
                 head = nullptr;
                 m_size = 0;
        }

这是节点class

class Node {
public:
    typedef Node* nodePtr;
    int data;
    //Left child- right sibling implementation
    nodePtr left, next, parent;
    int rank; //will be used for merging.
~Node()
         {
               if(left){delete left;}
                if(next){delete next;}
                if(parent){delete parent;}
          }
        
private:
    
    Node & operator =(const Node&);
};

这是使用上面节点的树

class Gen{
 public:
      typedef Node* nodePtr;
       Gen():m_size(0),head(0){}
       ~Gen()
       {
           if (head)
                 delete head; //call destructor on node
                 head = nullptr;
                 m_size = 0;
        }
        void push(int val)
        {
        nodePtr newNode = new Node;
        
        newNode->data = val;
        newNode->rank = 0;
        newNode->left = newNode->next = newNode->parent = 0; //set all pointers to null
        insertRoot(newNode); //call the inserthelper
        ++m_size;
        }
        //other functions (deleteMin, decreaseKey etc)
private:
int m_size;
nodePtr head;
nodePtr insertRoot(nodePtr newNode)
{
   //create a circular link
   if (!head)
    {
        head = newNode;
        newNode->next = newNode;
    }
    else
    {
        newNode->next = head->next;
        head->next = newNode;
        if (newNode->data < head->data)  //min heap (lazy insert)
            head = newNode;
    }
}
};

Answer 1

您需要以某种方式调用树中每个成员的析构函数，可以通过递归方式遍历树（如您的实现）或迭代方法。

最简单的迭代方法是使用堆栈并在沿着树向下移动时添加元素，并在向上移动时弹出元素以删除它们。在 this post

中查看有关此方法的更多信息

因此在您的特定情况下，通用树将有一个干扰器穿过树以销毁节点，您不需要节点析构函数。析构函数看起来像：

#include <stack>
...
....
~Gen() {
    std::stack<Node*> s;
    s.push(head);
    Node* current;
    while (!s.empty()) {
        current = s.top();
        s.pop();
        if (current->left != nullptr) {
            s.push(current->left);
        };
        if (current->next != nullptr) {
            s.push(current->next);
        }
        delete current;
    }
    head = nullptr;
}

因此，当您沿着树向下移动时，您将子级添加到堆栈中并删除父级。一旦堆栈为空，树中的所有节点将被删除。

Answer 2

Is it necessary to traverse a General Tree for destroying the tree (destructor)?

是的，有必要访问每个节点以删除它们（或者至少访问每个分支，因为您可以从分支中删除叶子）。

我假设节点 X 的 parent 指向一个这样的节点，其 child X 是。节点析构函数实现的一个问题是 parent 的析构函数删除了它的 child，它的 child 删除了 parent 删除了 child 删除了 child parent 删除 child 删除 parent 删除 child... 你能发现问题吗？递归是无止境的。此外，parent 的生命周期已经结束，因此 child 试图删除 parent 会导致未定义的行为。

解决方法很简单：不要删除 parent。如果从根开始，删除children，如果parent总是指向一个已经被删除的节点，那么你就随意访问一棵树的所有节点。

另一个问题是您的树不平衡，因此在最坏的情况下，树的深度可能与元素数量成线性关系。这会导致析构函数的递归深度线性增长（在最坏的情况下），这可能导致堆栈溢出，即使无限循环不是问题。

你不应该使用递归来破坏不平衡的树。您应该为节点使用平凡的析构函数，并为树实现迭代析构函数。

销毁不平衡二叉树的一个好算法是旋转一个子树直到它为空，然后删除根并用另一个 child 节点重复。示例（完全未经测试，可能有问题）：

while (head) {
    if (head->left) {
        // rotate
        Node* temp_left = head->left;
        head->left = head->left->next;
        temp_left->next = head;
        head = temp_left;
    } else {
        Node* temp_next = head->next;
        delete head;
        head = temp_next;
    }
}

Tree I am writing is a circular

这也会破坏您对析构函数的实现，因为当您到达指向根的“叶子”时，您将进入上述类似的无限循环和未定义行为。

不幸的是，这个属性也破坏了我建议的迭代析构函数。不过，我现在没有时间想出一个好的解决方案。一个想法是将其与循环检测算法结合起来。

是否需要遍历一颗General Tree来销毁树（析构函数）？

Is it necessary to traverse a General Tree for destroying the tree (destructor)?

c++

tree

destructor