VPF::Бинарное дерево - Форум программистов

Поцык

Дата 19.5.2011, 13:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 13.5.2011

Репутация: нет
Всего: нет

дело вот в чем:
при удалении элемента вылетает ошибка,в чем суть не пойму.

Код


#include <iostream>
#include <cstdlib>
using namespace std;
template<class T> 
class BinarySearchTree
{
private:
    struct tree_node
    {
        tree_node* left;
        tree_node* right;
        T data;
    };
    tree_node* root;
public:
    BinarySearchTree()
    {
        root = NULL;
    }
    bool isEmpty() const { return root==NULL; }
    void print_inorder();
    void inorder(tree_node*);
    void print_preorder();
    void preorder(tree_node*);
    void print_postorder();
    void postorder(tree_node*);
    void insert(T);
    void remove(T);
    bool search(T);
};


template <class T>
void BinarySearchTree<T>::insert(T d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;
    // Новое дерево
    if(isEmpty()) root = t;
    else
    {
        //Все вставки являются конечными узлами
        tree_node* curr;
        curr = root;
        // Поиск родителя узла
        while(curr)
        {
            parent = curr;
            if(t->data > curr->data) curr = curr->right;
            else curr = curr->left;
        }

        if(t->data < parent->data)
            parent->left = t;
        else
            parent->right = t;
    }
}
template <class T>
bool BinarySearchTree<T>::search(T d)
{
    //Найти элемент
    bool found = false;
    if(isEmpty())
    {
        cout<<" Это дерево пустое! "<<endl;
        return false;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    parent = (tree_node*)NULL;
    while(curr != NULL)
    {
        if(curr->data == d)
        {
            found = true;
            break;
        }
        else
        {
            parent = curr;
            if(d>curr->data) curr = curr->right;
            else curr = curr->left;
        }
    }
    if(!found)
    {
        cout<<" Данные не найдены! "<<endl;
    }
    else
    {
        cout<<" Данные найдены! "<<endl;
    }

    return found;
}

template <class T>
void BinarySearchTree<T>::remove(T d)
{
    bool found = false;
    if(isEmpty())
    {
        cout<<" Это дерево пустое! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    parent = (tree_node*)NULL;
    while(curr != NULL)
    {
        if(curr->data == d)
        {
            found = true;
            break;
        }
        else
        {
            parent = curr;
            if(d>curr->data) curr = curr->right;
            else curr = curr->left;
        }
    }
    if(!found)
    {
        cout<<" Данные не найдены! "<<endl;
        return;
    }

    // Узел с одним ребенком
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
        && curr->right == NULL))
    {
        if(curr->left == NULL && curr->right != NULL)
        {            
            if(parent->left == curr)
            {
                parent->left = curr->right;
                delete curr;
            }
            else
            {
                parent->right = curr->right;
                delete curr;
            }
        }
        else // Слева есть ребенок, справа его нет
        {
            if(parent->left == curr)
            {
                parent->left = curr->left;
                delete curr;
            }
            else
            {
                parent->right = curr->left;
                delete curr;
            }
        }
        return;
    }

    //Просмотр конечного узла
    if( curr->left == NULL && curr->right == NULL)
    {
        if (parent == NULL)
        {
            delete curr;

        } else
            if(parent->left == curr) parent->left = NULL;
            else parent->right = NULL;
            delete curr;
            return;
    }


    //Узел с двумя детьми
    // Заменяем узел с наименьшим значением в правое поддерево
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // У правого ребенка есть дети
        {
            //Если правый ребенок узла имеет левого ребенка
            //Перемещение снизу налево, чтобы найти меньший элемент

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                    lcurrp = lcurr;
                    lcurr = lcurr->left;
                }
                curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
            }
            else
            {
                tree_node* tmp;
                tmp = curr->right;
                curr->data = tmp->data;
                curr->right = tmp->right;
                delete tmp;
            }

        }
        return;
    }

}
template<class T>
void BinarySearchTree<T>::print_inorder()
{
    inorder(root);
}
template<class T>
void BinarySearchTree<T>::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}
template<class T>
void BinarySearchTree<T>::print_preorder()
{
    preorder(root);
}
template<class T>
void BinarySearchTree<T>::preorder(tree_node* p)
{
    if(p != NULL)
    {
        cout<<" "<<p->data<<" ";
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else return;
}
template<class T>
void BinarySearchTree<T>::print_postorder()
{
    postorder(root);
}

template<class T>
void BinarySearchTree<T>::postorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) postorder(p->left);
        if(p->right) postorder(p->right);
        cout<<" "<<p->data<<" ";
    }
    else return;
}

int main()
{
    BinarySearchTree<int> b;
    int ch;
    int tmp,tmp1;
    while(1)
    {
        cout<<endl<<endl;
        cout<<" Операции с бинарным деревом поиска "<<endl;
        cout<<" ----------------------------- "<<endl;
        cout<<" 1.Добавить/создать "<<endl;
        cout<<" 2. In-Order Traversal "<<endl;
        cout<<" 3. Pre-Order Traversal "<<endl;
        cout<<" 4. Post-Order Traversal "<<endl;
        cout<<" 5. Удаление "<<endl;
        cout<<" 6. Поиск "<<endl;
        cout<<" 7. Выход "<<endl;
        cout<<" Введите свой выбор : ";
        cin>>ch;
        switch(ch)
        {
        case 1 : cout<<" Введенные данные добавлены : ";
            cin.ignore(1);
            cin>>tmp;
            b.insert(tmp);
            break;
        case 2 : cout<<endl;
            cout<<" In-Order Traversal "<<endl;
            cout<<" -------------------"<<endl;
            b.print_inorder();
            break;
        case 3 : cout<<endl;
            cout<<" Pre-Order Traversal "<<endl;
            cout<<" -------------------"<<endl;
            b.print_preorder();
            break;
        case 4 : cout<<endl;
            cout<<" Post-Order Traversal "<<endl;
            cout<<" --------------------"<<endl;
            b.print_postorder();
            break;
        case 5 : cout<<" Введенные данные удалены : ";
            cin.clear();
            cin.ignore(1);
            cin>>tmp1;
            b.remove(tmp1);
            break;
        case 6 : cout<<" Введенные данные найдены : ";
            cin.ignore(1);
            cin>>tmp;
            b.search(tmp);
            break;
        case 7 : system("Пауза");                                                      
            return 0;
            break;
        }
    }
}

в программировании новичек.
и что это за функции in-,pre-,post-order traverse?

borisbn

Дата 19.5.2011, 13:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

Цитата(Поцык @ 19.5.2011, 13:01

)

при удалении элемента вылетает ошибка

Найди участок кода в ф-ции remove с комментарием // Узел с одним ребенком
и подправь так

Код


    // Узел с одним ребенком
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
        && curr->right == NULL))
    {
        if(curr->left == NULL && curr->right != NULL)
        {            
            if ( parent == NULL ) // <------
            {
                root = curr;
                delete curr;
            }
            else // <------
            {
                if(parent->left == curr)
                {
                    parent->left = curr->right;
                    delete curr;
                }
                else
                {
                    parent->right = curr->right;
                    delete curr;
                }
            }
        }
        else // Слева есть ребенок, справа его нет
        {
            if(parent->left == curr)
            {
                parent->left = curr->left;
                delete curr;
            }
            else
            {
                parent->right = curr->left;
                delete curr;
            }
        }
        return;
    }

Цитата(Поцык @ 19.5.2011, 13:01

)

и что это за функции in-,pre-,post-order traverse?

preorder печатает дерево от root до последнего листа, а inorder наобораот - от последнего листа до root

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

Поцык

Дата 19.5.2011, 16:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 13.5.2011

Репутация: нет
Всего: нет

странно, у меня in-order и pre-order совпадают.
post-order же печатает наоборот smile

borisbn

Дата 19.5.2011, 16:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

особо не вчитывался. м.б. это от данных зависит ?попробуй разные варианты данных повводить:
1 2 3 4 5
5 4 3 2 1
2 5 3 1 4
и т.п.

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

Поцык

Дата 20.5.2011, 08:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 13.5.2011

Репутация: нет
Всего: нет

а как лучше вывести дерево в консоль?

Это сообщение отредактировал(а) Поцык - 20.5.2011, 08:52

borisbn

Дата 20.5.2011, 08:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

дык оно уже выводится - ф-ции print_inorder(), print_preorder()
или у тебя вопрос как лучше: от корня к листам или наоборот ?
IMHO - дело вкуса, но логичнее, всё-таки, от корня к листам

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

Поцык

Дата 20.5.2011, 11:27 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 13.5.2011

Репутация: нет
Всего: нет

нет, я хотел типа этого:

a1(root)->  b2(R child a1)->        d2(R child b2)
             |                           |
             |                           |
             |                           |->      d1(L child b2)
             |
             |
             |
             |
             |
             |->  b1(L child a1)->    c2(R child b1)
                                        |
                                        |
                                        |->    c1(L child b1)

повернутое на 90 градусов против часовой стрелки дерево smile

Это сообщение отредактировал(а) Поцык - 20.5.2011, 11:28

borisbn

Дата 20.5.2011, 12:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

Цитата(Поцык @ 20.5.2011, 11:27

)

нет, я хотел типа этого:

я даю тебе не готовое решение, а идею. Поэкспериментируй - должно получиться то, что ты хочешь. Я в тебя верю smile

Код


template<class T>
void BinarySearchTree<T>::nice_print()
{
    nice_print( root, 0 );
}
template<class T>
void BinarySearchTree<T>::nice_print(tree_node* p, int indent)
{
    if(p != NULL)
    {
        cout << std::string( indent, ' ' ).c_str() << p->data << " ";
        if(p->left) nice_print( p->left, indent + 4 );
        cout << endl;
        if(p->right) nice_print( p->right, indent + 4 );
        cout << endl;
    }
}

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

Поцык

Дата 24.5.2011, 12:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 13.5.2011

Репутация: нет
Всего: нет

вот замудрил нечто:
не компилируется,в чем соль не пойму,пишет что-то про прототипы

код кусочка

Код


template<class T>
void BinarySearchTree<T>::nice_print()
{
    nice_print( root, 0 );
}
template<class T>
void BinarySearchTree<T>::nice_print(tree_node *p,int level)
{
    if(p)
    {
        nice_print(p->left,level+1);//Печать левого поддерева
        for(int i=0;i<level;i++)cout << " " << endl;
        cout << p->data << endl;//Печать корня
        nice_print(p->right,level+1);//Печать правого поддерева
    }
}

вот ошибки отсуда:
1)233 prototype for `void BinarySearchTree<T>::nice_print(BinarySearchTree<T>::tree_node*, int)' does not match any in class `BinarySearchTree<T>'
2) error 22 candidates are: void BinarySearchTree<T>::nice_print(BinarySearchTree<T>::tree_node*)
3)228 void BinarySearchTree<T>::nice_print()
4)233 template definition of non-template `void BinarySearchTree<T>::nice_print(BinarySearchTree<T>::tree_node*, int)'

майн

Код


case 2 : cout<<endl;
            cout<<" Дерево распечатано "<<endl;
            cout<<" -------------------"<<endl;
            b.nice_print(0);//!!!!!!!-----------------------------------------Здесь ноль вбил ошибка пропала
            break;

а было
1)271 instantiated from here
и куча наподобе: note void BinarySearchTree<T>::nice_print(BinarySearchTree<T>::tree_node*) [with T = int]

borisbn

Дата 24.5.2011, 12:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

в описании класса (там где такие строки)

Код


void print_inorder();
void inorder(tree_node*);

добавь

Код


void nice_print();
void nice_print(tree_node *p,int level);

Цитата(Поцык @ 24.5.2011, 12:41

)

b.nice_print(0);

0 не нужен

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

Поцык

Дата 26.5.2011, 08:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 13.5.2011

Репутация: нет
Всего: нет

спасибо,разобрался
думал все уже так Remove закосячил
то правильно работает,то ошибка сегментирования,то узлы теряются
грешу на алгоритм перестроения,наверно при удалении Parent указатели на Child пропадают

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »