Как определить, что бинарное дерево «завершено»
Я не совсем уверен, что делает дерево завершенным, но мне нужно выяснить, завершено ли мое дерево или нет, поэтому я проверяю, сбалансирована ли каждая часть дерева. Если дерево полностью сбалансировано, значит ли это, что оно завершено?
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;
}
Решение
Полное двоичное дерево — это когда каждый уровень, за исключением, возможно, последнего, полностью заполнен всеми узлами как можно левее. Таким образом, могут быть случаи, когда сбалансированное двоичное дерево может также не означать полное двоичное дерево.
Другие решения
Предположим, мы принимаем определение полное двоичное дерево это показано в веб-страница nist.gov:
Определение: бинарное дерево, в котором каждый уровень, кроме, возможно, самого глубокого, полностью заполнен. На глубине n высота дерева, все узлы должны быть как можно левее.
Ссылка NIST, показанная выше, является источником для определения Википедии полное двоичное дерево в его бинарное дерево статья. Веб-страница NIST указывает, что полное двоичное дерево (высотой n) имеет 2ᵏ узлов на каждой глубине k < nи между 2ⁿ и 2ⁿ⁺¹-1 узлами в целом.
Это правда, что корень невырожденного полного бинарного дерева с n Уровни имеют в качестве своего левого поддерева полное двоичное дерево n-1 уровни и правильное поддерево, которое является полным двоичным деревом n-1 (или возможно n-2) уровни. Тем не менее, тест высоты в вашем коде выглядит неправильно: он, очевидно, устанавливает isComplete = false когда разница в высоте равна нулю. Вместо этого он должен сообщить false, если левая высота меньше, чем правая высота, или если левое поддерево больше, чем на один уровень выше правого поддерева, или если какое-либо поддерево является неполным.
Я буду использовать это определение из nist.gov через @ jwpat7
Определение: бинарное дерево, в котором каждый уровень, кроме, возможно, самого глубокого, полностью заполнен. На глубине n высота дерева, все узлы должны быть как можно левее.
Теперь рекурсивному определению помогает определение «идеальный»:
Я буду использовать «отлично» для обозначения «каждый уровень полон или пуст». Дерево полно, если и левое, и правое поддеревья идеальны и имеют одинаковую глубину.
Тогда мы можем определить завершить рекурсивно следующим образом:
Дерево является полным (по вышеприведенному определению), если оно идеально, или если левое и правое поддеревья имеют одинаковую высоту, а левое идеально, а правое завершено, или если левое поддерево на одну глубину правее и право идеально, а слева полно.