從零開(kāi)始學(xué)java之二叉樹(shù)和哈希表實(shí)現(xiàn)代碼

更新時(shí)間：2025年04月30日 09:55:03 作者：愛(ài)吃小土豆豆豆豆

這篇文章主要介紹了java之二叉樹(shù)和哈希表實(shí)現(xiàn)的相關(guān)資料,二叉查找樹(shù)和平衡二叉樹(shù)是二叉樹(shù)的兩種特殊形式,哈希表是一種通過(guò)哈希函數(shù)將數(shù)據(jù)與哈希值關(guān)聯(lián)起來(lái)的數(shù)據(jù)結(jié)構(gòu),可以快速查找數(shù)據(jù),文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下

樹(shù)

樹(shù)形結(jié)構(gòu)：

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。
除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M > 0)個(gè)互不相交的集合T1、T2、......、Tm，其中每一個(gè)集合Ti (1 <= i <= m)又是一棵與樹(shù)類似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼。
樹(shù)是遞歸定義的。

注意：樹(shù)形結(jié)構(gòu)中，子樹(shù)之間不能有交集，否則就不是樹(shù)形結(jié)構(gòu)。

樹(shù)的概念：

結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度；如上圖：A的度為6

樹(shù)的度：一棵樹(shù)中，所有結(jié)點(diǎn)度的最大值稱為樹(shù)的度；如上圖：樹(shù)的度為6

葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)；如上圖：B、C、H、I...等節(jié)點(diǎn)為葉結(jié)點(diǎn)

雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)；如上圖：A是B的父結(jié)點(diǎn)

孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)；如上圖：B是A的孩子結(jié)點(diǎn)

根結(jié)點(diǎn)：一棵樹(shù)中，沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)；如上圖：A

結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子結(jié)點(diǎn)為第2層，以此類推

樹(shù)的高度或深度：樹(shù)中結(jié)點(diǎn)的最大層次；如上圖：樹(shù)的高度為4

樹(shù)的以下概念只需了解，在看書(shū)時(shí)只要知道是什么意思即可：

非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；如上圖：D、E、F、G...等節(jié)點(diǎn)為分支結(jié)點(diǎn)

兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)；如上圖：B、C是兄弟結(jié)點(diǎn)

堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟結(jié)點(diǎn)

結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；如上圖：A是所有結(jié)點(diǎn)的祖先

子孫：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。如上圖：所有結(jié)點(diǎn)都是A的子孫

森林：由m（m>=0）棵互不相交的樹(shù)組成的集合稱為森林

二叉樹(shù)

概念：

一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合：

1. 或者為空

2. 或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

二叉樹(shù)不存在度大于2的結(jié)點(diǎn)。二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒，因此二叉樹(shù)是有序樹(shù)。

對(duì)于任意的二叉樹(shù)都是由以下幾種情況復(fù)合而成的：

兩種特殊的二叉樹(shù)：

1. 滿二叉樹(shù): 一棵二叉樹(shù)，如果每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這棵二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō)，如果一棵二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 2的k次方-1 ，則它就是滿二叉樹(shù)。

2. 完全二叉樹(shù): 完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從0至n-1的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹(shù)。要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。

二叉樹(shù)的性質(zhì)：

1. 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹(shù)的第i層上最多有 (i>0)個(gè)結(jié)點(diǎn)

2. 若規(guī)定只有根結(jié)點(diǎn)的二叉樹(shù)的深度為1，則深度為K的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是 (k>=0)

3. 對(duì)任何一棵二叉樹(shù), 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2＋1

4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為上取整

5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下從左至右的順序?qū)λ泄?jié)點(diǎn)從0開(kāi)始編號(hào)，則對(duì)于序號(hào)為i 的結(jié)點(diǎn)有：

若i>0，雙親序號(hào)：(i-1)/2；i=0，i為根結(jié)點(diǎn)編號(hào)，無(wú)雙親結(jié)點(diǎn)
若2i+1，左孩子序號(hào)：2i+1，否則無(wú)左孩子
若2i+2，右孩子序號(hào)：2i+2，否則無(wú)右孩子

創(chuàng)建一個(gè)簡(jiǎn)單的二叉樹(shù)：

public class Main {
    public static void main(String[] args) {
        TreeNode<Character>a=new TreeNode<>('A');
        TreeNode<Character>b=new TreeNode<>('B');
        TreeNode<Character>c=new TreeNode<>('C');
        TreeNode<Character>d=new TreeNode<>('D');
        TreeNode<Character>e=new TreeNode<>('E');
 
        a.left=b;
        a.right=c;
        b.left=d;
        b.right=e;
 
        System.out.println(a.left.left.element);
    }
 
    public static class TreeNode<E>{
        public E element;
        public TreeNode<E> left,right;
 
        public TreeNode(E element){
            this.element=element;
        }
    }
}
 
//輸出D

二叉樹(shù)的遍歷

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié) 點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題(比如：打印節(jié)點(diǎn)內(nèi)容、節(jié)點(diǎn)內(nèi)容加 1)。遍歷是二叉樹(shù)上最重要的操作之一，是二叉樹(shù)上進(jìn)行其它運(yùn)算之基礎(chǔ)。

前序遍歷：

打印根節(jié)點(diǎn)
前序遍歷左子樹(shù)
前序遍歷右子樹(shù)

public class Main {
    public static void main(String[] args) {
        TreeNode<Character>a=new TreeNode<>('A');
        TreeNode<Character>b=new TreeNode<>('B');
        TreeNode<Character>c=new TreeNode<>('C');
        TreeNode<Character>d=new TreeNode<>('D');
        TreeNode<Character>e=new TreeNode<>('E');
        TreeNode<Character>f=new TreeNode<>('F');
        TreeNode<Character>g=new TreeNode<>('G');
        TreeNode<Character>h=new TreeNode<>('H');

        a.left=b;
        a.right=c;
        b.left=d;
        b.right=e;
        e.left=h;
        c.left=f;
        c.right=g;

        preOrder(a);
    }

    public static void preOrder(TreeNode<Character> root){
        if(root==null)return;
        System.out.print(root.element+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static class TreeNode<E>{
        public E element;
        public TreeNode<E> left,right;

        public TreeNode(E element){
            this.element=element;
        }
    }
}
//輸出A B D E H C F G

ABDEHCFG

中序遍歷：

中序遍歷左子樹(shù)
打印結(jié)點(diǎn)
中序遍歷右子樹(shù)

public static void inOrder(TreeNode<Character>root){
        if(root==null)return;
        inOrder(root.left);
        System.out.print(root.element+" ");
        inOrder(root.right);
    }
//輸出D B H E A F C G

DBEHAFCG

后序遍歷：

后序遍歷左子樹(shù)
后序遍歷右子樹(shù)
打印結(jié)點(diǎn)

    public static void postOrder(TreeNode<Character>root){
        if(root==null)return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.element+" ");
    }
//輸出D H E B F G C A

DHEBFGCA

層序遍歷：

利用隊(duì)列來(lái)實(shí)現(xiàn)層序遍歷，首先將根節(jié)點(diǎn)存入隊(duì)列中，接著循環(huán)執(zhí)行以下步驟：

進(jìn)行出隊(duì)操作，得到一個(gè)結(jié)點(diǎn)，并打印結(jié)點(diǎn)的值
將此結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)依次入隊(duì)

    public static void levelOrder(TreeNode<Character>root){
        LinkedQueue<TreeNode<Character>> queue=new LinkedQueue<>(); //創(chuàng)建一個(gè)隊(duì)列
        queue.offer(root); //將根結(jié)點(diǎn)丟進(jìn)隊(duì)列
        while (!queue.isEmpty()){ //如果隊(duì)列不為空，就一直不斷的取出來(lái)
            TreeNode<Character>node=queue.poll();  //取一個(gè)出來(lái)
            System.out.print(node.element+" ");  //打印
            if (node.left!=null)queue.offer(node.left);  //如果左右孩子不為空，直接將左右孩子丟進(jìn)隊(duì)列
            if (node.right!=null)queue.offer(node.right);
        }
    }
//輸出A B C D E F G H

二叉查找樹(shù)和平衡二叉樹(shù)

二叉查找樹(shù)：

二叉查找樹(shù)也叫二叉搜索樹(shù)或二叉排序樹(shù)

左子樹(shù)中所有結(jié)點(diǎn)的值，均小于其根結(jié)點(diǎn)的值
右子樹(shù)中所有結(jié)點(diǎn)的值，均大于其根結(jié)點(diǎn)的值
二叉搜索樹(shù)的子樹(shù)也是二叉搜索樹(shù)

平衡二叉樹(shù)：

在插入結(jié)點(diǎn)時(shí)要盡可能避免一邊倒的情況，引入平衡二叉樹(shù)的概念，在插入時(shí)如果不維護(hù)二叉樹(shù)的平衡，某一邊只會(huì)無(wú)限制的延伸下去，出現(xiàn)極度不平衡的情況。

平衡二叉樹(shù)一定是一顆二叉查找樹(shù)
任意結(jié)點(diǎn)的左右子樹(shù)也是一顆平衡二叉樹(shù)
從根結(jié)點(diǎn)開(kāi)始，左右子樹(shù)高度差都不能超過(guò)1，否則視為不平衡

二叉樹(shù)上結(jié)點(diǎn)的左子樹(shù)高度減去右子樹(shù)高度，得到的結(jié)果稱為該節(jié)點(diǎn)的平衡因子

失衡情況的調(diào)整：

1、LL型調(diào)整（右旋）

2、RR型調(diào)整（左旋）

3、RL型調(diào)整（先右旋再左旋）

4、LR型調(diào)整（先左旋再右旋）

紅黑樹(shù)

紅黑樹(shù)也是二叉查找樹(shù)的一種，結(jié)點(diǎn)有紅有黑。

規(guī)則1：每個(gè)結(jié)點(diǎn)可以是黑色或紅色
規(guī)則2：根結(jié)點(diǎn)一定是黑色
規(guī)則3：紅色結(jié)點(diǎn)的父結(jié)點(diǎn)和子結(jié)點(diǎn)不能為紅色（不能有兩個(gè)連續(xù)的紅色）
規(guī)則4：所有的空結(jié)點(diǎn)都是黑色（空結(jié)點(diǎn)視為null，紅黑樹(shù)中是將空結(jié)點(diǎn)視為葉子結(jié)點(diǎn)）
規(guī)則5：每個(gè)結(jié)點(diǎn)到空結(jié)點(diǎn)路徑上出現(xiàn)的黑色結(jié)點(diǎn)的個(gè)數(shù)都相等

哈希表

散列表

散列（Hashing）通過(guò)散列函數(shù)（哈希函數(shù)）將需要參與檢索的數(shù)據(jù)與散列值（哈希值）關(guān)聯(lián)起來(lái)，生成一種便于搜索的數(shù)據(jù)結(jié)構(gòu)，我們稱其為散列表（哈希表）。

散列函數(shù)也加哈希函數(shù)，哈希函數(shù)可以對(duì)一個(gè)目標(biāo)計(jì)算出其對(duì)應(yīng)的哈希值，并且，只要是同一個(gè)目標(biāo)，無(wú)論計(jì)算多少次，得到的哈希值都是一樣的結(jié)果，不同的目標(biāo)計(jì)算出的結(jié)果幾乎都不同，哈希函數(shù)在現(xiàn)實(shí)生活中應(yīng)用十分廣泛，比如很多下載網(wǎng)站都提供下載文件的MD5碼校驗(yàn)，可以用來(lái)判別文件是否完整，哈希函數(shù)多種多樣，目前應(yīng)用最為廣泛的是SHA-1和MD5。

我們可以利用哈希值的特性，設(shè)計(jì)一張全新的表結(jié)構(gòu)，這種表結(jié)構(gòu)是專門為哈希設(shè)立的，我們稱其為哈希表。我們可以將這些元素保存到哈希表中，而保存的位置則與其對(duì)應(yīng)的哈希值有關(guān)，哈希值是通過(guò)哈希函數(shù)計(jì)算得到的，我們只需要將對(duì)應(yīng)元素的關(guān)鍵字（一般是整數(shù)）提供給哈希函數(shù)就可以進(jìn)行計(jì)算了，一般比較簡(jiǎn)單的哈希函數(shù)就是取模操作，哈希表長(zhǎng)度是多少（長(zhǎng)度最好是一個(gè)素?cái)?shù)），模就是多少。

保存的數(shù)據(jù)是無(wú)序的，哈希表在查找時(shí)只需要進(jìn)行一次哈希函數(shù)計(jì)算就能直接找到對(duì)應(yīng)元素的存儲(chǔ)位置，效率極高。

public class HashTable<E> {
    private final int TABLE_SIZE=10;
    private final Object[]TABLE=new Object[TABLE_SIZE];

    //插入
    public void insert(E obj){
        int index=hash(obj);
        TABLE[index]=obj;
    }

    //判斷是否包含
    public boolean contains(E obj){
        int index=hash(obj);
        return TABLE[index]==obj;
    }

    private int hash(E obj){ //哈希函數(shù)，計(jì)算出存放的位置
        int hashCode=obj.hashCode();
        //每一個(gè)對(duì)象都有一個(gè)獨(dú)一無(wú)二的哈希值，可以通過(guò)hashCode方法得到（極小概率出現(xiàn)相同情況）
        return hashCode%TABLE_SIZE;
    }
}

import com.test.collection.HashTable;

    public static void main(String[] args) {
        HashTable<String>table=new HashTable<>();
        String str="AAA";
        System.out.println(table.contains(str));
        table.insert(str);
        System.out.println(table.contains(str));
    }

//輸出false
//true

通過(guò)哈希函數(shù)計(jì)算得到一個(gè)目標(biāo)的哈希值，但是在某些情況下哈希值可能會(huì)出現(xiàn)相同的情況，稱為哈希碰撞（哈希沖突）

常見(jiàn)的哈希沖突解決方案是鏈地址法，當(dāng)出現(xiàn)哈希沖突時(shí)，我們依然將其保存在對(duì)應(yīng)的位置上，我們可以將其連接為一個(gè)鏈表的形式：

package com.test.collection;

public class HashTable<E> {
    private final int TABLE_SIZE=10;
    private final Node[]TABLE=new Node[TABLE_SIZE];

    //放入頭結(jié)點(diǎn)
    public HashTable(){
        for (int i = 0; i < TABLE_SIZE; i++)
            TABLE[i]=new Node<>(null);
    }

    //插入
    public void insert(E obj){
        int index=hash(obj);
        Node<E>head=TABLE[index];
        Node<E>node=new Node<>(obj);
        node.next=head.next;
        head.next=node;
    }

    //判斷是否包含
    public boolean contains(E element){
        int index=hash(element);
        Node<E>node=TABLE[index].next;
        while (node!=null){
            if(node.element==element)
                return true;
            node=node.next;
        }
        return false;
    }

    private int hash(E obj){ //哈希函數(shù)，計(jì)算出存放的位置
        int hashCode=obj.hashCode();
        //每一個(gè)對(duì)象都有一個(gè)獨(dú)一無(wú)二的哈希值，可以通過(guò)hashCode方法得到（極小概率出現(xiàn)相同情況）
        return hashCode%TABLE_SIZE;
    }

    public String toString(){
        StringBuilder builder=new StringBuilder();
        for (int i = 0; i < TABLE_SIZE; i++) {
            Node<E>head=TABLE[i].next;
            while (head!=null){
                builder.append(head.element+"->");
                head=head.next;
            }
            builder.append("\n");
        }
        return builder.toString();
    }


    private static class Node<E>{
        private final E element;
        private Node<E> next;

        private Node(E element){
            this.element=element;
        }
    }
}

    public static void main(String[] args) {

        HashTable<Integer>table1=new HashTable<>();
        for (int i = 0; i < 100; i++)
            table1.insert(i);

        System.out.println(table1);
    }

/*輸出
90->80->70->60->50->40->30->20->10->0->
91->81->71->61->51->41->31->21->11->1->
92->82->72->62->52->42->32->22->12->2->
93->83->73->63->53->43->33->23->13->3->
94->84->74->64->54->44->34->24->14->4->
95->85->75->65->55->45->35->25->15->5->
96->86->76->66->56->46->36->26->16->6->
97->87->77->67->57->47->37->27->17->7->
98->88->78->68->58->48->38->28->18->8->
99->89->79->69->59->49->39->29->19->9->

*/