Общая высота бинарного дерева поиска

Question

Общая высота бинарного дерева поиска

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

Для меня сложность заключается в том, чтобы назначить высоту каждому узлу, а затем вернуться назад и суммировать ее. Разве я могу назначить и записать высоту за один проход? Заранее спасибо.

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

BST.h

int totalheight(node);
int getHeight(node);

class BST {
Node root;
public:
BST { root = NULL; }
int totalheight()
{ return ::totalheight(root);
};BST.cpp

int totalHeight(BSTNode* node)
{
if (node == NULL)
return -1;

int leftHeight = getheight(node->left);
int rightHeight = getheight(node->right);
int totalheight = 1 + leftHeight + rightHeight; // +1 to count the root

return totalheight;
}

int getheight(BSTNode* node)
{
if (node == NULL)
return 0;

return 1 + max(getheight(node->left), getheight(node->right));
}

main.cpp

int main() {
BST tree; // and various inserts

tree.totalheight();
} // main

1

binary-search-tree c++height recursion

Решение

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

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

Источник

Accepted Answer

Одна проблема здесь:

int myheight = max(leftheight, rightheight);

Так должно быть:

int myheight = max(leftheight, rightheight) + 1;

Вам нужен тот, который учитывает высоту этих узлов. Также в коде показано, чтобы рекурсировать findHeight должно быть getHeight,

Вот общая функция:


int getheight(BSTNode* node)
{
if (node == null)
return 0;
else
return 1 + max(getHeight(node->left), getHeight(node->right));
} // getheight

2