Implementierung eines Binärbaums @ tutorials.de: Tutorials, Forum & Hilfe

kodak · 06.07.06 11:25

Zitat von Thomas Darimont

Fragen zu Übungen und Hausaufgaben aus dem Algorithmenbereich sind auch erlaubt

Das werde ich doch gleich mal ausnutzen. *g*

Also di Aufgabe besteht darin, einen einfachen Binärbaum zu implementieren. Der soll im Groben nur insert und preorder output beherrschen. Das problem ist, es gibt eine vorgefertigte Klasse, die ich als Datenstruktur verwenden soll. Das ist auch nicht unbedingt das Problem, ehr das Einfügen in eine solche. meine Kongrete Frage dazu ist: wenn ich durch den Baum gegangen bin, und meinen Key+Info eingefügt habe, wie setzte ich meinen "pointer" wieder auf die Wurzel?

Code :

    public void insert(String key, Object info) {
 
        while (wurzel != null) {
 
            if (Integer.parseInt(wurzel.getKey()) > Integer.parseInt(key))
                wurzel = wurzel.getLeft();
            else
                wurzel = wurzel.getRight();
 
        }
 
        wurzel = new TreeNode(key, info);
 
 
    }

Dass der Key ein String ist, wurde schon vorgegeben, aber sollte nicht das Problem sein
Wurzel ist mein statisches Objekt aus der Klasse (fest vorgegeben):

Code :

public class TreeNode {
    // Instance variables:
 
    private String key;
 
    private Object info; // Daten private ergibt mehr Aufwand(set- und
 
    // get-Methoden)
 
    private TreeNode left; // Referenzen auf Soehne
 
    private TreeNode right;
 
    // Simple constructors:
 
    public TreeNode(String k, Object inf) {
        this(k, inf, null, null);
    }
 
    public TreeNode(String k, Object inf, TreeNode l, TreeNode r) {
        key = k;
        info = inf;
        left = l;
        right = r;
    }
 
    // Accessor methods:
 
    public String getKey() { // gibt den key of this TreeNode zurueck
        return key;
    }
 
    public Object getInfo() { // gibt die Daten des Knotens zurueck
        return info;
    }
 
    public TreeNode getLeft() { // gibt den linken Verkettungszeiger des Knotens
        // zurueck
        return left;
    }
 
    public TreeNode getRight() { // gibt den rechten Verkettungszeiger des
        // Knotens zurueck
        return right;
    }
 
    // Modifier methods: aendere Knoteninhalte und Pointer
 
    public void setKey(String nk) {
        key = nk;
    }
 
    public void setInfo(Object newinf) {
        info = newinf;
    }
 
    public void setNextLeft(TreeNode NextLeft) {// setzt in this treenode den
        // LeftPointer NextLeft
        left = NextLeft;
    }
 
    public void setNextRight(TreeNode NextRight) {// setzt in this treenode
        // den RightPointer
        // NextRight
        right = NextRight;
    }
}

Ich hoffe ihr könnt mir weiterhelfen, ich habe schon mehere Varianten ausprobiert, aber keine hat das gewünschte ergebnis gebracht.

Ciao
Kodak

kodak · 10.07.06 08:47

Vielen Dank für eure umfangreiche Hilfe, ihr seid Spitze

illaX · 10.07.06 09:51

Keine Ursache

**Thomas Darimont** · 10.07.06 13:00

Hallo!

Hier ein Beispiel für die Implementierung eines Binärbaums und die verschiedenen Traversierungs (Durchlauf) Techniken.

Traversierung via:
PreOrder
InOrder
PostOrder
LevelOrder

Schau mal hier:

Code java:

/**
 *
 */
package de.tutorials;
 
import java.util.LinkedList;
import java.util.Queue;
 
/**
 * @author Thomas.Darimont
 * 
 */
public class BinaryTreeExample {
    /**
     * @param args
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(100, "F");
 
        TreeNode nodeB = root.insertIterative(new TreeNode(50, "B"));
        TreeNode nodeG = root.insertIterative(new TreeNode(150, "G"));
        TreeNode nodeA = nodeB.insertIterative(new TreeNode(25, "A"));
        TreeNode nodeD = nodeB.insertIterative(new TreeNode(65, "D"));
        TreeNode nodeI = nodeG.insertIterative(new TreeNode(200, "I"));
        TreeNode nodeC = nodeD.insertIterative(new TreeNode(60, "C"));
        TreeNode nodeE = nodeD.insertIterative(new TreeNode(70, "E"));
        TreeNode nodeH = nodeI.insertIterative(new TreeNode(190, "H"));
 
        System.out.println("###############");
        System.out.println("printPreOrder");
        TreeNode.printPreOrder(root);
        System.out.println("###############");
        System.out.println("printInOrder");
        TreeNode.printInOrder(root);
        System.out.println("###############");
        System.out.println("printPostOrder");
        TreeNode.printPostOrder(root);
        System.out.println("###############");
        System.out.println("printLevelOrder");
        TreeNode.printLevelOrder(root);
 
    }
 
    static class TreeNode {
 
        int key;
 
        Object data;
 
        TreeNode left, right;
 
        public TreeNode(int key, Object data) {
            this.key = key;
            this.data = data;
        }
 
        public Object getData() {
            return data;
        }
 
        public void setData(Object data) {
            this.data = data;
        }
 
        public int getKey() {
            return key;
        }
 
        public TreeNode getLeft() {
            return left;
        }
 
        public void setLeft(TreeNode left) {
            this.left = left;
        }
 
        public TreeNode getRight() {
            return right;
        }
 
        public void setRight(TreeNode right) {
            this.right = right;
        }
 
        public TreeNode insertRecursive(TreeNode node) {
            if (node.key < this.key) {
                if (this.left != null) {
                    this.left.insertRecursive(node);
                } else {
                    this.left = node;
                }
            } else {
                if (this.right != null) {
                    this.right.insertRecursive(node);
                } else {
                    this.right = node;
                }
            }
            return node;
        }
 
        public TreeNode insertIterative(TreeNode node) {
            TreeNode currentNode = this;
            while (currentNode != null) {
                if (node.key < currentNode.key) {
                    if (currentNode.left == null) {
                        currentNode.left = node;
                        break;
                    } else {
                        currentNode = currentNode.left;
                    }
                }else if (node.key > currentNode.key) {
                    if (currentNode.right == null) {
                        currentNode.right = node;
                        break;
                    } else {
                        currentNode = currentNode.right;
                    }
                }
            }
            return node;
        }
 
        public String toString() {
            return this.key + ": " + this.data;
        }
 
        public static void printPreOrder(TreeNode baseNode) {
            System.out.println(baseNode);
            if (baseNode.left != null) {
                printPreOrder(baseNode.left);
            }
            if (baseNode.right != null) {
                printPreOrder(baseNode.right);
            }
        }
 
        public static void printInOrder(TreeNode baseNode) {
            if (baseNode.left != null) {
                printInOrder(baseNode.left);
            }
            System.out.println(baseNode);
            if (baseNode.right != null) {
                printInOrder(baseNode.right);
            }
        }
 
        public static void printPostOrder(TreeNode baseNode) {
            if (baseNode.left != null) {
                printPostOrder(baseNode.left);
            }
            if (baseNode.right != null) {
                printPostOrder(baseNode.right);
            }
            System.out.println(baseNode);
        }
 
        public static void printLevelOrder(TreeNode node) {
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(node);
 
            while (!queue.isEmpty()) {
                TreeNode currentNode = queue.poll();
                System.out.println(currentNode);
                if (null != currentNode.left) {
                    queue.add(currentNode.left);
                }
                if (null != currentNode.right) {
                    queue.add(currentNode.right);
                }
            }
        }
    }
}

Ausgabe:

Code :

###############
printPreOrder
100: F
50: B
25: A
65: D
60: C
70: E
150: G
200: I
190: H
###############
printInOrder
25: A
50: B
60: C
65: D
70: E
100: F
150: G
190: H
200: I
###############
printPostOrder
25: A
60: C
70: E
65: D
50: B
190: H
200: I
150: G
100: F
###############
printLevelOrder
100: F
50: B
150: G
25: A
65: D
200: I
60: C
70: E
190: H

Gruß Tom

tut orials.de	tut verbinden	tut dir helfen	tut kooperieren
©2000-2012 tutorials.de Alle Rechte vorbehalten	tut informieren » Impressum » Nutzungsregeln » Netiquette » Team » Redaktion	» Tutorials » Videotutorials » Showroom » Events & Contests » Chat » RSS-Feed » Blogs	» der-webdesigner.net » DesignerInAction » Design Nation » Directorforum » Flashhilfe » PHP-Resource » PHPwelt » PSD-Tutorials

Themen-Optionen

Anzeige

Ähnliche Themen

[C++] Probleme bei Implementierung eines eigenen Datei-Archiv-Formats

Schwierigkeiten bei der Implementierung/Entwurf eines Algorithmusses

IBM Artikel zeigt Implementierung eines Zustandsautomaten mit Ruby on Rails

Implementierung eines Upload

Implementierung eines Terminplans in Java

E-Mail:

Abonnieren Abbestellen