Ошибка узла двоичного дерева

Question

Вот определение узла:

struct node{
    int data;
    stuct node * left;
    struct node * right;
};

То, что я пытаюсь сделать, это перечислить все узлы, которые указывают на узел предка. После публикации неправильного решения и получения рекомендаций из ответов, мое новое решение:

Рекурсивно пройти через двоичное дерево. Добавьте текущий узел в массив узлов и затем проверьте, указывают ли дочерние элементы текущего узла на любой из предыдущих узлов-предков.

Случай по умолчанию - это NULL. Если это произойдет, функция вернется.

Как это должно работать:

Добавляет узел в массив

Проверяет, равен ли левый ребенок NULL.

Если нет, он сравнивает дочерний элемент с каждым из предыдущих узлов.

Если он находит ошибку, он сообщает об этом.

Если нет, то она вызывает функцию с дочерним элементом в качестве аргумента.

Повторяйте, пока не закончите. (То же самое для правой части двоичного дерева)

Вопросы:

• Лучше всего хранить массив узлы?
• Это работает? для (i = 0; i
• Поскольку функция рекурсивная, массив и индекс массива не могут инициализироваться внутри функции (или они могут быть?) глобальный?
• Было бы лучше иметь два массива? (один для LHS и один для RHS)

код:

void findFault(node * root){
    if (root == NULL){
      return;
    }

    arrOfNodes[index++] == root; // array of nodes

    if (root->left != NULL){
      for (i = 0; i < sizeof(arrOfNodes) / sizeof(node); i++){
         if (ar[i] == root->left){
             printf("%d", root->left);
             return;
         }
       }
       findFault(root->left);
    } else return;

    if (root->right != NULL){
      for (i = 0; i < sizeof(ar) / sizeof(node); i++){
         if (ar[i] == root->right){
             printf("%d", root->right);
             return;
         }
      }
      findFault(root->right);
    } else return;
}

Answer 1

Я не знаю о рекурсии, но это:

if (&root->left->left == &root){

неправильно во многих отношениях, которые я могу описать, но в любом случае здесь есть три проблемы:

• Почему вы берете адрес root?
• Почему бы вам не проверить, что первый левый указатель равен нулю?
• Вы можете просто использовать std :: map, но научиться реализовывать двоичное дерево тоже хорошая идея.

Answer 2

Это неверное решение проблемы. Нил Баттерворт уже отметил в вашем коде, я отмечу в алгоритме.

Ваш алгоритм проверяет только очень конкретный случай - указывает ли узел внука на своего прародителя. Что вы должны сделать, это собрать родителей по пути к узлу и увидеть, что ребенок узла не является одним из его родителей.

Есть много способов сделать это. Один из них - добавить счетчик в структуру вашего узла и установить счетчики всех узлов на ноль, прежде чем вы начнете обходить дерево. Всякий раз, когда вы достигаете узла, убедитесь, что счетчик равен нулю, а затем увеличиваете его на единицу. Это означает, что если вы видите ребенка, чей счетчик не равен нулю, вы уже посетили его, и поэтому дерево недействительно.

Answer 3

Еще один способ выполнить этот вид проверки - выполнить проверку узлов в ширину, сохраняя при этом вектор уже посещенных узлов (который можно сортировать по адресу). Каждый раз, когда вы посещаете узел, утверждайте, что его нет в векторе, а затем добавляйте его в соответствующее место, чтобы сохранить отсортированный список посещений.

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

Примечания:

• Массив будет хорошим способом хранения узлов. Если вы избегаете STL (любопытно: почему?), Тогда вам придется управлять своей собственной памятью. Выполнимо, но изобретать заново это хрупкое колесо.
• Ваша проверка цикла for для определения размера массивов не будет работать; если вы используете malloc / free или new / delete, вам придется заранее указать размер нужного вам массива; Вы должны использовать этот размер вместо того, чтобы вычислять его каждый раз в цикле for.
• Типичным шаблоном для рекурсивного алгоритма является наличие «внешней» и «внутренней» функции. Внешняя функция вызывается внешним кодом и выполняет первоначальную настройку и т. Д. Внутренняя функция вызывается только функцией outser, имеет тенденцию иметь более сложный набор параметров (принимая данные, установленные внешней функцией), и вызывает Сам выполнить рекурсию.
• Вам понадобятся два массива: один для списка узлов, которые вы посетили, и один для списка узлов, которые вам еще предстоит посетить.

Answer 4

Я не знаю, способен ли алгоритм, который генерирует двоичное дерево, распространять ошибку, отличную от левого / правого дочернего узла.
В любом случае, это исправленная версия для вашего кода:

void findFault(node * root){
    if (root == NULL){
      return;
    }

    if (root->left == root){
      printf("left: %d", root->data);
    } else findFault(root->left);

    if (root->right == root){
      printf("right: %d", root->data);
    } else findFault(root->right);
}