手把手教你實作二叉樹資料添加 | 帶你學《Java語言進階特性》之三十九

上一篇：初識二叉樹，領悟樹的概念 | 帶你學《Java語言進階特性》之三十八

二叉樹可以優化查找效率的關鍵原因在于其特殊的資料儲存方式，在儲存時就借助比較器提前完成資料的有序擺放。本節将結合具體案例講解實作二叉樹資料儲存的方法。

【本節目标】

通過閱讀本節内容，你将了解到二叉樹儲存資料的方式，并能夠複習之前所學的比較器相關内容，借助比較器實作二叉樹特殊的資料儲存功能。

在實作二叉樹的處理之中最為關鍵的問題在于資料的儲存，而且資料由于牽扯到對象比較的問題，那麼一定要有比較器的支援，而這個比較器首選一定是Comparable，是以本次将儲存一個Person 類資料：

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 + "\n";
    }

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

随後如果要想進行資料的儲存，首先一定要有一個節點類。節點類中由于牽扯到資料儲存問題，是以必須使用Comparable（可以區分大小）；

import java.util.Arrays;
public class JavaAPIDemo {
    public static void main(String[] args) throws Exception{
        BinaryTree<Person> tree=new BinaryTree<Person>();
        tree.add(new Person("小強-80",80));
        tree.add(new Person("小強-30",30));
        tree.add(new Person("小強-50",50));
        tree.add(new Person("小強-60",60));
        tree.add(new Person("小強-90",90));
        System.out.println(Arrays.toString(tree.toArray()));
    }
}
/**
 * 實作二叉樹操作
 * @param <T> 要進行二叉樹的實作
 */
class BinaryTree<T extends Comparable<T>>{
    private class Node{
        private Comparable<T> data;  //存放Comparable,可以比較大小
        private Node parent;   //儲存父節點
        private Node left;   //儲存左子樹
        private Node right;  //儲存右子樹
        public Node(Comparable<T> data){    //構造方法直接負責進行資料的存儲
            this.data=data;
        }
        /**
         * 實作節點資料的适當位置的存儲
         * @param newNode 建立的新節點
         * @throws IllegalArgumentException 儲存的資料已存在
         */
        public void addNode(Node newNode) {
            if(newNode.data.compareTo((T)this.data) <= 0){   //比目前節點資料小
                if(this.left==null){   //沒有左子樹
                    //目前沒有左子樹
                    this.left=newNode;   //儲存左子樹
                    newNode.parent=this;   //儲存父節點
                }else{   //需要向左邊繼續判斷
                    this.left.addNode(newNode);    //繼續向下判斷
                }
            }else{     //比根節點的資料大
                if(this.right==null){    //目前沒有右子樹
                    this.right=newNode;    //儲存左子樹
                    newNode.parent=this;   //儲存父節點
                }else{
                    this.right.addNode(newNode);  //繼續向下判斷
                }
            }
        }
        /**
         * 實作所有資料的擷取處理，按照中序周遊的形式來完成
         */
        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();
            }
        }
    }
    //-------------------以下為二叉樹的功能實作--------------
    private Node root;  //儲存根節點
    private int count;   //儲存資料個數
    private Object[] returnData;   //傳回的資料
    private int foot=0;   //腳标控制
    /**
     * 進行資料的儲存
     * @param data 要儲存的資料内容
     * @exception NullPointerException 儲存資料為空時抛出的異常
     */
    public void add(Comparable<T> data){
        if(data==null){
            throw new NullPointerException("儲存的資料不允許為空！");
        }
        //所有的資料本身不具備節點關系的比對，那麼一定要将其包裝在Node類之中
        Node newNode=new Node(data);   //儲存節點
        if(this.root==null){    //現在沒有根節點，則第一個節點作為根節點
            this.root=newNode;
        }else{    //需要為其儲存到一個合适的節點
            this.root.addNode(newNode);  //交由node類負責處理
        }
        this.count++;
    }
    /**
     * 以對象數組的形式傳回全部資料，如果沒有資料傳回null
     * @return 全部資料
     */
    public Object[] toArray(){
        if(this.count==0){
            return null;
        }
        this.returnData=new Object[this.count];//儲存長度為數組長度
        this.foot=0;    //腳标清零
        this.root.toArrayNode();   //直接通過Node類負責
        return this.returnData;   //傳回全部的資料
    }
}
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 +"\n";
    }

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

執行結果：

[【Person類對象】姓名：小強-30、年齡：30

, 【Person類對象】姓名：小強-50、年齡：50

, 【Person類對象】姓名：小強-60、年齡：60

, 【Person類對象】姓名：小強-80、年齡：80

, 【Person類對象】姓名：小強-90、年齡：90

]

在進行資料添加的時候隻是實作了節點關系的儲存，而這種關系的儲存後的結果就是所有的資料都屬于有序排列。

想學習更多的Java的課程嗎？從小白到大神，從入門到精通，更多精彩不容錯過！免費為您提供更多的學習資源。

本内容視訊來源于

阿裡雲大學 下一篇：淺談二叉樹節點删除之道 | 帶你學《Java語言進階特性》之四十 更多Java面向對象程式設計文章檢視此處