Как работать с бинарным деревом в C ++?

Question

У меня есть программа, в которой у меня есть двоичное дерево, представленное в виде структуры с двумя указателями и корнем. Затем я хочу ввести n элементов (обозначаемых переменной br) в качестве значений узлов дерева. Затем я ввожу эти элементы, используя функцию add(param1,...). Однако, когда я нажимаю клавишу возврата, после того как я ввел их все, программа вылетает. Я хотел бы спросить, почему это происходит?

// TreeGraph.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
struct elem {
    char key;
    elem *left, *right;
} *root = NULL;
void add(int n, elem * &t);
int num,br,i;
int main()
{
    cout << "Въведете брой елементи\n";
    cin >> br;
    cout << "Въведете стойнсотите на листата на дървото\n";
    while (i != br) {
    cin >> num;
    add(num, root);
    i++;
    }
    return 0;
}
void add(int n, elem * &t) {
    if (t) {
        t = new elem;
        t->key = n;
        t->left = t->right = NULL;
    }
    else {
        if (t->key < n)
            add(n, t->right);
        else
            add(n, t->left);
    }
}

Answer 1

Проблема не в бесконечном цикле. Вы разыменовываете нулевой указатель, поэтому программа вылетает.

В этом коде:

void add(int n, elem * &t) {
    if (t) {
        t = new elem;
        t->key = n;
        t->left = t->right = NULL;
    }
    else {
        if (t->key < n)
            add(n, t->right);
        else
            add(n, t->left);
    }
}

Ваше условие для добавления узла неверно. Это должно быть if (!t). Местоположение нового узла в бинарном дереве поиска должно быть дочерним по отношению к узлу с хотя бы одним нулевым дочерним указателем. Чтобы добавить узел, вам нужна рекурсия, чтобы добраться до одного из этих нулевых указателей, а затем добавить туда узел.

Подумайте о том, что происходит, когда вы передаете изначально нулевой корень функции add. Условие в первом операторе if является ложным, поэтому при попытке проверить условие if (t->key < n) вы пытаетесь получить доступ к полю key несуществующего объекта.