销毁树（析构函数）是否需要遍历通用树？

幽灵001

当销毁（当对象超出范围时）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 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;
    }
}
};

约丹夫塔诺斯基

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

最简单的迭代方法是使用堆栈并在您沿树向下时添加元素，并在向上时弹出元素以删除它们。在这篇文章中查看有关此方法的更多信息

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

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

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。