n child Tree

[navderm]

Hi All,

Its easy to create a tree when you know the no of child each node has.
How do i make a program that makes a tree with arbitrary no. of children which can be specified during run time ?

~Cheers!
navderm

[hanst99]

struct TreeNode
{
TreeNode *left, *right;
ValType val;
};

Something like that. Though of course you could also use an Node array or vector if you don't want a binary tree.

[navderm]

I dont' want a binary tree. and i don't want to use array as it has to be fixed before run time and i don't want to use vector because it becomes very high level abstraction. i want to create a bare bone of such a tree structure... with n (defined for each node separately) at run time.

[hanst99]

Arrays don't need to have defined sizes at compile time.

struct nTreeNode
{
     TreeNode *childArray[];
     ValType val;
     int childNum;
};

void reparentTo(nTreeNode *parent, nTreeNode *child)
{
     
     nTreeNode **_temp, *childArray[] = new nTreeNode*[parent->ChildNum+1];
     memcpy(childArray, parent->childArray, sizeof(nTreeNode*)*(parent->childNum));
     childArray[parent->ChildNum] =  child;
     _temp = parent->childArray;
     parent->childArray = childArray;
     parent->childNum++;
     delete[] _temp;     
     return;
}

Didn't try that one out, but technically it should work. Though I'd actually rather suggest you to go for an object oriented approach, this one here is very prone to user errors.

[m4ster r0shi]

hanst99 wrote:

Arrays don't need to have defined sizes at compile time.

Are you sure about that? How much money would you bet on it? :D

@OP: Does this look good?

template <class T>
struct TreeNode
{
    vector<TreeNode*> children;
    T value;
};

[hanst99]

Uh, I don't need to bet. You can request new chunks of memory any time O_o

Oh, and for some reason he said he doesn't want to use vectors... I'd rather have him use vectors too, but if he refuses, what can we do?

[m4ster r0shi]

hanst99 wrote:

You can request new chunks of memory any time O_o

You're right about that.

However, this -> TreeNode * childArray[]; is not the same as this -> TreeNode ** childArray;

#include <iostream>
using namespace std;

struct StrangeStruct
{
    int * Nothing[];
    int Something;
};

struct NotSoStrangeStruct
{
    int ** NotNothing;
    int Something;
};

int main()
{
    StrangeStruct ss;
    NotSoStrangeStruct nsss;

    cout << "StrangeStruct memory layout" << endl;
    cout << &ss.Nothing << endl;
    cout << &ss.Something << endl;

    cout << "\nNotSoStrangeStruct memory layout" << endl;
    cout << &nsss.NotNothing << endl;
    cout << &nsss.Something << endl;

    cout << "\nhit enter to quit..." << endl;
    cin.get();
    return 0;
}

Check this out -> http://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html

EDIT:

hanst99 wrote:

Oh, and for some reason he said he doesn't want to use vectors...
I'd rather have him use vectors too, but if he refuses, what can we do?

Oh, I just noticed...

navderm wrote:

i don't want to use array as it has to be fixed before run time and i don't want to use vector

Well, is there anything you are willing to use?

[hanst99]

Well, I normally don't work with those, so you might be right on that. But that's language semantics, at least when I say array I just mean a chunk of memory. As I said, I don't know if my example would work exactly like that, but I was just trying to get the idea across. In a real life situation you would have to do a few other things as well anyways, like checkin whether you actually got that new memory or not, or whether child and parent are actually distinct objects...

[navderm]

Hey hanst99 & m4ster r0shi,

I actually wanted to use something more primitive as pointer to pointer or something more basic. I know i can easily do it using vector . but the purpose of this exercise is to be able to build complex tree structure without any high level functionalities.

and i think even if i use a linked list ( a full class which i completed implementing a day ago) i should be able to get it done. But i want something more primitive and more powerful than all this.
~navderm

[hanst99]

You can't get any more basic than pointers you know...

[navderm]

ya pointers and pointer to pointer is what i want to use !!

[filipe]

You can represent a tree with variable, arbitrary numbers of nodes with a linked list. Each node in the list has to be able to hold either a terminal or another list. Then you can just throw in a convention: the first node of each list represents the tree node value, while the remaining nodes represent its children (which can be terminals or lists themselves).

[ne555]

struct TreeNode
{
  TreeNode *lchild, *rbrother;
  ValType val;
};