二叉樹的基本定義

簡而言之：二叉樹就是度不能超過2的樹（每個(gè)樹只能有兩個(gè)節(jié)點(diǎn)）

滿二叉樹：

一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)樹達(dá)到最大值，則在這個(gè)樹就是滿二叉樹

完全二叉樹：

葉結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，并且最下面那一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹

二叉查找樹：

二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左結(jié)點(diǎn)中，較大的值保存在右結(jié)點(diǎn)中。
根據(jù)對圖的觀察，我們發(fā)現(xiàn)二叉樹其實(shí)就是由一個(gè)一個(gè)的結(jié)點(diǎn)及其之間的關(guān)系組成的，按照面向?qū)ο蟮乃枷耄覀冊O(shè)計(jì)一個(gè)結(jié)點(diǎn)來描述結(jié)點(diǎn)這個(gè)事務(wù)。

首先我們先想著實(shí)現(xiàn)二叉樹需要一些什么參數(shù)？

    private static class Node{
        public Node left;
        public Node right;
        public Integer key;
        public String value;

        public Node(Node left, Node right, Integer key, String value) {
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
        }
    }

在上面我們定義了left，right，key，value四個(gè)參數(shù)，并且定義了這個(gè)類的構(gòu)造方法

我們看插入方法put思想：

1. 如果當(dāng)樹中沒有任何一個(gè)結(jié)點(diǎn)，則直接把新結(jié)點(diǎn)當(dāng)根結(jié)點(diǎn)使用
2. 如果當(dāng)前樹不為空，就從根結(jié)點(diǎn)開始
   2-1：如果要查詢的key，小于當(dāng)前結(jié)點(diǎn)的key，則繼續(xù)查找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)2-2：如果新結(jié)點(diǎn)的key大于當(dāng)前結(jié)點(diǎn)的key，則繼續(xù)找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)2-3：如果新結(jié)點(diǎn)的key等于當(dāng)前結(jié)點(diǎn)的key，則樹中已經(jīng)存在這樣的結(jié)點(diǎn)，替換該結(jié)點(diǎn)的value值就好

那么我們要怎么實(shí)現(xiàn)呢？

    //向樹中插入一個(gè)鍵值對
    public void put(Integer key,String value){
        root=put(root,key,value);
    }
    //給指定的數(shù)x添加一個(gè)鍵,添加一個(gè)鍵值對，并返回添加后的新數(shù)
    private Node put(Node tree,Integer key,String value){
        if(tree==null){
            //個(gè)數(shù)加1
            n++;
            //直接把新結(jié)點(diǎn)當(dāng)成根結(jié)點(diǎn)使用
            return new Node(null,null,key,value);
        }
        //比較key,如果新結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)的key，繼續(xù)尋找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
        if(key > tree.key){
            tree.right=put(tree.right,key,value);
        }else if(key<tree.key){
            //新結(jié)點(diǎn)的key小于當(dāng)前結(jié)點(diǎn)的key,繼續(xù)找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            tree.left=put(tree.left,key,value);
        }else{
            //新結(jié)點(diǎn)的key等于當(dāng)前結(jié)點(diǎn)的key
            tree.value=value;
        }
        return tree;
    }

在上面的代碼塊中，我們定義了兩個(gè)put方法，一個(gè)是給其他類操作的，一個(gè)是給自己類操作的，對于外部的用戶來說，他只需要將鍵值對傳遞進(jìn)來就好了，排序是我們程序員的事，所以，我們這里的put只有兩個(gè)參數(shù)：

public void put(Integer key,String value)

然后我們通過這個(gè)put方法再去調(diào)用我們內(nèi)部的put方法，在這個(gè)方法中，我們首先要把我們的根結(jié)點(diǎn)root傳遞進(jìn)去，然后再將前端傳給我們的key：value傳遞進(jìn)去

private Node put(Node tree,Integer key,String value)

這樣，我們就可以在這個(gè)put上進(jìn)行我們一開始定義的開發(fā)流程了：

1. 如果樹中沒有結(jié)點(diǎn)，就把當(dāng)前插入的結(jié)點(diǎn)當(dāng)成首節(jié)點(diǎn)使用：

        if(tree==null){
            //個(gè)數(shù)加1
            n++;
            //直接把新結(jié)點(diǎn)當(dāng)成根結(jié)點(diǎn)使用
            return new Node(null,null,key,value);
        }

2. 如果樹不為空，就從根結(jié)點(diǎn)開始遍歷，也就是root結(jié)點(diǎn)
   2-1. 如果要查詢的key，小于當(dāng)前結(jié)點(diǎn)的key，則繼續(xù)查找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)

        //比較key,如果新結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)的key，繼續(xù)尋找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
        if(key > tree.key){
            tree.right=put(tree.right,key,value);
        }

2-2. 如果新結(jié)點(diǎn)的key大于當(dāng)前結(jié)點(diǎn)的key，則繼續(xù)找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)

else if(key<tree.key){
            //新結(jié)點(diǎn)的key小于當(dāng)前結(jié)點(diǎn)的key,繼續(xù)找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            tree.left=put(tree.left,key,value);
        }

2-3：如果新結(jié)點(diǎn)的key等于當(dāng)前結(jié)點(diǎn)的key，則樹中已經(jīng)存在這樣的結(jié)點(diǎn)，替換該結(jié)點(diǎn)的value值就好

else{
            //新結(jié)點(diǎn)的key等于當(dāng)前結(jié)點(diǎn)的key
            tree.value=value;
        }

現(xiàn)在put方法就執(zhí)行完畢了，我們把一個(gè)前端傳遞過來的值放入了二叉樹中.

上面我們已經(jīng)實(shí)現(xiàn)了二叉樹中的put方法，按照我的習(xí)慣的話呢接下來我們還是先講思想，講get方法和delete方法：

查詢方法get實(shí)現(xiàn)思想：
從根結(jié)點(diǎn)開始：

1. 如果要查詢的key小于當(dāng)前結(jié)點(diǎn)的key，則繼續(xù)查找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
2. 如果要查詢的key大于當(dāng)前結(jié)點(diǎn)的key，則繼續(xù)找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
3. 如果要查詢的key等于當(dāng)前結(jié)點(diǎn)的key，則樹中返回當(dāng)前結(jié)點(diǎn)的value

刪除方法delete實(shí)現(xiàn)思想：

1. 找到被刪除結(jié)點(diǎn)
2. 找到被刪除結(jié)點(diǎn)右子樹的最小結(jié)點(diǎn)
3. 刪除右子樹中的最小結(jié)點(diǎn)
4. 讓被刪除結(jié)點(diǎn)的左子樹稱為最小結(jié)點(diǎn)的左子樹，讓被刪除結(jié)點(diǎn)的右子樹稱為最小結(jié)點(diǎn)的子樹
5. 讓被刪除節(jié)點(diǎn)的父結(jié)點(diǎn)指向最小結(jié)點(diǎn)

按照從簡單到困難的準(zhǔn)則，我們先從簡單的開始，get方法相對于delete而言要簡單一點(diǎn)，所以我們先實(shí)現(xiàn)get方法

    //從樹中找到對應(yīng)的值
    public String get(Integer key){
        return get(root,key);
    }
    private String get(Node tree,Integer key){
        if(root==null){
            return null;
        }
        //比較key,如果新結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)的key，繼續(xù)尋找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
        if(key > tree.key){
            
            return get(tree.right,key);
        }else if(key<tree.key){
            //比較key,如果新結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)的key，繼續(xù)尋找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
         
            return get(tree.left,key);
        }else{
            //要查找的key和當(dāng)前結(jié)點(diǎn)的key相等，返回value
            return tree.value;
        }
    }

通過不停的遞歸調(diào)用get方法，我們就可以不斷的查找樹的左右結(jié)點(diǎn)，從而最終返回get到的結(jié)果值，這個(gè)非常簡單，沒什么好說的。

接下來比較重要的是delete方法：

    //從指定的樹中，根據(jù)key刪除鍵中的鍵值對
    public void delete(Integer key){

        root=delete(root,key);
    }
    private Node delete(Node tree,Integer key){
        if(tree==null){
            return null;
        }
        if(key > tree.key){
            tree.right=delete(tree.right,key);
        }else if(key<tree.key){
            tree.left=delete(tree.left,key);
        }else{
            //待刪除的key等于當(dāng)前結(jié)點(diǎn)的key，說明當(dāng)前結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn)
            //1、如果當(dāng)前結(jié)點(diǎn)的右子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            if(tree.right==null){
                n--;
                return tree.left;
            }
            //2、如果當(dāng)前結(jié)點(diǎn)的左子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
            if(tree.left==null){
                n--;
                return  tree.right;
            }
            //當(dāng)前結(jié)點(diǎn)的左右子樹都存在
            //找到右子樹中的最小結(jié)點(diǎn)
            Node minNode=tree.right;
            //二叉查找樹的左結(jié)點(diǎn)一定比右結(jié)點(diǎn)小
            if(minNode.left!=null){
                minNode=minNode.left;
            }
            //到這里就找到了當(dāng)前結(jié)點(diǎn)右子樹中最小的結(jié)點(diǎn)minNode
            //刪除右子樹中最小的結(jié)點(diǎn)
            Node node=tree.right;
            while (node.left!=null){
                if(node.left.left==null){
                    //說明N的左結(jié)點(diǎn)就是我們要找的最小結(jié)點(diǎn)
                    node.left=null;
                }else{
                    node=node.left;
                }
            }
            //到這里，最小結(jié)點(diǎn)已經(jīng)被刪除了
            //讓被刪除結(jié)點(diǎn)的左子樹成為最小結(jié)點(diǎn)的左子樹，讓被刪除結(jié)點(diǎn)的右子樹，成為最小結(jié)點(diǎn)的右子樹
            minNode.left=tree.left;
            minNode.right=tree.right;
            //讓被刪除結(jié)點(diǎn)的父結(jié)點(diǎn)指向最小結(jié)點(diǎn)
            tree=minNode;
            //個(gè)數(shù)減1
            n--;
        }
        return tree;
    }

上面的這段代碼看著很長，且聽我與你一一分解

首先我們通過public方法方便別的類調(diào)用，用戶只需要傳遞key值進(jìn)入我們的后臺，我們就可以通過后臺的查找方法來查找二叉樹中的元素，然后對其進(jìn)行刪除。

這同樣使用了遞歸的思想。通過不斷的查找二叉樹中的元素，找到要?jiǎng)h除的那個(gè)數(shù)據(jù)。

        if(key > tree.key){
            tree.right=delete(tree.right,key);
        }else if(key<tree.key){
            tree.left=delete(tree.left,key);
        }else{
            //待刪除的key等于當(dāng)前結(jié)點(diǎn)的key，說明當(dāng)前結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn)
            //1、如果當(dāng)前結(jié)點(diǎn)的右子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            if(tree.right==null){
                n--;
                return tree.left;
            }
            //2、如果當(dāng)前結(jié)點(diǎn)的左子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
            if(tree.left==null){
                n--;
                return  tree.right;
            }
            //當(dāng)前結(jié)點(diǎn)的左右子樹都存在
            //找到右子樹中的最小結(jié)點(diǎn)
            Node minNode=tree.right;
            //二叉查找樹的左結(jié)點(diǎn)一定比右結(jié)點(diǎn)小
            if(minNode.left!=null){
                minNode=minNode.left;
            }
            //到這里就找到了當(dāng)前結(jié)點(diǎn)右子樹中最小的結(jié)點(diǎn)minNode
            //刪除右子樹中最小的結(jié)點(diǎn)
            Node node=tree.right;
            while (node.left!=null){
                if(node.left.left==null){
                    //說明N的左結(jié)點(diǎn)就是我們要找的最小結(jié)點(diǎn)
                    node.left=null;
                }else{
                    node=node.left;
                }
            }
            //到這里，最小結(jié)點(diǎn)已經(jīng)被刪除了
            //讓被刪除結(jié)點(diǎn)的左子樹成為最小結(jié)點(diǎn)的左子樹，讓被刪除結(jié)點(diǎn)的右子樹，成為最小結(jié)點(diǎn)的右子樹
            minNode.left=tree.left;
            minNode.right=tree.right;
            //讓被刪除結(jié)點(diǎn)的父結(jié)點(diǎn)指向最小結(jié)點(diǎn)
            tree=minNode;
            //個(gè)數(shù)減1
            n--;
        }

如果當(dāng)前遞歸到的這個(gè)結(jié)點(diǎn)的元素值小于我們用戶傳遞進(jìn)來的key的話我們將其往左進(jìn)行遞歸

        if(key > tree.key){
            tree.right=delete(tree.right,key);
        }

如果大于的話我們就往右進(jìn)行遞歸

else if(key<tree.key){
            tree.left=delete(tree.left,key);
        }

如果說用戶傳遞過來的key與當(dāng)前結(jié)點(diǎn)的key值相等的話，那么說明當(dāng)前的這個(gè)結(jié)點(diǎn)就是我們要?jiǎng)h除的這個(gè)結(jié)點(diǎn)

else{
            //待刪除的key等于當(dāng)前結(jié)點(diǎn)的key，說明當(dāng)前結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn)
            //1、如果當(dāng)前結(jié)點(diǎn)的右子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            if(tree.right==null){
                n--;
                return tree.left;
            }
            //2、如果當(dāng)前結(jié)點(diǎn)的左子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
            if(tree.left==null){
                n--;
                return  tree.right;
            }
            //當(dāng)前結(jié)點(diǎn)的左右子樹都存在
            //找到右子樹中的最小結(jié)點(diǎn)
            Node minNode=tree.right;
            //二叉查找樹的左結(jié)點(diǎn)一定比右結(jié)點(diǎn)小
            if(minNode.left!=null){
                minNode=minNode.left;
            }
            //到這里就找到了當(dāng)前結(jié)點(diǎn)右子樹中最小的結(jié)點(diǎn)minNode
            //刪除右子樹中最小的結(jié)點(diǎn)
            Node node=tree.right;
            while (node.left!=null){
                if(node.left.left==null){
                    //說明N的左結(jié)點(diǎn)就是我們要找的最小結(jié)點(diǎn)
                    node.left=null;
                }else{
                    node=node.left;
                }
            }
            //到這里，最小結(jié)點(diǎn)已經(jīng)被刪除了
            //讓被刪除結(jié)點(diǎn)的左子樹成為最小結(jié)點(diǎn)的左子樹，讓被刪除結(jié)點(diǎn)的右子樹，成為最小結(jié)點(diǎn)的右子樹
            minNode.left=tree.left;
            minNode.right=tree.right;
            //讓被刪除結(jié)點(diǎn)的父結(jié)點(diǎn)指向最小結(jié)點(diǎn)
            tree=minNode;
            //個(gè)數(shù)減1
            n--;
        }
        return tree;
    }

現(xiàn)在又要研究二叉樹中的刪除方法中結(jié)點(diǎn)的性質(zhì)了，我們既然要把這個(gè)元素進(jìn)行刪除操作的話，那么是不是，我們就要將他的子結(jié)點(diǎn)的層級往上提升一級，那么我們接著研究：

            //待刪除的key等于當(dāng)前結(jié)點(diǎn)的key，說明當(dāng)前結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn)
            //1、如果當(dāng)前結(jié)點(diǎn)的右子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            if(tree.right==null){
                n--;
                return tree.left;
            }
            //2、如果當(dāng)前結(jié)點(diǎn)的左子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
            if(tree.left==null){
                n--;
                return  tree.right;
            }

如果當(dāng)前結(jié)點(diǎn)的右子樹不存在，那么我們就把該結(jié)點(diǎn)的左子樹給他提上去
如果當(dāng)前結(jié)點(diǎn)的左子樹不存在，那么我們就把他的右子樹提上去

如果說當(dāng)前結(jié)點(diǎn)的左右子樹都存在的話，那么就有點(diǎn)小麻煩了，那么我們就要從要被刪除的這個(gè)結(jié)點(diǎn)的右子樹中找到他的最小元素，然后把他的最小元素給他提上去。

            //到這里就找到了當(dāng)前結(jié)點(diǎn)右子樹中最小的結(jié)點(diǎn)minNode
            //刪除右子樹中最小的結(jié)點(diǎn)
            Node node=tree.right;
            while (node.left!=null){
                if(node.left.left==null){
                    //說明N的左結(jié)點(diǎn)就是我們要找的最小結(jié)點(diǎn)
                    node.left=null;
                }else{
                    node=node.left;
                }
            }
            //到這里，最小結(jié)點(diǎn)已經(jīng)被刪除了
            //讓被刪除結(jié)點(diǎn)的左子樹成為最小結(jié)點(diǎn)的左子樹，讓被刪除結(jié)點(diǎn)的右子樹，成為最小結(jié)點(diǎn)的右子樹
            minNode.left=tree.left;
            minNode.right=tree.right;
            //讓被刪除結(jié)點(diǎn)的父結(jié)點(diǎn)指向最小結(jié)點(diǎn)
            tree=minNode;
            //個(gè)數(shù)減1
            n--;
        }

最后在我們所有操作都已經(jīng)執(zhí)行完畢之后，我們只要返回這個(gè)改變之后的tree就好了

好了，現(xiàn)在我們創(chuàng)建一個(gè)外部類Test1來驗(yàn)證此程序的正確性

class Test1{
    public static void main(String[] args) {
        BinaryTree tree=new BinaryTree();
        tree.put(8,"雞霸");
        tree.put(7,"田七");
        tree.put(9,"吳久");
        tree.put(3,"張三");
        tree.put(6,"陸遠(yuǎn)");
        System.out.println(tree.get(7));
        tree.delete(6);
        tree.delete(9);
        tree.delete(3);
        System.out.println(tree.size());
    }
}

然后我放出全部代碼方便大家實(shí)驗(yàn)：

package com.gm.tree;

public class BinaryTree {
    //記錄一個(gè)根結(jié)點(diǎn)
    private Node root;
    //記錄樹中的元素個(gè)數(shù)
    private int n;

    public BinaryTree() {
    }
    //向樹中插入一個(gè)鍵值對
    public void put(Integer key,String value){
        root=put(root,key,value);
    }
    //給指定的數(shù)x添加一個(gè)鍵,添加一個(gè)鍵值對，并返回添加后的新數(shù)
    private Node put(Node tree,Integer key,String value){
        if(tree==null){
            //個(gè)數(shù)加1
            n++;
            //直接把新結(jié)點(diǎn)當(dāng)成根結(jié)點(diǎn)使用
            return new Node(null,null,key,value);
        }
        //比較key,如果新結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)的key，繼續(xù)尋找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
        if(key > tree.key){
            tree.right=put(tree.right,key,value);
        }else if(key<tree.key){
            //新結(jié)點(diǎn)的key小于當(dāng)前結(jié)點(diǎn)的key,繼續(xù)找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            tree.left=put(tree.left,key,value);
        }else{
            //新結(jié)點(diǎn)的key等于當(dāng)前結(jié)點(diǎn)的key
            tree.value=value;
        }
        return tree;
    }
    //從樹中找到對應(yīng)的值
    public String get(Integer key){
        return get(root,key);
    }
    private String get(Node tree,Integer key){
        if(root==null){
            return null;
        }
        //比較key,如果新結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)的key，繼續(xù)尋找當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
        if(key > tree.key){
            return get(tree.right,key);
        }else if(key<tree.key){
            //比較key,如果新結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)的key，繼續(xù)尋找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            return get(tree.left,key);
        }else{
            //要查找的key和當(dāng)前結(jié)點(diǎn)的key相等，返回value
            return tree.value;
        }
    }
    //從指定的樹中，根據(jù)key刪除鍵中的鍵值對
    public void delete(Integer key){

        root=delete(root,key);
    }
    private Node delete(Node tree,Integer key){
        if(tree==null){
            return null;
        }
        if(key > tree.key){
            tree.right=delete(tree.right,key);
        }else if(key<tree.key){
            tree.left=delete(tree.left,key);
        }else{
            //待刪除的key等于當(dāng)前結(jié)點(diǎn)的key，說明當(dāng)前結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn)
            //1、如果當(dāng)前結(jié)點(diǎn)的右子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
            if(tree.right==null){
                n--;
                return tree.left;
            }
            //2、如果當(dāng)前結(jié)點(diǎn)的左子樹不存在，則直接返回當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
            if(tree.left==null){
                n--;
                return  tree.right;
            }
            //當(dāng)前結(jié)點(diǎn)的左右子樹都存在
            //找到右子樹中的最小結(jié)點(diǎn)
            Node minNode=tree.right;
            //二叉查找樹的左結(jié)點(diǎn)一定比右結(jié)點(diǎn)小
            if(minNode.left!=null){
                minNode=minNode.left;
            }
            //到這里就找到了當(dāng)前結(jié)點(diǎn)右子樹中最小的結(jié)點(diǎn)minNode
            //刪除右子樹中最小的結(jié)點(diǎn)
            Node node=tree.right;
            while (node.left!=null){
                if(node.left.left==null){
                    //說明N的左結(jié)點(diǎn)就是我們要找的最小結(jié)點(diǎn)
                    node.left=null;
                }else{
                    node=node.left;
                }
            }
            //到這里，最小結(jié)點(diǎn)已經(jīng)被刪除了
            //讓被刪除結(jié)點(diǎn)的左子樹成為最小結(jié)點(diǎn)的左子樹，讓被刪除結(jié)點(diǎn)的右子樹，成為最小結(jié)點(diǎn)的右子樹
            minNode.left=tree.left;
            minNode.right=tree.right;
            //讓被刪除結(jié)點(diǎn)的父結(jié)點(diǎn)指向最小結(jié)點(diǎn)
            tree=minNode;
            //個(gè)數(shù)減1
            n--;
        }
        return tree;
    }
    public int size(){
        return n;
    }
    private static class Node{
        public Node left;
        public Node right;
        public Integer key;
        public String value;

        public Node(Node left, Node right, Integer key, String value) {
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
        }
    }
}
class Test1{
    public static void main(String[] args) {
        BinaryTree tree=new BinaryTree();
        tree.put(8,"雷霸天");
        tree.put(7,"田七");
        tree.put(9,"吳久");
        tree.put(3,"張三");
        tree.put(6,"陸遠(yuǎn)");
        System.out.println(tree.get(7));
        tree.delete(6);
        tree.delete(9);
        tree.delete(3);
        System.out.println(tree.size());
    }
}