c++ - 这段插入 BST 的代码有什么问题？

Question

所以我写了这段代码用于在 BST(二叉搜索树)中插入一个节点，但程序总是打印出树是空的。我想我所做的函数调用有问题。你能解释一下这个问题吗？

    #include <bits/stdc++.h>
    #include <conio.h>
    using namespace std;

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


    void insert(node* root, int item)
    {
        if(root == NULL)
        {
            node* temp = new node();
            temp->key = item;
            temp->left = NULL;
            temp->right = NULL;
            root = temp;
        }
        else
        {
            if((root->key)>item)
            {
                insert(root->left,item);
            }
            else 
            {
                insert(root->right,item);
            }
        }
    }

    void inorder(node* root)
    {
        if(root!=NULL)
        {
            inorder(root->left);
            cout<<" "<<root->key<<" ";
            inorder(root->right);
        }
        else cout<<"The tree is empty.";
    }

    int main()
    {
        // cout<<endl<<" Here 5 ";
        node* root = NULL;
        int flag = 1 , item;
        while(flag == 1)
        {
            cout<<"Enter the number you want to enter : ";
            cin>>item;
            // cout<<endl<<" Here 6";
            insert(root, item);
            cout<<"Do you want to enter another number (1 -> YES)?";
            cin>>flag;
        }
        cout<<"The final tree is :";
        inorder(root);
        getch();
        return 0;
    }

Answer 1

首先，插入有点不正确。根指针必须通过引用传递。只是一些，例如:

void insert(node *& root, int item)
{
  if(root == NULL)
    {
      node* temp = new node();
      temp->key = item;
      temp->left = NULL;
      temp->right = NULL;
      root = temp;
    }
  else
    {
      if ((root->key) > item)
        {
          insert(root->left,item);
        }
      else 
        {
          insert(root->right,item);
        }
    }
}

它在结构上与您的代码相同(除了对根的引用)

此外，您的中序遍历很奇怪，因为它会打印出消息“The tree is empty”。每次遍历检测到一个空节点。我会这样修改:

void inorder(node* root)
{
  if (root == NULL)
    return;

  inorder(root->left);
  cout<<" "<<root->key<<" ";
  inorder(root->right);
}

最后，我会稍微修改 main() 以管理树为空时的情况(而不是在中序遍历中进行):

int main()
{
  node* root = NULL;
  int flag = 1 , item;
  while(flag == 1)
    {
      cout<<"Enter the number you want to enter : ";
      cin>>item;
      insert(root, item);
      cout<<"Do you want to enter another number (1 -> YES)?";
      cin>>flag;
    }
  cout<<"The final tree is :";
  if (root == NULL)
    cout << "The tree is empty.";
  else
    inorder(root);
  cout << endl;
  return 0;
}