Функция, которая определяет валидность двоичного дерева, проверяя наличие циклов - PullRequest
Новая
       9

Функция, которая определяет валидность двоичного дерева, проверяя наличие циклов

2 голосов
/ 20 апреля 2020

Я должен завершить функцию 

bool HasLoop(Node* root)
{    
}

, которая определяет допустимость двоичного дерева, проверив, есть ли в нем циклы.

Так пример: 

Valid:
  X1
 /  \
X4   X5
 \    \
  X3   X7

Invalid:
  X1
 /  \
X4   X5
 \  /  \
  X3   X7

Моя идея состоит в том, чтобы пометить каждый узел, который мы пересекаем, как посещенный, и если мы снова натолкнемся на посещенный узел, мы будем знать, что существует oop. Но большинство примеров включают наборы, и наш класс еще не прошел через это. Как мне продолжить?

РЕДАКТИРОВАТЬ: С чем я пришел: 

struct Node
{
int data;
struct node *left; 
struct node *right;
bool visited = false;
};

bool HasLoop(Node* root)
{    
  if(root==nullptr)
return;

if(root->visited)
return true;

if(!root->visited)
{
    root->visited = true;
    hasALoop(root->left);
    hasALoop(root->right);
}
return false;


}

Ответы [ 2 ]

2 голосов
/ 20 апреля 2020

Это можно сделать простым обходом дерева, используя атрибут флага visited (в основном, bool переменная-член).

Сначала у вас есть обход, где вы очищаете visited флаг. Затем вы делаете вторую проверку, установлен ли флаг visited для узла. Если это не так, вы устанавливаете его, иначе вы сообщаете о al oop.

. В псевдокоде это может выглядеть примерно так: 

void check_loop(tree_node* const root)
{
    if (root->visited)
    {
        // You have a loop, report it
    }
    else
    {
        root->visited = true;

        // Traverse to children
        if (root->left)
        {
            check_loop(root->left);
        }

        if (root->right)
        {
            check_loop(root->right);
        }
    }
}

В моем примере выше Обход поддерева останавливается после того, как вы нашли al oop.

. Он проверит все узлы дерева, внутренние и конечные узлы, а также перехватит сложные петли, а не только прямые, как вы видите.

0 голосов
/ 20 апреля 2020

Вы можете реализовать функцию, аналогичную той, что я делал в недавнем конкурсе 

bool vis[100000] = {false};
int flag = 0;

void HasLoop(Node* root)
{    

if(root==NULL)
    return;

if(vis[root->data]==false)
    vis[root->data]=true;
else
    flag = 1; // This means it is already visited so set flag = 1


HasLoop(root->left);
HasLoop(root->right);

return;
}

Хотя эта функция работает, только если у вас нет повторяющихся значений данных в дереве. Если он у вас есть, вы можете изменить структуру своего дерева, чтобы каждый узел имел уникальный идентификатор или значение индекса и мог проверить это в массиве vis.

...