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

Спасибо.

Omnifarious · Answer 1 · 12 апреля 2010

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;

paxdiablo · Answer 2 · 12 апреля 2010

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

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

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

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

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

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

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы