Baumstrukturen traversieren

Thomas Darimont

Erfahrenes Mitglied
Hallo!

Hier mal zwei Beispiele wie man Baumstrukturen rekursiv / halbrekusiv traversieren kann:
Code:
/*
 * Created on 04.11.2004
 */
package de.tutorials;

import java.util.Stack;

/**
 * @author Darimont
 *  
 */
public class Test42 {

    private Stack stack;

    public static void main(String[] args) {
        new Test42().doIt();
    }

    private void doIt() {
        Node root = new Node(new Integer(32));
        Node n0 = new Node(new Integer(17));
        root.left = n0;
        Node n1 = new Node(new Integer(11));
        n0.left = n1;
        Node n2 = new Node(new Integer(19));
        n0.right = n2;
        Node n3 = new Node(new Integer(65));
        root.right = n3;
        Node n4 = new Node(new Integer(42));
        n3.left = n4;
        stack = new Stack();

        System.out.println("traverse1:");
        traverse1(root);
        System.out.println("\ntraverse2:");
        traverse2(root);
    }

    public void traverse1(Node node) {
        stack.push(node);
        while (!stack.isEmpty()) {
            Node n = (Node) stack.pop();
            System.out.println(node);
            if (node.left != null)
                traverse1(node.left);
            if (node.right != null)
                traverse1(node.right);
        }
    }

    public void traverse2(Node node) {
        System.out.println(node);
        if (node.left != null)
            traverse2(node.left);
        if (node.right != null)
            traverse2(node.right);
    }

    class Node {
        public Node(Object o) {
            this.data = o;
        }

        public Node left;
        public Node right;
        public Object data;

        public String toString() {
            return this.data.toString();
        }
    }
}

Hat jemand noch Implementierung zur Hand die das Ganze NUR interativ (also allein mit Schleifen) löst?

Gruß Tom
 

RedWing

Erfahrenes Mitglied
Hi,
zu später Stunde würd ich folgendes Vorschlagen:

Code:
import java.util.Stack;                                                                                                                    

/**    
 * @author Darimont
 *  
 */
public class Test42 {                                                                                                                      

    private Stack stack;                                                                                                                   

    public static void main(String[] args) {
        new Test42().doIt();                                                                                                               
    }  

    private void doIt() {    
        Node root = new Node(new Integer(32));
        Node n0 = new Node(new Integer(17));                                                                                               
        root.left = n0;      
        Node n1 = new Node(new Integer(11));                                                                                               
        n0.left = n1;        
        Node n2 = new Node(new Integer(19));                                                                                               
        n0.right = n2;       
        Node n3 = new Node(new Integer(65));
        root.right = n3;     
        Node n4 = new Node(new Integer(42));                                                                                               
        n3.left = n4;        
        Node n5 = new Node(new Integer(43));                                                                                               
        n3.right = n5;       
        stack = new Stack();                                                                                                               

        System.out.println("traverse1:");
        traverse_iterativ(root);                                                                                                           
    }

    public void traverse_iterativ(Node node) {                                                                                             

        stack.push(node);    
        while(!stack.empty()){       
                Node t = (Node)stack.pop();
                if(t != null){               
                        System.out.println(t.data);
                        stack.push(t.right);  
                        stack.push(t.left);                                                                                               
                }
        }
                                                                                                                                           
    }

    class Node {
        public Node(Object o) {  
            this.data = o;   
        }

        public Node left;    
        public Node right;   
        public Object data;                                                                                                                

        public String toString() {
            return this.data.toString();                                                                                                   
        }
    }
}


Die Methode traverse_iterative(Node); sollte preorder (Wurzel->Leftson->Rightson)
implementieren...

Gruß

RedWing
 

Thomas Darimont

Erfahrenes Mitglied
Hallo!

Okay, hab mit meiner Frage leider etwas daneben gehauen.
Ich wollte eine Iterative Lösung ohne Stack / bzw. sonstige Collections.
Die 2te Lösung mit Stack lässt sich ja ganz leicht aus meiner ersten Varainte ableiten.

Trotzdem Danke!

Gruß Tom
 

RedWing

Erfahrenes Mitglied
Ok, die Lösung lag auf der Hand,
allerdings muss man den Stack der bei einer rekursiven Lösung im Speicher
aufgebaut/abgebaut wird, ja irgendwie iterativ abbilden, und das lässt sich nunmal
nur mit einem (dynamisch wachsenden) sequentiellen/ assoziaitven Container
erledigen...

Gruß

RedWing