樹，二叉樹，前中後序周遊-java

樹示意圖

樹的常用術語(結合示意圖了解):

結點 ： 結點是資料結構中的基礎，是構成複雜資料結構的基本組成機關。

根結點 ：沒有父節點的結點稱為根節點

父結點 ： ：若一個結點含有子結點，則這個結點稱為其子結點的父結點；

子結點 ：

葉子結點 ：沒有子結點的結點

結點 的權(節點值)

結點的度： 一個結點含有的子結點的個數稱為該結點的度

路徑(從root節點找到該結點 的路線)

層 ： 根結點的層次為1，其餘結點的層次等于該結點的雙親結點的層次加1

樹的高度(最大層數) ： 樹中結點的最大層次

森林 :多顆子樹構成森林

二叉樹

定義： 每個結點至多擁有兩棵子樹(即二叉樹中不存在度大于2的結點)，并且，二叉樹的子樹有左右之分，其次序不能任意颠倒。

二叉樹的性質

性質1：二叉樹第i層上的結點數目最多為2i-1(i>=1)

性質2：深度為k的二叉樹至多有2k-1個結點（k>=1）

性質3：包含n個結點的二叉樹的高度至少為(log2n)+1

性質4：在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1

滿二叉樹

定義：高度為h，并且由2h-1個結點組成的二叉樹，稱為滿二叉樹

完全二叉樹

完全二叉樹從根結點到倒數第二層滿足完美二叉樹，最後一層可以不完全填充，其葉子結點都靠左對齊。

二叉樹的周遊

前序周遊: 先輸出父節點，再周遊左子樹和右子樹

這棵樹的前序周遊為：ABDEGHCF

中序周遊: 先周遊左子樹，再輸出父節點，再周遊右子樹

這棵樹的中序周遊為：DBGEHACF

後序周遊: 先周遊左子樹，再周遊右子樹，最後輸出父節點

這棵樹的後序周遊為：DGHEBFCA

小結: 看輸出父節點的順序，就确定是前序，中序還是後序

層次周遊：按層次周遊

這棵樹的層次周遊為：ABCDEFGH

利用遞歸實作周遊

以圖中為例

package tree;

/**
 * @author: xingt   [email protected]
 * @date: 2019/11/2, 19:32
 * @version: 1.0
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //建立一顆二叉樹
        BinaryTree binaryTree = new BinaryTree();
        //建立節點
        Node root = new Node(1,"a");
        Node node2 = new Node(2,"b");
        Node node3 = new Node(3,"c");
        Node node4 = new Node(4,"d");
        Node node5 = new Node(5,"e");
        Node node6 = new Node(6,"f");
        //設定節點
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node4);
        node3.setRight(node5);
        node4.setLeft(node6);

        binaryTree.setRoot(root);

        System.out.println("前序周遊");
        binaryTree.preOrder();

        System.out.println("中序周遊");
        binaryTree.infixOrder();

        System.out.println("後序周遊");
        binaryTree.postOrder();

    }





}

class BinaryTree{
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    //前序周遊
    public void preOrder(){
        if(this.root !=null){
            this.root.preOrder();
        }else{
            System.out.printf("二叉樹為空，無法周遊");
        }
    }

    //前序周遊
    public void infixOrder(){
        if(this.root !=null){
            this.root.infixOrder();
        }else{
            System.out.printf("二叉樹為空，無法周遊");
        }
    }

    //前序周遊
    public void postOrder(){
        if(this.root !=null){
            this.root.postOrder();
        }else{
            System.out.printf("二叉樹為空，無法周遊");
        }
    }
}


class Node{
    private int no;
    private String name;
    private Node left;
    private Node right;
    public Node(int no, String name){
        //super();
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序周遊
    public void preOrder(){
        //先輸出父節點
        System.out.println(this);
        //遞歸向左子樹前序周遊
        if(this.left != null){
            this.left.preOrder();
        }
        //遞歸向右子樹前序周遊
        if(this.right != null){
            this.right.preOrder();
        }

    }
    //中序周遊
    public void infixOrder(){
        //遞歸向左子樹周遊
        if(this.left != null){
            this.left.infixOrder();
        }
        //輸出父節點
        System.out.println(this);
        //遞歸向右子樹周遊
        if(this.right != null){
            this.right.infixOrder();
        }
    }


    //後續周遊
    public void postOrder(){
        //遞歸向左子樹周遊
        if(this.left != null){
            this.left.postOrder();
        }
        //遞歸向右子樹周遊
        if(this.right != null){
            this.right.postOrder();
        }
        //輸出父節點
        System.out.println(this);
    }
}

//輸出結果
前序周遊
Node{no=1, name='a'}
Node{no=2, name='b'}
Node{no=3, name='c'}
Node{no=4, name='d'}
Node{no=6, name='f'}
Node{no=5, name='e'}
中序周遊
Node{no=2, name='b'}
Node{no=1, name='a'}
Node{no=6, name='f'}
Node{no=4, name='d'}
Node{no=3, name='c'}
Node{no=5, name='e'}
後序周遊
Node{no=2, name='b'}
Node{no=6, name='f'}
Node{no=4, name='d'}
Node{no=5, name='e'}
Node{no=3, name='c'}
Node{no=1, name='a'}