Как сказать, что бинарное дерево "завершено"

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

template<typename TYPE>
bool BinarySearchTree<TYPE>::CompleteTree()
{
    return PCompleteTree(TRoot);
}

template<typename TYPE>
bool BinarySearchTree<TYPE>::PCompleteTree(Node<TYPE>* root)
{
    bool isComplete= false;
    if(root)
    {
        if(abs(PHeight(root->left) - PHeight(root->right)) >= 1)
            isComplete = ((PCompleteTree(root->left)) && (PCompleteTree(root->right)));
        else
            isComplete = false;
    }
    return isComplete;
}

3 ответа

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

Я буду использовать это определение из nist.gov через @jwpat7

Определение: бинарное дерево, в котором каждый уровень, за исключением, возможно, самого глубокого, полностью заполнен. На глубине n высота дерева, все узлы должны быть как можно левее.

Теперь рекурсивному определению помогает определение "идеальный":

Я буду использовать "отлично" для обозначения "каждый уровень полон или пуст". Дерево заполнено, если и левое, и правое поддеревья идеальны и имеют одинаковую глубину.

Тогда мы можем определить завершить рекурсивно следующим образом:

Дерево является полным (по вышеприведенному определению), если оно идеально, или если левое и правое поддеревья имеют одинаковую высоту, а левое идеально и правое завершено, или если левое поддерево на одну глубину правее и право идеально, а слева полно.

Предположим, мы принимаем определение полного двоичного дерева, которое показано на веб-странице nist.gov:

Определение: бинарное дерево, в котором каждый уровень, за исключением, возможно, самого глубокого, полностью заполнен. На глубине n высота дерева, все узлы должны быть как можно левее.

Ссылка NIST, показанная выше, является источником для определения википедии полного двоичного дерева в ее статье о двоичном дереве. Веб-страница NIST указывает, что полное двоичное дерево (высотой n) имеет 2ᵏ узлов на каждой глубине k < nи между 2ⁿ и 2ⁿ⁺¹-1 узлами в целом.

Это правда, что корень невырожденного полного бинарного дерева с n Уровни имеют в качестве своего левого поддерева полное двоичное дерево n-1 уровни и правильное поддерево, которое является полным двоичным деревом n-1 (или возможно n-2) уровни. Тем не менее, тест высоты в вашем коде выглядит неправильно: он, очевидно, устанавливает isComplete = false когда разница в высоте равна нулю. Вместо этого он должен сообщить false, если левая высота меньше, чем правая высота, или если левое поддерево больше, чем на один уровень выше правого поддерева, или если любое поддерево является неполным.

Другие вопросы по тегам