исключение переполнения стека при получении высоты двоичного дерева

Question

Я пытаюсь создать простое двоичное дерево, затем добавить несколько целых чисел к дереву и, наконец, распечатать высоту дерева. Хотя я, кажется, получаю исключение переполнения стека при вызове метода BinaryTree height (). Кто-нибудь может сказать мне, почему? Пожалуйста, сообщите, если я что-то неправильно реализовал, так как я впервые работаю с двоичными деревьями (я просмотрел несколько руководств и нашел этот код)

TreeNode. cpp

#include "TreeNode.h"


TreeNode::TreeNode(int theData)
{
    theData = value;
}

BinaryTree. cpp

#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
    root = NULL;
}

void BinaryTree::add(int data)
{
    if (root != NULL) {
        add(root,data);
    }
    else {
        root = new TreeNode(data);
        root->value = data;
        root->left = NULL;
        root->right = NULL;
    }
}

int BinaryTree::height()
{
    return height(root);
}



void BinaryTree::add(TreeNode * toAdd, int key)
{
    if (key < toAdd->value) {
        if (toAdd->left != NULL) {
            add(toAdd->left, key);
        }
        else {
            toAdd->left = new TreeNode(key);
            toAdd->left->value = key;
            toAdd->left->left = NULL;
            toAdd->left->right = NULL;
        }
    }
    else {
        if (toAdd->right != NULL) {
            add(toAdd->right, key);
        }
        else {
            toAdd->right = new TreeNode(key);
            toAdd->right->value = key;
            toAdd->right->left = NULL;
            toAdd->right->right = NULL;
        }
    }

}

int BinaryTree::height(TreeNode *node)
{
    if (root == NULL) {
        return 0;
    }
    else {

        int leftSide = height(root->left);
        int rightSide = height(root->right);
        int total = leftSide + rightSide;
        return total;
    }

}

Main. cpp

#include "BinaryTree.h"
#include <iostream>

int main()
{
    BinaryTree *tree = new BinaryTree();

    tree->add(10);
    tree->add(12);
    tree->add(14);
    tree->add(15);
    tree->add(123);
    tree->add(14);
    tree->add(12);
    tree->add(15);

    tree->height();


    return 0;
}

Answer 1

height ссылается на неправильную переменную. Поскольку он смотрит на root и полностью игнорирует параметр node, каждый вызов height будет таким же, и рекурсия, однажды начавшаяся, никогда не закончится.

Замените все ссылки на root с node в height.

if (node == nullptr) 
    return 0;
int leftside = height(node->left);
int rightside = height(node->right);

И несколькими несвязанными вещами:

height может быть объявлено const или может быть частью c члена BinaryTree или перемещен в класс Node.

У вас есть конструктор для TreeNode, который должен обрабатывать инициализацию всех членов класса. Когда вы выделяете или добавляете узел, у вас должна быть только одна строка wherever = new TreeNode(key);. (И в чем разница между theData и value? Вам нужно различать поля для них?)

BinaryTree *tree в main может быть просто объектом, и не обязательно динамически распределяется (BinaryTree tree;, затем изменить все tree-> на tree.).