數(shù)據(jù)結(jié)構與算法之二叉樹(一)基本實現(xiàn)

引言

前面提到的順序表和單鏈表對于元素的訪問都有自己的局限性构订,而二叉樹的結(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é)點時:


圖片摘自澤堅博客

刪除操作相對麻煩泣侮,這里花費了很多筆墨說明它即彪,相信大家結(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地址

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市慰毅,隨后出現(xiàn)的幾起案子隘截,更是在濱河造成了極大的恐慌,老刑警劉巖汹胃,帶你破解...
    沈念sama閱讀 211,743評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件婶芭,死亡現(xiàn)場離奇詭異,居然都是意外死亡着饥,警方通過查閱死者的電腦和手機犀农,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,296評論 3 385
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來宰掉,“玉大人呵哨,你說我怎么就攤上這事赁濒。” “怎么了孟害?”我有些...
    開封第一講書人閱讀 157,285評論 0 348
  • 文/不壞的土叔 我叫張陵拒炎,是天一觀的道長。 經(jīng)常有香客問我纹坐,道長枝冀,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,485評論 1 283
  • 正文 為了忘掉前任耘子,我火速辦了婚禮果漾,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘谷誓。我一直安慰自己绒障,他們只是感情好,可當我...
    茶點故事閱讀 65,581評論 6 386
  • 文/花漫 我一把揭開白布捍歪。 她就那樣靜靜地躺著户辱,像睡著了一般。 火紅的嫁衣襯著肌膚如雪糙臼。 梳的紋絲不亂的頭發(fā)上庐镐,一...
    開封第一講書人閱讀 49,821評論 1 290
  • 那天,我揣著相機與錄音变逃,去河邊找鬼必逆。 笑死,一個胖子當著我的面吹牛揽乱,可吹牛的內(nèi)容都是我干的名眉。 我是一名探鬼主播,決...
    沈念sama閱讀 38,960評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼凰棉,長吁一口氣:“原來是場噩夢啊……” “哼损拢!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起撒犀,我...
    開封第一講書人閱讀 37,719評論 0 266
  • 序言:老撾萬榮一對情侶失蹤福压,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后或舞,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體隧膏,經(jīng)...
    沈念sama閱讀 44,186評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,516評論 2 327
  • 正文 我和宋清朗相戀三年嚷那,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片杆煞。...
    茶點故事閱讀 38,650評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡魏宽,死狀恐怖腐泻,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情队询,我是刑警寧澤派桩,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布,位于F島的核電站蚌斩,受9級特大地震影響铆惑,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜送膳,卻給世界環(huán)境...
    茶點故事閱讀 39,936評論 3 313
  • 文/蒙蒙 一员魏、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧叠聋,春花似錦撕阎、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,757評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至厦章,卻和暖如春镇匀,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背袜啃。 一陣腳步聲響...
    開封第一講書人閱讀 31,991評論 1 266
  • 我被黑心中介騙來泰國打工汗侵, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人囊骤。 一個月前我還...
    沈念sama閱讀 46,370評論 2 360
  • 正文 我出身青樓晃择,卻偏偏與公主長得像,于是被迫代替她去往敵國和親也物。 傳聞我的和親對象是個殘疾皇子宫屠,可洞房花燭夜當晚...
    茶點故事閱讀 43,527評論 2 349

推薦閱讀更多精彩內(nèi)容