I do not understand how to implement a "general tree" ADT

[Bdanielz]

I have been looking trough stack, all the c++ books I can find online, cplusplus forum and I cannot find one implementation of "general tree".

Could someone help me understand what a general tree is. I can find quite a bit of info on AVL, nth-child trees, Red Black Trees etc, but I cannot find any clear information about general trees.

Could someone offer a simple example?
Pesudo code?
A general overview?
A chapter in a book to read?
ANY online examples?
Links to any information?

Please let me know if you have any specific questions for me. I do not want people to do work for me, I just need to understand the concept though a simple implementation and example

For instance...

Here is some info I found on stack, that looks like the way I want to go, but I am still not making the connection.

http://stackoverflow.com/questions/26102323/how-do-i-use-doubly-pointer-in-c-for-general-tree-data-structure

and the upvoted post

For general tree data structure you can use :-

 struct tree{
 int element;
 struct tree *firstchild;
 struct tree *nextsibling;
 };

lement contains the data to be inserted at the node.

FirstChild contains the firstchild of the node.

nextsibling contains the other child of the same parent node. Example :-

   A

 B  C  D

EF  G     H

then

A->firstchild = B;
        B->nextsibling=C;
        C->nextsibling=D;
B->firstchild=E;
        E->nextsibling=F;
C->firstchild=g;
D->firstchild=H;

Other values which are not specified can taken as NULL;

The above makes sense from a conceptional point of view but I am not seeing the picture about how to implement it. Any advise or info would be appreciated.


EDIT 0:

I found
http://www.rsbauer.com/class/dsa2/slides/General%20Trees.pdf

General trees are similar to binary trees, except
that there is no restriction on the number of
children that any node may have.

So how would you take a binary tree and modify it? Is that the problem I need to solve?


EDIT 1:

This looks promising...

http://web.eecs.utk.edu/~mclennan/Classes/102/thinkCScpp/chap21.htm

[Bdanielz]

ok...
I think I got it..
based on
http://web.eecs.utk.edu/~mclennan/Classes/102/thinkCScpp/chap21.htm


Main.cpp

#include <iostream>
#include "Tree.h"


int main ( int argc, const char * argv[] )
{
    //  We allocate the child nodes first:
    Tree* left = new Tree ( 2, NULL, NULL );
    Tree* right = new Tree ( 3, NULL, NULL );
    //  We can create the parent node and link it to the children at the same time:
    Tree* tree = new Tree ( 1, left, right );
    // print total
    std::cout << tree->total ( tree ) << std::endl;
    //  print each node
    tree->print ( tree );
    std::cout << std::endl;
    // Print in order
    tree->printInorder ( tree );
    std::cout << std::endl;
    // Print Post order
    tree->printPostorder ( tree );
    return 0;
}

Tree.h

#ifndef __generalTreeClass__Tree__
#define __generalTreeClass__Tree__

#include <iostream>

class Tree
{
    public:
        Tree ( int cargo, Tree* left, Tree* right );
        int total ( Tree* tree );
        void print ( Tree* tree );
        void printPostorder ( Tree* tree );
        void printInorder ( Tree* tree );
        
    private:
        int cargo;
        Tree *left, *right;
};

#endif /* defined(__generalTreeClass__Tree__) */ 

Tree.cpp

#include "Tree.h"

Tree::Tree ( int cargo, Tree* left, Tree* right )
{
    this->cargo = cargo;
    this->left = left;
    this->right = right;
}

int Tree::total ( Tree* tree )
{
    if ( tree == NULL ) return 0;
    int cargo = tree->cargo;
    return cargo + total ( tree->left ) + total ( tree->right );
}

void Tree::print ( Tree* tree )
{
    if ( tree == NULL ) return;
    std::cout << tree->cargo << " ";
    print ( tree->left );
    print ( tree->right );
}

void Tree::printPostorder ( Tree* tree )
{
    if ( tree == NULL ) return;
    printPostorder ( tree->left );
    printPostorder ( tree->right );
    std::cout << tree->cargo << " ";
}

void Tree::printInorder ( Tree* tree )
{
    if ( tree == NULL ) return;
    printInorder ( tree->left );
    std::cout << tree->cargo << " ";
    printInorder ( tree->right );
}

output

6
1 2 3 
2 1 3 
2 3 1 

[Gamer2015]

My Tree Container class is a little bit different...
the Nodes themselves don't know anything about the rest.

However, I never used my Tree class...

It looks like this:

template <typename _identifier, typename _datatype>
class Tree : public std::map<_identifier, Tree<_identifier, _datatype>>
{
public:
	Tree() {}
	Tree(const _datatype& val) { mValue = val; }

	_datatype operator=(const _datatype& rhs) { return mValue = rhs; }
	using std::map<_identifier, Tree<_identifier, _datatype>>::operator=;
	_datatype value() const { return mValue; }

private:
	_datatype mValue;
};

and you can use it like that

namespace std
{
    std::string to_string(const std::string& _string) // to_string is not overloaded for std::strings
    {
        return _string;
    }
}
template <typename _id, typename _data>
void PrintTree(const Tree<_id, _data>& tree, std::string prefix)
{
    prefix += "/";
    std::cout << prefix << tree.value() << std::endl;

    for(typename Tree<_id, _data>::const_iterator iter = tree.begin(); iter != tree.end(); ++iter)
    {
        std::string tmp = prefix;
        tmp += std::to_string(iter->first);
        PrintTree(iter->second, tmp);
    }
}

int main(void)
{
    Tree<std::string, std::string> tree;
    tree = "Managers";
    tree["branch1"]["Leaf1"] = "Herbert";
    tree["branch1"]["Leaf2"] = "John";
    tree["branch1"]["Leaf3"] = "Christian";
    tree["branch2"]["Leaf1"] = "Stefan";
    tree["branch2"]["Leaf2"] = "Martin";
    tree["branch2"]["Leaf3"] = "Daniel";
    tree["branch3"]["Leaf1"] = "David";
    tree["branch3"]["Leaf2"] = "Marco";
    tree["branch3"]["Leaf3"] = "Deen";
    tree["super"]["mega"]["large"]["branch"]["Leaf1"] = "Deen";

    PrintTree(tree, "");

    return true;
}

output:

/Managers
/branch1/
/branch1/Leaf1/Herbert
/branch1/Leaf2/John
/branch1/Leaf3/Christian
/branch2/
/branch2/Leaf1/Stefan
/branch2/Leaf2/Martin
/branch2/Leaf3/Daniel
/branch3/
/branch3/Leaf1/David
/branch3/Leaf2/Marco
/branch3/Leaf3/Deen
/super/
/super/mega/
/super/mega/large/
/super/mega/large/branch/
/super/mega/large/branch/Leaf1/Deen

However, since I never actually used that class I don't know anything more than that^^

But you see, there are many possibilities to implement a tree :)

[Bdanielz]

- Nice.
Would you mind explaining two things to me about your code?

What is your reasoning for doing this? Is this just saving you from typing std::string?

namespace std
{
    std::string to_string(const std::string& _string) // to_string is not overloaded for std::strings
    {
        return _string;
    }
}

How would your tree deal with objects? I think since it is "templeted", I am assuming really well? Cold you show a trivial example with an object in your tree instead of a string?

Thanks in advace

[Gamer2015]

- Nice.
Would you mind explaining two things to me about your code?

What is your reasoning for doing this? Is this just saving you from typing std::string?

namespace std
{
    std::string to_string(const std::string& _string) // to_string is not overloaded for std::strings
    {
        return _string;
    }
}

No, the problem is that std::to_string is not overloaded for std::string
I use std::to_string in PrintTree because i want to print integer and strings.
to_string is only overloaded for numeric types but not for std::string so the compiler gave me something like "std::to_string(std:string) does not exist" so i implemented it this way

How would your tree deal with objects? I think since it is "templeted", I am assuming really well? Cold you show a trivial example with an object in your tree instead of a string?

Thanks in advace

I think something like this should work, not tested though
edit: Tested, it works

class SomeObject
{
public:
    SomeObject() : name(), position() {}
    SomeObject(std::string _name, std::string _position) : name(_name), position(_position)
    {}
    void print() const { std::cout << name << ' ' << position << std::endl; }
    std::string name;
    std::string position;
};

//...

    Tree<std::string, SomeObject> tree3;
    tree3 = SomeObject("Manager", "Bert");
    tree3.value().print();

edit:
up until now you couldn't modify the Object, but is it a good idea to overload operator-> to modify it?

template <typename _identifier, typename _datatype>
class Tree : public std::map<_identifier, Tree<_identifier, _datatype>>
{
public:
	Tree() {}
    Tree(const _datatype& val) { _mValue = val; }

    _datatype operator=(const _datatype& rhs) { return _mValue = rhs; }
	using std::map<_identifier, Tree<_identifier, _datatype>>::operator=;

    _datatype* operator->() { return &_mValue; }
    _datatype get() const {return _mValue; }

private:
    _datatype _mValue;
};

//...
class SomeObject
{
public:
    SomeObject() : name(), position() {}
    SomeObject(std::string _name, std::string _position) : name(_name), position(_position)
    {}
    void print() const { std::cout << name << ' ' << position << std::endl; }
    std::string name;
    std::string position;
};

// ...
tree<std::string, SomeObject> tree;
tree["Manager1"]->name = "Paul";
tree["Manager1"]->position = "Manager";
tree["Manager1"].get().print();