Binärer Suchbaum delete

Unit

Mitglied
Habe ein Problem mit der delete-Methode eines Binärbaumes. Es Klappt alles ganz gut nur die 3. Bedingung (Knoten mit 2 Kindern) macht mir noch Probleme kann mir da jemand helfen? Das Problem liegt darin, dass wenn der Successor selbst im Unterbaum liegt der an den Successor dran gehängt wird.
Code:
    public void delete(T data)

    {

        BNode<T> dNode = find(data);



        if (dNode == root)

        {

            if (root.getChildCount() > 0)

            {

                getSuccessor(root).setLeftChild(root.getLeftChild());

                root = getSuccessor(root);

            } else

            {

                root = null;

            }

        } else

        {



            BNode<T> parent = getParent(dNode);

            if (dNode.isLeaf())

            {



                if (parent.getLeftChild() == dNode)

                {

                    parent.setLeftChild(null);

                } else if (parent.getRightChild() == dNode)

                {

                    parent.setRightChild(null);

                }

            } else if (dNode.getChildCount() == 1)

            {

                if (dNode.getLeftChild() != null)

                {

                    if (getParent(dNode).getRightChild() == dNode)

                    {

                        getParent(dNode).setRightChild(dNode.getLeftChild());

                    } else if (getParent(dNode).getLeftChild() == dNode)

                    {

                        getParent(dNode).setLeftChild(dNode.getLeftChild());

                    }

                } else if (dNode.getRightChild() != null)

                {

                    if (getParent(dNode).getRightChild() == dNode)

                    {

                        getParent(dNode).setRightChild(dNode.getRightChild());

                    } else if (getParent(dNode).getLeftChild() == dNode)

                    {

                        getParent(dNode).setLeftChild(dNode.getRightChild());

                    }

                }

            } else if (dNode.getChildCount() == 2)

            {

                BNode<T> successor = getSuccessor(dNode);

                if (successor != null)

                {



                    if (getParent(dNode).getRightChild() == dNode)

                    {

                        successor.setLeftChild(dNode.getLeftChild());

                        successor.setRightChild(dNode.getRightChild());

                        getParent(dNode).setRightChild(successor);



                    } else if (getParent(dNode).getLeftChild() == dNode)

                    {

                        successor.setRightChild(dNode.getRightChild());

                        successor.setLeftChild(dNode.getLeftChild());

                        getParent(dNode).setLeftChild(successor);

                    }

                }

            }

        }

    }
 
Zuletzt bearbeitet:

Bitfehler

Bekanntes Mitglied
Moin,

Annahme: Knoten K hat zwei Kinder und soll gelöscht werden
Mögliches Vorgehen:
  1. Bestimme Vorgänger-Knoten V
  2. Merke dir den ersten Knoten R des rechten Teilbaums
  3. Hänge den linken Teilbaum (K.getLeftChild) an den Vorgänger-Knoten V(entweder rechts oder links)
  4. Hänge den gemerkten Knoten R nach unten in den linken Teilbaum
Dieses Verfahren erzeugt (hoffentlich) einen Baum, der allerdings nicht besonders gut ausbalanciert ist. Es gibt ein weiteres Verfahren, dass beim Löschen eines Knotens einen besser balancierten Baum erzeugt (Siehe: https://de.wikipedia.org/wiki/Binärbaum#L.C3.B6schen)

Schönen Abend noch
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Cassy3 Binärer Suchbaum Knoten rauslöschen Java Basics - Anfänger-Themen 1
G Java Binärer Suchbaum Java Basics - Anfänger-Themen 1
G Binärer Suchbaum Knoten zählen Java Basics - Anfänger-Themen 1
L Binärer Suchbaum Java Basics - Anfänger-Themen 2
S Binärer Suchbaum - Size als Variabel in innerer Klasse speichern Java Basics - Anfänger-Themen 2
E binärer suchbaum Java Basics - Anfänger-Themen 8
K Binärer Suchbaum Java Basics - Anfänger-Themen 3
D Binärer Suchbaum Java Basics - Anfänger-Themen 11
Q Binärer suchbaum Java Basics - Anfänger-Themen 2
Y Binärer Suchbaum Java Basics - Anfänger-Themen 5
M Binärer Suchbaum Höhe Java Basics - Anfänger-Themen 6
G Hoffe jemand kann mir ein paar Tips geben:binärer Suchbaum Java Basics - Anfänger-Themen 3
E Binärer Suchbaum Java Basics - Anfänger-Themen 7
R binärer Suchbaum Java Basics - Anfänger-Themen 1
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
H binärer String nach int convertieren Java Basics - Anfänger-Themen 3
T Binärer String zu Integer Java Basics - Anfänger-Themen 12
P Binärer Baum mit Composite-Entwurfsmuster Java Basics - Anfänger-Themen 2
S binärer string in negativen int umwandeln Java Basics - Anfänger-Themen 4
C binärer Exponentenbereich bezogen auf das Dezimalsystem Java Basics - Anfänger-Themen 2
G Binärer Baum Java Basics - Anfänger-Themen 3
M Binärer Baum Tiefe Java Basics - Anfänger-Themen 14
T binärer Baum Java Basics - Anfänger-Themen 3
R binärer Baum Java Basics - Anfänger-Themen 2
O Suchbaum Elternknoten finden Level eines Knoten bestimmen Java Basics - Anfänger-Themen 24
N ID3 - Suchbaum ertellen! Java Basics - Anfänger-Themen 0
M Suchbaum implementieren Java Basics - Anfänger-Themen 8
C Methoden Methode zu einem Binären Suchbaum Java Basics - Anfänger-Themen 8
J Suchbaum Java Basics - Anfänger-Themen 3
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
N Binären Suchbaum erstellen, nachzuvollziehen Java Basics - Anfänger-Themen 0
W binären Suchbaum Kantenanzahl Java Basics - Anfänger-Themen 3
G Rekursion Suchbaum Java Basics - Anfänger-Themen 2
W Löschen Datenknoten Suchbaum Java Basics - Anfänger-Themen 4
H Suchbaum iterativ absteigen? Java Basics - Anfänger-Themen 3
N Tiefe im binären Suchbaum Java Basics - Anfänger-Themen 9
I Rekursives Löschen in Binärem Suchbaum Java Basics - Anfänger-Themen 2
A Suchbaum Java Basics - Anfänger-Themen 4
DasDogma Suche im Suchbaum Java Basics - Anfänger-Themen 2
D suchbaum out of heap space Java Basics - Anfänger-Themen 8
G Binäre Suchbaum + Erstellung des Programmes Java Basics - Anfänger-Themen 4
Bierhumpen Suchbaum problem. Java Basics - Anfänger-Themen 8
Henri Webservice Delete und Update Methode funktioniert nicht Java Basics - Anfänger-Themen 27
P Schleife für insert() und delete() im StringBuilder in Verbindung mit indexOf() Java Basics - Anfänger-Themen 7
A Abstrakte Datentypen - Methode delete Java Basics - Anfänger-Themen 6
A file.delete funktioniert nicht Java Basics - Anfänger-Themen 15
J File.delete erfolgreich obwohl Datei geöffnet ist. Java Basics - Anfänger-Themen 3
T Datei wird nicht gelöscht mit file.delete() Java Basics - Anfänger-Themen 5
T If ; else error on system token delete Java Basics - Anfänger-Themen 5
E StringBuilder.delete Problem Java Basics - Anfänger-Themen 2
J JTable abstractTableModel delete Row Java Basics - Anfänger-Themen 4
R Syntax error on token "}", delete this token Java Basics - Anfänger-Themen 2
0 file.delete() geht nicht Java Basics - Anfänger-Themen 23
Burny91 File.delete(file) geht nicht-Offener Stream aber WO? Java Basics - Anfänger-Themen 4
B Delete Methode löscht falsches Element Java Basics - Anfänger-Themen 7
S Wieso funtkioniert das SQL DELETE nicht? Java Basics - Anfänger-Themen 1
S prepared statement delete Java Basics - Anfänger-Themen 5
G sql-delete von java aus Java Basics - Anfänger-Themen 18
N File.delete() und File.list() Java Basics - Anfänger-Themen 6
E java.io - File: delete funktioniert nicht Java Basics - Anfänger-Themen 5
G Über undo, copy, cat, paste, delete Funktionen Java Basics - Anfänger-Themen 3
B File mit Methode delete löschen Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben