3. Binäre Suchbäume remove-funktion

Binäre Suchbäume remove-funktion

  • W

    hi
    hab folgendes problem bei den binären suchbäumen in der remove funktion :

    und zwar nach dem ich die 4 entfernt habe wird das Element nicht komplett gelöscht nur die 4 und diese wird auch nur durch irgend einen wert ersetzt wenn ich also die 3 suche bleibt er in einer dauerschleife stecken in der er das element sucht
    so weit ich ich weiß muss ich den pointer auf das element löschen, aber die frage ist wie

    /* 

#ifndef LIST_H
#define	LIST_H

#include <cstdlib>
#include <string>
using namespace std;

class List {
public:
    virtual void add(int value) = 0;
    virtual bool remove(int value) = 0;
    virtual int size() = 0;
    virtual bool find(int value) = 0;

};

#endif	/* LIST_H */

    /* 

#ifndef BINARYSEARCHTREE_H
#define	BINARYSEARCHTREE_H
#include"List.h"
#include<iostream>

class BinarySearchTree : public List {
public:

    void add(int value);
    bool remove(int value);
    bool find(int value);
    int size();
    BinarySearchTree();
    virtual ~BinarySearchTree();

protected:

    class Element {
    public:
        Element(int value);
        Element(int value, Element* left, Element* right);

        int value_;
        Element* left_;
        Element* right_;

    };

    bool findElement(int value, Element* element);
    void addElement(int value, Element* &element );
    bool removeElement(int value, Element* element);

    Element* root_;
    int size_;

};

#endif	/* BINARYSEARCHTREE_H */

    #include "BinarySearchTree.h"
using namespace std;

BinarySearchTree::Element::Element(int value) 
{
    value_ = value;
    left_ = NULL;
    right_ = NULL;
}

BinarySearchTree::Element::Element(int value, Element* left, Element* right)
{
    value_ = value;
    left_ = left;
    right_ = right;
}

void BinarySearchTree::add(int value)
{
    addElement(value, root_);
    size_++;
}

void BinarySearchTree::addElement(int value, Element* &element)//stimmt
{

    if (element == NULL) //noch kein element
    {
        element = new Element(value); 
    } 
    else if (value < element->value_)// das vorherige Element ist größer
    {
        addElement(value, element->left_);
    } 
    else  // das vorherige Element ist kleiner
    {
        addElement(value, element->right_);
    }
}
bool BinarySearchTree::removeElement(int value, Element* element)
{

    if(element == NULL)//element nicht vorhanden
    {
        return false;

    }
    else if(value < element->value_)//sucht in den elementen die kleiner sind 
    {
        removeElement(value, element->left_);
    }
    else  // sucht in den elementen die größer sind
    {
        removeElement(value, element->right_);
    }
    if(value == element->value_)//hat das richtige element gefunden
    {

        if(!element->left_ && !element->right_)// ein Blatt(keine werte unter sich)

        { 

            delete element;
            size_ --;
        }
        else if(element->right_=NULL)//ein Kind (ein wert unter sich auf der linken Seite)

        {

           element->value_ = element->left_->value_;
           delete element;
           size_ --;
        }
        else if(element->left_=NULL) //ein Kind (ein wert unter sich auf der rechten Seite)

        {

            element->value_ = element->right_->value_;
            delete element;
            size_ --;
        }
        else   // zwei Kinder ( mehrere werte unter sich)
        {
            element =element->right_;
            while(element->left_!=NULL)
            {
                element = element->left_;
            }
            element->value_=element->right_->value_;
            delete(element->right_);

        }
    }
}
bool BinarySearchTree::remove(int value) 
{
    removeElement(value, root_);

}

bool BinarySearchTree::find(int value) 
{
    return findElement(value, root_);
}

bool BinarySearchTree::findElement(int value, Element* element)//stimmt
{
    if (element == NULL) //element nicht gefunden
    {
        return false;
    } 
    else if (value == element->value_)  //element gefunden
        {
            return true;
        } 
    else if (value < element->value_) //element ist größer als gesucht wert-> auf linken seite suchen
         {
                return findElement(value, element->left_);
         } 
    else // element ist kleiner als gesuchter wert-> auf rechten seite suchen
         {
        return findElement(value, element->right_);
        }
}

int BinarySearchTree::size() 
{
    return size_;
}
BinarySearchTree::BinarySearchTree()
{
    root_ = NULL;
    size_ = 0;
}

BinarySearchTree::~BinarySearchTree()
{

}

    #include <cstdlib>
#include"List.h"
#include "BinarySearchTree.h"

using namespace std;

int main()
{

  BinarySearchTree myList;

    myList.add(5);
    myList.add(3);
    myList.add(4);
    myList.add(2);
    myList.add(7);

    cout<<"Das ergebnis für 8 ist: "<<myList.find(8)<<endl;
    cout<<"Das ergebnis für 2 ist: "<<myList.find(2)<<endl;
    cout<<"das ergebnis für 4 ist: "<<myList.find(4)<<endl;
    cout<<"Die Listengroeße ist: "<<myList.size()<<endl;

    myList.remove(4);
    myList.remove(3);
    myList.remove(5);
    myList.remove(8);

    cout<<"das ergebnis für 4 ist: "<<myList.find(4)<<endl;
    cout<<"Die Listengroeße ist: "<<myList.size()<<endl;

    //myList.remove(42);

    return 0;
}
    0
  • T

    Wenn Du einen Blatt löschst, dann muss Du auch den Parent updaten, damit der nicht ins Nirvana zeigt.
    Abgesehen davon meine ich, dass Du auch gerne den Child und den Parent in deinem Code durcheinander wirfst.

    0
  • ?
     

    if (element->right_=NULL)  // Zuweisung, kein Vergleich
    0
  • W

    okj hab das ganze jetzt noch mal überarbeitet aber es ist immer noch die frage wie ich den pointer auf das element lösche

    bool BinarySearchTree::removeElement(int value, Element* element)
{

    if(element == NULL)//element nicht vorhanden
    {
        return false;

    }
    else if(value < element->value_)//sucht in den elementen die kleiner sind 
    {
        removeElement(value, element->left_);
    }
    else  // sucht in den elementen die größer sind
    {
        removeElement(value, element->right_);
    }
    if(value == element->value_)//hat das richtige element gefunden
    {

        if(!element->left_ && !element->right_)// ein Blatt(keine werte unter sich)
//        if(element->left_=NULL && element->right_=NULL)
        { 

            delete element;
            size_ --;
        }
        else if(element->left_ && !element->right_)//ein Kind (ein wert unter sich auf der linken Seite)
        //else if(element->right_=NULL)
        {

           element->value_ = element->left_->value_;
           delete element;
           size_ --;
        }
        else if(!element->left_ && element->right_)//ein Kind (ein wert unter sich auf der rechten Seite)
        //else if(element->left_=NULL)
        {

            element->value_ = element->right_->value_;
            delete element;
            size_ --;
        }
        else   // zwei Kinder ( mehrere werte unter sich)
        {
            element =element->right_;
            while(element->left_!=NULL)
            {
                element = element->left_;
            }
            element->value_=element->right_->value_;
            delete(element->right_);
            //delete(temp->value_);
            //if(element->left_->value_< element->left_->left_->value_)

        }
    }
}
    0
  • W

    okj habs jetzt noch mal überarbeitet und mit hilfe von wikipedia soweit fertig aus denn fall wenn ein element zwei kinder hat
    http://en.wikipedia.org/wiki/Binary_search_tree

    bool BinarySearchTree::removeElement(int value,Element* &element)
{

    if(element == NULL)//element nicht vorhanden
    {
        return false;

    }
    else if(value < element->value_)//sucht in den elementen die kleiner sind 
    {
        removeElement(value, element->left_);
    }
    else  // sucht in den elementen die größer sind
    {
        removeElement(value, element->right_);
    }
    if(value == element->value_)//hat das richtige element gefunden
    {
       Element* temp; 

         if(element->right_==NULL)//ein Kind (ein wert unter sich auf der linken Seite)
        {
           temp=element->left_;
           delete element;
           element=temp;
           size_ --;
        }
         else if(element->left_==NULL)//ein Kind (ein wert unter sich auf der rechten Seite)
        {
            temp=element->right_;
            delete element;
            element=temp;
            size_ --;
        }
        else   // zwei Kinder ( mehrere werte unter sich)
        {
             temp = element->right_;

                        while(temp->left_!=NULL)
                        {
                                temp = temp->left_;
                        }
                        element->value_ = temp->value_;
                        delete(element->right_,temp->value_); //das delete temp->value geht nicht BinarySearchTree.cpp:93:60: error: type ‘int’ argument given to ‘delete’, expected pointer                      
                        size_--;

        }
    }
}
    0
Anmelden zum Antworten