c++ - 如何设计 C++ 树和节点类？

Question

我所做的如下所示，但是在破坏树以及尝试打印树时（基本上我需要在树上使用递归的任何地方），我遇到了很多问题。

这是因为在尝试print在右子树的左侧递归调用时，我的方法中断了，因为我的左子树和右子树实际上只有Nodes 而不是Trees。所以，我需要将我的节点类型化为树，或者我需要创建新的树，这两种都是丑陋的解决方案。

我认为这里的问题在于类设计。你能评论一下吗？谢谢！

class Node {
    int _data;
public:
    Node* left;       // left child
    Node* right;      // right child
    Node* p;          // parent
    Node(int data) {
        _data = data;
        left = NULL;
        right = NULL;
        p  = NULL;
    }
    ~Node() {
    }
    int d() {
        return _data;
    }
    void print() {
        std::cout << _data << std::endl;
    }
};

class Tree {
    Node* root;
public:
    Tree() {
        root = NULL;
    }
    Tree(Node* node) {
        root = node;
    }
    ~Tree() {
        delete root->left; // this is NOT RIGHT as
                           // it only deletes the node
                           // and not the whole left subtree
        delete root->right;
        delete root;
    }

    void print(int);
    void add(int);
};

Answer 1

你为什么不让Node成为你的树类？根据定义，非空节点是某棵树的根。这将大大简化您的代码，因为您不需要为Tree和制作不同的案例Node。

Answer 2

更改 Node 的析构函数，使其删除其左右子节点。然后对于您的 Tree 析构函数，只需删除根目录，因此：

~Tree() {
   delete root;
}

~Node() {
   delete left;
   delete right;
}

Answer 3

public:
~Tree() {
        clear();
        delete root;
    }

    void clear()
    {
        recursive_delete(root);
    }
private:
    void recursive_delete(Node* node)
    {
        if (node!=NULL)
        {
            recursive_delete(node->left);
            recursive_delete(node->right);
            deleteNode(node);
        }
    }
    void deleteNode(Node* node)
    {
        delete node;
        node = NULL;
    }