How to search in this tree?

Question

I have a tree data structure in which parent node can have any number of child nodes(>=0). I want to create such tree. One of the possible approach thought by me is creating a linked list as shown in my_approach picture. Linked list are connected as shown.

U can suggest alternative approach also

So I wrote a code to search in tree.(sorry for long code)

class node
{   public:
    node* boss;
    string name;
    node* next;
    int level;
    node* next_level;
    node* search(string);
    node() : boss(NULL), next(NULL), next_level(NULL){ }
    friend class my_tree;

};

node* ans=NULL;
class my_tree
{
    public:
    my_tree();
    void print(node*);
    node* search(string,node*);
    node* gethead();
    bool is_empty();
    void add(string, node*);
    node* head;
};

my_tree::my_tree()
{
    head=new node;
    head->boss=NULL;
    head->name=""; 
    head->next=NULL;
    head->level=0;
    head->next_level=NULL;
}


bool my_tree::is_empty()
{
    if(head->next_level==NULL)
        {return 1;}
    else if(head->next_level!=NULL)
        {return 0;}
}

node* my_tree::gethead()
{   
    return head;
}

node* my_tree::search(string employee, node* ptr)
{   
    cout<<"ptr="<<ptr<<endl;
    if (ptr==NULL)
        {return NULL;}
    else if(ptr->name==employee)
        {cout<<"yup"<<endl;
        ans=ptr;
        return ptr;}
    else if(ptr->name!=employee)
        {
        search(employee, ptr->next_level);
        search(employee, ptr->next);
        cout<<"in search ans : "<<ans<<endl;
        return ans;
        }

}

void my_tree::add(string employee, node* immediate_boss)
{
    node* temp;
    temp=new node;
    temp->name=employee;
    if(immediate_boss->next_level==NULL)
        {
        temp->boss=immediate_boss;
        temp->level=immediate_boss->level+1;
        immediate_boss->next_level=temp;
        }
    else if(immediate_boss->next_level!=NULL)
        {node* ptr=immediate_boss->next_level;
        while(ptr->next!=NULL)
            {ptr=ptr->next;}
        temp->boss=immediate_boss;
        temp->level=immediate_boss->level+1;
        ptr->next=temp;
        }
    cout<<"employee added:"<<temp->name<<" at "<<temp<<endl;
}


main()
{
    my_tree Company;
    char a;
    string line1;
    string line2;
    a=myfile.get();
    bool e;
    cout<<"head : "<<Company.gethead()<<endl;
    while(myfile.good() and myfile.is_open())
        {

        //I do some operations and get line2 and line1
            //search functions searches for element( here I called employee) and gives its pointer. I use this pointer to add line1 as child node of line2. 
                Company.add(line2,Company.search(line2,Company.gethead()));
                line1.clear();
                line2.clear();
                ans=NULL;
                }


            }


}

This works for 1st node but search gives incorrect result after adding >1 nodes. NOTE : I am new at c++ and don't know concept of vectors. So I have to do this without using vectors. Also ,U can suggest suitable structure if possible.

Answer 1

You may consider storing next pointers in vector (or array) of pointers:

class Node{
public:
    string name() const {return _name;}
....


private:
    string _name;  //some data stored in node
    vector<Node *> next;  //vector of childs
};

Then in your search method you iterate over this vector:

Node *search (string name)
{
    if (_name == name)
        return this;
    else
        for(int ix = 0; ix < next.size(); ++ix)
        {
            Node *temp = next[ix]->search(name);
            if (temp->name() == name)
                return temp;
        }
    return 0; //nothing found
}

}