程序不显示插入二叉搜索树中的值

Question

我曾尝试编写代码来实现二叉搜索树，但是当我运行我的代码不输出任何内容并关闭程序时。我认为我的插入函数是正确的，因为我在插入函数的多个地方写了 cout<<"yes" ，并显示了我在顺序遍历中使用的二叉搜索树的所有节点，这是在一个简单的函数中递归完成的。这是我的代码：

#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *right;
    Node *left;
};

void insert(Node **root_ref, int value)
{
    Node *temp = new Node();
    temp->data = value;
    temp->right = NULL;
    temp->left = NULL;
    Node *current = *root_ref;
    if (*root_ref == NULL)
    {
        *root_ref = temp;
        return;
    }
    while (current != NULL)
    {
        if ((temp->data < current->data) && (current->left == NULL))
        {
            current->left = temp;
            return;
        }
        else if ((temp->data > current->data) && (current->right == NULL))
        {
            current->right = temp;
            return;
        }
        else if ((temp->data > current->data))
        {
            current = current->right;
        }
        else
        {
            current = current->left;
        }
    }
}

void printinorder(Node *root1)
{
    printinorder(root1->left);
    cout << " " << root1->data << " ";
    printinorder(root1->right);
}

int main()
{
    Node *root = NULL;
    insert(&root, 60);
    insert(&root, 50);
    insert(&root, 70);
    insert(&root, 30);
    insert(&root, 53);
    insert(&root, 80);
    insert(&root, 65);
    printinorder(root);
}

Answer 1

对于初学者来说，当一个值被添加到树中时，如果已经有一个具有相同值的节点，函数 insert 可能会产生内存泄漏，因为在这种情况下只能评估这个 else 语句

while (current != NULL)
{
    //...
    else
    {
        current = current->left;
    }
}

所以循环将结束它的迭代，尽管已经分配了一个节点，但不会向树中添加任何内容。

函数可以写成下面这样的例子

void insert( Node **root_ref, int value )
{
    Node *temp = new Node { value, nullptr, nullptr };

    while ( *root_ref != nullptr )
    {
        if ( ( *root_ref )->data < value )
        {
            root_ref = &( *root_ref )->right;
        }
        else
        {
            root_ref = &( *root_ref )->left;
        }
    }

    *root_ref = temp;
}

在递归函数中printinorder

void printinorder(Node *root1)
{
    printinorder(root1->left);
    cout << " " << root1->data << " ";
    printinorder(root1->right);
}

您没有检查传递的参数是否等于 nullptr。所以函数调用了未定义的行为。

函数可以这样写

std::ostream & printinorder( const Node *root, std::ostream &os = std::cout )
{
    if ( root != nullptr )
    {
        printinorder( root->left, os );
        os << " " << root->data << " ";
        printinorder( root->right, os );
    }

    return os;
}

程序不显示插入二叉搜索树中的值

Program not showing the values inserted in a binary search tree

c++

class

recursion

binary-search-tree

function-definition