二进制搜索树节点插入

Question

想要将元素插入二进制树中。此代码中有什么问题。我有一个带有数据的结构，左右作为自我引用结构和根作为初始化为null的类型结构的全局变量。

void insert(struct tree_node *root,int data)
{
    if(root == NULL)
    {
        tree_node *new_node = new tree_node();
        new_node->left = NULL;
        new_node->right = NULL;
    }
    else if(root->data > data)
    {
        insert(root->left,data);
    }
    else
    {
    insert(root->right,data);
    }
}

Answer 1

您在此处提出的代码有几个问题：

• 您永远不会设置全局变量" root"。另外，全局变量始终是一件坏事（尤其是如果您打算使用线程）。
• 您永远不会将新条目链接到现有结构。
• 您永远不会设置新的条目数据

您可能应该尝试一下：

struct tree_node *insert(struct tree_node *root, int data) 
{
  if(root == NULL) {
    struct tree_node *new_node = new tree_node();
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
  } else if(root->data > data) {
    root->left = insert(root->left, data);
  } else {
    root->right = insert(root->right, data);
  }
  return root;
}

您可以使用

调用

root = insert(root, data);

如此codepad上所示

Answer 2

**您已经创建了new_node，但没有分配值。因此，您无法将值插入。

您也可以使用非递归功能插入

void insert_nrec(int m)  //for insert in binary tree
{
node *tmp,*par,*ptr;
ptr=root;
par=NULL;
tmp=NULL;
    while(ptr!=NULL)
    {
        par=ptr;
        if(m<ptr->data)
        {   ptr=ptr->lchild;    }
        else if(m>ptr->data)
        {   ptr=ptr->rchild;    }
        else
            {   
                cout<<"duplicate key found::";
                return;             
            }       
    }
tmp=new node;
tmp->data=m;
tmp->lchild=NULL;
tmp->rchild=NULL;
if(par==NULL)
    {
        root=tmp;
    }   
else if(m<par->data)
    {
        par->lchild=tmp;    
    }
else
    {
        par->rchild=tmp;
    }
}

Answer 3

何时将root设置为NULL以外的任何东西？

完成后，您如何实际更改root->left或right？

Answer 4

我只是要重写 @therealneo的nifty'functional'答案，以便将其传递给根指针：

void insert(struct tree_node * &root, int data) 
{
  if(root == NULL) {
    struct tree_node *new_node = new tree_node();
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    root = new_node;
  } else if(root->data > data) {
    insert( root->left, data);
  } else {
    insert( root->right, data);
  }
}

您使用

调用的

insert(root, data);

比功能上的优点是，编译器很有可能会实际上将递归调用作为"尾部递归"，即，当左插入左插入时，而不是进行递归呼叫，代码将简单地更改'''root'引用"引用" root->左"，然后跳回函数的开始。

明确的非恢复形式并不清楚，因为它涉及一些指针到指针的东西，但实际上还不错：

void insert(struct tree_node * &root, int data) 
{
  struct tree_node **ptrp = &root;
  while(*ptrp != NULL ){
     struct tree_node *np = *ptrp;
     if( np->data > data ){
          ptrp = &np->left;
     }else{
          ptrp = &np->right;
     }
  }
   // new node will be placed at *ptrp, a location
   // currently containing NULL.
  struct tree_node *new_node = new tree_node();
  new_node->data = data;
  new_node->left = NULL;
  new_node->right = NULL;
  *ptrp = new_node;
}