【資料結構】樹的周遊

                                                     樹的周遊

以前序周遊為例

（1）先周遊樹根

（2）然後前序周遊左子樹

（3）最後前序周遊右子樹

對于這樣的一個二叉樹

前序周遊結果：ABDEGCF

周遊流程：

【1】首先周遊樹根，輸出A

【2】對A的左子樹進行前序周遊，怎麼前序周遊？對于B這個左子樹而言，首先周遊根節點，輸出B

【3】然後周遊子樹B的左子樹，得到D這個子樹，對D進行前序周遊，首先周遊樹根節點，輸出D

【4】然後周遊D的左子樹，不存在。那就周遊D的右子樹，不存在。此時B的左子樹D周遊完成

【5】周遊B的右子樹E，則前序周遊E，首先周遊樹根結點，輸出E

【6】周遊E的左子樹，得到子樹G，對于子樹G，前序周遊G，得到樹根節點G，輸出G，此時G周遊完成

【7】此時A的左子樹周遊完成，現在開始周遊A的右子樹C，前序周遊C，得到樹根結點，輸出C

【8】周遊C的左子樹，不存在，則周遊其右子樹，得到子樹F，前序周遊F，得到樹根結點F，輸出F

同理，中序周遊結果：DBGEACF

           後序周遊結果：DGEBFCA

樹的周遊  代碼示範

節點類

public class TreeNode {
    private final char value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public char getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

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

    public TreeNode getRight() {
        return right;
    }

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

人肉構造一棵樹，也就是圖中的那棵樹

public class TreeCreator {
    public TreeNode createTree() {
        TreeNode root = new TreeNode('A');
        root.setLeft(new TreeNode('B'));
        root.setRight(new TreeNode('C'));
        root.getLeft().setLeft(new TreeNode('D'));
        root.getLeft().setRight(new TreeNode('E'));
        root.getLeft().getRight().setLeft(new TreeNode('G'));
        root.getRight().setRight(new TreeNode('F'));
        return root;
    }
}      

前序周遊、中序周遊、後序周遊代碼

public class Main {
    //前序周遊
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getValue());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

    //中序周遊
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.getLeft());
        System.out.print(root.getValue());
        inOrder(root.getRight());

    }

    //後序周遊
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue());
    }


    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        Main main = new Main();
        System.out.print("前序周遊:");
        main.preOrder(creator.createTree());
        System.out.println();
        System.out.print("中序周遊:");
        main.inOrder(creator.createTree());
        System.out.println();
        System.out.print("後序周遊:");
        main.postOrder(creator.createTree());
    }
}