Найти путь к узлу, Дерево 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); 
    } 
} 

Initialise Дерево:

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, я хочу найти родителя этого узла и так далее, пока не найду корневой узел, и каждый раз, когда я нахожу узел между ними, я хочу сохранить его coords в массиве, поэтому позже я могу использовать их, чтобы нарисовать путь к выходу.

Как найти узел, который имеет значение 2 в этом случае?

Как найти родительский узел данного узла в этом случае?

Answer 1

Это похоже на общий вопрос, связанный с поиском путей. Одним из популярных решений является внедрение A* search algorithm. Как вы в конечном итоге структурируете и обходите свои данные, зависит от вас, но этот алгоритм описывает, как добраться от точки A до B (кратчайшее расстояние, избегая препятствий). Вы должны уметь использовать этот алгоритм для своей ситуации.