Binary Tree - Complete

Question

В настоящее время я изучаю BST и записываю различные функции, такие как поиск вставки. Я наткнулся на интересный вопрос о задании программирования и попросил написать функцию, которая проверит, завершен ли bst.

Так что я понимаю, что BST завершен, если все листья заканчиваются на том же уровне.

Мой возможный подход для этого решения

я понял, что высоту правого и левого узлов должны быть одинаковыми, если листья под них заканчиваются на том же уровне. поэтому могу ли я сделать простую проверку, чтобы увидеть, соответствует ли высота правого под дерева таким же, как левое поддерево, и если это тогда, то это должно указывать мне, что дерево BST завершено. Может ли кто-нибудь подтвердить правильность моего подхода или предложить другие возможные подходы? Я не ищу код, просто хочу работать над своим пониманием и подходом.

Answer 1

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

• Является ли левый ребенок корнем полного BST, и если да, то какова его высота?
• Является ли правильный ребенок корнем полного BST, и если да, то является ли его высота такой же, как у левого ребенка?

Если ответ на оба является да, у вас есть полный BST.

Другой способ решить эту проблему - ответить на следующие три вопроса о дереве.

• Является ли это BST?
• Сколько в нем узлов?
• Какова его высота?

Если дерево является BST высоты h с 2**h - 1 узлами, у вас есть полный BST. На каждый из трех вопросов можно ответить рекурсивным обходом дерева.

Answer 2

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

 5 
     /\ 
    3 6 
    / \ 
    1  7 

Это дерево имеет равный левые и правые, но 6 не оставили ребенок и 3 не имеют права ребенка. И определение полного дерева Полное бинарное дерево представляет собой бинарное дерево, в котором каждый уровень, за исключением, возможно, последний, полностью заполнен, and all nodes are as far left as possible

Количество узлов = 2^п-1 не собирается решать это также потому, что оно может содержать это число, но не сбалансировано.

Правильный подход будет

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

и что обрабатывать такой случай (который является полным BST деревом)

 4 
     /\ 
    2 6 
    /\ /\ 
    1 3 5 

Answer 3

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

Код выглядит

int isComplete(Tree *t){ 
    if(t->left==NULL && t->right==NULL) 
     return 0; 
    else if(t->left!=NULL && t->right != NULL){ 
     int leftheight = isComplete(t->left); 
     int rightheight = isComplete(t->right); 
     if(leftheight == rightheight && leftheight != -1) 
      return leftheight+1； 
    } 
    return -1; 
} 

-1 указывает не полный. Неотрицательный возврат указывает высоту дерева.