Basic Tree Template

What i'm whilling to do is to create a basic Tree that accepts all kind of data.
But i get an error when trying to dynamically initializate an arm.
The Tree should work like this:
Father->Son(Where son is a list of Sons)
And when i do Son->Add(new ArmS<T>) it requires me to put an int insthead of *int

here is the code:

//tree.h
#include "list.h"
template <class T>
struct ArmS
{
    T Item;
    ArmS *Father;
    List<ArmS> *Sons;
    int NumberOfSons;
};

template <class T>
class Tree
{
public:
    Tree();
    ArmS<T> *Up();
    ArmS<T> *Down();
    ArmS<T> *Down(int);
    int RNumberOfSons();
    void NewArm(T);
    T AddItem(T);
private:
    ArmS<T> Arm;
    ArmS<T> *CurrentArm;
};

template <class T>
Tree<T>::Tree()
{
    this->CurrentArm = &this->Arm;
}

template <class T>
void Tree<T>::NewArm(T Item)
{
    if(this->CurrentArm->NumberOfSons = 0)
    {
        this->CurrentArm->Item = Item;
    }

//errors are here
    else
    {
        this->CurrentArm->Sons->Add(new ArmS<T>); //actually this line.
        this->CurrentArm->NumberOfSons++;
        this->CurrentArm->Sons->Return(this->CurrentArm->NumberOfSons)->Father = this->CurrentArm;
        this->CurrentArm->Sons->Return(this->CurrentArm->NumberOfSons)->Item = Item;
    }
}

template <class T>
T Tree<T>::AddItem(T Item)
{
    this->CurrentArm->Item = Item;
}

template <class T>
int Tree<T>::RNumberOfSons()
{
    return this->CurrentArm->NumberOfSons;
}

template <class T>
ArmS<T> *Tree<T>::Up()
{
    if(this->CurrentArm->Father == NULL)
    {
        return this->CurrentArm;
    }
    else
    {
        this->CurrentArm = this->CurrentArm->Father;
        return this->CurrentArm;
    }
}

template <class T>
ArmS<T> *Tree<T>::Down()
{
    if(this->CurrentArm->NumberOfSons == 0)
    {
        return this->CurrentArm;
    }
    else
    {
        this->CurrentArm = this->CurrentArm->Sons->Return(1);
        return this->CurrentArm;
    }
}

template <class T>
ArmS<T> *Tree<T>::Down(int Pos)
{
    this->CurrentArm->Sons->Return(Pos);
    return this->CurrentArm;
}

[code]
//list.h
#pragma once
template <class T>
struct Object
{
    T Item;
    Object *Previous;
    Object *Next;
    int N;
};

template <class T>
class List
{
public:
    List();
    T Add(T);
    /*T Delete(int); To Implement */
    T Next();
    T Previous();
    T Return(int); //To "Betterize"

    //
private:
    Object<T> *Start;
    Object<T> *End;
    Object<T> Item;
    static int ItemNumber;
    int ItemNumberP();
};
template <class T>
int List<T>::ItemNumber = 0;

template <class T>
int List<T>::ItemNumberP()
{
    ItemNumber++;
    return ItemNumber;
}
//Now

template <class T>
List<T>::List()
{
    this->Item.Item = 0;
    this->Item.Next = 0;
    this->Item.Previous = 0;
    this->Start = 0;
    this->End = 0;
}

template <class T>
T List<T>::Add(T Itm)
{
    if(this->Start == 0)
    {
        this->Start = &this->Item;
        this->End = this->Start;
        this->Item.Item = Itm;
        this->Item.N = ++ItemNumber;
    }
    else
    {
        this->End->Next = new Object<T>;
        this->End->Next->Previous = this->End;
        this->End = this->End->Next;
        this->End->Item = Itm;
        this->End->N = ++ItemNumber;
    }
}

/*To Implement
template <class T>
T List<T>::Delete(int N)
{

}

template <class T>
T List<T>::Previous()
{
    return CurrentItem->Previous;
}

template <class T>
T List<T>::Next()
{
    return CurrentItem->Next;
}
*/

template <class T>
T List<T>::Return(int Selection)
{
    if(Selection > this->End->N)
    {
        return this->End->Item;
    }
    else
    {
        bool found = true;
        Object<T> *ToFound;
        ToFound = this->Start;
        do
        {
            if(Selection == ToFound->N)
            {
                found = true;
            }
            else
            {
                ToFound = ToFound->Next;
                found = false;
            }
        }
        while(found != true);
        return ToFound->Item;
    }
}

[code]
and ofc main.
[code]
#include <iostream>
#include <fstream>
#include "list.h"
#include "list2.h"
#include "tree.h"
using namespace std;

int main()
{
    Tree<int> tre;
    cout << "Hello world!" << endl;
    cout << "Testing Tree:" << endl;
    cout << "U: UP \t D: DOWN" << endl;
    tre.NewArm(123);
    tre.Down();
    return 0;
}

The errors:

\Projects\Tree\tree.h||In instantiation of 'void Tree<T>::NewArm(T) [with T = int]':|
\Tree\main.cpp|14|required from here|
\tree.h|36|warning: suggest parentheses around assignment used as truth value [-Wparentheses]|
\Tree\tree.h|42|error: no matching function for call to 'List<ArmS<int> >::Add(ArmS<int>*)'|
\Tree\tree.h|42|note: candidate is:|
\Tree\list.h|52|note: T List<T>::Add(T) [with T = ArmS<int>]|
\Tree\list.h|52|note:   no known conversion for argument 1 from 'ArmS<int>*' to 'ArmS<int>'|
\Tree\tree.h|44|error: base operand of '->' has non-pointer type 'ArmS<int>'|
\Tree\tree.h|45|error: base operand of '->' has non-pointer type 'ArmS<int>'|
\Tree\tree.h||In instantiation of 'ArmS<T>* Tree<T>::Down() [with T = int]':|
\main.cpp|15|required from here|
\Tree\tree.h|84|error: cannot convert 'ArmS<int>' to 'ArmS<int>*' in assignment|
||=== Build finished: 4 errors, 5 warnings (0 minutes, 0 seconds) ===|

Last edited on

coder777 (8439)

on line 8 you probably want this:

List<ArmS *> Sons; // Now it's a list of pointers to ArmS. Note the position of the *

you can have a pointer to the list, but you need the list as an object anyway

xx1182 (54)

But why this line has changed:

this->CurrentArm->Sons.Add(new ArmS<T>); //. insthead of ->

also

List<ArmS *> Sons; // Now it's a list of pointers to ArmS

before what was(sorry for my english) i use a grammatical Approach.

Last edited on

coder777 (8439)

But why this line has changed:

because Sons is now the object itself not a pointer.

So you don't need to Sons = new List<ArmS *> (what you didn't do anyway -> crash)

xx1182 (54)

OK, i got another problem, here is the changed tree.h
What i'm willing to do is this:
First i add something, then i add 2 sons,
then i go down to the first son and try to add a son.
But my program crashes..

//tree.h
#include "list.h"
template <class T>
struct ArmS
{
    T Item;
    ArmS *Father;
    List<ArmS*> Sons;
    int NumberOfSons;
};

template <class T>
class Tree
{
public:
    Tree();
    ArmS<T> *Up();
    ArmS<T> *Down();
    ArmS<T> *Down(int);
    ArmS<T> *GoTop();
    void NewArm(T);
    T Return();

    ArmS<T> Arm;
    ArmS<T> *CurrentArm;
};

template <class T>
Tree<T>::Tree()
{
    this->CurrentArm = &this->Arm;
    this->CurrentArm->NumberOfSons = 0;
    this->CurrentArm->Item = NULL;
}

template <class T>
void Tree<T>::NewArm(T Item)
{
    if(this->CurrentArm->Item == NULL)
    {
        this->CurrentArm->Item = Item;
        this->CurrentArm->NumberOfSons++;
    }
    else
    {
        this->CurrentArm->Sons.Add(new ArmS<T>);
        this->CurrentArm->NumberOfSons++;
        this->CurrentArm->Sons.Return(this->CurrentArm->NumberOfSons)->Father = this->CurrentArm;
        this->CurrentArm->Sons.Return(this->CurrentArm->NumberOfSons)->Item = Item;
    }
}

template <class T>
T Tree<T>::Return()
{
    return this->CurrentArm->Item;
}

template <class T>
ArmS<T> *Tree<T>::Up()
{
    if(this->CurrentArm->Father == NULL)
    {
        return this->CurrentArm;
    }
    else
    {
        this->CurrentArm = this->CurrentArm->Father;
        return this->CurrentArm;
    }
}

template <class T>
ArmS<T> *Tree<T>::Down()
{
    if(this->CurrentArm->NumberOfSons == 0)
    {
        return this->CurrentArm;
    }
    else
    {
        this->CurrentArm = this->CurrentArm->Sons.Return(1);
        return this->CurrentArm;
    }
}

template <class T>
ArmS<T> *Tree<T>::Down(int Pos)
{
    if(this->CurrentArm->NumberOfSons == 0)
    {
        return this->CurrentArm;
    }
    else
    {
        this->CurrentArm = this->CurrentArm->Sons.Return(Pos);
        return this->CurrentArm;
    }
}

template <class T>
ArmS<T> *Tree<T>::GoTop()
{
    this->CurrentArm = this->Arm;
}

and The main

#include <iostream>
#include <fstream>
#include "list.h"
#include "list2.h"
#include "tree.h"
using namespace std;

int main()
{
    Tree<int> tre;
    cout << "Hello world!" << endl;
    cout << "Adding Items to the tre" << endl;
    tre.NewArm(123);
    tre.NewArm(432);
    tre.NewArm(444);
    tre.Down();
    tre.NewArm(44444);
    return 0;
}

xx1182 (54)

It is permitted to BUMP?

coder777 (8439)

somehow i think that you have a rather faint idea about what you're doing?

your current problem is the (oddly named) function:

template <class T>
T List<T>::Return(int Selection)
{
    if(Selection > this->End->N) // what happens when this->End is null?
    {
        return this->End->Item;
    }
    else
    {
        bool found = true;
        Object<T> *ToFound;
        ToFound = this->Start; // what happen when this->Start is null?
        do
        {
            if(Selection == ToFound->N)
            {
                found = true;
            }
            else
            {
                ToFound = ToFound->Next;
                found = false;
            }
        }
        while(found != true);
        return ToFound->Item; // what will happen if ToFound is null?
    }
}

Your're trying to find the object (usually named as node) by the index, but the way you use the index in the tree does not correlate with the index in the list. For instance

this->CurrentArm->Sons.Return(this->CurrentArm->NumberOfSons)->Father = this->CurrentArm

this->CurrentArm->NumberOfSons in a subtree might be 1, but there might be a lot of others in other branches/'arm's. The indexes in the list are continuous hence 1 is a complete different 'arm'

Topic archived. No new replies allowed.

C++

Forum

Basic Tree Template