Реализация дерева двоичного дерева C++

Question

Я работаю над проектом на C++, в котором я должен создать двоичное дерево поиска, которое вставляет элементы из массива. Я должен использовать следующий алгоритм вставки:

дерево-вкладыш (Т, г)

y = NIL 
x = T.root 
while x != NIL 
    y = x 
    if z.key < x.key 
     x = x.left 
    else x = x.right 
z.p = y 
if y == NIL 
    T.root = z 
else if z.key < y.key 
    y.left = z 
else y.right = z 

Вот то, что я до сих пор:

#include <iostream> 
using namespace std; 

struct node 
{ 
    int key; 
    node* left; 
    node* right; 
    node* p; 
    node* root; 
}; 

void insert(node*, node*); 
void printinorder(node*); 

int main() 
{ 
    node *root; 
    node* tree = new node; 
    node* z = new node; 
    int array [10] = {30, 10, 45, 38, 20, 50, 25, 33, 8, 12}; 

    for (int i = 0; i < 10; i++) 
    { 
     z->key = array[i]; 
     insert(tree, z); 
    } 

    printinorder(tree); 

    return 0; 
} 

void insert(node *T, node *z) 
{ 
    node *y = nullptr; 
    node* x = new node; 
    x = T->root; 
    while (x != NULL) 
    { 
     y = x; 
     if (z->key < x->key) 
      x = x->left; 
     else 
      x = x->right; 
    } 
    z->p = y; 
    if (y == NULL) 
     T->root = z; 
    else if (z->key < y->key) 
     y->left = z; 
    else 
     y->right = z; 
} 

void printinorder(node *x) 
{ 
    if (x != NULL) 
    { 
     printinorder(x->left); 
     cout << x->key << endl; 
     printinorder(x->right); 
    } 
}  

Этот код компилируется, однако при запуске это, это seg неисправностей. Я считаю, что проблема имеет какое-то отношение к тем узлам, которые я создаю, или к вызовам моей функции. Спасибо за помощь.

Answer 1

Помимо проблем, отмеченных в комментариях, самой большой ошибкой в ​​этом коде является отсутствие конструктора, который инициализирует все указатели в новом node до NULL.

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

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