使用Java實現(xiàn)二叉樹的添加，刪除，獲取以及遍歷

一段來自百度百科的對二叉樹的解釋：

在計算機科學(xué)中，二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。

一棵深度為k，且有2^k-1個節(jié)點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節(jié)點數(shù)都是最大節(jié)點數(shù)。而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點，則此二叉樹為完全二叉樹。具有n個節(jié)點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子節(jié)點，至多有2k-1個節(jié)點。

二叉樹的結(jié)構(gòu)：

image

二叉樹節(jié)點的聲明：

  static final class Entry<T extends Comparable<T>>{ //保存的數(shù)據(jù)
        private T item; //左子樹
        private Entry<T> left; //右子樹
        private Entry<T> right; //父節(jié)點
        private Entry<T> parent;
        Entry(T item,Entry<T> parent){ this.item = item; this.parent = parent;
        }
    }

類屬性：

    //根節(jié)點
    private Entry<T> root; 
    //數(shù)據(jù)量
    private int size = 0;

二叉樹添加數(shù)據(jù)：

/**
     * 添加元素
     * @param item 待添加元素
     * @return 已添加元素
     */
    public T put(T item){
        //每次添加數(shù)據(jù)的時候都是從根節(jié)點向下遍歷
        Entry<T> t = root;
  if (t == null){
            //當(dāng)前的叉樹樹的為空，將新節(jié)點設(shè)置為根節(jié)點，父節(jié)點為null
            root = new Entry<>(item,null);　　　　　　　size++;　
            return root.item;
        }
        //自然排序結(jié)果，如果傳入的數(shù)據(jù)小于當(dāng)前節(jié)點返回-1，大于當(dāng)前節(jié)點返回1，否則返回0
        int ret = 0;
        //記錄父節(jié)點
        Entry<T> p = t;
        while (t != null){
            //與當(dāng)前節(jié)點比較
            ret = item.compareTo(t.item);
            p = t;
            //插入節(jié)點比當(dāng)前節(jié)點小，把當(dāng)前節(jié)點設(shè)置為左子節(jié)點，然后與左子比較，以此類推找到合適的位置
            if (ret < 0)
                t = t.left;
            //大于當(dāng)前節(jié)點
            else if (ret > 0)
                t = t.right;
            else {
                //相等就把舊值覆蓋掉
                t.item = item;
                return t.item;
            }
        }
        //創(chuàng)建新節(jié)點
        Entry<T> e = new Entry<>(item,p);
        //根據(jù)比較結(jié)果將新節(jié)點放入合適的位置
        if (ret < 0)
            p.left = e;
        else
            p.right = e;　　　　　size++;
        return e.item;
    }

在put的過程中，使用Comparable<T>中的compareTo來比較兩個元素的大小的，所以在二叉樹中存儲的元素必須要繼承Comparable<T> 類，覆寫compareTo方法。

二叉樹刪除數(shù)據(jù)

/**
     * 刪除元素
     * 刪除元素如果細分的話，可以分為4中：沒有子節(jié)點，只有左節(jié)點，只有右節(jié)點，有兩個子節(jié)點
     * 1）沒有子節(jié)點這種情況比較簡單，直接刪除就可以了
     * 2）只有左節(jié)點或右節(jié)點，這兩種情況處理方式是一致的，只是方向相反，所以在一起講了，
     * 將刪除節(jié)點的父節(jié)點的左節(jié)點（右節(jié)點）指向刪除節(jié)點的子節(jié)點，將左節(jié)點（右節(jié)點）指向刪除節(jié)點的父節(jié)點
     * 3）有兩個子節(jié)點，這種情況相對來說比較復(fù)雜一點：
     * 找到刪除節(jié)點的前驅(qū)節(jié)點或后繼節(jié)點，然后將前驅(qū)或后繼節(jié)點的值賦給刪除節(jié)點，然后將前驅(qū)或后繼節(jié)點刪除。本質(zhì)是刪除前驅(qū)或后繼節(jié)點
     * 前驅(qū)節(jié)點的特點：
     * 1）刪除的左子節(jié)點沒有右子節(jié)點，那么左子節(jié)點即為前驅(qū)節(jié)點
     * 2）刪除節(jié)點的左子節(jié)點有右子節(jié)點，那么最右邊的最后一個節(jié)點即為前驅(qū)節(jié)點
     * 后繼節(jié)點的特點：
     * 與前驅(qū)節(jié)點剛好相反，總是右子節(jié)點，或則右子節(jié)點的最左子節(jié)點;例如：刪除節(jié)點為c ，那么前驅(qū)節(jié)點為 m，后繼節(jié)點為n
     *                                          a
     *                                       /     \
     *                                    b          c
     *                                  / \         /  \
     *                                d    e       f    g
     *                              /  \  / \     / \   / \
     * @param item 刪除元素          h   i  j  k   l   m n   o
     * @return 刪除結(jié)果 */
    public boolean remove(T item){ //獲取刪除節(jié)點
        Entry<T> delEntry = getEntry(item); if (delEntry == null) return false; //刪除節(jié)點的父節(jié)點
        Entry<T> p = delEntry.parent;
        size--; //情況1：沒有子節(jié)點
        if (delEntry.left == null && delEntry.right == null){ //刪除節(jié)點為根節(jié)點
            if (delEntry == root){
                root = null;
            }else {//非根節(jié)點 //刪除的是父節(jié)點的左節(jié)點
                if (delEntry == p.left){
                    p.left = null;
                }else {//刪除右節(jié)點
                    p.right = null;
                }
            } //情況2：刪除的節(jié)點只有左節(jié)點
        }else if (delEntry.right == null){
            Entry<T> lc = delEntry.left; //刪除的節(jié)點為根節(jié)點，將刪除節(jié)點的左節(jié)點設(shè)置成根節(jié)點
            if (p == null) {
                lc.parent = null;
                root = lc;
            } else {//非根節(jié)點
                if (delEntry == p.left){//刪除左節(jié)點
                    p.left = lc;
                }else {//刪除右節(jié)點
                    p.right = lc;
                }
                lc.parent = p;
            } //情況3：刪除節(jié)點只有右節(jié)點
        }else if (delEntry.left == null){
            Entry<T> rc = delEntry.right; //刪除根節(jié)點
            if (p == null) {
                rc.parent = null;
                root = rc;
            }else {//刪除非根節(jié)點
                if (delEntry == p.left)
                    p.left = rc; else p.right = rc;
                rc.parent = p;
            } //情況4：刪除節(jié)點有兩個子節(jié)點
        }else {//有兩個節(jié)點,找到后繼節(jié)點，將值賦給刪除節(jié)點，然后將后繼節(jié)點刪除掉即可
            Entry<T> successor = successor(delEntry);//獲取到后繼節(jié)點
            delEntry.item = successor.item; //后繼節(jié)點為右子節(jié)點
            if (delEntry.right == successor){ //右子節(jié)點有右子節(jié)點
                if (successor.right != null) {
                    delEntry.right = successor.right;
                    successor.right.parent = delEntry;
                }else {//右子節(jié)點沒有子節(jié)點
                    delEntry.right = null;
                }
            }else {//后繼節(jié)點必定是左節(jié)點
                successor.parent.left = null;
            } return true;
        } //讓gc回收
        delEntry.parent = null;
        delEntry.left = null;
        delEntry.right = null; return true;
    } /**
     * 獲取節(jié)點節(jié)點
     * @param item 獲取節(jié)點
     * @return 獲取到的節(jié)點，可能為null */
    private Entry<T> getEntry(T item){
        Entry<T> t = root; int ret; //從根節(jié)點開始遍歷
        for (;t != null;){
            ret = item.compareTo(t.item); if (ret < 0)
                t = t.left; else if (ret > 0)
                t = t.right; else
                return t;
        } return null;
    } /**
     * 查找后繼節(jié)點
     * @param delEntry 刪除節(jié)點
     * @return 后繼節(jié)點 */
    private Entry<T> successor(Entry<T> delEntry) {
        Entry<T> r = delEntry.right;//r節(jié)點必定不為空
        while (r.left != null){
            r = r.left;
        } return r;
    }

二叉樹獲取節(jié)點

   /**
     * 判斷是否存在該元素
     * @param item 查找元素
     * @return 結(jié)果 */
    public boolean contains(T item){ return getEntry(item) != null;
    } /**
     * 獲取節(jié)點節(jié)點
     * @param item 獲取節(jié)點
     * @return 獲取到的節(jié)點，可能為null */
    private Entry<T> getEntry(T item){
        Entry<T> t = root; int ret; //從根節(jié)點開始遍歷
        for (;t != null;){
            ret = item.compareTo(t.item); if (ret < 0)
                t = t.left; else if (ret > 0)
                t = t.right; else
                return t;
        } return null;
    }

因為我這個例子是存儲一個元素，獲取到的元素和傳進去的元素是一致的，所以我用contains方法來判斷返回true即表示獲取成功了，不返回獲取到的結(jié)果了。當(dāng)然，如果將entry存儲的元素改為kv形式的話，就可以使用get方法了。

二叉樹的遍歷

二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷和后續(xù)遍歷，其中中序遍歷是最常用的遍歷方式，因為它遍歷出來的結(jié)果的升序的。

前序遍歷：

    /**
     * 前序遍歷
     * @param e 開始遍歷元素 */
    public void prevIterator(Entry<T> e){ if (e != null) {
            System.out.print(e.item + " ");
            prevIterator(e.left);
            prevIterator(e.right);
        }
    }</pre>

　　中序遍歷：

<pre style="color: rgb(0, 0, 0); font-family: &quot;Courier New&quot;; font-size: 12px; margin: 5px 8px; padding: 5px;">   /**
     * 中序遍歷
     * @param e */
    public void midIterator(Entry<T> e){ if (e != null){
            midIterator(e.left);
            System.out.print(e.item + " ");
            midIterator(e.right);
        }
    }

后序遍歷：

    /**
     * 后續(xù)遍歷
     * @param e 開始遍歷元素 */
    public void subIterator(Entry<T> e){ if (e != null) {
            subIterator(e.left);
            subIterator(e.right);
            System.out.print(e.item + " ");
        }
    }

demo完整的代碼：也可以到我的github中下載代碼：https://github.com/rainple1860/MyCollection

 /**
 * 二叉樹
 * @param <T> */
public class BinaryTree<T extends Comparable<T>> { //根節(jié)點
    private Entry<T> root; //數(shù)據(jù)量
    private int size = 0; public BinaryTree(){} /**
     * 添加元素
     * @param item 待添加元素
     * @return 已添加元素 */
    public T put(T item){ //每次添加數(shù)據(jù)的時候都是從根節(jié)點向下遍歷
        Entry<T> t = root;
        size++; if (t == null){ //當(dāng)前的叉樹樹的為空，將新節(jié)點設(shè)置為根節(jié)點，父節(jié)點為null
            root = new Entry<>(item,null); return root.item;
        } //自然排序結(jié)果，如果傳入的數(shù)據(jù)小于當(dāng)前節(jié)點返回-1，大于當(dāng)前節(jié)點返回1，否則返回0
        int ret = 0; //記錄父節(jié)點
        Entry<T> p = t; while (t != null){ //與當(dāng)前節(jié)點比較
            ret = item.compareTo(t.item);
            p = t; //插入節(jié)點比當(dāng)前節(jié)點小，把當(dāng)前節(jié)點設(shè)置為左子節(jié)點，然后與左子比較，以此類推找到合適的位置
            if (ret < 0)
                t = t.left; //大于當(dāng)前節(jié)點
            else if (ret > 0)
                t = t.right; else { //相等就把舊值覆蓋掉
                t.item = item; return t.item;
            }
        } //創(chuàng)建新節(jié)點
        Entry<T> e = new Entry<>(item,p); //根據(jù)比較結(jié)果將新節(jié)點放入合適的位置
        if (ret < 0)
            p.left = e; else p.right = e; return e.item;
    } public void print(){
        midIterator(root);
    } /**
     * 中序遍歷
     * @param e */
    public void midIterator(Entry<T> e){ if (e != null){
            midIterator(e.left);
            System.out.print(e.item + " ");
            midIterator(e.right);
        }
    } /**
     * 獲取根節(jié)點
     * @return 根節(jié)點 */
    public Entry<T> getRoot(){return root;} /**
     * 前序遍歷
     * @param e 開始遍歷元素 */
    public void prevIterator(Entry<T> e){ if (e != null) {
            System.out.print(e.item + " ");
            prevIterator(e.left);
            prevIterator(e.right);
        }
    } /**
     * 后續(xù)遍歷
     * @param e 開始遍歷元素 */
    public void subIterator(Entry<T> e){ if (e != null) {
            subIterator(e.left);
            subIterator(e.right);
            System.out.print(e.item + " ");
        }
    } /**
     * 獲取節(jié)點節(jié)點
     * @param item 獲取節(jié)點
     * @return 獲取到的節(jié)點，可能為null */
    private Entry<T> getEntry(T item){
        Entry<T> t = root; int ret; //從根節(jié)點開始遍歷
        for (;t != null;){
            ret = item.compareTo(t.item); if (ret < 0)
                t = t.left; else if (ret > 0)
                t = t.right; else
                return t;
        } return null;
    } /**
     * 判斷是否存在該元素
     * @param item 查找元素
     * @return 結(jié)果 */
    public boolean contains(T item){ return getEntry(item) != null;
    } /**
     * 刪除元素
     * 刪除元素如果細分的話，可以分為4中：沒有子節(jié)點，只有左節(jié)點，只有右節(jié)點，有兩個子節(jié)點
     * 1）沒有子節(jié)點這種情況比較簡單，直接刪除就可以了
     * 2）只有左節(jié)點或右節(jié)點，這兩種情況處理方式是一致的，只是方向相反，所以在一起講了，
     * 將刪除節(jié)點的父節(jié)點的左節(jié)點（右節(jié)點）指向刪除節(jié)點的子節(jié)點，將左節(jié)點（右節(jié)點）指向刪除節(jié)點的父節(jié)點
     * 3）有兩個子節(jié)點，這種情況相對來說比較復(fù)雜一點：
     * 找到刪除節(jié)點的前驅(qū)節(jié)點或后繼節(jié)點，然后將前驅(qū)或后繼節(jié)點的值賦給刪除節(jié)點，然后將前驅(qū)或后繼節(jié)點刪除。本質(zhì)是刪除前驅(qū)或后繼節(jié)點
     * 前驅(qū)節(jié)點的特點：
     * 1）刪除的左子節(jié)點沒有右子節(jié)點，那么左子節(jié)點即為前驅(qū)節(jié)點
     * 2）刪除節(jié)點的左子節(jié)點有右子節(jié)點，那么最右邊的最后一個節(jié)點即為前驅(qū)節(jié)點
     * 后繼節(jié)點的特點：
     * 與前驅(qū)節(jié)點剛好相反，總是右子節(jié)點，或則右子節(jié)點的最左子節(jié)點;例如：刪除節(jié)點為c ，那么前驅(qū)節(jié)點為 m，后繼節(jié)點為n
     *                                          a
     *                                       /     \
     *                                    b          c
     *                                  / \         /  \
     *                                d    e       f    g
     *                              /  \  / \     / \   / \
     * @param item 刪除元素       h   i  j  k   l   m n   o
     * @return 刪除結(jié)果 */
    public boolean remove(T item){ //獲取刪除節(jié)點
        Entry<T> delEntry = getEntry(item); if (delEntry == null) return false; //刪除節(jié)點的父節(jié)點
        Entry<T> p = delEntry.parent;
        size--; //情況1：沒有子節(jié)點
        if (delEntry.left == null && delEntry.right == null){ //刪除節(jié)點為根節(jié)點
            if (delEntry == root){
                root = null;
            }else {//非根節(jié)點 //刪除的是父節(jié)點的左節(jié)點
                if (delEntry == p.left){
                    p.left = null;
                }else {//刪除右節(jié)點
                    p.right = null;
                }
            } //情況2：刪除的節(jié)點只有左節(jié)點
        }else if (delEntry.right == null){
            Entry<T> lc = delEntry.left; //刪除的節(jié)點為根節(jié)點，將刪除節(jié)點的左節(jié)點設(shè)置成根節(jié)點
            if (p == null) {
                lc.parent = null;
                root = lc;
            } else {//非根節(jié)點
                if (delEntry == p.left){//刪除左節(jié)點
                    p.left = lc;
                }else {//刪除右節(jié)點
                    p.right = lc;
                }
                lc.parent = p;
            } //情況3：刪除節(jié)點只有右節(jié)點
        }else if (delEntry.left == null){
            Entry<T> rc = delEntry.right; //刪除根節(jié)點
            if (p == null) {
                rc.parent = null;
                root = rc;
            }else {//刪除非根節(jié)點
                if (delEntry == p.left)
                    p.left = rc; else p.right = rc;
                rc.parent = p;
            } //情況4：刪除節(jié)點有兩個子節(jié)點
        }else {//有兩個節(jié)點,找到后繼節(jié)點，將值賦給刪除節(jié)點，然后將后繼節(jié)點刪除掉即可
            Entry<T> successor = successor(delEntry);//獲取到后繼節(jié)點
            delEntry.item = successor.item; //后繼節(jié)點為右子節(jié)點
            if (delEntry.right == successor){ //右子節(jié)點有右子節(jié)點
                if (successor.right != null) {
                    delEntry.right = successor.right;
                    successor.right.parent = delEntry;
                }else {//右子節(jié)點沒有子節(jié)點
                    delEntry.right = null;
                }
            }else {//后繼節(jié)點必定是左節(jié)點
                successor.parent.left = null;
            } return true;
        } //讓gc回收
        delEntry.parent = null;
        delEntry.left = null;
        delEntry.right = null; return true;
    } /**
     * 查找后繼節(jié)點
     * @param delEntry 刪除節(jié)點
     * @return 后繼節(jié)點 */
    private Entry<T> successor(Entry<T> delEntry) {
        Entry<T> r = delEntry.right;//r節(jié)點必定不為空
        while (r.left != null){
            r = r.left;
        } return r;
    } public int size(){return size;} public boolean isEmpty(){return size == 0;} public void clear(){
        clear(getRoot());
        root = null;
    } private void clear(Entry<T> e){ if (e != null){
            clear(e.left);
            e.left = null;
            clear(e.right);
            e.right = null;
        }
    } static final class Entry<T extends Comparable<T>>{ //保存的數(shù)據(jù)
        private T item; //左子樹
        private Entry<T> left; //右子樹
        private Entry<T> right; //父節(jié)點
        private Entry<T> parent;
        Entry(T item,Entry<T> parent){ this.item = item; this.parent = parent;
        }
    }

}

測試代碼示例：

public static void main(String[] args) {
       BinaryTree<Integer> binaryTree = new BinaryTree<>(); //放數(shù)據(jù)
        binaryTree.put(73);
        binaryTree.put(22);
        binaryTree.put(532);
        binaryTree.put(62);
        binaryTree.put(72);
        binaryTree.put(243);
        binaryTree.put(42);
        binaryTree.put(3);
        binaryTree.put(12);
        binaryTree.put(52);

        System.out.println("size： " + binaryTree.size());
        binaryTree.put(52);
        System.out.println("添加相同元素后的size： " + binaryTree.size()); //判斷數(shù)據(jù)是否存在
        System.out.println("數(shù)據(jù)是否存在：" + binaryTree.contains(12)); //中序遍歷
        System.out.print("中序遍歷結(jié)果： ");
        binaryTree.midIterator(binaryTree.getRoot());
        System.out.println(); //前序遍歷
        System.out.print("前遍歷結(jié)果： ");
        binaryTree.prevIterator(binaryTree.getRoot());
        System.out.println(); //后序遍歷
        System.out.print("后續(xù)遍歷結(jié)果： ");
        binaryTree.subIterator(binaryTree.getRoot()); //刪除數(shù)據(jù)
        System.out.println();
        binaryTree.remove(62);
        System.out.println("刪除數(shù)據(jù)后判斷是否存在：" + binaryTree.contains(62)); //清空二叉樹
 binaryTree.clear();
        System.out.print("清空數(shù)據(jù)后中序遍歷： ");
        binaryTree.midIterator(binaryTree.getRoot());
    }

測試結(jié)果：

size： 10 
添加相同元素后的size： 10 
數(shù)據(jù)是否存在：true 
中序遍歷結(jié)果： 3 12 22 42 52 62 72 73 243 532 
前遍歷結(jié)果： 73 22 3 12 62 42 52 72 532 243 
后續(xù)遍歷結(jié)果： 12 3 52 42 72 62 22 243 532 73 
刪除數(shù)據(jù)后判斷是否存在：false 
清空數(shù)據(jù)后中序遍歷：

純手寫的demo，有什么錯誤的地方歡迎指正，謝謝大家的閱讀?。?！

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容