#1 27. Dezember 2010 Zuletzt von einem Moderator bearbeitet: 14. April 2017 Binärbaum Hallo! Ich habe ein kleines Problem und zwar folgendes: Ich muss als Hausübung einen Binärbaum in C#.net programmieren. Ich habe soweit auch eigentlich alles, bis auf die Löschmethode... Hier mal der Sourcecode (ist eine Konsolenanwendung): Klasse: BinaryTreeLib.cs Code: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace BinaryTreeLib { // class TreeNode definition class TreeNode { private TreeNode leftNode; private int data; private TreeNode rightNode; private int[] arrayInOrder = new int[10]; private int arrayCounter = 0; private bool statusArray = false; // initialize data and make this a leaf node public TreeNode( int nodeData ) { data = nodeData; leftNode = rightNode = null; // node has no children } // LeftNode property public TreeNode LeftNode { get { return leftNode; } set { leftNode = value; } } // Data property public int Data { get { return data; } set { data = value; } } // RightNode property public TreeNode RightNode { get { return rightNode; } set { rightNode = value; } } // insert TreeNode into Tree that contains nodes; // ignore duplicate values public void Insert( int insertValue ) { // insert in left subtree if ( insertValue < data ) { // insert new TreeNode if ( leftNode == null ) leftNode = new TreeNode( insertValue ); // continue traversing left subtree else leftNode.Insert( insertValue ); } // insert in right subtree else if ( insertValue > data ) { // insert new TreeNode if ( rightNode == null ) rightNode = new TreeNode( insertValue ); // continue traversing right subtree else rightNode.Insert( insertValue ); } } // end method Insert // delete TreeNode from Tree that contains nodes; public void Delete(int deleteValue, TreeNode root) { if (!statusArray) { InOrderArray(root); //Fills String strInOrder statusArray = true; //call InOrderArray only once. } if (arrayInOrder.Contains(deleteValue)) { int index = 0; //get index... for (int i = 0; i < arrayInOrder.Length; i++) { if(arrayInOrder[i] == deleteValue) index = i; } Console.WriteLine("Value found! Deleting Process...."); //Get References TreeNode delValue = FindNode(deleteValue, root); TreeNode nextInOrderElem = FindNode(arrayInOrder[index+1], root); delValue = nextInOrderElem; //Override Reference if (nextInOrderElem.HasAChild()) nextInOrderElem = nextInOrderElem.LeftNode; } else Console.WriteLine("Value not found."); } // end method DeleteNode //Helper Methods private bool IsLeaf() { if (this.LeftNode == null && this.RightNode == null) return true; else return false; } private bool HasAChild() { if ((this.LeftNode != null && this.RightNode == null) || (this.LeftNode == null && this.RightNode != null)) return true; else return false; } private TreeNode FindNode(int value, TreeNode r) { if (r.Data < value) //Left { if (r.LeftNode != null && r.LeftNode.Data == value) return r.LeftNode; else if(r.LeftNode == null) return FindNode(value, r.RightNode); else return FindNode(value, r.LeftNode); } else if (r.Data > value) //right { if (r.RightNode != null && r.RightNode.Data == value) return r.RightNode; else if (r.RightNode == null) return FindNode(value, r.LeftNode); else return FindNode(value, r.RightNode); } return null; } private void InOrderArray( TreeNode node ) { if ( node == null ) return; // traverse left subtree InOrderArray(node.LeftNode); arrayInOrder[arrayCounter] = node.Data; arrayCounter++; // traverse right subtree InOrderArray(node.RightNode); } } // end class TreeNode // class Tree definition public class Tree { private TreeNode root; // construct an empty Tree of integers public Tree() { root = null; } // Insert a new node in the binary search tree. // If the root node is null, create the root node here. // Otherwise, call the insert method of class TreeNode. public void InsertNode( int insertValue ) { lock ( this ) { if ( root == null ) root = new TreeNode( insertValue ); else root.Insert( insertValue ); } } public void DeleteNode(int deleteValue) { lock (this) { if (root == null) Console.WriteLine("Baum leer - kann nicht gelöscht werden.\n"); else root.Delete(deleteValue, root); } } // begin preorder traversal public void PreorderTraversal() { lock ( this ) { PreorderHelper( root ); } } // recursive method to perform preorder traversal private void PreorderHelper( TreeNode node ) { if ( node == null ) return; // output node data Console.Write( node.Data + " " ); // traverse left subtree PreorderHelper( node.LeftNode ); // traverse right subtree PreorderHelper( node.RightNode ); } // begin inorder traversal public void InorderTraversal() { lock ( this ) { InorderHelper( root ); } } // recursive method to perform inorder traversal private void InorderHelper( TreeNode node ) { if ( node == null ) return; // traverse left subtree InorderHelper( node.LeftNode ); // output node data Console.Write( node.Data + " " ); // traverse right subtree InorderHelper( node.RightNode ); } // begin postorder traversal public void PostorderTraversal() { lock ( this ) { PostorderHelper( root ); } } // recursive method to perform postorder traversal private void PostorderHelper( TreeNode node ) { if ( node == null ) return; // traverse left subtree PostorderHelper( node.LeftNode ); // traverse right subtree PostorderHelper( node.RightNode ); // output node data Console.Write( node.Data + " " ); } } // end class Tree } Klasse: TreeTest.cs (Hauptprogramm) Code: // Fig. 23.18: TreeTest.java // This program tests class Tree. using System; using BinaryTreeLib; //using BinaryTreeLibrary; namespace TreeTest { // class TreeTest definition public class TreeTest { // test class Tree static void Main( string[] args ) { Tree tree = new Tree(); int insertValue; int deleteValue = 0; Console.WriteLine("Delete nothing:"); tree.DeleteNode(1); Console.WriteLine( "Inserting values: " ); Random random = new Random(); // insert 10 random integers from 0-99 in tree for ( int i = 1; i <= 10; i++ ) { insertValue = random.Next( 100 ); Console.Write( insertValue + " " ); tree.InsertNode( insertValue ); } // perform preorder traversal of tree Console.WriteLine( "\n\nPreorder traversal" ); tree.PreorderTraversal(); // perform inorder traversal of tree Console.WriteLine( "\n\nInorder traversal" ); tree.InorderTraversal(); // perform postorder traversal of tree Console.WriteLine( "\n\nPostorder traversal" ); tree.PostorderTraversal(); while (true) { Console.Write("\n\nEnter a Value to delete (Stop with -1): "); deleteValue = Convert.ToInt32(Console.ReadLine()); if (deleteValue == -1) break; tree.DeleteNode(deleteValue); // perform preorder traversal of tree Console.WriteLine("\n\nPreorder traversal"); tree.PreorderTraversal(); // perform inorder traversal of tree Console.WriteLine("\n\nInorder traversal"); tree.InorderTraversal(); // perform postorder traversal of tree Console.WriteLine("\n\nPostorder traversal"); tree.PostorderTraversal(); Console.WriteLine(); } Console.Read(); } } // end class TreeTest } Wo liegt das Problem genau? Man hat uns zum Informieren diesen Link gegeben: Binärbaum – Wikipedia Ich dachte mir, dass es einfacher ist nach dieser Methode zu löschen: Meine Überlegungen: 1. ich dachte mir, ich lass das ganze per InOrder durchlaufen, bau mir einen String zusammen; such das zu löschende Element im String (IndexOf()) und wenn es gefunden wird, kann ich weiterarbeiten, andernfalls ist der Wert nicht vorhanden. 2. Wenn ich die Werte im Array habe, kann ich den Array durchlaufen lassen und mit einer Methode (FindNode) diesen Knoten/dieses Blatt suchen/finden und die Referenz zurück geben 3. Wenn ich die Referenz vom Knoten, der gelöscht werden soll, und von dem nächsten Knoten in der InOrder Reihe habe, kann ich die Referenzen einfach umspeichern und erledigt. 4. fertig^^ Leider macht mir die FindNode Probleme... es kommt ständig die Fehlermeldung: r wird immer null.... er findet keine passenden Werte.... Kann mir da jemand vll einen Denkanstoß geben? Ich sitz schon total auf der Leitung Vielen Dank Gruß Rag Edit: Hier das gesamte Projekt: No File | www.xup.in + Multi-Zitat Zitieren
#2 27. Dezember 2010 Zuletzt von einem Moderator bearbeitet: 15. April 2017 AW: Binärbaum [Python] BinaryTree (binärer Suchbaum) - RR:Board Da habe ich mal den Quellcode von einem Binärbaum in Python vorgestellt. (Murdoc auch noch in PHP) Da kannst du dir mal anschauen, wie ich bei der Löschmethode vorgegangen bin. Grundsätzlich geht man so vor, dass wenn ein innerer Knoten gelöscht wird, dann wird da einfach entweder der größte Wert im linken Teilbaum oder der kleinste aus dem rechten Teilbaum genommen. Blätter kannst du ja einfach so löschen. greez + Multi-Zitat Zitieren
#3 27. Dezember 2010 Zuletzt von einem Moderator bearbeitet: 14. April 2017 AW: Binärbaum Richtig. Es wäre eine umständlichere Arbeit, jetzt herzugehen und einen Knoten mit einem Knoten aufzufüllen, dann muss man diesen Knoten wieder mit einem Knoten auffüllen, etc. Ausgehend bei einem Index von mehreren Millionen Stellen kann das schonmal das Programm, respektive den Rechner in die Knie ziehen. Wenn du allerdings einfach hergehst und immer den größten/kleinsten Wert links/rechts nimmst, dann kannst du löschen, wen und was du willst. G löschst du, K, P oder W setzt du ein. Der Vorteil, wie gesagt: diese Werte haben keine Kinder/weiteren Blätter und sind somit einfach wegzunehmen, als wären sie nie da gewesen. (wobei hier P anstatt K vermutlich netter zu nehmen wäre) + Multi-Zitat Zitieren
#4 28. Dezember 2010 AW: Binärbaum Okay super vielen Dank Jetzt habe ich das auch verstanden ^^ Werde mich dann wohl weiter dran setzen - wenn ich eine funktionierende Lösung habe, werde ich sie hier posten - dann haben wir binärbäume in python, php und c# xD Vielen Dank für die Infos Melde mich wieder Edit: So habe das ganze zum Laufen gebracht Habe es getestet (ca. 10 Durchläufe) und es hat einwandfrei funktioniert Vielen Dank für eure Hilfe. (Habe in dem oben genannten Thema meinen Code angehängt) Gruß + Multi-Zitat Zitieren
#5 5. Januar 2011 Zuletzt von einem Moderator bearbeitet: 14. April 2017 AW: Binärbaum Bei einem normalen Binärbaum ist das so richtig. Bei einem binären Suchbaum hingegen kannst weder K, noch P noch W nehmen ohne die Struktur des Baums zu zerstören. Bei nem binären Suchbaum muss man es so machen wie cable sagte (Den du auch zitiert, aber offenbar nicht ganz verstanden hast) + Multi-Zitat Zitieren