Реализация двоичного дерева поиска

Question

Я искал форум и попытался реализовать код в найденных вами потоках. Но я работаю над этой простой простой программой примерно с 10 утра и не могу решить сег. ошибки для жизни меня.

Любые идеи о том, что я делаю неправильно, будут очень признательны.

BST.h (Все проблемы реализации должны быть здесь, и это было обновлено некоторые с учетом дальнейшей работы по развитию, взглянуть на историю, чтобы увидеть старые версии.)

#ifndef BST_H_ 
#define BST_H_ 

#include <stdexcept> 
#include <iostream> 
#include "btnode.h" 

using namespace std; 

/* 
    A class to represent a templated binary search tree. 
*/ 
template <typename T> 
class BST 
{ 
    private: 

     //pointer to the root node in the tree 
     BTNode<T>* root; 

    public: 

     //default constructor to make an empty tree 
     BST(); 

     /* 
      You have to document these 4 functions 
     */ 
     void insert(T value); 
     bool search(const T& value) const; 
     bool search(BTNode<T>* node, const T& value) const; 
     void printInOrder() const; 
     void remove(const T& value); 

     //function to print out a visual representation 
     //of the tree (not just print the tree's values 
     //on a single line) 
     void print() const; 

    private: 

     //recursive helper function for "print()" 
     void print(BTNode<T>* node,int depth) const; 
}; 

/* 
    Default constructor to make an empty tree 
*/ 
template <typename T> 
BST<T>::BST() 
{ 
    root = NULL; 
} 

template <typename T> 
void BST<T>::insert(T value) 
{ 
    BTNode<T>* newNode = new BTNode<T>(value); 
    cout << newNode->data; 
    if(root == NULL) 
    { 
     root = newNode; 
     return; 
    } 
    BTNode<T>* current = root; 
    while(true) 
    { 
     if(current->left == NULL && current->right == NULL) 
      break; 
     if(current->right != NULL && current->left != NULL) 
     { 
      if(newNode->data > current->data) 
       current = current->right; 
      else if(newNode->data < current->data) 
       current = current->left; 
     } 
     else if(current->right != NULL && current->left == NULL) 
     { 
      if(newNode->data < current->data) 
       break; 
      else if(newNode->data > current->data) 
       current = current->right; 
     } 
     else if(current->right == NULL && current->left != NULL) 
     { 
      if(newNode->data > current->data) 
       break; 
      else if(newNode->data < current->data) 
       current = current->left; 
     } 
    } 

    if(current->data > newNode->data) 
    { 
     current->left = newNode; 
    /* cout << current->data << "DATA" << endl; 
     cout << &current << "ADDY" << endl; 
     cout << &current->left << "L ADDY" << endl; 
     cout << &current->right << "R ADDY" << endl;*/ 
    } 
    else 
    { 
     current->right = newNode; 
     /*cout << current->data << "DATA" << endl; 
     cout << &current << "ADDY" << endl; 
     cout << &current->left << "L ADDY" << endl; 
     cout << &current->right << "R ADDY" << endl;*/ 
    } 
    return; 
} 

//public helper function 
template <typename T> 
bool BST<T>::search(const T& value) const 
{ 
    return(search(root,value)); //start at the root 
} 

//recursive function 
template <typename T> 
bool BST<T>::search(BTNode<T>* node, const T& value) const 
{ 
    if(node == NULL || node->data == value) 
     return(node != NULL); //found or couldn't find value 
    else if(value < node->data) 
     return search(node->left,value); //search left subtree 
    else 
     return search(node->right,value); //search right subtree 
} 

template <typename T> 
void BST<T>::printInOrder() const 
{ 
    //print out the value's in the tree in order 
    // 
    //You may need to use this function as a helper 
    //and create a second recursive function 
    //(see "print()" for an example) 
} 

template <typename T> 
void BST<T>::remove(const T& value) 
{ 
    if(root == NULL) 
    { 
     cout << "Tree is empty. No removal. "<<endl; 
     return; 
    } 
    if(!search(value)) 
    { 
     cout << "Value is not in the tree. No removal." << endl; 
     return; 
    } 
    BTNode<T>* current = root; 
    BTNode<T>* parent; 

    cout << root->data << " ROOT" << endl; 
    cout << current->data << "CURRENT BEFORE" << endl; 

    while(current != NULL) 
    { 
     if(root->data == value) 
     { 
      delete current; 
      return; 
     } 
     else if(value > current->data) 
     { 
      parent = current; 
      current = current->right; 
     } 
     else 
     { 
      parent = current; 
      current = current->left;    
     } 
    } 
    cout << current->data << "CURRENT AFTER" << endl; 

    // 3 cases : 
    //We're looking at a leaf node 

    if(current->left == NULL && current->right == NULL)    // It's a leaf 
    { 
     if(parent == current) 
      delete parent; 
     else if(parent->left == current) 
     { 
      parent->left = NULL; 
      delete current; 
     } 
     else 
     { 
      parent->right = NULL; 
      delete current; 
     } 
     cout << "The value " << value << " was removed." << endl; 
     return; 
    } 

    // Node with single child 
    if((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL)) 
    { 
     if(current->left == NULL && current->right != NULL) 
     { 
      if(parent->left == current) 
      { 
       parent->left = current->right; 
       cout << "The value " << value << " was removed." << endl; 
       delete current; 
      } 
      else 
      { 
       parent->right = current->right; 
       cout << "The value " << value << " was removed." << endl; 
       delete current; 
      } 
     } 
     else // left child present, no right child 
     { 
      if(parent->left == current) 
      { 
       parent->left = current->left; 
       cout << "The value " << value << " was removed." << endl; 
       delete current; 
      } 
      else 
      { 
       parent->right = current->left; 
       cout << "The value " << value << " was removed." << endl; 
       delete current; 
      } 
     } 
     return; 
    } 

    //Node with 2 children - Replace node with smallest value in right subtree. 
    if (current->left != NULL && current->right != NULL) 
    { 
     BTNode<T>* check; 
     check = current->right; 
     if((check->left == NULL) && (check->right == NULL)) 
     { 
      current = check; 
      delete check; 
      current->right = NULL; 
      cout << "The value " << value << " was removed." << endl; 
     } 
     else // right child has children 
     { 
      //if the node's right child has a left child; Move all the way down left to locate smallest element 
      if((current->right)->left != NULL) 
      { 
       BTNode<T>* leftCurrent; 
       BTNode<T>* leftParent; 
       leftParent = current->right; 
       leftCurrent = (current->right)->left; 
       while(leftCurrent->left != NULL) 
       { 
        leftParent = leftCurrent; 
        leftCurrent = leftCurrent->left; 
       } 
       current->data = leftCurrent->data; 
       delete leftCurrent; 
       leftParent->left = NULL; 
       cout << "The value " << value << " was removed." << endl; 
      } 
      else 
      { 
       BTNode<T>* temp; 
       temp = current->right; 
       current->data = temp->data; 
       current->right = temp->right; 
       delete temp; 
       cout << "The value " << value << " was removed." << endl; 
      } 
     } 
     return; 
    } 
} 

/* 
    Print out the values in the tree and their 
    relationships visually. Sample output: 

         22 
       18 
     15 
10 
       9 
     5 
       3 
         1 
*/ 
template <typename T> 
void BST<T>::print() const 
{ 
    print(root,0); 
} 

template <typename T> 
void BST<T>::print(BTNode<T>* node,int depth) const 
{ 
    if(node == NULL) 
    { 
     std::cout << std::endl; 
     return; 
    } 

    print(node->right,depth+1); 
    for(int i=0; i < depth; i++) 
    { 
     std::cout << "\t"; 
    } 
    std::cout << node->data << std::endl; 
    print(node->left,depth+1); 
} 

#endif 

main.cpp

#include "bst.h"  
#include <iostream> 
using namespace std; 

int main() 
{ 
    BST<int> tree; 
    cout << endl << "LAB #13 - BINARY SEARCH TREE PROGRAM" << endl; 
    cout << "----------------------------------------------------------" << endl; 
    // Insert. 
    cout << endl << "INSERT TESTS" << endl;   // No duplicates allowed. 
    tree.insert(0); 
    tree.insert(5); 
    tree.insert(15); 
    tree.insert(25); 
    tree.insert(20); 

    // Search. 
    cout << endl << "SEARCH TESTS" << endl; 
    int x = 0; 
    int y = 1; 
    if(tree.search(x)) 
     cout << "The value " << x << " is on the tree." << endl; 
    else 
     cout << "The value " << x << " is NOT on the tree." << endl; 
    if(tree.search(y)) 
     cout << "The value " << y << " is on the tree." << endl; 
    else 
     cout << "The value " << y << " is NOT on the tree." << endl; 

    // Removal. 
    cout << endl << "REMOVAL TESTS" << endl; 
    tree.remove(0); 
    tree.remove(1); 
    tree.remove(20); 

    // Print. 
    cout << endl << "PRINTED DIAGRAM OF BINARY SEARCH TREE" << endl; 
    cout << "----------------------------------------------------------" << endl; 
    tree.print(); 
    cout << endl << "Program terminated. Goodbye." << endl << endl; 
} 

BTNode.h

#ifndef BTNODE_H_ 
#define BTNODE_H_ 

#include <iostream> 

/* 
    A class to represent a node in a 
    binary search tree. 
*/ 
template <typename T> 

    class BTNode 
    { 
     public: 

      //constructor 
      BTNode(T d); 

      //the node's data value 
      T data; 

      //pointer to the node's left child 
      BTNode<T>* left; 

      //pointer to the node's right child 
      BTNode<T>* right; 
    }; 

    /* 
     Simple constructor. Sets the data 
     value of the BTNode to "d" and defaults its 
     left and right child pointers to NULL. 
    */ 
    template <typename T> 
    BTNode<T>::BTNode(T d) 
    : left(NULL), right(NULL) 
    { 
     data = d; 
    } 

    #endif 

Спасибо.

Answer 1

insert имеет утечку памяти. Эти три линий:

BTNode<T>* current = new BTNode<T>(NULL); 
current = root; 
current->data = root->data; 

следует читать:

BTNode<T>* current = root; 

Вся функция имеет несколько искаженной логику и может быть smooshed примерно до 1/4 его текущего размера, продумывая случаи тщательно и сжимая их ,

Кроме того, здесь есть подсказка, почему вы получаете ошибку сегмента при удалении. Это довольно очевидно, и не потому, что какая-либо другая часть вашего кода нарушена. Отладчики - ваш друг.

Подсказка: что делает этот блок кода в remove? Подумайте внимательно:

BTNode<T>* current; 
BTNode<T>* parent; 
current = root; 
parent->left = NULL; 
parent->right = NULL; 

Answer 2

Поскольку это домашнее задание, я помогу вам помочь себе. первой вещь, которую вы должны сделать, это написать код на dump функции, которая выплевывает дерево в читаемом виде, показывая, для каждого узла:

• адреса текущего узла.
• Значение текущего узла.
• адрес указателя левого узла.
• адрес указателя правильного узла.

Затем вызовите эту функцию dump после каждый вставки и удаления. Это стандартная отладка 101, и вы можете, если хотите, оставить этот код. Возможно, вы получите больше баллов от своего преподавателя, если вы покажете им, что у вас есть умения написать код модульного тестирования.