ノード、ツリーCへのパスを見つける

Question

こんにちは私は、ツリー内の特定のノードへのパスを見つけることを試みています。

私は、ツリーを使用して、intの行列として定義された迷路内のすべての可能な経路を分析します。ここで

は行列です：

int room[20][20] = 
{ 
    {0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
}; 

1は2が終了し、0である、壁があることを意味し、ここで

フリースペースですが、私はノードの定義された方法は次のとおりです。

struct node 
{ 
int i,j; //NODE COORDS 
int key; 
struct node *right; 
struct node *left; 
struct node *up; 
struct node *down; 
}; 

ツリーにノードを挿入するために使用しているメソッドは次のとおりです。

void insert(int room[20][20], struct node **leaf, int i, int j) 
{ 

    if(*leaf == 0) 
    { 
     *leaf = (struct node*) malloc(sizeof(struct node)); 
     (*leaf)->key = room[i][j]; 
     (*leaf)->i = i; 
     (*leaf)->j = j; 
     (*leaf)->left = 0; 
     (*leaf)->right = 0; 
     (*leaf)->up = 0; 
     (*leaf)->down = 0; 
    } 
    else if((room[i][j+1]==0 || room[i][j+1]==2) && i<20 && j<20 && i>=0 && j+1>=0)//CHECK IF RIGHT IS FREE OR IS EXIT OF THE MAZE 
    { 
     (*leaf)->key = room[i][j+1]; 
     insert(room, &(*leaf)->right, i ,j+1); 
    } 
    else if((room[i][j-1]==0 || room[i][j-1]==2) && i<20 && j<20 && i>=0 && j-1>=0)//CHECK IF LEFT IS FREE OR IS EXIT OF THE MAZE 
    { 
     (*leaf)->key = room[i][j-1]; 
     insert(room, &(*leaf)->left, i ,j-1); 
    } 
    else if((room[i+1][j]==0 || room[i+1][j]==2) && i<20 && j<20 && i+1>=0 && j>=0)//CHECK IF DOWN IS FREE OR IS EXIT OF THE MAZE 
    { 
     (*leaf)->key = room[i+1][j]; 
     insert(room, &(*leaf)->down, i+1 ,j); 
    } 
    else if((room[i-1][j]==0 || room[i-1][j]==2) && i<20 && j<20 && i-1>=0 && j>=0)//CHECK IF UP IS FREE OR IS EXIT OF THE MAZE 
    { 
     (*leaf)->key = room[i-1][j]; 
     insert(room, &(*leaf)->up, i-1 ,j); 
    } 
} 

はツリーを初期化：

struct node *root = 0; 
for(i=0;i<400;i++) 
insert(room,&root,0,0); //INITIALIZE THE TREE ANALIZING EVERY CELL OF THE MATRIX 

私は値2を持つキー（出口）を検索し、そのノードからルートノードへのパスを見つけることができるようにしたい上記のように、私はツリーを初期化したら、それらの間にあるすべてのノードの座標を収集します。

これを行うには、値2を持つノードを見つけたら、そのノードの親を見つけたいと思います。ルートノードを見つけるまで、そしてそれらの間にノードを見つけるたびに、コイードを配列に入れて、後でそれらを使って出口へのパスを描くことができます。

この場合、値2のノードを見つけるにはどうすればよいですか？

この場合、特定のノードの親ノードを見つけるにはどうすればよいですか？

Answer 1

これは一般的な経路探索の問題のようです。 1つの一般的な解決策は、A* search algorithmを実装することです。どのようにデータを構造化してトラバースするかはあなた次第ですが、このアルゴリズムはA点からB点（最短距離、障害物回避）に到達する方法を説明しています。あなたの状況にこのアルゴリズムを採用することができるはずです。