How to design C++ tree and node classes?

Question

What I have done is as below, but with this I am having a lot of problems while destructing the tree, and while trying to print the tree (basically anywhere I need to use recursion on the tree).

This is because while trying to call print recursively on the left of the right subtrees, my method breaks because my left and right subtrees are actually only Nodes and not Trees. So, I need to either typecase my Nodes to Trees or I need to create new trees, both of which are ugly solutions.

I think the problem here is with class design. Can you please comment on the same? Thanks!

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

Solution 1

Why don't you just allow Node to be your tree class? A non-empty node, by definition, is the root of some tree. This will substantially simplify your code since you don't need to make different cases for Tree and Node.

Solution 2

Change the destructor for Node so that it deletes its left and right children. Then for your Tree destructor just delete root, so:

~Tree() {
   delete root;
}

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

Comments

[Moeb]

Because I wanted to create a generic Node structure that can be used not just for a tree, but for other data structures as well, for example, a linked list, and for tree to be composed of a set of nodes.

[Rollie]

This does simplify the algorithm, but some concepts differ. For example, you would expect Tree::Print() to recursively print all nodes, but not Node::Print(), or keeping track of Node count need not be done in every Node if there is a Tree class wrapping everything.

[nneonneo]

But your Node structures contain left and right pointers. They can't really be construed as generic! If you want, call them TreeNode. Realistically, TreeNode and ListNode should be different classes.

[nneonneo]

@Rollie: Node would probably benefit from having a recursive printing function. It may also have a non-recursive printing function. The two need not be exclusive. Note too that having Nodes act like the root of their own tree allows you to examine subtrees in isolation easily, without having to copy their contents to a new Tree.

[Rollie]

@nneonneo of course that's true - it's just 2 ways of writing the same function. whether it's part of Node and explicitly PrintRecursive(), part of Tree as Print(), or just an algorithm Print(Node *, bool bRecursive = false). My statement is merely that there is some value in having the tree class; not that it's superior in all respects. The way OP is describing his Node class though, PrintRecursive() would not be implemented the same way if used in a List class. Re that - what would be the most optimal/elegant way to implement a Tree that can transform into a List?

[nneonneo]

Trees and lists are really very different beasts. I don't feel there's any value in trying to unify them. How you implement the linearization of a tree is strongly dependent upon the tree's usage and contents.

[José Manuel]

Other choice is using smart pointers for memory handling, that way you can forget about the destructors, you just have to use std::unique_ptr<Node> instead of Node* in all the declarations. The exception would be the p (parent), it should still be Node* as you are not handling memory there, just pointing.

[Rollie]

I haven't used unique_ptr yet, but the doc I'm looking at suggests it's not copyable - this might make rebalancing more difficult. Maybe shared_ptr would be more appropriate?

[Rollie]

If you visualize a tree on it's side, with the 'root' being on the left, you can think of a 'binary tree' as a general tree where each node is restricted to have at most 2 children, and a linked list as a general tree where each node is restricted to have at most 1 child. They aren't so completely different. When/why would you unify them? A contrived example: you have a list to start, because you care about insertion order. At some point, you no longer care about insertion, but want it sorted, so you convert it to a tree.

[José Manuel]

shared_ptr introduces a certain risk of accidental cyclic references. You can still move unique_ptr, and its not a big deal. Just do target = std::move( source ); instead of target = source; (target and source would be of type std::unique_ptr<Node>).

[nneonneo]

Sure. General tree nodes would have a generic children list which you could use to implement lists. But, it's definitely overkill just to implement a list, and won't work if you try to do anything past singly-linked lists (e.g. doubly-linked, circularly-linked, etc.) If you're going to convert from one representation to another, you would probably just reinsert everything into a new tree.

[Rollie]

Seems plausible, if I'm understanding though: consider the case where you have a 3 node imbalanced tree (values 3, 2, 1, with 3 being root). Assuming Tree uses unique_ptr<Node> root;, to balance you would first have to Node2->right = move(root);, then root = move(Node3->left); - order seems like it suddenly matters a great deal, as doing the opposite order would delete Node3. Not an insurmountable issue, but a concern nonetheless.

[Rollie]

Isn't circularly-linked just having a Node * pParent?

[OneOfOne]

You are deleting root in ~Tree and in recursive_delete.