算法和數據結構基礎知識分享（中）

2）哈希表的基本操作？

寫入：O(1)、讀?。篛(1)、擴容O(n)。

3）什么是哈希函數？

哈希表本質上是一個數組，只是數組只能根據下標，像a[0] a[1] a[2] a[3] 這樣來訪問，而哈希表的key則是以字符串類型為主的。

通過哈希函數，我們可以把字符串或其他類型的key，轉化成數組的下標index。

如給出一個長度為8的數組，則：

當key=001121時，

index = HashCode ("001121") % Array.length = 7

當key=this時，

index = HashCode ("this") % Array.length = 6

4）什么是哈希沖突？

不同的key通過哈希函數獲得的下標有可能是相同的，例如002936這個key對應的數組下標是2，002947對應的數組下標也是2，這種情況就是哈希沖突。

5）如何解決哈希沖突？

開放尋址法：例子Threadlocal。

6 樹

1）什么是樹？

樹（tree）是n（n≥0）個節(jié)點的有限集。

當n=0時，稱為空樹。在任意一個非空樹中，有如下特點：

• 有且僅有一個特定的稱為根的節(jié)點。
• 當n>1時，其余節(jié)點可分為m（m>0）個互不相交的有限集，每一個集合本身又是一個樹，并稱為根的子樹。

2）樹的遍歷？

（1）深度優(yōu)先

前序：根節(jié)點、左子樹、右子樹。

中序：左子樹、根節(jié)點、右子樹。

后序：左子樹、右子樹、根節(jié)點。

實現方式：遞歸或棧。

（2）廣度優(yōu)先

層序：一層一層遍歷。

實現方式：隊列。

7 二叉樹

1）什么是二叉樹?

二叉樹（binary tree）是樹的一種特殊形式。二叉，顧名思義，這種樹的每個節(jié)點最多有2個孩子節(jié)點。注意，這里是最多有2個，也可能只有1個，或者沒有孩子節(jié)點。

2）什么是滿二叉樹?

一個二叉樹的所有非葉子節(jié)點都存在左右孩子，并且所有葉子節(jié)點都在同一層級上，那么這個樹就是滿二叉樹。

3）什么是完全二叉樹?

對一個有n個節(jié)點的二叉樹，按層級順序編號，則所有節(jié)點的編號為從1到n。如果這個樹所有節(jié)點和同樣深度的滿二叉樹的編號為從1到n的節(jié)點位置相同，則這個二叉樹為完全二叉樹。

8 二叉查找樹

1）什么是二叉查找樹？

二叉查找樹在二叉樹的基礎上增加了以下幾個條件：

• 如果左子樹不為空，則左子樹上所有節(jié)點的值均小于根節(jié)點的值。
• 如果右子樹不為空，則右子樹上所有節(jié)點的值均大于根節(jié)點的值。
• 左、右子樹也都是二叉查找樹。

2）二叉查找樹的作用？

• 查找==》二分查找。
• 排序==》中序遍歷。

3）二叉樹的實現方式？

• 鏈表。
• 數組：對于稀疏二叉樹來說，數組表示法是非常浪費空間的。

9 二叉堆

1）什么是二叉堆？

二叉堆是一種特殊的完全二叉樹，它分為兩個類型：最大堆和最小堆。

• 最大堆的任何一個父節(jié)點的值，都大于或等于它左、右孩子節(jié)點的值。
• 最小堆的任何一個父節(jié)點的值，都小于或等于它左、右孩子節(jié)點的值。

2）二叉堆的基本操作？

（1）插入：插入最末，節(jié)點上浮。

（2）刪除：刪除頭節(jié)點，尾節(jié)點放到頭部，再下沉。

（3）構建二叉堆：二叉樹==》二叉堆，所有非葉子節(jié)點依次下沉。

3）二叉堆的實現方式？

數組：