二進制搜索樹實現

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，如果你願意的話，你可以留下代碼。如果你向他們展示你有編寫單元測試代碼的聰明才智，那麼你的教育者可能會獲得更多的評價。