摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。

聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。

前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷方式實現、求二叉樹的子樹、求節點的父節點、二叉樹高度....），可能是考試中的，也可能是面試中的。

1.二叉樹的定義

二叉樹（Binary Tree）是有限個節點的集合，這個集合可以是空集，也可以是一個根節點和兩顆不相交的子二叉樹組成的集合，其中一顆樹叫根的左子樹，另一顆樹叫右子樹。所以二叉樹是一個遞歸地概念。

值得注意的是二叉樹規定自己可以使空集，而且很明確的區分了一個根節點的兩個子樹分別是左子樹和右子樹，如下圖所示的兩棵樹就不是同一棵樹。

2.兩種特殊的二叉樹

2.1 滿二叉樹（Full Binary Tree）
一棵滿二叉樹就是高度為k，且擁有(2^k)-1個節點的二叉樹，一棵滿二叉樹每個節點，要么都有兩棵子樹，要么都沒有子樹；而且每一層所有的節點之間必須要么都有兩棵子樹，要么都沒子樹。

2.2 完全二叉樹（Complete Binary Tree）
完全二叉樹是一顆特殊的二叉樹，它遵循以下規則：
假設完全二叉樹高度為k，則完全二叉樹需要符合以下兩點：
1）所有葉子節點都出現在k層或k-1層，并且從1~k-1層必須達到最大節點數。
2）第k層可以是不滿的，但是第k層的所有節點必須集中在最左邊。

3.二叉樹的實現

二叉樹的實現要比普通樹容易，因為其每個節點最多只有兩個子節點
其實，二叉樹的每個左右子節點仍是一顆二叉樹，因此，我們可以使用遞歸的方式來定義二叉樹，二叉樹的實現代碼如下

public class BinaryTreeNode {
    
    private int data;  //數據
    private BinaryTreeNode leftChirld;  //左孩子
    private BinaryTreeNode rightChirld; //右孩子
    
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public BinaryTreeNode getLeftChirld() {
        return leftChirld;
    }
    public void setLeftChirld(BinaryTreeNode leftChirld) {
        this.leftChirld = leftChirld;
    }
    public BinaryTreeNode getRightChirld() {
        return rightChirld;
    }
    public void setRightChirld(BinaryTreeNode rightChirld) {
        this.rightChirld = rightChirld;
    }        
}

這種實現方式稱之為二叉樹的左右鏈表表示法，如圖所示

到此為止，二叉樹的節點已經有了，接下來是對二叉樹的操作，比如創建二叉樹、添加元素、清空元素、遍歷二叉樹...
3.1 二叉樹的創建
創建二叉樹，一般有兩種情況：初始化一個根節點或者初始化一棵空二叉樹。代碼如下：

public class BinaryTree {
    private BinaryTreeNode root;
    
    //初始化二叉樹
    public BinaryTree(){}
    
    public BinaryTree(BinaryTreeNode root){
        this.root = root;
    }
    
    public void setRoot(BinaryTreeNode root){
        this.root = root;
    }
    
    public BinaryTreeNode getRoot(){
        return root;
    }
}

3.2 二叉樹的清空
對于二叉樹的清空，首先提供一個清空某個節點為根節點的子樹的方法，即遞歸的刪除每個節點；接著提供刪除一個刪除樹的方法：

    /**
     * 二叉樹的清空：
     * 首先提供一個清空以某個節點為根節點的子樹的方法，既遞歸地刪除每個節點；
     * 接著提供一個刪除樹的方法，直接通過第一種方法刪除到根節點即可
     */
    //清除某個子樹的所有節點
    public void clear(BinaryTreeNode node){
        if(node!=null){
            clear(node.getLeftChirld());
            clear(node.getRightChirld());
            node = null; //刪除節點
        }
    }
    //清空樹
    public void clear(){
        clear(root);
    }

3.3 判斷二叉樹是否為空
只需判斷根節點是否存在即可：

    //判斷二叉樹是否為空
    public boolean isEmpty(){
        return root == null;
    }

3.4 求二叉樹的高度
思路：首先需要一種獲取以某個節點為子樹的高度方法，使用遞歸實現。如果一個節點為空，那么這個節點肯定是一顆空樹，高度為0；如果不為空，則遍歷地比較它的左右子樹高度，高的一個為這顆子樹的最大高度，然后加上自身的高度即可

    /**
     * 求二叉樹的高度：
     * 首先要一種獲取以某個節點為子樹的高度的方法，使用遞歸調用。
     * 如果一個節點為空，那么這個節點肯定是一顆空樹，高度為0；
     * 如果不為空，那么我們要遍歷地比較它的左子樹高度和右子樹高度，
     *     高的一個為這個子樹的最大高度，然后加上自己本身的高度就是了
     * 獲取二叉樹的高度，只需要調用第一種方法，即傳入根節點
     */
    
    //獲取二叉樹的高度
    public int heigh(){
        return heigh(root);
    }
    
    //獲取以某節點為子樹的高度
    public int heigh(BinaryTreeNode node){
        if(node==null){
            return 0; //遞歸結束，空子樹高度為0
        }else{
            //遞歸獲取左子樹高度
            int l = heigh(node.getLeftChirld());
            //遞歸獲取右子樹高度
            int r = heigh(node.getRightChirld());
            //高度應該算更高的一邊，（+1是因為要算上自身這一層）
            return l>r? (l+1):(r+1);
        }
    }

3.5 求二叉樹的節點數
思路：獲取二叉樹節點數，需要獲取以某個節點為根的子樹的節點數實現。
如果節點為空，則個數肯定為0；如果不為空，則算上這個節點之后，繼續遞歸計算所有子樹的節點數，全部相加即可

    /**
    * 獲取二叉樹的節點數
    */
    public int size(){
        return size(root);
    }
    /**
     * 求二叉樹的節點數：
     * 求節點數時，我們看看獲取某個節點為子樹的節點數的實現。
     * 首先節點為空，則個數肯定為0；
     * 如果不為空，那就算上這個節點之后繼續遞歸所有左右子樹的子節點數，
     *    全部相加就是以所給節點為根的子樹的節點數
     * 如果求二叉樹的節點數，則輸入根節點即可
     */
    
    public int size(BinaryTreeNode node){
        if(node==null){
            return 0;  //如果節點為空，則返回節點數為0
        }else{
            //計算本節點 所以要+1
            //遞歸獲取左子樹節點數和右子樹節點數，最終相加
            return 1+size(node.getLeftChirld())+size(node.getRightChirld());
        }
    }

3.6 返回某節點的父親節點
思路：首先，同樣需要通過一種方法來獲取某個節點在某個子樹中的父節點，這里使用遞歸實現，接著通過這種方法獲取這個節點在二叉樹中的父節點
事實上，以現有的這種二叉樹的形式，我們并沒有辦法直接獲取一個節點的父節點， 這里只能通過從根節點遍歷來比較獲取

    //node節點在subTree子樹中的父節點
    public BinaryTreeNode getParent(BinaryTreeNode subTree,BinaryTreeNode node){
        if(subTree==null){
            return null;   //如果是空子樹，則沒有父節點
        }
        if(subTree.getLeftChirld()==node || subTree.getRightChirld() == node){
            return subTree;   //如果子樹的根節點的左右孩子之一是待查節點，則返回子樹的根節點
        }
        BinaryTreeNode parent = null;
        if(getParent(subTree.getLeftChirld(),node)!=null){
            parent = getParent(subTree.getLeftChirld(),node);
            return parent;
        }else{
            //遞歸左右子樹
            return getParent(subTree.getRightChirld(),node);
        }
    }
    
    //查找node節點在二叉樹中的父節點
    public BinaryTreeNode getParent(BinaryTreeNode node){
        return (root==null||root==node)? null:getParent(root,node);
    }

3.7 返回左右子樹
這個操作很簡單，直接用節點的方法來獲取即可

    //獲取某個節點的左子樹
    public BinaryTreeNode getleftTree(BinaryTreeNode node){
        return node.getLeftChirld();
    }
    
    //獲取某個節點的右子樹
    public BinaryTreeNode getrightTree(BinaryTreeNode node){
        return node.getRightChirld();
    }

3.8 二叉樹的插入
二叉樹的插入分析：

 * 分兩種情況：插入某個節點的左子節點；插入某個節點的右子節點
 * 值得指出的是，當這個節點本身有子節點時，這樣的插入也會覆蓋原來在這個位置上的節點。
 * 另外，雖然插入的是子節點，但是子節點也可以代表一顆子樹。
 * 因為但從這個節點來看并不知道這個節點是否有左右子樹存在，所以雖然插入的是一個節點，但有可能
 * 插入可很多節點（插入的是一顆子樹）

    //給某個節點插入左節點
    public void insertLeft(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setLeftChirld(newnode);
    }
    //給某個節點插入右節點
    public void insertRitht(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setRightChirld(newnode);
    }

4、二叉樹的遍歷

二叉樹的遍歷是按照一定的規律來順序遍歷各二叉樹節點，使得每個節點都會被訪問且僅訪問一次。通常二叉樹的遍歷根據根節點的遍歷次序分為：先根遍歷、中根遍歷、后根遍歷。
4.1 先根遍歷(PreOrder)
若二叉樹為空，則退出，否則進行下面操作

訪問根節點

先根遍歷左子樹

先根遍歷右子樹

退出

按照先根遍歷地方式，遍歷如下二叉樹，則訪問順序為：A、B、D、H、I、E、J、C、F、G

    public void PreOrder(BinaryTreeNode node){
        if(node!=null){
            System.out.println(node.getData()); //先訪問根節點
            PreOrder(node.getLeftChirld());  //先根遍歷左子樹
            PreOrder(node.getRightChirld());  //先根遍歷右子樹
        }
    }

4.2 中根遍歷(InOrder)
若二叉樹為空，則退出，否則進行下面操作

中根遍歷左子樹

訪問根節點

中根遍歷右子樹

退出

按照中根遍歷地方式，遍歷如下二叉樹，則訪問順序為：H、D、I、B、J、E、A、F、C、G

    public void InOrder(BinaryTreeNode node){
        if(node!=null){
            InOrder(node.getLeftChirld());  //中根遍歷左子樹
            System.out.println(node);    //訪問根節點
            InOrder(node.getRightChirld());  //中根遍歷右子樹
        }
    }

4.3 后根遍歷(PostOrder)
若二叉樹為空，則退出，否則進行下面操作

后根遍歷左子樹

后根遍歷右子樹

訪問根節點

退出

按照后根遍歷地方式，遍歷如下二叉樹，則訪問順序為：H、I、D、J、E、B、F、G、C、A

    public void PostOrder(BinaryTreeNode node){
        if(node!=null){
            PostOrder(node.getLeftChirld());  //后根遍歷左子樹
            PostOrder(node.getRightChirld());  //后根遍歷右子樹
            System.out.println(node);   //訪問根節點
        }
    }
}

碼字不易，如對您有幫助，歡迎點贊收藏打賞^_^
樹體系文章的索引請點擊二叉樹系列文章