二进制搜索树实现

Question

我搜索了论坛，并试图在我发现的线程中实现代码。但从上午10点开始，我一直在研究这个真正简单的程序，并且无法解决seg问题。为我的生活带来的错误。

任何想法，我做错了将不胜感激。

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，如果你愿意的话，你可以留下代码。如果你向他们展示你有编写单元测试代码的聪明才智，那么你的教育者可能会获得更多的评价。