C++ 二叉搜索树实现

Question

我正在用 C++ 开发一个项目，在该项目中我必须创建一个二叉搜索树来插入数组中的项目。我必须使用以下插入算法：

树插入（T，z）

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);
    }
}

这段代码可以编译，但是当我运行它时，它会出现段错误。我相信问题与我正在创建的节点或我的函数调用有关。感谢您的帮助。

Answer 1

除了评论中指出的问题外，此代码中最大的错误是缺少将新 node 中的所有指针初始化为 NULL 的构造函数。

因此，您创建的每个 node 都将有包含随机垃圾的指针。您的代码会初始化其中一些，但大多数不会。尝试使用未初始化的指针将导致立即崩溃。

您需要修复评论中提到的所有问题，并为您的 node class.

提供合适的构造函数

C++ 二叉搜索树实现

C++ Binary Search Tree Implementation

c++

algorithm

binary-tree

binary-search-tree