차례차례 비차례차례 두 갈래 나무를 두루 다니다

package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinTree {

    public int[] array = {1,2,3,4,5,6,7,8,9};
    public List nodelist = null;

    public  class Node {
        Node leftChild;
        Node rightChild;
        int data;

        Node(int data) {
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    public void createBinTree() {
        nodelist = new ArrayList();
        for(int index=0; indexnew Node(array[index]));
        }

        // 9, (9/2-1=3) 。 n-1 
        for(int parentIndex=0; parentIndex2 - 1; parentIndex++) {
            nodelist.get(parentIndex).leftChild = nodelist.get(parentIndex*2 + 1);
            nodelist.get(parentIndex).rightChild = nodelist.get(parentIndex*2 + 2);
        }
        // 。 
        int lastParent = array.length / 2 - 1;
        nodelist.get(lastParent).leftChild = nodelist.get(lastParent*2 + 1);
        if(array.length % 2 == 1) {
            nodelist.get(lastParent).rightChild = nodelist.get(lastParent*2 + 2);
        }
    }

    public void preOrderTraverse(Node node) {
        if(node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }

    public void inOrderTraverse(Node node) {
        if(node == null) {
            return;
        }
        inOrderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        inOrderTraverse(node.rightChild);
    }

    public void lastOrderTraverse(Node node) {
        if (node == null) {
            return;
        }
        lastOrderTraverse(node.leftChild);
        lastOrderTraverse(node.rightChild);
        System.out.print(node.data + " ");

    }

    public void norecursivePre(Node node) {
        /*
         *  
         */
        Stack stack = new Stack();
        if(node != null) {
            stack.push(node);
            while(!stack.empty()) {
                node = stack.pop();
                System.out.print(node.data + " ");
                if (node.rightChild != null) {
                    stack.push(node.rightChild);
                }
                if(node.leftChild != null) {
                    stack.push(node.leftChild);
                }
            }
        }
    }

    public void norecursiveIn(Node node) {
        if (node == null) {
            return;
        }
        Stack stack = new Stack();
        stack.push(node);

        while(!stack.isEmpty()) {
            while(stack.peek() != null) {
                stack.push(stack.peek().leftChild);
            }
            Node p = stack.pop();

            if(!stack.isEmpty()) {
                System.out.print(stack.peek().data + " ");
                p = stack.pop();
                stack.push(p.rightChild);
            }
        }
    }


    public static void main(String[] args) {
        BinTree tree = new BinTree();
        tree.createBinTree();
        Node root = tree.nodelist.get(0);

        tree.preOrderTraverse(root);
        System.out.println();
        tree.norecursivePre(root);
        System.out.println();

        System.out.println();
        tree.inOrderTraverse(root);
        System.out.println();
        tree.norecursiveIn(root);
        System.out.println();

        System.out.println();
        tree.lastOrderTraverse(root);

    }
}

1 2 4 8 9 5 3 6 7 
1 2 4 8 9 5 3 6 7 

8 4 9 2 5 1 6 3 7 
8 4 9 2 5 1 6 3 7 

8 9 4 5 2 6 7 3 1