Блог

Главная - Вопросы по программированию - Как бы вы получили список несбалансированных по высоте конечных узлов в двоичном дереве поиска?

Как бы вы получили список несбалансированных по высоте конечных узлов в двоичном дереве поиска?

#c #data-structures #binary-search-tree

#c #структуры данных #binary-search-tree

Вопрос:

Чтобы узнать, сбалансировано ли дерево по высоте или нет, мы просто сравниваем высоту левого и правого поддеревьев.

Однако как мне создать программу, которая сообщит мне, сколько узлов несбалансировано, и распечатает эти узлы?

Ответ №1:

Как и во всех деревьях вещей: используйте рекурсию.

 int num_unbalanced(node* root, int* height_out, int should_print) {
    if (!root) { *height_out = 0; return 0; }
    int left_height, right_height;
    int left_unbalanced = num_unbalanced(root->left, amp;left_height, should_print);
    int right_unbalanced = num_unbalanced(root->right, amp;right_height, should_print);
    int this_unbalanced = abs(left_height - right_height) > 1;
    *height_out = 1   max(left_height, right_height);
    if (should_print amp;amp; this_unbalanced) print_node(root);
    return left_unbalanced   right_unbalanced   this_unbalanced;
}