Pre-order/Post-order iterative Traversierung der n-ary tree mit Iterator-Muster

Ich habe implementiert eine Generische (n-ary) Struktur in Java als gegeben hier und durch einen Verweis auf die Quelle gegeben, auf die GitHub - repository des Autors Eins. Ich möchte zu implementieren, die eine pre-order und post-order-Traversierung der n-ary tree unter Verwendung der Iterator in java. Also, die Methoden hasNext() wird eine true zurück, wenn sich ein Knoten und die Methode next() wird wieder der Knoten, der vorhanden wäre nächste in der pre - /post-order-traversal.

Ich versuche zu Folgen, die pseudo-codes angegeben, die in diesem Frage aber ich bin nicht in der Lage, stecken Sie es in die next-Methode von Iterator, die ich geschrieben habe, unter

public class DepthFirstIterator<T> implements Iterator<TreeNode<T>> {

    private Stack<TreeNode<T>> dfsStack;
    private Tree<T> tree;
    private TreeNode<T> start;

    public DepthFirstIterator(Tree<T> tree) {
        this.tree = tree;
        this.dfsStack = new Stack<TreeNode<T>>();
        if (!this.tree.isEmpty())
            this.dfsStack.push(this.tree.getRoot());
    }

    public DepthFirstIterator(Tree<T> tree, TreeNode<T> startNode) {
        this.tree = tree;
        this.dfsStack = new Stack<TreeNode<T>>();
        if (startNode != null)
            this.dfsStack.push(startNode);
    }

    public boolean hasNext() {
        return (!this.dfsStack.isEmpty());
    }

    public TreeNode<T> next() {
                //Iterative code to obtain pre/post-order traversal
    }

    public void remove() {
     //Do nothing
    } 

Tree-Klasse:

public class Tree<T> {

    private TreeNode<T> root;

    public TreeNode<T> getRoot() {
        return this.root;
    }

    public void setRoot(TreeNode<T> element) {
        this.root = element;
    }

    public boolean isEmpty() {
        return (this.root == null);
    }

    public int size() {
        if (isEmpty())
            return 0;
        else
            return getNumberOfNodes(root) + 1;
    }

    private int getNumberOfNodes(TreeNode<T> node) {
        int num = 0;
        Stack<TreeNode<T>> nodeStack = new Stack<TreeNode<T>>();
        nodeStack.push(node);
        while (!nodeStack.isEmpty()) {
            TreeNode<T> top = nodeStack.pop();
            for (TreeNode<T> child : top.getChildren()) {
                num++;
                nodeStack.push(child);
            }
        }
        return num;
    }
}

TreeNode-Klasse:

public class TreeNode<T> {

    private T data;
    private List<TreeNode<T>> children;
    private TreeNode<T> parent;

    public TreeNode() {
        super();
        children = new ArrayList<TreeNode<T>>();
        parent = null;
    }

    public TreeNode(T data) {
        this();
        setData(data);
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return this.data;
    }

    public List<TreeNode<T>> getChildren() {
        return children;
    }

    public void setChildren(List<TreeNode<T>> children) {
        for (TreeNode<T> child : children)
            child.parent = this;
        this.children = children;
    }

    public void addChild(TreeNode<T> child) {
        child.parent = this;
        children.add(child);
    }

    public void insertChildAt(int index, TreeNode<T> child)
            throws IndexOutOfBoundsException {
        child.parent = this;
        children.add(index, child);
    }

    public TreeNode<T> getChildAt(int index) throws IndexOutOfBoundsException {
        return children.get(index);
    }

    public void removeChildAt(int index) throws IndexOutOfBoundsException {
        children.remove(index);
    }

    public void removeChildren() {
        children.clear();
    }

    public int getNumberOfChildren() {
        return children.size();
    }

    public String toString() {
        return getData().toString();
    }

    public boolean hasChildren() {
        return (getChildren().size() > 0);
    }

    public TreeNode<T> getParent() {
        return this.parent;
    }
}

Weiß ich, dass mit als-für viele Blöcke wie die Tiefe des Baumes geht, ist vollkommen falsch, aber die stack-Logik war nicht intuitiv für mich. Wenn jemand,könnte Sie bitte führe mich ich würde es wirklich schätzen.

Dank,
Chaitanya

  • Ich verstehe nicht, Ihre Frage. Sie haben bereits (oder kopiert) next() Methode. Was ist dein problem mit ihm?
  • Die Methode ist sehr falsch. Ich bin mit 2 for-Schleifen, die nur für eine Tiefe von 3 in der n-ary tree. Also, es ist überhaupt nicht generisch.
  • Verwenden Sie Rekursion. Ich bin sicher, Sie finden ähnliche Beispiele, wenn Sie google für "recursive tree traversal".
  • Ich glaube, ich habe einen Beispielcode mit Rekursion. Eigentlich wollte ich geben den iterativen Ansatz eine Chance. Da bekam ich klebte ich die Frage gepostet hier.
  • Wenn Sie dieses tun, sind iterativ, müssen Sie zu verfolgen die Ordnung des Baumes (das n bei n-Fach)
InformationsquelleAutor chaitanya | 2012-02-21
Schreibe einen Kommentar