首页 文章

二进制搜索树中插入的递归函数（C）

提问于
浏览 次
-2

我试图使用递归将新节点插入BST .
但插入后我丢失了链接 .
按顺序遍历显示程序只能访问根节点 .
这是我的计划

class for BST

class bst
     {
       struct node
        {
          struct node *lchild;
          int info;
          struct node *rchild;  
        }*start;
   public:
    bst();
    void insert(int num,struct node *start);
    void search(int num,struct node *start);
    void display();
    void inorder(node *start);
    struct node *getRoot(){
    return start;
   }
};

Insertion Function

void bst :: insert(int num,struct node *ptr)
    {
    if(ptr == NULL)
    {
        ptr = new node;
        ptr->info = num;
        ptr->lchild = NULL;
        ptr->rchild = NULL;     
       if(start == NULL)
         start = ptr;
       return;
    }
    else if(num < ptr->info)
     {
        insert(num,ptr->lchild);
     }
     else if(num > ptr->info)
     {
        insert(num,ptr->rchild);
     }
    else
    {
       cout << "Duplicate element \n";
       return;
    }
   }

main function

int main()
{
    bst S;
    int option,key;
    cout << "Enter an element\n";
    cin >> key;
    S.insert(key,S.getRoot());
}

如何在不更改插入函数的返回类型的情况下维护正确的链接？

c++ recursion data-structures binary-tree binary-search-tree

3 回答

  • 0

    start 在某处初始化为 NULL ？

    此外，当 start 不是 NULL 时，您永远不会将新创建的节点链接到树中：

    if(ptr == NULL)
{
    ptr = new node;
    ptr->info = num;
    ptr->lchild = NULL;
    ptr->rchild = NULL;     
   if(start == NULL)
     start = ptr;
   return;
}

    您应检查节点的子节点是否为 NULL ，然后在其中链接新节点 . 我认为你的递归太过分了 .

    回复于
  • 0

    在此处将您的 start 初始化为 NULL

    bst()
    {
        start=NULL;
    }
    回复于
  • 1

    您需要通过引用传递root .

    Main Function

    S.insert(key,&S.getRoot());

    Insertion Function

    void bst :: insert(int num,struct node **ptr)
{
    if(*ptr == NULL)
    {
        *ptr = new node;
        (*ptr)->info = num;
        (*ptr)->lchild = NULL;
        (*ptr)->rchild = NULL;     
       //if(start == NULL)      //No need for this statement
       //  start = *ptr;        //No need for this statement
       return;
    }
    else if(num < *ptr->info)
     {
        insert(num,&((*ptr)->lchild));
     }
     else if(num > *ptr->info)
     {
        insert(num,&((*ptr)->rchild));
     }
    else
    {
       cout << "Duplicate element \n";
       return;
    }
}
    回复于

相关问题