在二叉搜索树（C++）中插入的递归函数

-2

我试图用递归插入一个新的节点到BST中。
但插入后我失去了链接。
有序遍历表明程序只能访问根节点。
这是我的计划在二叉搜索树（C++）中插入的递归函数

类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; 
    } 
};

插入功能

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; 
    } 
    }

主要功能

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

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

来源

2014-10-06 Pradeep

您的节点结构真的可以使用一个构造函数。 – Borgleader 2014-10-06 15:17:30

@Borgleader对不起，我不明白。 – Pradeep 2014-10-06 15:18:27

@Rustam'getRoot（）'函数在类中定义。 – Pradeep 2014-10-06 15:34:01

是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，然后在那里链接新的节点。我认为你正在把你的递归放到一个太远的地步。

来源

2014-10-06 15:34:32 dohashi

是'start'使用构造函数 'bst（）'初始化为'NULL'。你说的是对的，我没有链接新创建的节点。我想知道如何做到这一点。 – Pradeep 2014-10-06 15:36:19

你能告诉我正确的代码来维护链接 – Pradeep 2014-10-06 15:38:51

初始化start到NULL这里

bst() 
    { 
     start=NULL; 
    }

来源

2014-10-06 15:49:11 Rustam

我在构造函数中做到了这一点。我只是没有把这个问题放在上面的问题。 – Pradeep 2014-10-06 15:49:52

你需要按引用传递根。

主要功能

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

插入功能

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; 
    } 
}

来源

2017-09-14 09:23:12

在二叉搜索树（C++）中插入的递归函数

回答

相关问题