算法--樹的深度優先周遊兩種方式

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 樹的兩種種深度優先、先序周遊方式
 */
public class TreeIterator {
    public static void main(String[] args) {
        //建構一棵樹
        Node tree = buildTree();
        //1 遞歸周遊
        System.out.println("遞歸周遊開始");
        recursiveDFS(tree);
        System.out.println("遞歸周遊結束\n");
        //2 隊列實作
        System.out.println("堆棧實作開始");
        dequeDFS(tree);
        System.out.println("堆棧實作結束");
    }

    /**
     * 堆棧實作
     * @param root
     */
    private static void dequeDFS(Node root) {
        Deque<Node> stack = new ArrayDeque();
        stack.push(root);
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            System.out.println(pop.getData());
            //這裡為什麼要右邊先進棧，因為先進後出。經典啊
            Node right = pop.getRight();
            if(right != null){
                stack.push(right);
            }
            Node left = pop.getLeft();
            if(left != null){
                stack.push(left);
            }
        }
    }

    /**
     * 遞歸周遊
     * 先序周遊，根在最前 根左右
     * 中序周遊，根在中間 左根右
     * 後序周遊，根在最後 左右根
     * 看下面代碼的位置，真tm經典
     * @param tree
     */
    private static void recursiveDFS(Node tree) {
        System.out.println(tree.getData());//先序周遊
        if(tree.getLeft() != null){
            recursiveDFS(tree.getLeft());
        }
        //System.out.println(tree.getData());//先序周遊
        if(tree.getRight() != null){
            recursiveDFS(tree.getRight());
        }
        //System.out.println(tree.getData());//後序周遊
    }

    /**
     * 建構一顆三層的樹
     *              1
     *         2          3
     *       4   5      6   7
     * @return
     */
    private static Node buildTree() {
        //第一層 1
        Node root = new Node(1);

        Node left = new Node(2);
        Node right = new Node(3);

        Node left_left = new Node(4);
        Node left_right = new Node(5);

        Node right_left = new Node(6);
        Node right_right = new Node(7);
        //第二層 2 3
        root.setLeft(left);
        root.setRight(right);
        //第三層 4 5 6 7
        left.setLeft(left_left);
        left.setRight(left_right);

        right.setLeft(right_left);
        right.setRight(right_right);
        return root;
    }

    /**
     * 樹的節點
     */
    private static class Node{
        Object data;
        Node right;
        Node left;

        public Node() {
        }

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

        public Object getData() {
            return data;
        }

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

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }
    }
}