Baumstrukturen traversieren

[Thomas Darimont]

Hallo!

Hier mal zwei Beispiele wie man Baumstrukturen rekursiv / halbrekusiv traversieren kann:

/*
 * 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]

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

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]

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]

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