在二叉搜索樹（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++）中插入的遞歸函數

回答

相關問題