8

親ノードが任意の数の子ノードを持つことができるツリーデータ構造があります(> = 0)。そんな木を作りたい。私が考えた可能なアプローチの 1 つは、my_approach の図に示すように、リンクされたリストを作成することです。リンクされたリストは、図のように接続されています。

Uは代替アプローチも提案できます

ここに画像の説明を入力 ここに画像の説明を入力

ということで、ツリー内を検索するコードを書いてみました(コードが長くてすみません)私の表記を理解するのを助けるために

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;
                }


            }


}

これは最初のノードでは機能しますが、1 つ以上のノードを追加すると、検索で誤った結果が返されます。注：私はc ++が初めてで、ベクトルの概念を知りません。したがって、ベクトルを使用せずにこれを行う必要があります。また、可能であれば、適切な構造を提案できます。

4

1 に答える 1

1

次のポインターをポインターのベクトル (または配列) に格納することを検討できます。

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
}

}

于 2013-09-14T12:20:40.563 に答える