二进制搜索树实现

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;

整个功能有一些扭曲的逻辑,可以通过仔细思考并压缩它们,将其压缩到当前大小的1/4左右.

此外,这里还有一个提示,说明为什么要删除段错误.这很明显,并不是因为代码的任何其他部分都被破坏了.调试器是你的朋友.

提示是,这段代码做了remove什么？仔细想想:

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