二叉樹周遊——Java代碼實作

二叉樹周遊——Java的代碼實作

• 二叉樹
• 二叉樹的周遊
• 代碼實作
• • 首先建立一個結點類
  • 其次是進行周遊操作的BinaryTree類
  • • 遞歸實作二叉樹周遊方法詳述（以中序周遊為例）
  • 主函數
  • 輸出結果

二叉樹

二叉樹是樹的一種，每個結點最多可具有兩個子樹，即結點的度最大為2。

二叉樹的周遊

先序周遊：先通路根節點，然後通路左節點，最後通路右節點。

【1->2->4->8->9->5->10->3->6->7】

中序周遊：先通路左節點，然後通路根節點，最後通路右節點。

【8->4->9->2->10->5->1->6->3->7】

後序周遊：先通路左節點，然後通路右節點，最後通路根節點。

【8->9->4->10->5->2->6->7->3->1】

代碼實作

首先建立一個結點類

這個結點包括，一個根結點，一個根所對應的左結點，一個根所對應的右節點。

public class Node {
    Object data;
    Node left = null;
    Node right = null;
    void Node(Object data,Node left,Node right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
           

其次是進行周遊操作的BinaryTree類

用遞歸的方法實作周遊

public class BinaryTree {
    // 先序周遊
    void preSearch(Node root){
        if (root != null){
            System.out.printf("%-4s",root.data);
            preSearch(root.left);
            preSearch(root.right);
        }
    }
    // 中序周遊
    void midSearch(Node root){
        if (root != null){
            midSearch(root.left);
            System.out.printf("%-4s",root.data);
            midSearch(root.right);
        }
    }
    // 後序周遊
    void bacSearch(Node root){
        if (root != null){
            bacSearch(root.left);
            bacSearch(root.right);
            System.out.printf("%-4s",root.data);
        }
    }
}
           

遞歸實作二叉樹周遊方法詳述（以中序周遊為例）

主函數

public class E1 {
    public static void main(String[] args) {
        //構造一個二叉樹
        Node node10 = new Node();
        node10.Node("10",null,null);
        Node node9 = new Node();
        node9.Node("9",null,null);
        Node node8 = new Node();
        node8.Node("8",null,null);
        Node node7 = new Node();
        node7.Node("7",null,null);
        Node node6 = new Node();
        node6.Node("6",null,null);
        Node node5 = new Node();
        node5.Node("5",node10,null);
        Node node4 = new Node();
        node4.Node("4",node8,node9);
        Node node3 = new Node();
        node3.Node("3",node6,node7);
        Node node2 = new Node();
        node2.Node("2",node4,node5);
        Node node1 = new Node();
        node1.Node("1",node2,node3);
        BinaryTree b = new BinaryTree();
        //對所構造的二叉樹周遊輸出
        System.out.println("前序周遊輸出：");
        b.preSearch(node1);
        System.out.println();
        System.out.println("中序周遊輸出：");
        b.midSearch(node1);
        System.out.println();
        System.out.println("後序周遊輸出：");
        b.bacSearch(node1);
    }
}
           

輸出結果