在二进制搜索树中某些未知位置添加了节点

Question

要学习二进制搜索树的实现，我创建了一个类bst，并且在其add_node_private函数中遇到了问题。

bst.cpp-

#include <iostream>
#include <cstdlib>
using namespace std;
#include "bst.h"
// bst constructor
bst::bst() {
  root = nullptr;
}
// methods of binary search tree
bst::node* bst::create_leaf(int a) {  // creating a leaf with key
  node* leaf = new node;
  leaf->key = a;
  leaf->left = nullptr;
  leaf->right = nullptr;
  return leaf;
}
// adding a leaf to the tree
void bst::add_leaf(int k) {
  bst::add_leaf_private(k, root);  // just calls the private function 
                                   // providing it with root
}
void bst::add_leaf_private(int k, node* ptr) {
  if (ptr == nullptr) {
    ptr = create_leaf(k);
    cout << k << " added\n";
    return;
  }
  if (k > ptr->key) {
    cout << "went left of " << ptr->key << endl;
    add_leaf_private(k, ptr->right);
  }
  if (k < ptr->key) {
    cout << "went left of " << ptr->key << endl;
    add_leaf_private(k, ptr->left);
  }
  if (k == ptr->key) {
    cout << "key " << k << " already exists\n";
  }
}

bst.h

#ifndef _BST_H
#define _BST_H

class bst
{
    private:
    struct node{
        int key;
        node* left;
        node* right;
    };
//private methods
void add_leaf_private(int k,node* ptr);
//void print_private(node* ptr);

public:
node* root=nullptr;
//bst constructor
bst();
//public methods

node* create_leaf(int k);
void add_leaf(int k);
//void print();
};


#endif // _BST_H

[当我添加叶子时，我的输出显示它们已添加（例如-5 added）

main.cpp

#include <iostream>
#include <cstdlib>
#include "bst.h"
using namespace std;
int main(){
    bst b1;     
    int tree_keys[]{50,70,21,4,32,64,15,51,14,100,83,2,3,70,87,90};
    for(int x: tree_keys){
        b1.add_leaf(x);
    }
    cout<<"root"<<b1.root<<endl;
    return 0;
}

但是我没有看到我期望的任何语句went left of ...或went right of ...。之后，我检查并发现即使添加了一堆节点，我也有root==nullptr，不知道在哪里添加节点？

Answer 1

您永远不会更新root。它总是nullptr

您需要

void bst::add_leaf_private(int k, node* ptr) {
  if (ptr == nullptr) {
    ptr = create_leaf(k);
    root = ptr;
    cout << k << " added\n";
    return;
  }