c++ - bst 插入递归 C++

Question

我有一个 bst 封装在一个带有嵌套节点的类中。

当我尝试插入然后打印树时，类的根属性似乎没有更新，即使我更新了它。

void bst::insert(int key,node* temp)
{
  if(temp==NULL)
  {
      node* ptr=getnewnode(key);
      if(root==NULL)
        root=ptr;
       else
       {
         temp=ptr;
         return ;
       }
  }
     if(key<temp->key)
      insert(key,temp->left);
     if(key>temp->key)
      insert(key,temp->right);
}

class bst
{
typedef struct node
{
int key;
node* left;
node* right;
}node;
node* root; 
void insert(int key,node* temp);
public:
inline void _insert(int key){insert(key,root);}   
};

当我插入说 22,11,33 然后打印它时，它只显示 22，始终是根节点。

Answer 1

我想当您从类外部调用 insert() 时，NULL 将作为第二个参数提供，因为 root 是私有(private)的。

问题 1:

如果你insert(22, NULL)第一个节点被添加到你的bst中作为傻瓜:

  ... 
     if(root==NULL)   // yes, the bst is still empty:  
        root=ptr;     // so root is set to the new node that was created
     else {...}       // and this bloc is ignored 
  }
  if(key<temp->key)   // OUCH !!!! temp is not initalized here                        
  ...                 

你在这里冒着内存损坏或段错误的风险!

问题 2:

如果您随后 insert(11, NULL) 会发生以下情况:

  ... 
      if(root==NULL)   // No, the bst has already a root  
      else {           // so the else block is executed
          temp = ptr;  // you prepare to do something with temp
          return;      // WHY ??  You end the function an return without having done anything 
  ...  

问题 3:

假设您删除了 return 语句，那么请记住您只是覆盖了 temp。代码将继续如下:

 if(key<temp->key)     // this is false, because temp points to the new node, which has the seme key (temp->key==key) !
 if(key>temp->key)     // this is false, for the same reason 

所以递归插入都没有完成!

解决方案:

我建议你这样:

void bst::insert(int key,node* temp)
{
    if(temp==NULL) {
       if(root==NULL) {
           root=getnewnode(key);
           return; 
       }
       else 
           temp=root;  // we now start browsing the tree with root 
    }
    if(key<temp->key) {
        if (temp->left==NULL) 
           temp->left = getnewnode(key);  
       else insert(key,temp->left);
    }
    else if(key>temp->key) {
        if (temp->right==NULL) 
           temp->right = getnewnode(key);
       else insert(key,temp->right);
    }
    else if (key==temp->key) { 
        // to do:  what happens if key==temp->key 
    }
}

不清楚再次插入现有 key 时的预期结果。由您根据您的期望进行调整。

编辑:带有包装器的解决方案:

根据您对使用包装器的编辑，我建议您使用以下变体:

void bst::insert(int key,node*& temp)  // attention:  change of signature !!!
{
    if(temp==NULL) {  // either root is null or we have reached a null leave
       temp = getnewnode(key);    // temp is a reference to original root or node pointer.  It can be changed directly with this statement 
       }
    else if(key<temp->key) 
       insert(key,temp->left);
    else if(key>temp->key) 
       insert(key,temp->right);
    else if (key==temp->key) { 
        // to do:  what happens if key==temp->key 
    }
}