Сбалансированная двоичная древовидная структура, EXC_BAD_ACCESS при использовании рекурсии - PullRequest
Новая
       41

Сбалансированная двоичная древовидная структура, EXC_BAD_ACCESS при использовании рекурсии

0 голосов
/ 30 января 2020

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

Предполагается, что код нажмет NULL и вернет (true, -1) в некоторой точке и go вглубь левого поддерева. Затем вернитесь и go к правому поддереву. Мы можем проверить, сбалансированы ли поддеревы левого и правого каналов разными, если оно <= 1., и получить его высоту по максимуму (слева, справа) +1 для каждого узла. если <= 1 означает несбалансированность возвратов (ложь, высоту), и она пузырится до рекурсии. </p>

Спасибо 

#include <iostream>
using namespace std;

struct TreeNode {
    TreeNode * left;
    TreeNode * right;
};


class balanceStatusAndHeight{
public:
    bool isBalanced;
    int height;
    balanceStatusAndHeight(bool isBalanced, int height);
};


balanceStatusAndHeight::balanceStatusAndHeight(bool isBalanced, int height) {
    this->isBalanced = isBalanced;    
    this->height = height;
}




balanceStatusAndHeight checkBalance(TreeNode * root) {    

    if (root == NULL ) {
        return balanceStatusAndHeight(true, -1);
    }

    balanceStatusAndHeight leftResult = checkBalance(root->left);
    if ( !leftResult.isBalanced  ) {
        return leftResult;
    }

    balanceStatusAndHeight rightResult = checkBalance(root->right);
    if ( !rightResult.isBalanced) {
        return rightResult;
    }


    bool subTreesAreBalanced = abs(leftResult.height - rightResult.height) <= 1;
    int height = max(leftResult.height, rightResult.height) + 1;

    return balanceStatusAndHeight(subTreesAreBalanced, height);

};




int main(int argc, const char * argv[]) {

    TreeNode *a = new TreeNode;
    a->left = new TreeNode;
    a->left->left = new TreeNode;

    balanceStatusAndHeight c = checkBalance(a);


    cout << c.isBalanced << endl;



    return 0;
}

1 Ответ

0 голосов
/ 30 января 2020

В checkBalance

if (root == NULL )

ожидает, что ветви дерева будут NULL завершены. К сожалению, ничто в коде не гарантирует, что деревья NULL завершены, поэтому этот тест не пройден, когда он попадает в неинициализированный указатель left или right, а затем программа пытается получить доступ к недействительному TreeNode по неинициализированному указателю.

С помощью современного компилятора 

struct TreeNode {
    TreeNode * left = NULL; // but prefer nullptr to NULL as it has better type safety
    TreeNode * right = NULL;
};

решает эту проблему. Поскольку nullptr используется вместо *1016*, компилятор может быть старым или преднамеренно установлен на более старую версию C ++ Standard, и вместо этого потребуется конструктор. 

struct TreeNode {
    TreeNode * left;
    TreeNode * right;

    TreeNode():left(NULL), right(NULL)
    {

    }
};

Более умный конструктор или хитрое использование агрегатная инициализация может облегчить вашу жизнь.

Работает ли программа после этого изменения? Без понятия. Не проверял на это. Выходит без кратера sh, хотя.

...