引言

前面提到的順序表和單鏈表對于元素的訪問都有自己的局限性构订，而二叉樹的結(jié)構兼具完美解決了二者的訪問元素效率問題销部，原因是它的節(jié)點結(jié)構存放了左右兩個子節(jié)點，左邊的元素小于父節(jié)點，右邊的元素大于父節(jié)點薄风，它是的二分法思想運用的典型牢贸。我們訪問節(jié)點竹观，如查找時，都會從根節(jié)點出發(fā)潜索，比較元素確定查找的方向臭增，遍歷的次數(shù)最大為樹的深度，時間復雜度為O(lgN)竹习。相應的誊抛，由于是非線性結(jié)構，它的各種操作的實現(xiàn)也相對復雜許多整陌。由于樹的內(nèi)容確實比較多拗窃，僅僅一篇博文肯定不夠，本篇主要講它的基本實現(xiàn)泌辫，如插入随夸、查找、遍歷震放、包含等操作宾毒，大部分操作采用遍歷和遞歸分別實現(xiàn)。二叉樹的應用相當廣泛澜搅，java的中的集合框架(HashMap伍俘、TreeSet等等)、赫夫曼編碼勉躺、數(shù)據(jù)庫索引等等方面都會用到癌瘾，在數(shù)據(jù)結(jié)構中非常重要，修煉內(nèi)功必備饵溅！希望大家認真研究妨退。

二叉樹的概念

1.定義:二叉樹（Binary Tree）是n(n≥0)個結(jié)點組成的有限集合，n=0時稱為空二叉樹；n>0的二叉樹由一個根結(jié)點和兩棵互不相交咬荷、分別稱為左子樹和右子樹的子二叉樹構成冠句，二叉樹也是遞歸定義的，在樹種定義的度幸乒、層次等術語懦底，同樣適用于二叉樹。
說白了罕扎，它由一個根節(jié)點和若干子節(jié)點構成聚唐，每個一個節(jié)點最多有倆子節(jié)點，邏輯結(jié)構和分叉的樹一樣腔召。
2.相關術語:
1>根節(jié)點:沒有雙親的節(jié)點杆查，也是整個樹的代表;
2>孩子節(jié)點:一個節(jié)點的子樹的根節(jié)點為其孩子節(jié)點;
3>父母節(jié)點:和孩子節(jié)點對應，是孩子節(jié)點的前驅(qū),父母節(jié)點掛載孩子節(jié)點;
4>兄弟節(jié)點:同一父母節(jié)點下的孩子節(jié)點;
5>葉子節(jié)點:沒有孩子節(jié)點的節(jié)點臀蛛，處于樹的最下層;
6>樹的層(高度):反應樹的層次亲桦，約定根的層為1，沒向下遍歷一次則層數(shù)+1浊仆。它的本質(zhì)反應了從根節(jié)點到所有葉子節(jié)點遍歷路徑中最長的路徑長度,可以反應樹的訪問效率客峭。
二叉樹是一個遞歸結(jié)構，它的子樹和自己結(jié)構相同氧卧，大部分操作都可以通過遞歸實現(xiàn)桃笙，遞歸的結(jié)束條件問遍歷到葉子節(jié)點，此時的主要工作就是對最簡單的樹結(jié)構進行處理沙绝。最簡單的樹結(jié)構有五種基本狀態(tài):
1>空樹:根節(jié)點為空;
2>只有根節(jié)點的樹:
3>只有左孩子或者右孩子的樹;
4>有左右孩子的樹。

二叉樹的抽象數(shù)據(jù)結(jié)構描述

1>節(jié)點類:

package tree;

/**
 * Created by chenming on 16/12/30.
 */

public class BinaryNode<T extends Comparable> {
    public BinaryNode<T> left;//左結(jié)點

    public BinaryNode<T> right;//右結(jié)點

    public int mDupCount;//重復的節(jié)點值放到一個節(jié)點,mDupCount=1表示重復次數(shù)為1,兩個相同值

    public T data;

    public BinaryNode(T data,BinaryNode left,BinaryNode right){
        this.data=data;
        this.left=left;
        this.right=right;
    }

    public BinaryNode(T data){
        this(data,null,null);
    }

    /**
     * 判斷是否為葉子結(jié)點
     * @return
     */
    public boolean isLeaf(){
        return this.left==null&&this.right==null;
    }

}

本文采用二叉鏈表存儲結(jié)構鼠锈，它持有左右孩子的節(jié)點引用;持有的元素類型需要實現(xiàn)Comparable接口用于比較闪檬。
2>頂層接口定義:

package tree;

/**
 * Created by chenming on 16/12/30.
 */

public interface Tree<T extends Comparable> {
    /**
     * 判空
     * @return
     */
    boolean isEmpty();

    /**
     * 二叉樹的結(jié)點個數(shù)
     * @return
     */
    int size();

    /**
     * 返回二叉樹的高度或者深度,即結(jié)點的最大層次
     * @return
     */
    int height();

    /**
     * 先根次序遍歷
     */
    String preOrder();

    /**
     * 中根次序遍歷
     */
    String inOrder();

    /**
     * 后根次序遍歷
     */
    String postOrder();

    /**
     * 層次遍歷
     */
    String levelOrder();

    /**
     * 將data 插入
     * @return
     */
    void insert(T data);

    /**
     * 刪除
     */
    void remove(T data);

    /**
     * 查找最大值
     * @return
     */
    T findMin();

    /**
     * 查找最小值
     * @return
     */
    T findMax();

    /**
     * 根據(jù)值找到結(jié)點
     * @param data
     * @return
     */
    BinaryNode findNode(T data);

    /**
     * 是否包含某個值
     * @param data
     * @return
     */
    boolean contains(T data) throws Exception;

    /**
     * 清空
     */
    void clear();
}

3>SearchTree的定義

/**
 * Created by chenming on 2018/6/1
 * 排序二叉樹樹的復習,方法盡量提供循環(huán)和遞歸兩種方式實現(xiàn)
 */
public class SearchTree<T extends Comparable> implements Tree<T> {

    private BinaryNode<T> mRoot;

    public SearchTree() {
        mRoot = null;
    }
......
}

成員變量很簡單，僅僅包含根節(jié)點购笆，所有操作均從它開始粗悯。

二叉樹的插入元素

1>循環(huán)實現(xiàn):比較當前節(jié)點和待插入元素的大小,如果待插入元素大，則向左樹遍歷同欠，否則向右子樹遍歷,直到遍歷到葉子節(jié)點样傍，它的父節(jié)點掛載新節(jié)點。代碼如下:

   /**
     * 循環(huán)插入
     */
    private void insertByTrans(T data) {
        BinaryNode<T> newNode = new BinaryNode<>(data);
        if (mRoot == null) {
            mRoot = newNode;
            return;
        }

        BinaryNode<T> curNode = mRoot;//從根節(jié)點出發(fā)
        BinaryNode<T> parentNode = mRoot;//當前節(jié)點的父節(jié)點
        boolean isLeft = false;//標記插入位置是左還是右
        while (curNode != null) {
            //循環(huán)體：判斷大小
            parentNode = curNode;//保存父節(jié)點
            int compare = data.compareTo(curNode.data);
            if (compare > 0) {//data較大
                //curNode往右走
                isLeft = false;
                curNode = curNode.right;
            } else if (compare < 0) {
                //curNode往左走
                curNode = curNode.left;
                isLeft = true;
            } else {
                curNode.mDupCount++;
            }
        }
        //掛載新節(jié)點
        if (isLeft) {
            parentNode.left = newNode;
        } else {
            parentNode.right = newNode;
        }
    }

2>遞歸插入:每次遞歸做如下操作:比較元素铺遂，判斷大小衫哥，然后向子樹遞歸插入；

 node.left = insertByRecursion(node.left, data);
 or:
 node.right = insertByRecursion(node.right, data);

遞歸結(jié)束條件:node為空襟锐，表示已經(jīng)遍歷到葉子節(jié)點的下一層撤逢，此時返回新建節(jié)點.完整代碼如下:

    /**
     * 遞歸插入元素
     *
     * @param node 子樹節(jié)點
     * @param data 插入數(shù)據(jù)
     */
    private BinaryNode<T> insertByRecursion(BinaryNode<T> node, T data) {
        //遞歸結(jié)束條件 node == null表示已經(jīng)到葉子節(jié)點的下面一層了，掛載新節(jié)點,返回
        if (node == null) {
            node = new BinaryNode<>(data);//連接新節(jié)點返回給上一層鏈接
        } else {//向左右子樹遞歸
            //遞歸比較
            int compare = data.compareTo(node.data);

            if (compare < 0) {//左
                node.left = insertByRecursion(node.left, data);//由于插入操作需要鏈接節(jié)點,所以需要將低層次的node返回給上一層次的rootNode
            } else if (compare > 0) {//右
                node.right = insertByRecursion(node.right, data);
            } else {//相等
                node.mDupCount++;//重復計數(shù)+1
            }
        }
        return node;
    }

二叉樹的查找元素

二叉樹的查找和插入元素的原理基本一樣，不再贅述蚊荣，具體看代碼:

    @Override
    public BinaryNode findNode(T data) {
        return findNodeByTrans(data);
//        return findNodeByRecursion(mRoot, data);
    }

    /**
     * 循環(huán)查找
     *
     * @param data
     * @return
     */
    private BinaryNode findNodeByTrans(T data) {
        if (mRoot == null) {
            return null;
        }
        BinaryNode<T> curNode = mRoot;
        while (curNode != null) {
            int compare = data.compareTo(curNode.data);
            if (compare > 0) {//data較大
                //curNode往右走
                curNode = curNode.right;
            } else if (compare < 0) {
                //curNode往左走
                curNode = curNode.left;
            } else {//相等,則查找到
                return curNode;
            }
        }
        return null;
    }

    /**
     * 遞歸查找元素
     *
     * @param data
     * @return
     */
    private BinaryNode findNodeByRecursion(T data) {
        return findNodeByRecursion(mRoot, data);
    }

    /**
     * 當前子樹節(jié)點
     *
     * @param node
     * @param data
     */
    public BinaryNode findNodeByRecursion(BinaryNode<T> node, T data) {
        //遞歸結(jié)束條件：子樹節(jié)點為空 or node.data = data
        if (node == null) {
            return null;
        }
        int compare = data.compareTo(node.data);
        if (compare == 0) {//找到匹配元素,返回
            return node;
        }

        //否則向左右子樹遞歸
        if (compare > 0) {//右子樹遞歸
            return findNodeByRecursion(node.right, data);
        } else {
            return findNodeByRecursion(node.left, data);
        }
    }

二叉樹的包含判斷

有了查找元素的實現(xiàn)初狰，包含判斷水到渠成:

   /**
     * 是否包含元素
     *
     * @param data
     * @return
     * @throws Exception
     */
    @Override
    public boolean contains(T data) {
//        return containsByRecursion(data, mRoot);
        return containsByTrans(data);
    }

    /***
     * 遞歸判斷是否包含元素
     * @param data
     * @param tree
     * @return
     */
    public boolean containsByRecursion(T data, BinaryNode<T> tree) {
        if (data == null) {
            return false;
        }

        if (tree == null) {//遍歷到葉子節(jié)點的下一層，表示遍歷完畢互例，遞歸結(jié)束
            return false;
        }

        int compareResult = data.compareTo(tree.data);
        if (compareResult == 0) {//相等則返回ture
            return true;
        } else if (compareResult > 0) {
            return containsByRecursion(data, tree.right);//向右子樹遍歷
        } else if (compareResult < 0) {
            return containsByRecursion(data, tree.left);//向右左子樹遍歷
        }
        return false;
    }

    /**
     * 循環(huán)判斷是否包含某個元素
     *
     * @param data
     * @return
     */
    public boolean containsByTrans(T data) {
        BinaryNode<T> p = mRoot;
        while (p != null) {
            int compareResult = data.compareTo(p.data);
            if (compareResult == 0) {
                return true;
            } else if (compareResult > 0) {
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return false;
    }

二叉樹查找最值

循環(huán)和遞歸實現(xiàn)思路和查找元素基本一樣奢入，具體看代碼實現(xiàn):

    @Override
    public T findMin() {
//        return findMinByTrans(mRoot);
        return findMinRecursion(mRoot);
    }

    /**
     * 循環(huán)查找最小值
     *
     * @param root
     * @return
     */
    public T findMinByTrans(BinaryNode<T> root) {
        BinaryNode<T> p = root;
        while (p.left != null) {
            p = p.left;
        }
        return p.data;
    }

    /**
     * 遞歸查找最小值
     *
     * @param root
     * @return
     */
    public T findMinRecursion(BinaryNode<T> root) {
        if (root.left == null) {
            return root.data;
        }

        return findMinRecursion(root.left);
    }

    /**
     * 循環(huán)查找最小值
     *
     * @param root
     * @return
     */
    public T findMaxByTrans(BinaryNode<T> root) {
        BinaryNode<T> p = root;
        while (p.right != null) {
            p = p.right;
        }
        return p.data;
    }

    /**
     * 遞歸查找最小值
     *
     * @param root
     * @return
     */
    public T findMaxRecursion(BinaryNode<T> root) {
        if (root.right == null) {
            return root.data;
        }

        return findMaxRecursion(root.right);
    }


    @Override
    public T findMax() {
        return findMaxRecursion(mRoot);
//        return findMaxByTrans(mRoot);
    }

二叉樹刪除元素

刪除元素相對于增加和查找元素相對復雜些，原因有二:
1)二叉樹是非線性結(jié)構,節(jié)點之間的斷開和連接操作比較復雜;
2)二叉樹的基本結(jié)構有五種媳叨，所以刪除元素考慮的情況比較多腥光。
設要刪除的結(jié)點為q，其父母結(jié)點為p肩杈，刪除節(jié)點的大致思路如下:
① 如果要刪除的結(jié)點q恰好是葉子結(jié)點柴我，那么它可以立即被刪除
② 如果要刪除的結(jié)點q擁有一個孩子結(jié)點，則應該調(diào)整要被刪除的父結(jié)點(p.left 或 p.right)指向被刪除結(jié)點的孩子結(jié)點（q.left 或 q.right）
③如果要刪除的結(jié)點q擁有兩個孩子結(jié)點扩然，則刪除策略是用q的右子樹的最小的節(jié)點(中繼節(jié)點)數(shù)據(jù)替代要被刪除結(jié)點的數(shù)據(jù)艘儒，并遞歸刪除用于中繼節(jié)點(此時該結(jié)點已為空)，或者在右子樹中刪除中繼節(jié)點夫偶，然后將它替換到q的位置界睁，此時二叉查找樹的結(jié)構并不會被打亂，其特性仍舊生效兵拢。采用這樣策略的主要原因是右子樹的最小結(jié)點的數(shù)據(jù)替換要被刪除的結(jié)點后可以滿足維持二叉查找樹的結(jié)構和特性翻斟，又因為右子樹最小結(jié)點不可能有左孩子，刪除起來也相對簡單些说铃。
刪除元素的節(jié)點情況如下圖:

刪除點分析(圖片摘自澤堅博客).png

1>刪除元素遞歸實現(xiàn):

    /**
     * 遞歸刪除元素
     * 1.當找到目標節(jié)點時访惜，分三種情況刪除元素
     * 1>葉子節(jié)點，直接刪除
     * 2>帶一個子節(jié)點,父節(jié)點指向它的子節(jié)點
     * 3>帶倆節(jié)點腻扇，找到右子樹的最小元素(中繼節(jié)點)债热，替換當前節(jié)點,并遞歸刪除右子樹的這個中繼節(jié)點
     *
     * @param data
     * @param p
     * @return
     */
    public BinaryNode<T> removeByRecursion(T data, BinaryNode<T> p) {
        if (p == null) {
            return null;//沒有找到元素,返回空
        }
        int compareResult = data.compareTo(p.data);
        if (compareResult < 0) {//左邊查找刪除結(jié)點
            //左邊相當于父節(jié)點，右邊相當于刪除節(jié)點后的子節(jié)點
            p.left = removeByRecursion(data, p.left);
        } else if (compareResult > 0) {
            p.right = removeByRecursion(data, p.right);
        } else {
            //找到目標節(jié)點幼苛，刪除分三種情況
            if (p.left != null && p.right != null) {
                //情況3 找到中繼節(jié)點,替換元素窒篱，刪除它
                p.data = findMinByTrans(p.right);//找到中繼節(jié)點
                p.right = removeByRecursion(p.data, p.right);//右子樹刪除這個中繼節(jié)點
            } else {//情況1和2，遍歷到最下面了
                p = (p.left != null) ? p.left : p.right;
            }
        }
        return p;//返回刪除后的子樹節(jié)點,用于返回上層遞歸連接父節(jié)點
    }

2>刪除元素的循環(huán)實現(xiàn):
1)先找到目標位置舶沿，并記錄它的父節(jié)點;
2)根據(jù)目標節(jié)點的子節(jié)點掛載情況分前面已經(jīng)分析的三種情況分析墙杯。
代碼如下:

   /**
     * 循環(huán)刪除
     *
     * @param data
     * @return
     */
    public BinaryNode<T> removeByTrans(T data) {
        //找到目標節(jié)點
        if (data == null) {
            return null;
        }

        BinaryNode<T> current = mRoot;
        BinaryNode<T> parent = mRoot;//記錄父節(jié)點
        //判斷左右孩子的flag
        boolean isLeft = true;

        //找到要刪除的結(jié)點
        while (data.compareTo(current.data) != 0) {
            //更新父結(jié)點記錄
            parent = current;
            int result = data.compareTo(current.data);

            if (result < 0) {//從左子樹查找
                isLeft = true;
                current = current.left;
            } else if (result > 0) {//從右子樹查找
                isLeft = false;
                current = current.right;
            }
            //如果沒有找到,返回null
            if (current == null) {
                return null;
            }
        }

        //找到目標位置,判斷它的掛載情況
        //刪除葉子節(jié)點
        if (current.left == null && current.right == null) {
            if (current == mRoot) {
                mRoot = null;
            } else if (isLeft) {
                parent.left = null;
            } else {
                parent.right = null;
            }

        } else if (current.left == null) {//right不為空
            if (current == mRoot) {
                mRoot = current.right;
            } else if (isLeft) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else if (current.right == null) {//left不為空
            if (current == mRoot) {
                mRoot = current.left;
            } else if (isLeft) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else {//帶有倆孩子的節(jié)點(說明1)
            //找右邊子樹的最小節(jié)點（中繼節(jié)點）
            //找到當前要刪除結(jié)點current的右子樹中的最小值元素
            BinaryNode<T> successor = findRelayNode(current);//找到中繼節(jié)點，并且中繼節(jié)點的右邊子樹已經(jīng)指向了要刪除節(jié)點的右子樹
            if (current == mRoot) {
                mRoot = successor;
            } else if (isLeft) {
                parent.left = successor;//左子樹連接中繼節(jié)點
            } else {
                parent.right = successor;//右子樹連接中繼節(jié)點
            }
            //把當前要刪除的結(jié)點的左子樹賦值給successor的左子樹
            successor.left = current.left;

        }
        return current;
    }

    /**
     * 查找中繼節(jié)點
     *
     * @param delNode 要刪除的節(jié)點
     * @return
     */
    private BinaryNode<T> findRelayNode(BinaryNode<T> delNode) {
        BinaryNode<T> relayNode = delNode;//最小節(jié)點
        BinaryNode<T> relayParentNode = delNode;//父節(jié)點
        BinaryNode<T> curNode = delNode.right;//臨時遍歷變量
        while (curNode != null) {
            relayParentNode = relayNode;//保存父節(jié)點
            relayNode = curNode;
            curNode = curNode.left;
        }

        if (relayNode != delNode.right) {
            //如果relayNode不是刪除節(jié)點的直接子節(jié)點括荡，relayNode就是要替換delNode的節(jié)點,
            // 第一步先處理好它的斷開操作:relayNode是最小節(jié)點高镐，所以它必然在父節(jié)點的左邊，且沒有左子節(jié)點
            // 所以relayParentNode的左子樹指向relayNode的右子樹,即可完成relayNode的斷開操作
            // 斷開操作之后,relayNode需要替代delNode,需要把delNode的右邊子樹賦給relayNode.right
            relayParentNode.left = relayNode.right;
            //這種情況下relayNode和delNode至少隔了一層一汽，所以需要將delNode的右邊子樹賦值給relayNode的右子樹避消，
            relayNode.right = delNode.right;
        }//relayNode == delNode.right時候低滩，說明delNode和relayNode是直接的父子關系，不用額外操作
        return relayNode;
    }

前面兩種情況很容易實現(xiàn)岩喷，比較麻煩的是第三種情況恕沫。下面是關鍵代碼的說明:
說明1:findRelayNode方法是找到當前要刪除節(jié)點右子樹下面的最小節(jié)點作為中繼節(jié)點，用來替換目標節(jié)點(見代碼)纱意，將中繼節(jié)點掛載到目標節(jié)點的父節(jié)點上婶溯，然后將目標節(jié)點的左子樹掛在到中繼節(jié)點下，因為中繼節(jié)點是是從右子樹得到的偷霉，所以右子樹結(jié)構不變迄委，只要將目標節(jié)點的左子樹掛載到中繼節(jié)點即可實現(xiàn)節(jié)點替換;
說明2: 說明1中的代碼處理好了目標節(jié)點的替換，findRelayNode方法除了尋找中繼節(jié)點意外类少，還做了下面幾個工作:
① 當中繼節(jié)點是目標節(jié)點的直接子節(jié)點時(relayNode == delNode.right)直接返回叙身，因為這種情況下說明1中的處理足夠完成替換操作,不用額外處理;
②當relayNode!=delNode.right表明中繼節(jié)點與目標節(jié)點隔了若干層，這就需要調(diào)整數(shù)的結(jié)構了:首先處理好中繼節(jié)點和父節(jié)點的斷開操作:relayNode是最小節(jié)點，它必然在父節(jié)點的左邊,且沒有左子節(jié)點,因此relayNode的右子樹掛載到relayParentNode的左子樹上,即可完成relayNode的斷開操作;斷開操作后，這些老數(shù)據(jù)已經(jīng)掛載到它父節(jié)點的左子樹上了佛纫，要實現(xiàn)目標節(jié)點的替換，需要把目標節(jié)點的右子樹掛載到中繼節(jié)點的右子樹上财忽。說的很復雜，看圖就一目了然了(圖中的successor為中繼節(jié)點):

刪除節(jié)點示意圖(摘自澤堅博客).png

當中繼節(jié)點是目標節(jié)點的直接子節(jié)點時:

圖片摘自澤堅博客

二叉樹的遍歷

根據(jù)節(jié)點的訪問順序,二叉樹有四種遍歷方式
1.前序遍歷:先訪問根節(jié)點活尊，再遍歷左右子樹;
2.中序遍歷:先遍歷左子樹隶校，再訪問根節(jié)點，再遍歷右子樹;
3.后序遍歷:先遍歷左右子樹,再訪問根節(jié)點;
4.層序遍歷:按層從左向右訪問.

前序遍歷

1>遞歸實現(xiàn):

    /**
     * 遞歸前序遍歷：先訪問根節(jié)點蛹锰，在訪問左右子樹
     *
     * @param root
     * @return
     */
    private String preOrderByRecursion(BinaryNode<T> root) {
        StringBuilder sb = new StringBuilder();
        if (root != null) {//遞歸結(jié)束條件
            sb.append(root.data + ", ");//先訪問根節(jié)點
            sb.append(preOrderByRecursion(root.left));
            sb.append(preOrderByRecursion(root.right));
        }
        return sb.toString();
    }

2>循環(huán)實現(xiàn):引入棧惠况，保存訪問的根節(jié)點p，直到最左邊的葉子節(jié)點宁仔，此時表明一條路徑走到盡頭，彈出棧頂元素峦睡，向右子樹遍歷翎苫，繼續(xù)循環(huán);代碼如下:

    /**
     * 利用棧實現(xiàn)前序遍歷,利用棧保存已經(jīng)訪問的節(jié)點，實現(xiàn)思想如下：
     * 1.當前節(jié)點p不為空時,訪問節(jié)點榨了，并保存入棧
     * 2.p節(jié)點向左遍歷,執(zhí)行1的操作,直到p為空
     * 3.p為空時煎谍，表示一條完整的路徑已經(jīng)遍歷完,棧頂存放的是上一個節(jié)點即當前的父節(jié)點,彈出這個父節(jié)點，向它的右子樹遍歷,執(zhí)行
     * p=stack.pop,p = p.right,然后重復1.2.3操作龙屉。
     * 當p==null && 棧為空時表示遍歷完呐粘，退出循環(huán)
     *
     * @return
     */
    private String preOrderByTrans() {
        Stack<BinaryNode<T>> historyNodeStack = new Stack<>();
        BinaryNode<T> p = mRoot;
        StringBuilder result = new StringBuilder();
        while (p != null || !historyNodeStack.isEmpty()) {
            if (p == null) {//一條完整路徑走到盡頭,向父節(jié)點的右子樹遍歷
                p = historyNodeStack.pop();//彈出當前的父節(jié)點
                p = p.right;
            } else {
                //訪問節(jié)點,保存路徑,向左邊遍歷直到p=null
                result.append(p.data + ",");
                historyNodeStack.push(p);
                p = p.left;
            }
        }
        return result.toString();
    }

中序遍歷

1>遞歸實現(xiàn):

 /**
     * 遞歸中序遍歷
     *
     * @return
     */
    public String inOrderByRecursion(BinaryNode root) {
        StringBuilder sb = new StringBuilder();
        if (root != null) {//遞歸結(jié)束條件
            sb.append(inOrderByRecursion(root.left));//先訪問左子樹
            sb.append(root.data + ", ");//訪問根節(jié)點
            sb.append(inOrderByRecursion(root.right));//最后訪問右子樹
        }
        return sb.toString();
    }

2>循環(huán)實現(xiàn)：引入棧存放歷史節(jié)點满俗，思路和前序遍歷基本一致

   /**
     * 循環(huán)中序遍歷,和前序引入棧存放經(jīng)過的路徑,這些路徑?jīng)]有被訪問，當向左的路徑走到盡頭作岖，彈棧訪問節(jié)點唆垃，并向右遍歷，
     * 如果p不為空痘儡，則存入stack辕万，向左邊遍歷
     *
     * @return
     */
    public String inOrderByTrans(BinaryNode root) {
        Stack<BinaryNode<T>> historyNodeStack = new Stack<>();
        BinaryNode<T> p = mRoot;
        StringBuilder result = new StringBuilder();
        while (p != null || !historyNodeStack.isEmpty()) {
            if (p == null) {//一條完整路徑走到盡頭,彈棧，并訪問它
                p = historyNodeStack.pop();
                result.append(p.data + ",");
                p = p.right;
            } else {
                //向左邊遍歷直到p=null
                historyNodeStack.push(p);
                p = p.left;
            }
        }
        return result.toString();
    }

3>后序遍歷:注意彈棧的條件是棧頂節(jié)點的右子樹為空或者被訪問過沉删，表明它的右子樹已經(jīng)訪問完畢渐尿，可以彈棧訪問棧頂節(jié)點.

   /**
     * 循環(huán)實現(xiàn)后序遍歷
     *
     * @return
     */
    public String postOrderByTrans() {
        Stack<BinaryNode<T>> stack = new Stack<>();
        BinaryNode<T> currentNode = mRoot;
        BinaryNode<T> prev = mRoot;
        StringBuilder result = new StringBuilder();
        while (currentNode != null || !stack.isEmpty()) {
            //把左子樹加入棧中,直到葉子結(jié)點為止,這是左子樹先遍歷的前提
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }

            if (!stack.isEmpty()) {//當前的棧頂節(jié)點未訪問，先看看它的右節(jié)點是否被訪問過或者是否為空矾瑰，如果是則表示右子樹遍歷完砖茸，可以彈出訪問
                BinaryNode<T> rightNode = stack.peek().right;
                if (rightNode == null || rightNode == prev) {//右子樹訪問完畢，才彈出父節(jié)點
                    currentNode = stack.pop();//彈出父節(jié)點訪問
                    result.append(currentNode.data + ",");
                    prev = currentNode;
                    currentNode = null;//curnode=null殴穴，避免上面的while重復循環(huán)
                } else {
                    currentNode = rightNode;//向右遍歷
                }

            }
        }
        return result.toString();
    }

3>層序遍歷:由于層序遍歷按層遍歷凉夯，也就是說左右兄弟節(jié)點按層順序輸出，由于兄弟節(jié)點以及上下層的的首尾沒有直接關系推正，這里無法用遞歸實現(xiàn)恍涂，需要引入隊列保存兄弟節(jié)點，每遇到一個節(jié)點植榕，就將它的子節(jié)點入隊再沧，這樣就保證兄弟節(jié)點按層順序輸出.

    /**
     * 程序遍歷:二叉樹的兄弟節(jié)點沒有直接聯(lián)系，無法用遞歸實現(xiàn),引入隊列
     *
     * @return
     */
    @Override
    public String levelOrder() {
        Queue<BinaryNode<T>> queue = new Queue<>();
        StringBuilder result = new StringBuilder();
        BinaryNode<T> p = mRoot;
        while (p != null) {
            result.append(p.data + ",");
            //左右子節(jié)點入隊
            if (p.left != null) {
                queue.enquene(p.left);
            }
            //左右子節(jié)點入隊
            if (p.right != null) {
                queue.enquene(p.right);
            }
            p = queue.dequeue();
        }
        return result.toString();
    }

好了尊残，以上就是二叉樹的基本實現(xiàn)炒瘸，內(nèi)容比較多，然而不僅限于此寝衫，后面還有赫夫曼樹以及平衡二叉樹等內(nèi)容需要另開篇幅研究顷扩。
完整代碼地址:數(shù)據(jù)結(jié)構與算法學習JAVA描述GayHub地址