Обход двоичного дерева поиска

Question

Я включил базовое двоичное дерево поиска. Вот мой узел

#ifndef NODE_H 
    #define NODE_H 

    template<typename T> class node{ 

     template<typename E> friend class bst; 

     public: 
      node():data(0), left(NULL), right(NULL){} 
      node(T data):data(data),left(NULL), right(NULL){} 

     private: 
      T data; 
      node<T>* left; 
      node<T>* right; 
    }; 

#endif 

И вот мой bst.

#ifndef BST_H 
#define BST_H 

template<typename T> class bst{ 
    public: 
     bst():root(NULL), nodes(0){} 
     bst(node<T>* root):root(root), nodes(0){} 

     void insert(node<T>* root, const T& data){ 

      if(root == NULL){ 
       node<T>* root = new node<T>(); 
       root->data = data; 
       nodes++; 
       return; 
      }else if(data <= root->data) { 
       insert(root->left, data); 

      }else if(data >= root->data){ 
       insert(root->right, data); 

      } 
     } 

     void preorder(node<T>* root){ 
      if(root == NULL) return; 
      std::cout<< root->data<<'\n'; 

      preorder(root->left); 
      preorder(root->right); 
     } 
    private: 
     node<T>* root; 
     int nodes; 
}; 
#endif 

Вот функция вызова

int main(){ 

    node<int>* root = new node<int>(17); 
    bst<int>* t = new bst<int>(root); 


    t->insert(root,21); 
    t->insert(root,12); 
    t->insert(root, 9); 

    t->preorder(root); 

    delete t; 
} 

Выход просто 17, который является корнем. Я чувствую, как-то мой метод вставки не работает правильно, так как предварительный заказ является довольно стандартной реализацией. Может ли кто-нибудь помочь мне в том, что здесь происходит не так.

Answer 1

Я вижу две проблемы.

Во-первых, вы объявляете root в качестве локальной переменной внутри метода insert(). Это имя перекрывается с корнем данных.

Во-вторых, поскольку вы его разработали, корень не обновляется.

Этот код должен работать:

void insert(node<T>*& root, // <-- root as reference for updating 
      const T& data){ 

     if(root == NULL){ 
      root = new node<T>(); // <-- here you update root 
      root->data = data; 
      nodes++; 
      return; 
     }else if(data <= root->data) { 
      insert(root->left, data); 

     }else if(data >= root->data){ 
      insert(root->right, data); 

     } 
    } 

Конечно, можно реорганизовать и, таким образом, чтобы получить более краткую и элегантную реализацию. Но это должно привести к тому, что вы ожидаете

Answer 2

Внутренняя вставка не создает локальную переменную, просто используйте один столбец. Таким образом, вместо

node<T>* root = new node<T>(); 

сделать только

root = new node<T>(); 

И передать корень по ссылке. Я хотел бы сделать это с ЬурейиМ

typedef node<T>* nodePtr; 
void insert(nodePtr &root, const T& data){ 

, но вы можете сделать это и без

Answer 3

Вы должны пройти корень путем refrence, и не создаю локальную переменное затенения его:

// ... 
void insert(node<T>*& root, const T& data){ // passed by reference 

      if(root == NULL){ 
       root = new node<T>();  // reference overwritten 
//... 

Это дает мне

17 
12 
9 
21 

как выход, как и следовало ожидать от предзаказа, я думаю.