# Durch Bäume iterieren



## Zootlex (11. Mai 2014)

Hallo Leute,

ich habe folgende Klasse:


```
import java.util.*;
import java.util.function.*;

class Tree<E>{
    E elem;
    boolean isNil;
    List<Tree<E>> children = new ArrayList<>();

    Tree(){
	isNil = true;
    }
    Tree(E e,Tree<E>... ts){
	isNil = false;a
	elem = e;
	for (Tree<E> t:ts) children.add(t);
    }

  // Zu implementierende Funktionen
       // Aufgabe 1:
        List<E> fringe() {
           return null;
        }
        
        //Aufgabe 2:
        List<E> pathTo(E elem) {
            return null;
        }
        //Aufgabe 3:
        boolean contains(java.util.function.Predicate<E> pred) {
            return true;
        }
        //Aufgabe 4:
        boolean contains(E el) {
            return true;
        }
        //Aufgabe 5:
        <R> Tree<R> mapTree(java.util.function.Function<E, R> f) {
            return null;
        }
    
  //********************************
    
    
    int size2(){
	if (isNil) return 0;

	int result = 1;
	for (Tree<E> child:children){
	    result = result +child.size2();
	}
	return result;
    }


    int size(){
	if (isNil) return 0;

	return children.stream().map( x -> x.size() ).reduce(1, (result,childSize) -> result +childSize );
	/*	int result = 1;
	for (Tree<E> child:children){
	    result = result +child.size();
	}
	return result;*/
    }

    void fuerAlle(Consumer<E> c) {
	if (!isNil){
	    for (Tree<E> child:children){
		child.fuerAlle(c);
	    }
	    c.accept(elem);

	}
    }

    static public void main(String[] args){
	Tree<String> windsor
	    = new Tree<>("George"
			 ,new Tree<>("Elizabeth"
				     ,new Tree<>("Charles"
						 ,new Tree<>("William"
							     ,new Tree<>("George")
							     )
						 ,new Tree<>("Harry")
						 )
				     ,new Tree<>("Anne")
				     ,new Tree<>("Andrew")
				     ,new Tree<>("Edward")
				     )
			 ,new Tree<>("Margret")
			 ) ;
	System.out.println(windsor.size());
        windsor.fringe();
	windsor.fuerAlle(x ->  System.out.println(x));
    }

}
```

Aufgabe 1)

Schreiben Sie für die Klasse Tree eine Methode List<E> fringe(),
die die Liste der Blätter des Baumes zurück gibt. 
Ein Blatt ist dabei ein Baumknoten, der keine Kinder mehr hat.

*****

Ich weiss leider absolut nicht was ich hier machen soll.. Wie kann ich durch die Knoten des Baumes iterieren? 

LG


----------



## Gucky (11. Mai 2014)

Bei Wikipedia gibt es einen kleinen Codeteil. Durch Bäume iterieren ist sehr einfach rekursiv zu realisieren.

Aber dein Baum scheint ein Baum bestehend aus noch mehr Bäumen zu sein und nicht bestehend aus Blättern (vom Wortsinn kein Unterschied, Java Technisch schon)


----------



## trez (12. Mai 2014)

Das ist kein schwerwiegender Unterschied ;-)


```
private boolean isLeafe() {
		return (children.size() == 0);
	}

	List<E> fringe() {
		List<E> l = new ArrayList<E>();
		if (isLeafe()) {
			l.add(this.elem);
		} else {
			// iteriere durch alle Kinder und hänge alle gefundenen
			// Blätter an die temporäre Liste an
			for (Tree<E> t : children) {
				l.addAll(
					ja genau - hier iterieren, aber das ist ja wohl genau der
					Bestandteil der Aufgabe den du selbst lösen musst
				)
			}
		}
		return l;
	}
```


----------



## Zootlex (12. Mai 2014)

danke


----------

