General Tree implementation

Hi guys,

so after looking at different implementations online I found them all pretty basic or at least lacking a lot of features, so I decided to try and implement my own general tree ADT.

Anyway I would like your feedback, can you implement the generic tree with a better design and if so how and what ideas would you try?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

template <class T>
class Tree{

public:

    bool rootIsSet = false;

    Tree(){}

    NodeB<T>* addNode(T elem,NodeB<T>* parent){

        if(!rootIsSet){

            parent = new NodeB<T>;
            parent->parent = NULL;
            parent->element = elem;
            rootIsSet = true;
            return parent;
        }
        parent->child.push_back(new NodeB<T>);

        parent->child.at(parent->child.size()-1)->element = elem;
        parent->child.at(parent->child.size()-1)->parent = parent;
        return parent;
    }

    void printAll(NodeB<T>* n){

       if(isRoot(n))
        cout << "element = " << n->element << endl;

       if(n->child.size() == 0)
        return;

       int i = 0;
       while(i < n->child.size()){

          cout << "element = " << n->child.at(i)->element << endl;
          printAll(n->child.at(i));
          ++i;
       }
    }

    bool isRoot(NodeB<T>* n){

       return (n->parent == NULL);
    }

    bool isExternal(NodeB<T>* n){

        return (n->child.size() == 0);
    }

    bool isInternal(NodeB<T>* n){

       return (!isExternal(n));
    }

    int height(NodeB<T>* tree){

       if(isExternal(tree))
        return 0;

       int i = 0;
       int greatest = 0;
       while(i < tree->child.size()){

         int number = height(tree->child.at(i))+1;
         if(number > greatest)
            greatest = number;

          ++i;
       }
       return greatest;
    }

    int depthAtNode(NodeB<T>* n){

       if(isRoot(n))
        return 1;

       return 1+depthAtNode(n->parent);
    }
};



int main()
{

    // general tree

    Tree<int> gtree;
    NodeB<int>* root = NULL;
    root = gtree.addNode(8,root); // set Root
    gtree.addNode(5,root); // add first child of root
    gtree.addNode(4,root); // add second child of root
    gtree.addNode(3,root); // add third child of root
    gtree.addNode(2,root->child.at(0)); // add first child of roots first child
    gtree.addNode(6,root->child.at(0));
    gtree.addNode(10,root->child.at(0));
    gtree.addNode(1,root->child.at(1));
    gtree.addNode(15,root->child.at(2));
    gtree.addNode(20,root->child.at(2));
    gtree.addNode(17,root->child.at(0)->child.at(0));

    gtree.printAll(root);

    cout << "height == " << gtree.height(root) << endl;
    cout << "depth == " << gtree.depthAtNode(root->child.at(0)->child.at(0)) << endl;

    return 0;
}
Print all should be user-defined or not even exist, or possibly just return a string or container of strings or the like?
What if the user wants to use a gui and print into a text box widget? I recommend you always, always separate your real/worker classes from the interface.

I would expect insert, delete, search methods, at least.

The general approach seems OK, but it feels like you are looking for a nail.
Why do you want a general tree; what do you think it is useful for, and does your class solve that problem? What else might it be useful for, and can it solve those problems? Why do you care about the height, is root, etc things? Those are classroom questions usually, of little practical value. I don't think I have ever had a requirement to give my company the height of my tree as output :) You only need those things if they help you with some algorithm that can exploit that kind of info.
Last edited on
Print all should be user-defined or not even exist, or possibly just return a string or container of strings or the like?
What if the user wants to use a gui and print into a text box widget? I recommend you always, always separate your real/worker classes from the interface.


that would be a much better idea, return a vector of the values of each node

I would expect insert, delete, search methods, at least.


I'll get on that.

The general approach seems OK, but it feels like you are looking for a nail.
Why do you want a general tree; what do you think it is useful for, and does your class solve that problem? What else might it be useful for, and can it solve those problems?


Mainly just for practice for now but possibly could use it in a future project.
ok. If its just for practice, I don't want to intimidate you but I would slowly try to make your thing more and more like an stl container. What do all those have in common (lots!!). Why do they have those things?
do you need an assignment operator?
a copy ctor?
.size() ?
iterator support?
can you pass your thing into the appropriate <algorithms>?

Maybe work on just some of those ideas, one by one, see where you end up.


Topic archived. No new replies allowed.