Рекурсивный тест, если бинарное дерево поиска завершено

Question

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

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

Мы знаем, что нам нужно проверить уровень h-1 дерева (h высота), чтобы убедиться, что он совершенен, тогда нам нужно убедиться, что все листовые узлы на конечном уровне идут слева вправо без пробелов.

Независимо от того, что мы пытаемся, мы не можем понять, как рекурсивно проверять оставшиеся узлы листа, чтобы убедиться, что они являются последовательными слева направо. Мы можем убедиться, что он идеально до уровня (h-1).

Может ли кто-то указать нам в правильном направлении, как рекурсивно проверять узлы листа на последнем уровне, чтобы убедиться, что они выровнены влево?

до сих пор это код?

public boolean isComplete() 
{ 
    if (isPerfect(root)) 
     return true;  
    return isComplete(root); 

} 
/** 
* 
* @param node 
* @return 
*/ 
private boolean isComplete(Node node) 
{ 
    if (height(node) > 1) 
    { 
    if (node.left != null && node.right != null && (height(node.left) == height(node.right))) 
     return isComplete(node.left) && isComplete(node.right); 
    else 
     return false; 
    } 

} 

PS все тривиальные случаи обрабатываются в методе isPerfect(), так как каждое совершенного дерево также полный

Answer 1

Я был в состоянии общаться с моим профессором, и он сообщил MOF в O (N) способ сделать это только один параметр в методе isComplete, по сравнению с некоторыми ответами здесь.

этот ответ здесь является лучшим ответом на мой первоначальный вопрос

1. если Hr> гл дерево не является полным.
2. если hL - HR> 1, дерево не является полным.
3. если Hr == ЛЕ, то левое поддерево должно быть совершенным и правое поддерево должно быть полным
4. иначе (ЛЙ - Hr == 1), то левые поддерева должно быть совершенным и правое поддерево сусла быть совершенным.

шаги 3 и 4 должны рекурсивно проверить, если дерево isPerfect() и isComplete()

Answer 2

Постараюсь первой нотой алгоритма для проверки полноты, а затем перейдут к коде ,

Давайте подумаем об этом в подходе к порядку обхода.

• нужно количество узлов в дереве
• рекурсии от корня, лечение корня как индекс узла 0
• , если узел является нулевым, дерево является полным
• , если индекс узла больше, чем (или равное числу узлов в дереве, то оно не является полным
• рекурсия в левом и правом поддереве; с учетом предварительного подхода к обходу, левое дерево получает индекс 2*i + 1, а правое дерево получает 2*i + 2.

Немного понимания того, почему это должно сработать.

Ниже приводится полное дерево [с индексами узлов в квадратных скобках]. Обратите внимание, что индексы узлов в случае этого полного двоичного дерева строго меньше, чем число узлов в полном двоичном дереве.

  1 [0] 
     /\ 
     / \ 
    [1] 2  3 [2] 
    /\ 
    / \ 
[3] 4  5 [4] 

Функции возвращать общее количество узлов в дереве

private int totalNodes(Node root) { 
    if (root == null) 
     return 0; 

    return 1 + totalNodes(root.left) + totalNodes(root.right)); 
} 

Теперь обертка isComplete функции() [с 0 параметрами, так как корень будет поле класса] ...

public boolean isComplete() { 
    return isCompleteHelper(root, 0, totalNodes(root)); 
} 

isCompleteHelper() ...

private booelan isCompleteHelper(Node root, int indx, int totalNodes) { 

    // empty tree 
    if (root == null)   
     return true; 

    // present index >= number of nodes in tree 
    if (indx >= totalNodes) 
     return false; 

    // recurse 
    return isCompleteHelper(root.left, 2*indx+1, totalNodes) && isCompleteHelper(root.right, 2*indx+2, totalNodes); 
}