treenode — C ++ AVL пересчитывает высоту дерева

Question

treenode — C ++ AVL пересчитывает высоту дерева

Я работаю над имплементацией дерева AVL, и у меня возникли проблемы с моей функцией пересчета высоты. Когда я вызываю его, я передаю корень дерева и переменную, которая имеет значение 1. Я прошел по нему и обнаружил, что, как только он попадает в цикл while, он преформируется, как и ожидалось, но после этого возвращается к одному. пожалуйста, посмотрите на это и посмотрите, что я делаю неправильно. Я опубликую больше кода, если нужно, но я думаю, что только функция предоставит вам достаточно информации. Спасибо

void BinaryTree::recalculate(Node *leaf, int count)
{
if(leaf == NULL)//if we are at the root
{
return;//exit the function
}

if((leaf->getLeft() != NULL))//if we are not at the end of the subtree
{
recalculate(leaf->getLeft(), count);//advance to the next node and re-enter the function

}

if(leaf->getRight() != NULL)//if we are not at the end of the right subtree
{
recalculate(leaf->getRight(), count);//advance to the next node and re-enter the program
}

else
{
while(leaf->getParent() != NULL)//calculate each subtree until we are at the root
{
leaf = leaf->getParent();//get the parent node
count++;//increment the height

if(leaf->getLeft() != NULL)//if there is an item in the left
{

leaf->getLeft()->setHeight(count-1);//sets the hight of the left child
}

if(leaf->getRight() != NULL)//if there is an item in the right
{
leaf->getRight()->setHeight(count -1);//sets the height of the right child

}
}

return;//exit the function
}
}

2

avl-tree c++treenode

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Ваша функция должна вычислять высоту каждого поддерева двоичного дерева и сохранять это значение в корневом узле этого поддерева. Вы выбрали рекурсивный подход, который является стандартным. При таком подходе высота как левого, так и правого поддерева должна быть сначала вычислена, а затем для текущего узла берется наибольшее из обоих.

В вашей реализации вы используете значение с именем count передается в параметре для рекурсивного вызова. Какова цель этого значения, учитывая, что нам нужно получить счетчик из подузлов, а не передать их им?

Если ты:

удалить это значение из recalculate параметры
иметь recalculate Сначала вызовите метод для обоих потомков, если это применимо
сделать recalculate обновить текущую высоту узла от каждой высоты подузла

у вас должно быть это работает. Ниже приведена возможная реализация, основанная на этом алгоритме:

void BinaryTree::recalculate(Node *leaf) {
int count = 0;
if (leaf == NULL)  {
return;
}
if (leaf->getLeft() == NULL && leaf->getRight() == NULL) {
// no child, the height is 0
setHeight(0);
return;
}
if (leaf->getLeft() != NULL) {
recalculate(leaf->getLeft());
count = leaf->getLeft()->getHeight();
}
if (leaf->getRight() != NULL){
recalculate(leaf->getRight());
count = max(count, leaf->getRight()->getHeight());
}
// include leaf in the height
setHeight(count+1);
}

Если getHeight метод не может быть использован, вы можете заменить его, имея recalculate вернуть высоту, которую он вычислил.

0