I have a tree data structure in which the parent node can have any number of child nodes (>=0). I want to create such a tree. One possible approach is to create a linked list as shown in the "my_approach" picture. The linked list is connected as shown.
You can suggest alternative approaches.
Here is my code for searching in the tree. (Sorry for the lengthy code.) Please refer to the image for notation clarification.
You can suggest alternative approaches.
Here is my code for searching in the tree. (Sorry for the lengthy code.) Please refer to the image for notation clarification.
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;
}
}
}
这个方法可以在只有一个节点时工作,但是在添加了多个节点后搜索会给出错误的结果。 注意:我刚接触c++,还不了解向量的概念。因此我必须在不使用向量的情况下完成这个任务。如果可能的话,您可以建议适当的数据结构。