二叉樹介紹

??在進行鏈表結(jié)構(gòu)開發(fā)的過程之中會發(fā)現(xiàn)所有的數(shù)據(jù)按照首尾相連的狀態(tài)進行保存，那么當要進行某一個數(shù)據(jù)查詢的時候（判斷該數(shù)據(jù)是否存在），這種情況下的時間復雜度是“O(n)”，如果說鏈表的數(shù)據(jù)量小的情況下，性能上是不會有很大差別的，而一旦數(shù)據(jù)量很大，這個時候時間復雜度就會很大程度上損耗程序的運行性能，因此數(shù)據(jù)的存儲結(jié)構(gòu)必然要做出改變，應(yīng)該可以盡可能的減少檢索次數(shù)為出發(fā)點進行設(shè)計。對于現(xiàn)在的數(shù)據(jù)結(jié)構(gòu)而言，最好的性能就是“O(logn)”，所以要想實現(xiàn)它，就可以利用二叉樹的結(jié)構(gòu)來完成。
??如果要實現(xiàn)一棵樹的結(jié)構(gòu)的定義，那么需要去考慮數(shù)據(jù)的存儲形式，在二叉樹的是實現(xiàn)中，其基本的實現(xiàn)原理如下：取第一個數(shù)據(jù)為保存的根節(jié)點，小于該節(jié)點的數(shù)據(jù)放在該節(jié)點的左子樹，而大于該節(jié)點的數(shù)據(jù)要放在該節(jié)點的右子樹。

二叉樹

??如果要進行數(shù)據(jù)檢索的話，此時就需要進行每個節(jié)點的判斷，但是它的判斷是區(qū)分左右的，所以不會是整個結(jié)構(gòu)都進行判斷處理，所以它的時間復雜度就是“O(logn)”。
??而對于二叉樹而言，在進行數(shù)據(jù)獲取的時候也有三種形式：前序遍歷（根-左-右）、中序遍歷（左-根-右）、后序遍歷（左-右-根），那么現(xiàn)在只是以中序遍歷為主，則以上的數(shù)據(jù)進行中序遍歷的時候最終的結(jié)果：10、20、25、30、38、50、80、100；

二叉樹的基礎(chǔ)實現(xiàn)

數(shù)據(jù)添加

??在實現(xiàn)二叉樹的處理之中最為關(guān)鍵的問題在于數(shù)據(jù)的保存，而且數(shù)據(jù)由于涉及到對象比較的問題，那么一定要有比較器的支持，而這個比較器首選一定是Comparable，隨后如果想要進行數(shù)據(jù)的保存，首先一定要有一個節(jié)點類，節(jié)點類中由于涉及數(shù)據(jù)保存問題，所以必須使用Comparable（可以區(qū)分大小）；

import java.util.Arrays;
public class JavaApiDemo {
    public static void main(String[] args) throws Exception{
        BinaryTree<Person> tree=new BinaryTree();
        tree.add(new Person("張三",30));
        tree.add(new Person("李四",31));
        tree.add(new Person("王五",28));
        tree.add(new Person("趙六",38));
        tree.add(new Person("孫七",37));
        System.out.println(Arrays.toString(tree.toArray()));
        //[【Person類對象】姓名：王五、年齡：28, 【Person類對象】姓名：張三、年齡：30, 【Person類對象】姓名：李四、年齡：31, 【Person類對象】姓名：孫七、年齡：37, 【Person類對象】姓名：趙六、年齡：38]
    }
}
/**
 * 實現(xiàn)二叉樹操作
 * @param <T> 要進行二叉樹的實現(xiàn)
 */
class BinaryTree<T extends Comparable<T>>{
    private class Node{
        private Comparable<T> data;//存放Comparable,可以比較大小
        private Node parent;//父節(jié)點
        private Node left;//左子樹
        private Node right;//右子樹
        public Node(Comparable<T> data){//構(gòu)造方法直接進行數(shù)據(jù)的存儲
            this.data=data;
        }
        /**
         * 實現(xiàn)節(jié)點數(shù)據(jù)的適當位置的存儲
         * @param newNode 創(chuàng)建的新節(jié)點
         * @throws IllegalArgumentException 保存的數(shù)據(jù)已存在
         */
        public void addNode(Node newNode)throws IllegalArgumentException {
            int rs=newNode.data.compareTo((T)this.data);
            if(rs==0){
                throw new IllegalArgumentException("添加失敗，保存的數(shù)據(jù)已存在");
            }
            if(rs<0){//比當前節(jié)點數(shù)據(jù)小
                if(this.left==null){//判斷是否有左子樹
                    //當前沒有左子樹
                    this.left=newNode;//保存左子樹
                    newNode.parent=this;//更新父節(jié)點
                }else{
                    //需要向左邊繼續(xù)判斷
                    this.left.addNode(newNode);//繼續(xù)向下判斷
                }
            }else{
                //比根節(jié)點的數(shù)據(jù)大
                if(this.right==null){
                    //當前沒有右子樹
                    this.right=newNode;//保存左子樹
                    newNode.parent=this;//更新父節(jié)點
                }else{
                    this.right.addNode(newNode);//繼續(xù)向下判斷
                }
            }
        }
        /**
         * 實現(xiàn)所有數(shù)據(jù)的獲取處理，按照中序遍歷的形式來完成
         */
        public void toArrayNode() {
            if(this.left!=null){
                this.left.toArrayNode();
            }
            BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
            if(this.right!=null){
                this.right.toArrayNode();
            }
        }
    }
    //-------------------以下為二叉樹的功能實現(xiàn)--------------
    private Node root;//根節(jié)點
    private int count;//數(shù)據(jù)個數(shù)
    private Object[] returnData;//返回的數(shù)據(jù)
    private int foot=0;//腳標控制
    /**
     * 進行數(shù)據(jù)的保存
     * @param data 要保存的數(shù)據(jù)內(nèi)容
     * @throws NullPointerException 保存數(shù)據(jù)為空時拋出的異常
     * @throws IllegalArgumentException 保存的數(shù)據(jù)已存在
     */
    public void add(Comparable<T> data)throws NullPointerException,IllegalArgumentException{
        if(data==null){
            throw new NullPointerException("保存的數(shù)據(jù)不允許為空！");
        }
        //所有的數(shù)據(jù)本身不具備節(jié)點關(guān)系的匹配，那么一定要將其包裝在Node類之中
        Node newNode=new Node(data);//包裝節(jié)點
        if(this.root==null){//現(xiàn)在沒有根節(jié)點，則將第一個節(jié)點作為根節(jié)點
            this.root=newNode;
        }else{
            this.root.addNode(newNode);//交由node類進行處理
        }
        this.count++;
    }
    /**
     * 以對象數(shù)組的形式返回全部數(shù)據(jù)，如果沒有數(shù)據(jù)就返回null
     * @return 全部數(shù)據(jù)
     */
    public Object[] toArray(){
        if(this.count==0){
            return null;
        }
        this.returnData=new Object[this.count];//保存長度為數(shù)組長度
        this.foot=0;//腳標清零
        this.root.toArrayNode();//直接通過Node類負責
        return this.returnData;//返回全部的數(shù)據(jù)
    }
}
class Person implements Comparable<Person>{
    private String name;
    private int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "【Person類對象】姓名：" + this.name + "、年齡：" + this.age;
    }

    @Override
    public int compareTo(Person person) {
        return this.age-person.age;//升序
//        return person.age-this.age;//降序
    }
}

??在進行數(shù)據(jù)添加的時候只是實現(xiàn)了節(jié)點關(guān)系的保存，而這種關(guān)系的保存后的結(jié)果就是所有的數(shù)據(jù)都是有序排列。

數(shù)據(jù)刪除

??二叉樹中數(shù)據(jù)刪除操作是非常復雜的，因為在進行數(shù)據(jù)刪除的時候需要考慮很多情況：
??root：根節(jié)點、isRoot：待刪除節(jié)點是否為根節(jié)點
??removeNode：待刪除節(jié)點、removeParentNode：待刪除節(jié)點父節(jié)點
??parent：父節(jié)點、left：左子節(jié)點、right：右子節(jié)點
??isLeftNode：待刪除節(jié)點是否為父節(jié)點的左子節(jié)點，true為左子節(jié)點，false為右子節(jié)點

??情況1、如果待刪除節(jié)點沒有子節(jié)點；

//不包含子節(jié)點
if(isRoot){
    this.root=null;
}else{
    removeNode.parent = null;//父節(jié)點斷開引用
    if(isLeftNode){
        removeParentNode.left=null;
    }else{
        removeParentNode.right=null;
    }
}

情況1

??情況2、如果待刪除節(jié)點只有一個左子節(jié)點；

//有左子樹、沒有右子樹
if(isRoot){
    this.root=this.root.left;
}else{
    removeNode.left.parent=removeNode.parent;
    if(isLeftNode){
        removeParentNode.left=removeNode.left;
    }else{
        removeParentNode.right=removeNode.left;
    }
}

情況2

??情況3、如果待刪除節(jié)點只有一個右子節(jié)點；

 //有右子樹、沒有左子樹
if(isRoot){
    this.root=this.root.right;
}else{
    removeNode.right.parent=removeNode.parent;
    if(isLeftNode){
        removeParentNode.left=removeNode.right;
    }else{
        removeParentNode.right=removeNode.right;
    }
}

情況3

??情況4、如果待刪除節(jié)點有兩個子節(jié)點：

//有左子樹和右子樹，將右邊節(jié)點中最左邊的節(jié)點找到，改變其指向
Node moveNode=removeNode.right;//移動的節(jié)點
if(moveNode.hasLeft()){
    while (moveNode.hasLeft()){
        //還有左邊的節(jié)點,一直向左找
        moveNode=moveNode.left;
    }
    //當前moveNode就是有節(jié)點的最小左節(jié)點
    if(moveNode.hasRight()){
        //如果后繼節(jié)點有右子樹，右子樹將替換其原始的位置
        moveNode.parent.left=moveNode.right;
    }else{
        //后繼節(jié)點不包含右子樹
        moveNode.parent.left=null;
    }
    moveNode.right=removeNode.right;//改變原始的有節(jié)點的指向
}
moveNode.left=removeNode.left;
if(isRoot){
    this.root=moveNode;
}else{
    moveNode.parent=removeNode.parent;
    if(isLeftNode){
        removeParentNode.left=moveNode;
    }else{
        removeParentNode.right=moveNode;
    }
}

情況4

??下面通過具體的代碼實現(xiàn)操作功能。

public class JavaApiDemo {
    public static void main(String[] args) throws Exception{
        BinaryTree<Person> tree=new BinaryTree();
        tree.add(new Person("張三",80));
        tree.add(new Person("李四",50));
        tree.add(new Person("王五",90));
        tree.add(new Person("趙六",30));
        tree.add(new Person("孫七",60));
        tree.add(new Person("周八",85));
        tree.add(new Person("吳九",95));
        tree.add(new Person("鄭十",10));
        tree.add(new Person("劉一",55));
        tree.add(new Person("陳二",70));
        tree.remove(new Person("張三",80));
        Object[] arrays=tree.toArray();
        for (Object array:arrays){
            System.out.println(array);
        }
        /**
         * 【Person類對象】姓名：鄭十、年齡：10
         * 【Person類對象】姓名：趙六、年齡：30
         * 【Person類對象】姓名：李四、年齡：50
         * 【Person類對象】姓名：劉一、年齡：55
         * 【Person類對象】姓名：孫七、年齡：60
         * 【Person類對象】姓名：陳二、年齡：70
         * 【Person類對象】姓名：周八、年齡：85
         * 【Person類對象】姓名：王五、年齡：90
         * 【Person類對象】姓名：吳九、年齡：95
         */
    }
}
/**
 * 實現(xiàn)二叉樹操作
 * @param <T> 要進行二叉樹的實現(xiàn)
 */
class BinaryTree<T extends Comparable<T>>{
    private class Node{
        private Comparable<T> data;//存放Comparable,可以比較大小
        private Node parent;//父節(jié)點
        private Node left;//左子樹
        private Node right;//右子樹
        public Node(Comparable<T> data){//構(gòu)造方法直接進行數(shù)據(jù)的存儲
            this.data=data;
        }
        public boolean hasLeft(){
           return left!=null;
        }
        public boolean hasRight(){
            return right!=null;
        }
        /**
         * 實現(xiàn)節(jié)點數(shù)據(jù)的適當位置的存儲
         * @param newNode 創(chuàng)建的新節(jié)點
         * @throws IllegalArgumentException 保存的數(shù)據(jù)已存在
         */
        public void addNode(Node newNode)throws IllegalArgumentException {
            int rs=newNode.data.compareTo((T)this.data);
            if(rs==0){
                throw new IllegalArgumentException("添加失敗，保存的數(shù)據(jù)已存在");
            }
            if(rs<0){//比當前節(jié)點數(shù)據(jù)小
                if(this.left==null){//判斷是否有左子樹
                    //當前沒有左子樹
                    this.left=newNode;//保存左子樹
                    newNode.parent=this;//更新父節(jié)點
                }else{
                    //需要向左邊繼續(xù)判斷
                    this.left.addNode(newNode);//繼續(xù)向下判斷
                }
            }else{
                //比根節(jié)點的數(shù)據(jù)大
                if(this.right==null){
                    //當前沒有右子樹
                    this.right=newNode;//保存左子樹
                    newNode.parent=this;//更新父節(jié)點
                }else{
                    this.right.addNode(newNode);//繼續(xù)向下判斷
                }
            }
        }
        /**
         * 實現(xiàn)所有數(shù)據(jù)的獲取處理，按照中序遍歷的形式來完成
         */
        public void toArrayNode() {
            if(this.left!=null){
                this.left.toArrayNode();
            }
            BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
            if(this.right!=null){
                this.right.toArrayNode();
            }
        }
        /**
         *  獲取要刪除的節(jié)點對象
         * @param data 比較的對象
         * @return 要刪除的節(jié)點對象，
         */
        public Node findNode(Comparable<T> data) {
            int rs=data.compareTo((T)this.data);
            if(rs==0){
                return this;//查找到了
            }
            if (rs < 0) {
                if (this.left != null) {
                    return this.left.findNode(data);
                }
                return null;
            }
            if (this.right != null) {
                return this.right.findNode(data);
            }
            return null;

        }
    }
    //-------------------以下為二叉樹的功能實現(xiàn)--------------
    private Node root;//根節(jié)點
    private int count;//數(shù)據(jù)個數(shù)
    private Object[] returnData;//返回的數(shù)據(jù)
    private int foot=0;//腳標控制
    /**
     * 進行數(shù)據(jù)的保存
     * @param data 要保存的數(shù)據(jù)內(nèi)容
     * @throws NullPointerException 保存數(shù)據(jù)為空時拋出的異常
     * @throws IllegalArgumentException 保存的數(shù)據(jù)已存在
     */
    public void add(Comparable<T> data)throws NullPointerException,IllegalArgumentException{
        if(data==null){
            throw new NullPointerException("保存的數(shù)據(jù)不允許為空！");
        }
        //所有的數(shù)據(jù)本身不具備節(jié)點關(guān)系的匹配，那么一定要將其包裝在Node類之中
        Node newNode=new Node(data);//包裝節(jié)點
        if(this.root==null){//現(xiàn)在沒有根節(jié)點，則將第一個節(jié)點作為根節(jié)點
            this.root=newNode;
        }else{
            this.root.addNode(newNode);//交由node類進行處理
        }
        this.count++;
    }
    /**
     * 以對象數(shù)組的形式返回全部數(shù)據(jù)，如果沒有數(shù)據(jù)就返回null
     * @return 全部數(shù)據(jù)
     */
    public Object[] toArray(){
        if(this.count==0){
            return null;
        }
        this.returnData=new Object[this.count];//保存長度為數(shù)組長度
        this.foot=0;//腳標清零
        this.root.toArrayNode();//直接通過Node類負責
        return this.returnData;//返回全部的數(shù)據(jù)
    }
    /**
     * 執(zhí)行數(shù)據(jù)的刪除處理
     * @param data 需要刪除的數(shù)據(jù)
     */
    public void remove(Comparable<T> data) {
        if(this.root==null){//根節(jié)點不存在
            return;
        }
        Node removeNode = this.root.findNode(data);
        if (removeNode == null) {
            return;
        }
        this.count--;
        Node removeParentNode=removeNode.parent;
        boolean isRoot=removeParentNode==null;
        Boolean isLeftNode=null;
        if(isRoot==false){
            isLeftNode=data.compareTo((T)removeParentNode.data)<0;
        }
        //找到要刪除的節(jié)點信息了
        if (!removeNode.hasLeft() && !removeNode.hasRight()) {
            if(isRoot){
                this.root=null;
            }else{
                //不包含子節(jié)點
                removeNode.parent = null;//父節(jié)點斷開引用
                if(isLeftNode){
                    removeParentNode.left=null;
                }else{
                    removeParentNode.right=null;
                }
            }
        } else if (removeNode.hasLeft() && !removeNode.hasRight()) {
            //有左子樹、沒有右子樹
            if(isRoot){
                this.root=this.root.left;
            }else{
                removeNode.left.parent=removeNode.parent;
                if(isLeftNode){
                    removeParentNode.left=removeNode.left;
                }else{
                    removeParentNode.right=removeNode.left;
                }
            }
        } else if (!removeNode.hasLeft() && removeNode.hasRight()) {
            //有右子樹、沒有左子樹
            if(isRoot){
                this.root=this.root.right;
            }else{
                removeNode.right.parent=removeNode.parent;
                if(isLeftNode){
                    removeParentNode.left=removeNode.right;
                }else{
                    removeParentNode.right=removeNode.right;
                }
            }
        }else{
            //有左子樹和右子樹，將右邊節(jié)點中最左邊的節(jié)點找到，改變其指向
            Node moveNode=removeNode.right;//移動的節(jié)點
            if(moveNode.hasLeft()){
                while (moveNode.hasLeft()){
                    //還有左邊的節(jié)點,一直向左找
                    moveNode=moveNode.left;
                }
                //當前moveNode就是有節(jié)點的最小左節(jié)點
                if(moveNode.hasRight()){
                    //如果后繼節(jié)點有右子樹，右子樹將替換其原始的位置
                    moveNode.parent.left=moveNode.right;
                }else{
                    //后繼節(jié)點不包含右子樹
                    moveNode.parent.left=null;
                }
                moveNode.right=removeNode.right;//改變原始的有節(jié)點的指向
            }
            moveNode.left=removeNode.left;
            if(isRoot){
                this.root=moveNode;
            }else{
                moveNode.parent=removeNode.parent;
                if(isLeftNode){
                    removeParentNode.left=moveNode;
                }else{
                    removeParentNode.right=moveNode;
                }
            }
        }
    }
}
class Person implements Comparable<Person>{
    private String name;
    private int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "【Person類對象】姓名：" + this.name + "、年齡：" + this.age;
    }

    @Override
    public int compareTo(Person person) {
        return this.age-person.age;//升序
//        return person.age-this.age;//降序
    }
}

??可見，二叉樹數(shù)據(jù)結(jié)構(gòu)刪除操作是非常繁瑣的，所以如果不是必須的情況下，不建議進行刪除操作。