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

聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷方式實(shí)現(xiàn)、求二叉樹的子樹、求節(jié)點(diǎn)的父節(jié)點(diǎn)、二叉樹高度....），可能是考試中的，也可能是面試中的。

1.二叉樹的定義

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

值得注意的是二叉樹規(guī)定自己可以使空集，而且很明確的區(qū)分了一個(gè)根節(jié)點(diǎn)的兩個(gè)子樹分別是左子樹和右子樹，如下圖所示的兩棵樹就不是同一棵樹。

2.兩種特殊的二叉樹

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

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

3.二叉樹的實(shí)現(xiàn)

二叉樹的實(shí)現(xiàn)要比普通樹容易，因?yàn)槠涿總€(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)
其實(shí)，二叉樹的每個(gè)左右子節(jié)點(diǎn)仍是一顆二叉樹，因此，我們可以使用遞歸的方式來(lái)定義二叉樹，二叉樹的實(shí)現(xiàn)代碼如下

public class BinaryTreeNode {
    
    private int data;  //數(shù)據(jù)
    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;
    }        
}

這種實(shí)現(xiàn)方式稱之為二叉樹的左右鏈表表示法，如圖所示

到此為止，二叉樹的節(jié)點(diǎn)已經(jīng)有了，接下來(lái)是對(duì)二叉樹的操作，比如創(chuàng)建二叉樹、添加元素、清空元素、遍歷二叉樹...
3.1 二叉樹的創(chuàng)建
創(chuàng)建二叉樹，一般有兩種情況：初始化一個(gè)根節(jié)點(diǎn)或者初始化一棵空二叉樹。代碼如下：

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 二叉樹的清空
對(duì)于二叉樹的清空，首先提供一個(gè)清空某個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹的方法，即遞歸的刪除每個(gè)節(jié)點(diǎn)；接著提供刪除一個(gè)刪除樹的方法：

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

3.3 判斷二叉樹是否為空
只需判斷根節(jié)點(diǎn)是否存在即可：

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

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

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

3.5 求二叉樹的節(jié)點(diǎn)數(shù)
思路：獲取二叉樹節(jié)點(diǎn)數(shù)，需要獲取以某個(gè)節(jié)點(diǎn)為根的子樹的節(jié)點(diǎn)數(shù)實(shí)現(xiàn)。
如果節(jié)點(diǎn)為空，則個(gè)數(shù)肯定為0；如果不為空，則算上這個(gè)節(jié)點(diǎn)之后，繼續(xù)遞歸計(jì)算所有子樹的節(jié)點(diǎn)數(shù)，全部相加即可

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

3.6 返回某節(jié)點(diǎn)的父親節(jié)點(diǎn)
思路：首先，同樣需要通過(guò)一種方法來(lái)獲取某個(gè)節(jié)點(diǎn)在某個(gè)子樹中的父節(jié)點(diǎn)，這里使用遞歸實(shí)現(xiàn)，接著通過(guò)這種方法獲取這個(gè)節(jié)點(diǎn)在二叉樹中的父節(jié)點(diǎn)
事實(shí)上，以現(xiàn)有的這種二叉樹的形式，我們并沒有辦法直接獲取一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)， 這里只能通過(guò)從根節(jié)點(diǎn)遍歷來(lái)比較獲取

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

3.7 返回左右子樹
這個(gè)操作很簡(jiǎn)單，直接用節(jié)點(diǎn)的方法來(lái)獲取即可

    //獲取某個(gè)節(jié)點(diǎn)的左子樹
    public BinaryTreeNode getleftTree(BinaryTreeNode node){
        return node.getLeftChirld();
    }
    
    //獲取某個(gè)節(jié)點(diǎn)的右子樹
    public BinaryTreeNode getrightTree(BinaryTreeNode node){
        return node.getRightChirld();
    }

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

 * 分兩種情況：插入某個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)；插入某個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)
 * 值得指出的是，當(dāng)這個(gè)節(jié)點(diǎn)本身有子節(jié)點(diǎn)時(shí)，這樣的插入也會(huì)覆蓋原來(lái)在這個(gè)位置上的節(jié)點(diǎn)。
 * 另外，雖然插入的是子節(jié)點(diǎn)，但是子節(jié)點(diǎn)也可以代表一顆子樹。
 * 因?yàn)榈珡倪@個(gè)節(jié)點(diǎn)來(lái)看并不知道這個(gè)節(jié)點(diǎn)是否有左右子樹存在，所以雖然插入的是一個(gè)節(jié)點(diǎn)，但有可能
 * 插入可很多節(jié)點(diǎn)（插入的是一顆子樹）

    //給某個(gè)節(jié)點(diǎn)插入左節(jié)點(diǎn)
    public void insertLeft(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setLeftChirld(newnode);
    }
    //給某個(gè)節(jié)點(diǎn)插入右節(jié)點(diǎn)
    public void insertRitht(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setRightChirld(newnode);
    }

4、二叉樹的遍歷

二叉樹的遍歷是按照一定的規(guī)律來(lái)順序遍歷各二叉樹節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)都會(huì)被訪問(wèn)且僅訪問(wèn)一次。通常二叉樹的遍歷根據(jù)根節(jié)點(diǎn)的遍歷次序分為：先根遍歷、中根遍歷、后根遍歷。
4.1 先根遍歷(PreOrder)
若二叉樹為空，則退出，否則進(jìn)行下面操作

訪問(wèn)根節(jié)點(diǎn)

先根遍歷左子樹

先根遍歷右子樹

退出

按照先根遍歷地方式，遍歷如下二叉樹，則訪問(wèn)順序?yàn)椋篈、B、D、H、I、E、J、C、F、G

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

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

中根遍歷左子樹

訪問(wèn)根節(jié)點(diǎn)

中根遍歷右子樹

退出

按照中根遍歷地方式，遍歷如下二叉樹，則訪問(wèn)順序?yàn)椋篐、D、I、B、J、E、A、F、C、G

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

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

后根遍歷左子樹

后根遍歷右子樹

訪問(wèn)根節(jié)點(diǎn)

退出

按照后根遍歷地方式，遍歷如下二叉樹，則訪問(wèn)順序?yàn)椋篐、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);   //訪問(wèn)根節(jié)點(diǎn)
        }
    }
}

碼字不易，如對(duì)您有幫助，歡迎點(diǎn)贊收藏打賞^_^
樹體系文章的索引請(qǐng)點(diǎn)擊二叉樹系列文章