如何在这棵树中进行搜索？

Question

如何在这棵树中进行搜索？

8

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.

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++，还不了解向量的概念。因此我必须在不使用向量的情况下完成这个任务。如果可能的话，您可以建议适当的数据结构。

- Nikhil Chilwant

基本上这是公司的层次结构。 - Nikhil Chilwant

1

在你的搜索函数解决方案中，你正在递归调用search()，但你没有检查这些调用的结果...所以当你有更多节点时，你实际上永远不会得到正确的答案，因为你没有捕获它... - Dusan Plavak

请注意，我的方法图中的第三级节点未连接。此外，子节点数量不固定。那么，在这里如何应用呢？ - Nikhil Chilwant

@DusanPlavak 谢谢。但是我该如何确保一旦我改变了答案（全局变量），就能尽快退出递归。其中一个可能的方法是使用异常。（在异常中，我必须在try之后立即编写catch {....}部分。因此，它不能将我带回main()）。 - Nikhil Chilwant

仍未运行。我分享了整个代码和文本文件。请记得在代码中更改文本文件地址。http://temp-share.com/show/gFHc4Jx6Y - Nikhil Chilwant

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cpp · Accepted Answer

你可以考虑将下一个指针存储在指针的向量（或数组）中：

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


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

然后在你的搜索方法中，你需要迭代这个向量：

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
}

}