轉載和引用,請注明原文出處！ Fork me on GitHub

結局很美妙的事,開頭并非如此!

InterV 6：數據結構

一. Queue(隊列)

1. 什么是隊列

隊列是數據結構中比較重要的一種類型，它支持 FIFO，尾部添加、頭部刪除（先進隊列的元素先出隊列），隊列結構與日常生活中排隊等候服務的模型是一致的，像火車站買票，早排隊進入隊列的人，早買到票并最先離開（出隊）；后到來的人只能排在隊列的后，后得到服務并后離開。

2. 隊列的種類

單隊列（單隊列就是常見的隊列, 每次添加元素時，都是添加到隊尾，存在“假溢出”的問題也就是明明有位置卻不能添加的情況）
循環隊列（避免了“假溢出”的問題）

3. 隊列－順序存儲方式：

在隊列的順序存儲實現中，我們可以將隊列當作一般的表用數組加以實現，但這樣做的效果并不好。盡管我們可以用一個指針 last 來指示隊尾，使得 enqueue 運算可在Ο(1)時間內完成，但是在執行 dequeue 時，為了刪除隊首元素，必須將數組中其他所有元素都向前移動一個位置。這樣，當隊列中有 n 個元素時，執行 dequeue 就需要Ο(n)時間。

為了提高運算的效率，我們用另一種方法來表達數組中各單元的位置關系。設想數組 A[0.. capacity-1]中的單元不是排成一行，而是圍成一個圓環

可看代碼例子QueueTest.java

4. 隊列－鏈式存儲方式：

隊列的鏈式存儲可以使用單鏈表來實現。為了操作實現方便，這里采用帶頭結點的單鏈表結構。根據單鏈表的特點，選擇鏈表的頭部作為隊首，鏈表的尾部作為隊尾。除了鏈表頭結點需要通過一個引用來指向之外，還需要一個對鏈表尾結點的引用，以方便隊列的入隊操作的實現。為此一共設置兩個指針，一個隊首指針和一個隊尾指針，如圖所示，隊首指針指(front)向隊首元素的前一個結點，即始終指向鏈表空的頭結點; 隊尾指針(rear)指向隊列當前隊尾元素所在的結點。當隊列為空時，隊首指針與隊尾指針均指向空的頭結點

在Java中沒有顯式的指針類型，然而實際上對象的訪問就是使用指針來實現的，即在Java中是使用對象的引用來替代指針的。

在節點中數據域用來存儲數據元素，指針域用于指向下一個具有相同結構的節點

SLNode類：由data和next指針組成。

QueueSLinked類：出隊入隊實現

在Java中沒有顯式的指針類型，然而實際上對象的訪問就是使用指針來實現的，即在Java中是使用對象的引用來替代指針的。因此在使用Java實現該節點結構時，一個節點本身就是一個對象。節點的數據域data可以使用一個Object類型的對象來實現，用于存儲任何類型的數據元素，并通過對象的引用指向該元素；而指針域next可以通過節點對象的引用來實現

5. Java 集合框架中的隊列 Queue

Java 集合中的 Queue 繼承自 Collection 接口，Deque, LinkedList, PriorityQueue, BlockingQueue 等類都實現了它。 Queue 用來存放等待處理元素的集合，這種場景一般用于緩沖、并發訪問。除了繼承 Collection 接口的一些方法，Queue 還添加了額外的添加、刪除、查詢操作。

二. Set

1. 什么是 Set

Set 繼承于 Collection 接口，是一個不允許出現重復元素，并且無序的集合，主要 HashSet 和 TreeSet 兩大實現類。

在判斷重復元素的時候，Set 集合會調用 hashCode()和 equal()方法來實現。

補充：有序集合與無序集合說明

有序集合：集合里的元素可以根據 key 或 index 訪問 (List、Map)
無序集合：集合里的元素只能遍歷。（Set）

2. HashSet 和 TreeSet 底層數據結構

HashSet 是哈希表結構，主要利用 HashMap 的 key 來存儲元素，計算插入元素的 hashCode 來獲取元素在集合中的位置；

TreeSet 是紅黑樹結構，每一個元素都是樹中的一個節點，插入的元素都會進行排序；

三、List

1. 什么是List

在 List 中，用戶可以精確控制列表中每個元素的插入位置，另外用戶可以通過整數索引（列表中的位置）訪問元素，并搜索列表中的元素。與 Set 不同，List 通常允許重復的元素。另外 List 是有序集合而 Set 是無序集合。

2. List的常見實現類

ArrayList 是一個數組隊列，相當于動態數組。它由數組實現，隨機訪問效率高，隨機插入、隨機刪除效率低。

LinkedList 是一個雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率高。

它每一個節點（Node）都包含兩方面的內容：

1.節點本身的數據（data）；

2.下一個節點的信息（nextNode）。

所以當對LinkedList做添加，刪除動作的時候就不用像基于數組的ArrayList一樣，必須進行大量的數據移動。只要更改nextNode的相關信息就可以實現了，這是LinkedList的優勢。

Vector 是矢量隊列，和ArrayList一樣，它也是一個動態數組，由數組實現。但是ArrayList是非線程安全的，而Vector是線程安全的。

Stack 是棧，它繼承于Vector。它的特性是：先進后出(FILO, First In Last Out)。

總結：

大多數情況下，從性能上來說ArrayList最好，但是當集合內的元素需要頻繁插入、刪除時LinkedList會有比較好的表現，但是它們三個性能都比不上數組，另外Vector是線程同步的。所以：
如果能用數組的時候(元素類型固定，數組長度固定)，請盡量使用數組來代替List；
如果沒有頻繁的刪除插入操作，又不用考慮多線程問題，優先選擇ArrayList；
如果在多線程條件下使用，可以考慮Vector；
如果需要頻繁地刪除插入，LinkedList就有了用武之地；
如果你什么都不知道，用ArrayList沒錯。

所有的List中只能容納單個不同類型的對象組成的表，而不是Key－Value鍵值對。例如：[ tom,1,c ]

所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]

所有的List中可以有null元素，例如[ tom,null,1 ]

基于Array的List（Vector，ArrayList）適合查詢，而LinkedList 適合添加，刪除操作

4. 推薦閱讀

java 數據結構與算法之順序表與鏈表深入分析

四. Map

1．HashMap: 元素成對，元素可為空

2．HashTable: 元素成對，線程安全，元素不可為空

集合框架源碼學習之 HashMap(JDK1.8)
ConcurrentHashMap 實現原理及源碼分析

五、樹

1. 樹的基本概念

樹是由一個集合以及在該集合上定義的一種關系構成的。集合中的元素稱為樹的結點，所定義的關系稱為父子關系。父子關系在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或簡稱為樹根

樹（Tree）是n(n>=0)個結點的有限集。n=0時稱為空樹。

在任意一顆非空樹中

(1)有且僅有一個特定的稱為根（Root）的結點。

(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1、T2、.....、Tm,其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。

下圖就符合樹的定義：

其中根結點A有兩個子樹：

需要注意的是雖然子樹的個數沒有限制，但是它們一定是互不交互的。下面的圖明顯不符合互不交互的原則，所以不是樹。

樹的結點

樹的結點包含一個數據元素及若干指向其子樹的分支。結點擁有的子樹數稱為結點的度（Degree）。樹的度是樹內各結點度的最大值。

結點的層次從根開始定義起，根為第一層，根的孩子為第二層，以此類推。樹的深度（Depth）或高度是樹中結點的最大層次。

樹的存儲結構

2. 二叉樹定義

每個結點的度均不超過 2 的有序樹，稱為二叉樹（binary tree）。

二叉樹（Binary Tree）是n(n>=0)個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成（子樹也為二叉樹）。

二叉樹的特點

每個結點最多有兩棵子樹，所以二叉樹中不存在度大于2的結點。
左子樹和右子樹是有順序的，次序不能任意顛倒。
即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹。

二叉樹五種基本形態

空二叉樹
只有一個根結點
根結點只有左子樹
根結點只有右子樹
根結點既有左子樹又有右子樹

幾種特殊的二叉樹

斜樹

左斜樹：右斜樹：

滿二叉樹

滿二叉樹：

完全二叉樹

完全二叉樹：

二叉樹的性質

二叉樹性質1

性質1：在二叉樹的第i層上至多有2^i-1個結點（i>=1）

二叉樹性質2

性質2：深度為k的二叉樹至多有2^k-1個結點（k>=1）

二叉樹性質3

性質3：對任何一棵二叉樹T，如果其終端結點數為n₀,度為2的結點數為n₂，則n₀ = n₂+1。

一棵二叉樹，除了終端結點（葉子結點），就是度為1或2的結點。假設n₁度為1的結點數，則數T 的結點總數n=n₀+n₁+n₂。我們再換個角度，看一下樹T的連接線數，由于根結點只有分支出去，沒有分支進入，所以連接線數為結點總數減去1。也就是n-1=n₁+2n₂，可推導出n₀+n₁+n₂-1 = n₁+2n₂，繼續推導可得n₀ = n₂+1。

二叉樹性質4

性質4：具有n個結點的完全二叉樹的深度為[log₂n ] + 1([X]表示不大于X的最大整數)。

由性質2可知，滿二叉樹的結點個數為2^k-1，可以推導出滿二叉樹的深度為k=log₂(n + 1)。對于完全二叉樹，它的葉子結點只會出現在最下面的兩層，所以它的結點數一定少于等于同樣深度的滿二叉樹的結點數2^k-1，但是一定多于2^k-1-1。因為n是整數，所以2^k-1 <= n < 2^k，不等式兩邊取對數得到：k-1 <= log₂n <k。因為k作為深度也是整數，因此 k= [log₂n ]+ 1。

二叉樹性質5

性質5：如果對一顆有n個結點的完全二叉樹（其深度為[log₂n ] + 1）的結點按層序編號（從第1層到第[log₂n ] + 1層，每層從左到右），對任一結點i(1<=i<=n)有：

如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是結點[i/2]。

如果2i>n,則結點i無左孩子（結點i為葉子結點）；否則其左孩子是結點i。

如果2i+1>n,則結點i無右孩子；否則其右孩子是結點2i+1。

結合下圖很好理解：

3. 二叉樹數據結構

鏈式存儲結構

二叉樹的存儲結構

二叉樹順序存儲結構

^代表不存在的結點。

對于右斜樹，順序存儲結構浪費存儲空間：

二叉樹的順序存儲結構缺點很明顯：不能反應邏輯關系；對于特殊的二叉樹（左斜樹、右斜樹），浪費存儲空間。所以二叉樹順序存儲結構一般只用于完全二叉樹。

二叉鏈表

鏈表每個結點包含一個數據域和兩個指針域：

其中data是數據域，lchild和rchild都是指針域，分別指向左孩子和右孩子。

二叉樹的二叉鏈表結點結構定義:

/*二叉樹的二叉鏈表結點結構定義*/
typedef struct BiNode
{
    char data;      /*結點數據*/
    struct BiNode *lchild, *rchild;     /*左右孩子指針*/
}BiNode,*BiTree;

4. 如何初始化二叉樹及遍歷？

二叉樹遍歷：從樹的根節點出發，按照某種次序依次訪問二叉樹中所有的結點，使得每個結點被訪問僅且一次。

這里有兩個關鍵詞：訪問和次序。

二叉樹遍歷方法

前序遍歷

遞歸方式實現前序遍歷

具體過程：

先訪問根節點

再序遍歷左子樹

最后序遍歷右子樹

代碼實現：

public static void PreOrderRecur(TreeNode<char> treeNode)
 {
     if (treeNode == null)
     {
         return;
     }
     Console.Write(treeNode.Data); 
     PreOrderRecur(treeNode.LChild);
     PreOrderRecur(treeNode.RChild);
 }

非遞歸方式實現前序遍歷

具體過程：

首先申請一個新的棧，記為stack；

將頭結點head壓入stack中；

每次從stack中彈出棧頂節點，記為cur，然后打印cur值，如果cur右孩子不為空，則將右孩子壓入棧中；如果cur的左孩子不為空，將其壓入stack中；

重復步驟3，直到stack為空.

代碼實現：

 public static void PreOrder(TreeNode<char> head)
{
    if (head == null)
    {
        return;
    }
    Stack<TreeNode<char>> stack = new Stack<TreeNode<char>>();
    stack.Push(head);
    while (!(stack.Count == 0))
    {
        TreeNode<char> cur = stack.Pop();
        Console.Write(cur.Data);

        if (cur.RChild != null)
        {
            stack.Push(cur.RChild);
        }
        if (cur.LChild != null)
        {
            stack.Push(cur.LChild);
        }
    }
}

過程模擬：

執行結果：

中序遍歷

遞歸方式實現中序遍歷

具體過程：

先中序遍歷左子樹

再訪問根節點

最后中序遍歷右子樹

代碼實現：

public static void InOrderRecur(TreeNode<char> treeNode)
{
    if (treeNode == null)
    {
        return;
    }  
    InOrderRecur(treeNode.LChild);
    Console.Write(treeNode.Data); 
    InOrderRecur(treeNode.RChild);
}

非遞歸方式實現中序遍歷

具體過程：

申請一個新棧，記為stack，申請一個變量cur，初始時令cur為頭節點；

先把cur節點壓入棧中，對以cur節點為頭的整棵子樹來說，依次把整棵樹的左子樹壓入棧中，即不斷令cur=cur.left，然后重復步驟2；

不斷重復步驟2，直到發現cur為空，此時從stack中彈出一個節點記為node，打印node的值，并讓cur = node.right，然后繼續重復步驟2；

當stack為空并且cur為空時結束。

代碼實現：

public static void InOrder(TreeNode<char> treeNode)
{
    if (treeNode == null)
    {
        return;
    }
    Stack<TreeNode<char>> stack = new Stack<TreeNode<char>>();

    TreeNode<char> cur = treeNode;

    while (!(stack.Count == 0) || cur != null)
    {
        while (cur != null)
        {
            stack.Push(cur);
            cur = cur.LChild;
        }
        TreeNode<char> node = stack.Pop();
        Console.WriteLine(node.Data);
        cur = node.RChild;
    }
}

過程模擬：

執行結果：

后序遍歷

遞歸方式實現后序遍歷

先后序遍歷左子樹

再后序遍歷右子樹

最后訪問根節點

代碼實現：

public static void PosOrderRecur(TreeNode<char> treeNode)
{
    if (treeNode == null)
    {
        return;
    }
    PosOrderRecur(treeNode.LChild);
    PosOrderRecur(treeNode.RChild);
    Console.Write(treeNode.Data); 
}

非遞歸方式實現后序遍歷一

具體過程：

使用兩個棧實現

申請兩個棧stack1，stack2，然后將頭結點壓入stack1中；

從stack1中彈出的節點記為cur，然后先把cur的左孩子壓入stack1中，再把cur的右孩子壓入stack1中；

在整個過程中，每一個從stack1中彈出的節點都放在第二個棧stack2中；

不斷重復步驟2和步驟3，直到stack1為空，過程停止；

從stack2中依次彈出節點并打印，打印的順序就是后序遍歷的順序；

代碼實現：

public static void PosOrderOne(TreeNode<char> treeNode)
{
    if (treeNode == null)
    {
        return;
    }

    Stack<TreeNode<char>> stack1 = new Stack<TreeNode<char>>();
    Stack<TreeNode<char>> stack2 = new Stack<TreeNode<char>>();

    stack1.Push(treeNode);
    TreeNode<char> cur = treeNode;

    while (!(stack1.Count == 0))
    {
        cur = stack1.Pop();
        if (cur.LChild != null)
        {
            stack1.Push(cur.LChild);
        }
        if (cur.RChild != null)
        {
            stack1.Push(cur.RChild);
        }
        stack2.Push(cur);
    }

    while (!(stack2.Count == 0))
    {
        TreeNode<char> node = stack2.Pop();
        Console.WriteLine(node.Data); ;
    }
}

過程模擬：

執行結果：

非遞歸方式實現后序遍歷二

具體過程：

使用一個棧實現

申請一個棧stack，將頭節點壓入stack，同時設置兩個變量 h 和 c，在整個流程中，h代表最近一次彈出并打印的節點，c代表當前stack的棧頂節點，初始時令h為頭節點，，c為null；

每次令c等于當前stack的棧頂節點，但是不從stack中彈出節點，此時分一下三種情況：

(1)如果c的左孩子不為空，并且h不等于c的左孩子，也不等于c的右孩子，則吧c的左孩子壓入stack中

(2)如果情況1不成立，并且c的右孩子不為空，并且h不等于c的右孩子，則把c的右孩子壓入stack中；

(3)如果情況1和2不成立，則從stack中彈出c并打印，然后令h等于c；

一直重復步驟2，直到stack為空.

代碼實現：

public static void PosOrderTwo(TreeNode<char> treeNode)
{
    if (treeNode == null)
    {
        return;
    }

    Stack<TreeNode<char>> stack = new Stack<TreeNode<char>>();
    stack.Push(treeNode);

    TreeNode<char> h = treeNode;
    TreeNode<char> c = null;
    while (!(stack.Count == 0))
    {
        c = stack.Peek();
        //c結點有左孩子 并且 左孩子沒被遍歷（輸出）過 并且 右孩子沒被遍歷過
        if (c.LChild != null && h != c.LChild && h != c.RChild)
            stack.Push(c.LChild);
        //c結點有右孩子 并且 右孩子沒被遍歷（輸出）過
        else if (c.RChild != null && h != c.RChild)
            stack.Push(c.RChild);
        //c結點沒有孩子結點 或者孩子結點已經被遍歷（輸出）過
        else
        {
            TreeNode<char> node = stack.Pop();
            Console.WriteLine(node.Data);
            h = c;
        }
    }
}

過程模擬：

執行結果：

層序遍歷

具體過程：

首先申請一個新的隊列，記為queue；

將頭結點head壓入queue中；

每次從queue中出隊，記為node，然后打印node值，如果node左孩子不為空，則將左孩子入隊；如果node的右孩子不為空，則將右孩子入隊；

重復步驟3，直到queue為空。

代碼實現：

public static void LevelOrder(TreeNode<char> treeNode)
{
    if(treeNode == null)
    {
         return;
    }
    Queue<TreeNode<char>> queue = new Queue<TreeNode<char>>();
    queue.Enqueue(treeNode);

    while (queue.Any())
    {
        TreeNode<char> node = queue.Dequeue();
        Console.Write(node.Data);

        if (node.Left != null)
        {
            queue.Enqueue(node.Left);
        }

        if (node.Right != null)
        {
            queue.Enqueue(node.Right);
        }
    }
}

執行結果：

7. 堆

數據結構之堆的定義

堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。

8. 二叉查找樹（BST）

淺談算法和數據結構: 七二叉查找樹

二叉查找樹的特點：

若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
任意節點的左、右子樹也分別為二叉查找樹；
沒有鍵值相等的節點（no duplicate nodes）。

9. 平衡二叉樹（Self-balancing binary search tree）

平衡二叉樹（百度百科，平衡二叉樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等）

10. 紅黑樹

紅黑樹的簡介：

R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它是一種特殊的二叉查找樹。紅黑樹的每個節點上都有存儲位表示節點的顏色，可以是紅(Red)或黑(Black)。

紅黑樹的特性:
（1）每個節點或者是黑色，或者是紅色。
（2）根節點是黑色。
（3）每個葉子節點（NIL）是黑色。 [注意：這里葉子節點，是指為空(NIL或NULL)的葉子節點！]
（4）如果一個節點是紅色的，則它的子節點必須是黑色的。
（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

注意：
(01) 特性(3)中的葉子節點，是只為空(NIL或null)的節點。
(02) 特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。

紅黑樹示意圖如下：

紅黑樹的應用：

紅黑樹的應用比較廣泛，主要是用它來存儲有序的數據，它的時間復雜度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬內存的管理，都是通過紅黑樹去實現的。

參考文章：http://www.rzrgm.cn/skywang12345/p/3245399.html

11. B-，B+，B*樹

二叉樹學習筆記之B樹、B+樹、B*樹

《B-樹，B+樹，B*樹詳解》

《B-樹，B+樹與B*樹的優缺點比較》

B-樹（或B樹）是一種平衡的多路查找（又稱排序）樹，在文件系統中有所應用。主要用作文件的索引。其中的B就表示平衡(Balance) 1. B+ 樹的葉子節點鏈表結構相比于 B- 樹便于掃庫，和范圍檢索。 2. B+樹支持range-query（區間查詢）非常方便，而B樹不支持。這是數據庫選用B+樹的最主要原因。 3. B*樹是B+樹的變體，B*樹分配新結點的概率比B+樹要低，空間使用率更高；

12. LSM 樹

[HBase] LSM樹 VS B+樹

B+樹最大的性能問題是會產生大量的隨機IO

為了克服B+樹的弱點，HBase引入了LSM樹的概念，即Log-Structured Merge-Trees。

LSM樹由來、設計思想以及應用到HBase的索引

【圖解數據結構】樹

六、圖

BFS及DFS

《使用BFS及DFS遍歷樹和圖的思路及實現》

posted @ 2020-11-09 00:32 小不點啊閱讀(170) 評論(0) 收藏舉報

刷新頁面返回頂部

小不點啊

InterV 6：數據結構

一. Queue(隊列)

1. 什么是隊列

2. 隊列的種類

5. Java 集合框架中的隊列 Queue

二. Set

1. 什么是 Set

補充：有序集合與無序集合說明

2. HashSet 和 TreeSet 底層數據結構

三、List

1. 什么是List

2. List的常見實現類

3. ArrayList 和 LinkedList 源碼學習

4. 推薦閱讀

四. Map

五、樹

樹的結點

樹的存儲結構

二叉樹的特點

二叉樹五種基本形態

幾種特殊的二叉樹

斜樹

滿二叉樹

完全二叉樹

二叉樹的性質

二叉樹性質1

二叉樹性質2

二叉樹性質3

二叉樹性質4

二叉樹性質5

二叉樹的存儲結構

二叉樹順序存儲結構

二叉鏈表

二叉樹遍歷方法

前序遍歷

遞歸方式實現前序遍歷

非遞歸方式實現前序遍歷

中序遍歷

遞歸方式實現中序遍歷

非遞歸方式實現中序遍歷

后序遍歷

遞歸方式實現后序遍歷

非遞歸方式實現后序遍歷一

非遞歸方式實現后序遍歷二

層序遍歷

7. 堆

8. 二叉查找樹（BST）

9. 平衡二叉樹（Self-balancing binary search tree）

10. 紅黑樹

11. B-，B+，B*樹

12. LSM 樹

推薦文章：

【圖解數據結構】 樹

六、圖

BFS及DFS

公告

【圖解數據結構】樹