亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

從零開始學java之二叉樹和哈希表實現代碼

 更新時間：2025年04月30日 09:55:03   作者：愛吃小土豆豆豆豆  
這篇文章主要介紹了java之二叉樹和哈希表實現的相關資料,二叉查找樹和平衡二叉樹是二叉樹的兩種特殊形式,哈希表是一種通過哈希函數將數據與哈希值關聯起來的數據結構,可以快速查找數據,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

樹

樹形結構：

樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

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

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構。

樹的概念：

結點的度：一個結點含有子樹的個數稱為該結點的度； 如上圖：A的度為6

樹的度：一棵樹中，所有結點度的最大值稱為樹的度； 如上圖：樹的度為6

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

雙親結點或父結點：若一個結點含有子結點，則這個結點稱為其子結點的父結點； 如上圖：A是B的父結點

孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點； 如上圖：B是A的孩子結點

根結點：一棵樹中，沒有雙親結點的結點；如上圖：A

結點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推

樹的高度或深度：樹中結點的最大層次； 如上圖：樹的高度為4

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

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

兄弟結點：具有相同父結點的結點互稱為兄弟結點； 如上圖：B、C是兄弟結點

堂兄弟結點：雙親在同一層的結點互為堂兄弟；如上圖：H、I互為兄弟結點

結點的祖先：從根到該結點所經分支上的所有結點；如上圖：A是所有結點的祖先

子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫

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

二叉樹

概念：

一棵二叉樹是結點的一個有限集合，該集合：

1. 或者為空

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

二叉樹不存在度大于2的結點。 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

對于任意的二叉樹都是由以下幾種情況復合而成的：

兩種特殊的二叉樹：

1. 滿二叉樹: 一棵二叉樹，如果每層的結點數都達到最大值，則這棵二叉樹就是滿二叉樹。也就是說，如果一棵二叉樹的層數為K，且結點總數是 2的k次方-1 ，則它就是滿二叉樹。

2. 完全二叉樹: 完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n 個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從0至n-1的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。 

二叉樹的性質：

1. 若規(guī)定根結點的層數為1，則一棵非空二叉樹的第i層上最多有 (i>0)個結點

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

3. 對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉結點個數為 n2,則有n0＝n2＋1

4. 具有n個結點的完全二叉樹的深度k為 上取整

5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節(jié)點從0開始編號，則對于序號為i 的結點有：

若i>0，雙親序號：(i-1)/2；i=0，i為根結點編號，無雙親結點
若2i+1，左孩子序號：2i+1，否則無左孩子
若2i+2，右孩子序號：2i+2，否則無右孩子

創(chuàng)建一個簡單的二叉樹：

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

二叉樹的遍歷

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

前序遍歷：

  • 打印根節(jié)點
  • 前序遍歷左子樹
  • 前序遍歷右子樹
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

中序遍歷：

  • 中序遍歷左子樹
  • 打印結點
  • 中序遍歷右子樹
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

后序遍歷：

  • 后序遍歷左子樹
  • 后序遍歷右子樹
  • 打印結點
    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

層序遍歷：

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

  • 進行出隊操作，得到一個結點，并打印結點的值
  • 將此結點的左右孩子結點依次入隊
    public static void levelOrder(TreeNode<Character>root){
        LinkedQueue<TreeNode<Character>> queue=new LinkedQueue<>(); //創(chuàng)建一個隊列
        queue.offer(root); //將根結點丟進隊列
        while (!queue.isEmpty()){ //如果隊列不為空，就一直不斷的取出來
            TreeNode<Character>node=queue.poll();  //取一個出來
            System.out.print(node.element+" ");  //打印
            if (node.left!=null)queue.offer(node.left);  //如果左右孩子不為空，直接將左右孩子丟進隊列
            if (node.right!=null)queue.offer(node.right);
        }
    }
//輸出A B C D E F G H

二叉查找樹和平衡二叉樹

二叉查找樹：

二叉查找樹也叫二叉搜索樹或二叉排序樹

  • 左子樹中所有結點的值，均小于其根結點的值
  • 右子樹中所有結點的值，均大于其根結點的值
  • 二叉搜索樹的子樹也是二叉搜索樹

平衡二叉樹：

在插入結點時要盡可能避免一邊倒的情況，引入平衡二叉樹的概念，在插入時如果不維護二叉樹的平衡，某一邊只會無限制的延伸下去，出現極度不平衡的情況。

  • 平衡二叉樹一定是一顆二叉查找樹
  • 任意結點的左右子樹也是一顆平衡二叉樹
  • 從根結點開始，左右子樹高度差都不能超過1，否則視為不平衡

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

失衡情況的調整：

1、LL型調整（右旋）

2、RR型調整（左旋）

3、RL型調整（先右旋再左旋）

4、LR型調整（先左旋再右旋）

紅黑樹

紅黑樹也是二叉查找樹的一種，結點有紅有黑。

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

哈希表

散列表

散列（Hashing）通過散列函數（哈希函數）將需要參與檢索的數據與散列值（哈希值）關聯起來，生成一種便于搜索的數據結構，我們稱其為散列表（哈希表）。

散列函數也加哈希函數，哈希函數可以對一個目標計算出其對應的哈希值，并且，只要是同一個目標，無論計算多少次，得到的哈希值都是一樣的結果，不同的目標計算出的結果幾乎都不同，哈希函數在現實生活中應用十分廣泛，比如很多下載網站都提供下載文件的MD5碼校驗，可以用來判別文件是否完整，哈希函數多種多樣，目前應用最為廣泛的是SHA-1和MD5。

我們可以利用哈希值的特性，設計一張全新的表結構，這種表結構是專門為哈希設立的，我們稱其為哈希表。我們可以將這些元素保存到哈希表中，而保存的位置則與其對應的哈希值有關，哈希值是通過哈希函數計算得到的，我們只需要將對應元素的關鍵字（一般是整數）提供給哈希函數就可以進行計算了，一般比較簡單的哈希函數就是取模操作，哈希表長度是多少（長度最好是一個素數），模就是多少。

保存的數據是無序的，哈希表在查找時只需要進行一次哈希函數計算就能直接找到對應元素的存儲位置，效率極高。

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){ //哈希函數，計算出存放的位置
        int hashCode=obj.hashCode();
        //每一個對象都有一個獨一無二的哈希值，可以通過hashCode方法得到（極小概率出現相同情況）
        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

通過哈希函數計算得到一個目標的哈希值，但是在某些情況下哈希值可能會出現相同的情況，稱為哈希碰撞（哈希沖突）

常見的哈希沖突解決方案是鏈地址法，當出現哈希沖突時，我們依然將其保存在對應的位置上，我們可以將其連接為一個鏈表的形式：

package com.test.collection;

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

    //放入頭結點
    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){ //哈希函數，計算出存放的位置
        int hashCode=obj.hashCode();
        //每一個對象都有一個獨一無二的哈希值，可以通過hashCode方法得到（極小概率出現相同情況）
        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->

*/

總結

到此這篇關于java二叉樹和哈希表實現代碼的文章就介紹到這了,更多相關java二叉樹和哈希表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論