узлы добавляются в некоторые неизвестные места в моем двоичном дереве поиска - PullRequest
Новая
       13

узлы добавляются в некоторые неизвестные места в моем двоичном дереве поиска

0 голосов
/ 05 мая 2020

Чтобы изучить реализацию двоичного дерева поиска,
я создал класс 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 right 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, и я не знаю, куда тогда добавлялись узлы?

Ответы [ 2 ]

2 голосов
/ 05 мая 2020

вы никогда не обновляете 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;
  }
0 голосов
/ 05 мая 2020

Я сделал глупую ошибку, использовав ptr в функции add_leaf_private по значению. Я должен был передать его по ссылке, так как намереваюсь изменить его в функции. Замена ptr на &ptr решила проблему.

...