Delete nie działa w implementacji drzewa binarnego

Odpowiedz Nowy wątek
2014-05-14 19:57
0

Witam wszystkich. Stworzyłem klasę reprezentującą drzewo binarne i posiadającą podstawowe operacje na nim, problem w tym, że wszystko działa do momentu kiedy spróbuję usunąć jakiś element. Wtedy wszystko się sypie i zwyczajnie nie działa (chociaż kompiluje się i odpala). Cztery razy przepisywałem od nowa funkcję Delete i cały czas to samo. Poniżej zamieszczam kod:

Node.h

#ifndef NODE_H_
#define NODE_H_

#include <stdlib.h>

template <class T>
class Node
{
public:
    Node(T key2) {
        this->key = key2;
        this->left = NULL;
        this->right = NULL;
        this->parent = NULL;
    };
    Node<T> *right;
    Node<T> *left;
    Node<T> *parent;
    T key;
};

#endif

Tree.h

#ifndef TREE_H_
#define TREE_H_

#include <stdlib.h>
#include "Node.h"
#include <iostream>

template <class T>
class Tree
{
public:
    Node<T> *root;
    Tree() {
        this->root = NULL;
    };
    //-----------------------------------------------------INSERT--------------------------------------------------------
    bool Insert(T keyToInsert) {
            if(this->root == NULL) {
                this->root = new Node<T>(keyToInsert);
                return true;
            }
            else {
                Node<T> *tmp = this->root;
                while(tmp != NULL) {
                    if(keyToInsert < tmp->key) {
                        if(tmp->left != NULL) {
                            tmp = tmp->left;
                        }
                        else  {
                            tmp->left = new Node<T>(keyToInsert);
                            return true;
                        }
                    }
                    else if(keyToInsert > tmp->key) {
                        if(tmp->right != NULL) {
                            tmp = tmp->right;
                        }
                        else {
                            tmp->right = new Node<T>(keyToInsert);
                            return true;
                        }
                    }
                    else return false;
                }
            }
            return true;
        };

    //-----------------------------------------------------SEARCH--------------------------------------------------------
    Node<T> *Search(T key, Node<T> *start) {
        if(start == NULL || key == start->key) return start;
        else if(key < start->key) return Search(key, start->left);
        else return Search(key, start->right);
    };

    //--------------------------------------------------------MIN--------------------------------------------------------
    Node<T> *Min(Node<T> *start) {
        while(start->left != NULL) {
            start = start->left;
        }
        return start;
    };

    //----------------------------------------------------NASTEPNIK-----------------------------------------------------
    Node<T> *Nastepnik(Node<T> *start) {
        if( start->right != NULL ) return Min( start->right );
        else
        {
        Node<T> *tmp = start->parent;

        while( tmp != NULL && start != tmp->right )
        {
        start = tmp;
        tmp = tmp->parent;
        }

        return tmp;
        }
    };

    //-----------------------------------------------------DELETE-------------------------------------------------------
    Node<T> *Delete(T key) {
        Node<T> *wezelek = Search(key, this->root);
        Node<T> *rodzicek = wezelek->parent;
        Node<T> *tmp;

        if(wezelek->left != NULL && wezelek->right != NULL) {
            tmp = Delete(Nastepnik(Search(key, this->root))->key);
            tmp->left = wezelek->left;
            if(tmp->left != NULL) tmp->left->parent = tmp;
            if(tmp->right != NULL) tmp->right->parent = tmp;
        }
        else tmp = (wezelek->left != NULL) ? wezelek->left : wezelek->right;

        if(tmp != NULL) tmp->parent = rodzicek;
        if(rodzicek == NULL) this->root = tmp;
        else if(rodzicek->left == wezelek) rodzicek->left = tmp;
        else rodzicek->right = tmp;
        return rodzicek;
    };

    //-----------------------------------------------------PRINT------------------------------------------------------------
    void PrintInOrder(Node<T> *start) {
        if(start != NULL) {
            PrintInOrder(start->left);
            std::cout << start->key << "->";
            PrintInOrder(start->right);
        }
    };
};

#endif

main.cpp

#include "Tree.h"
#include <iostream>
#include <string>

int main() {
    Tree<std::string> *Drzewko = new Tree<std::string>();

    Drzewko->Insert("Ala");
    Drzewko->Insert("Tomek");
    Drzewko->Insert("Monika");
    Drzewko->Insert("Adam");
    Drzewko->Insert("Daniel");
    Drzewko->Insert("Zdzislaw");
    Drzewko->Insert("Michal");
    Drzewko->Insert("Tadeusz");
    Drzewko->Insert("Wieslaw");

    //Drzewko->Delete("Tomek");

    Drzewko->PrintInOrder(Drzewko->root);

    std::cout << Drzewko->Search("Tomek", Drzewko->root)->key;

    return 0;
};

Z góry dzięki za pomoc.

edytowany 2x, ostatnio: Lukasz_, 2014-05-14 19:59

Pozostało 580 znaków

2014-05-14 20:07
1

Zamiast czterokrotnie przepisywać jedną funkcję, użyj jeden raz debuggera ;]


int main( int, char** ) try { throw std::logic_error( myCode() ); }
catch( const std::exception& e ) { puts( e.what() ); } ///:~
edytowany 1x, ostatnio: dampe, 2014-05-14 20:08

Pozostało 580 znaków

2014-05-14 20:10
0

A co, Tobie się udało znaleźć to za pomocą debuggera ?

Pozostało 580 znaków

2014-05-14 20:28
0

A co Tobie udało się znaleźć za pomocą debuggera? I czy w ogóle spróbowałeś?

Pozostało 580 znaków

2014-05-14 20:50
0

Wydaje mi się, że problem występuje w linii tmp->left = wezelek->left; natomiast nie mam zielonego pojęcia co jest nie tak. Tutaj segmentation fault dostaje według debuggera ;<

Pozostało 580 znaków

2014-05-14 22:34
0

No cóż poradziłem sobie sam. Problem leży w funkcji dodawania która zapomina ustawić rodziców.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0