【面試題】Java周遊二叉樹

先序周遊：先查找父節點，然後是左節點，最後是右節點，“父左右”或“根左右”；

中序周遊：先查找左節點，然後是父節點，最後是右節點，“左父右”或“左根右”；

後序周遊：先查找左子樹，然後是右節點，最後是父節點，“左右父”或“左右根”；

先建立一個節點數，命名為NodeTree.java，代碼如下：

public class NodeTree {

    private String data;
    private NodeTree leftNodeTree;
    private NodeTree rightNodeTree;

    public NodeTree(String data, NodeTree leftNodeTree, NodeTree rightNodeTree) {
        this.data = data;
        this.leftNodeTree = leftNodeTree;
        this.rightNodeTree = rightNodeTree;
    }

    public String getData() {
        return data;
    }

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

    public NodeTree getLeftNodeTree() {
        return leftNodeTree;
    }

    public void setLeftNodeTree(NodeTree leftNodeTree) {
        this.leftNodeTree = leftNodeTree;
    }

    public NodeTree getRightNodeTree() {
        return rightNodeTree;
    }

    public void setRightNode() {
        this.rightNodeTree = rightNodeTree;
    }
}
           

再建立一個Java檔案BinaryTree.java，代碼如下：

public class BinaryTree {

    //建立一個二叉樹節點，從子節點建立起來，再往上建立父節點，因為非葉子節點需要用到下面的節點
    public NodeTree init() {
        NodeTree J = new NodeTree("J", null, null);
        NodeTree I = new NodeTree("I", null, null);
        NodeTree H = new NodeTree("H", null, null);
        NodeTree G = new NodeTree("G", null, null);
        NodeTree F = new NodeTree("F", I, J);
        NodeTree E = new NodeTree("E", H, null);
        NodeTree D = new NodeTree("D", null, G);
        NodeTree C = new NodeTree("C", F, null);
        NodeTree B = new NodeTree("B", D, E);
        NodeTree A = new NodeTree("A", B, C);
        //傳回根節點
        return A;
    }

    //先序周遊，先查找父節點，然後是左節點，最後是右節點
    public void preTraversal(NodeTree nodeTree) {
        System.out.print(nodeTree.getData());
        if (nodeTree.getLeftNodeTree() != null) {
            System.out.print("->");
            preTraversal(nodeTree.getLeftNodeTree());
        }

        if (nodeTree.getRightNodeTree() != null) {
            System.out.print("->");
            preTraversal(nodeTree.getRightNodeTree());
        }
    }

    //中序周遊，先查找左節點，然後是父節點，最後是右節點
    public void inTraversal(NodeTree nodeTree) {
        if (nodeTree.getLeftNodeTree() != null) {
            inTraversal(nodeTree.getLeftNodeTree());
            System.out.print("->");
        }
        System.out.print(nodeTree.getData());
        if (nodeTree.getRightNodeTree() != null) {
            System.out.print("->");
            inTraversal(nodeTree.getRightNodeTree());
        }
    }

    //後序周遊，先查找左子樹，然後是右節點，最後是父節點
    public void postTraversal(NodeTree nodeTree) {
        if (nodeTree.getLeftNodeTree() != null) {
            postTraversal(nodeTree.getLeftNodeTree());
            System.out.print("->");
        }

        if(nodeTree.getRightNodeTree() != null) {
            postTraversal(nodeTree.getRightNodeTree());
            System.out.print("->");
        }

        System.out.print(nodeTree.getData());
    }

    /*
    * 1.如果一個樹隻有根節點，那麼傳回樹深度是1
    * 2.如果根節點隻有左節點而沒有右節點，那麼傳回樹的深度是左子樹的深度+1
    * 3.如果根節點隻有右節點而沒有左節點，那麼傳回樹的深度是右子樹的深度+1
    * 4.如果根節點既有左節點，又有右節點，那麼傳回樹的深度是左、右子樹的較大值+1
    */
    public int getTreeDepth(NodeTree nodeTree) {

        if (nodeTree.getLeftNodeTree() == null && nodeTree.getRightNodeTree() == null) {
            return 1;
        }

        int leftDepth = 0, rightDepth = 0;
        if (nodeTree.getLeftNodeTree() != null) {
            leftDepth = getTreeDepth(nodeTree.getLeftNodeTree());
        }

        if (nodeTree.getRightNodeTree() != null) {
            rightDepth = getTreeDepth(nodeTree.getRightNodeTree());
        }

        return leftDepth > rightDepth ? leftDepth+1: rightDepth+1;
    }
    
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        NodeTree nodeTree = tree.init();

        System.out.print("先序周遊：");
        tree.preTraversal(nodeTree);

        System.out.println();
        System.out.print("中序周遊：");
        tree.inTraversal(nodeTree);

        System.out.println();
        System.out.print("後序周遊：");
        tree.postTraversal(nodeTree);

        System.out.println();
        System.out.print("樹的高度為：");
        System.out.println(tree.getTreeDepth(nodeTree));
    }
}
           

運作結果：

先序周遊：A->B->D->G->E->H->C->F->I->J
中序周遊：D->G->B->H->E->A->I->F->J->C
後序周遊：G->D->H->E->B->I->J->F->C->A
樹的高度為：4