二叉搜索树实现 [英] Binary Search Tree Implementation

问题描述

我搜索了论坛，并尝试在我发现的线程中实现代码。但我一直在这个真正的简单程序工作，从上午10点左右，不能解决seg。对我生命的错误。

I've searched the forum, and tried to implement the code in the threads I found. But I've been working on this real simple program since about 10am, and can't solve the seg. faults for the life of me.

对我做错了的任何想法将非常感谢。

Any ideas on what I'm doing wrong would be greatly appreciated.

BST.h（所有的实现问题应该在这里，这已经更新了一些，以反映进一步的开发工作，看历史看老版本。）

BST.h (All the implementation problems should be in here, and this has been updated some to reflect further development work, look at the history to see old versions.)

#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

推荐答案

insert 有内存泄漏。这三行：

insert has a memory leak. These three lines:

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

应为：

BTNode<T>* current = root;

整个函数有些扭曲的逻辑，并且可以被减少到当前大小的1/4仔细考虑这些情况并压缩它们。

The whole function has somewhat contorted logic and could be smooshed down to about 1/4th its current size by thinking through the cases carefully and compressing them.

此外，这里有一个提示，为什么你得到一个段错误删除。这是相当明显的，而不是因为你的代码的任何其他部分被打破。调试器是你的朋友。

Also, here's a hint as to why you're getting a segment fault in remove. It's fairly obvious, and not because any other part of your code is broken. Debuggers are your friend.

提示是，这个代码块在 remove 仔细思考：

The hint is, what does this block of code do in remove? Think carefully:

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

这篇关于二叉搜索树实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！