狠狠插狠狠爱,欧美日韩人人,欧美日韩国产在线一区

一、概念

(1) 棧（Stack）
????????棧（Stack）和隊列（Queue）是兩種操作受限的線性表棧的插入和刪除操作只允許在表的尾端進(jìn)行（在棧中成為“棧頂”），滿足“LIFO：Last?In??First Out”；

用數(shù)組模擬實現(xiàn)棧
????????1.棧的創(chuàng)建? ? function stack(){各種屬性和方法的聲明}
????????2.實現(xiàn)棧的push方法，該方法是負(fù)責(zé)向棧中添加元素，重要的一點是該方法只能往棧頂添加元素，也就是棧的尾部。this.push = function (element) {items.push(element)}
????????因為我們用了數(shù)組來保存棧里的元素，因此移除的是最后添加進(jìn)去的元素。

3. 棧的pop方法實現(xiàn)：this.pop = fucntion (items) {return items.pop}
????????只能使用push 和 pop方法來實現(xiàn)棧的添加和刪除
????????棧的全部代碼

棧的全部代碼

4.從十進(jìn)制到二進(jìn)制

十進(jìn)制轉(zhuǎn)換成二進(jìn)制

十進(jìn)制轉(zhuǎn)換成任意進(jìn)制

（2）隊列
????????隊列是遵循first in first out 原則的一組有序隊列，隊列從尾部添加新元素，從頂部移除元素，最新添加的元素必須排在隊列的末尾。

1.創(chuàng)建隊列，我們通過創(chuàng)建自己類來創(chuàng)建隊列，先從最基本的聲明開始：
????????function Queue() {這里聲明屬性核對方法}

首先需要一個用于存儲隊列中元素的數(shù)據(jù)結(jié)構(gòu)。我們可以使用數(shù)組，就像在上一章Stack類中那樣使用（你會發(fā)現(xiàn)Queue類和Stack類非常類似，只是添加和移除元素的原則不同）

完整的Queue類

2.優(yōu)先隊列

優(yōu)先隊列

默認(rèn)的Queue類和PriorityQueue類實現(xiàn)上的區(qū)別是，要向PriorityQueue添加元素，需要創(chuàng)建一個特殊的元素（行{1}）。這個元素包含了要添加到隊列的元素（它可以是任意類型）及其在隊列中的優(yōu)先級。

如果隊列為空，可以直接將元素入列（行{2}）。否則，就需要比較該元素與其他元素的優(yōu) 先級。當(dāng)找到一個比要添加的元素的priority值更大（優(yōu)先級更低）的項時，就把新元素插入到它之前（根據(jù)這個邏輯，對于其他優(yōu)先級相同，但是先添加到隊列的元素，我們同樣遵循先進(jìn) 先出的原則）。要做到這一點，我們可以用第2章學(xué)習(xí)過的JavaScript的array類的splice方法。一旦找到priority值更大的元素，就插入新元素（行{3}）并終止隊列循環(huán)（行{4}）。這樣，隊列也就根據(jù)優(yōu)先級排序了。

棧與隊列的相同點：

1.都是線性結(jié)構(gòu)。
2.插入操作都是限定在表尾進(jìn)行。
3.都可以通過順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。
4.插入與刪除的時間復(fù)雜度都是O（1），在空間復(fù)雜度上兩者也一樣。
5.多鏈棧和多鏈隊列的管理模式可以相同。

棧與隊列的不同點：
1.刪除數(shù)據(jù)元素的位置不同，棧的刪除操作在表尾進(jìn)行，隊列的刪除操作在表頭進(jìn)行。
2.應(yīng)用場景不同；常見棧的應(yīng)用場景包括括號問題的求解，表達(dá)式的轉(zhuǎn)換和求值，函數(shù)調(diào)用和遞歸實現(xiàn)，深度優(yōu)先搜索遍歷等；常見的隊列的應(yīng)用場景包括計算機系統(tǒng)中各種資源的管理，消息緩沖器的管理和廣度優(yōu)先搜索遍歷等。

3.順序棧能夠?qū)崿F(xiàn)多?？臻g共享，而順序隊列不能。
說明：js中基本類型的變量賦值是隊列的原理；

(3) 鏈表

????????鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用（也稱指針或鏈接）組成。下圖展示了一個鏈表的結(jié)構(gòu)：

1.創(chuàng)建一個鏈表

現(xiàn)在我們要實現(xiàn)我們的數(shù)據(jù)結(jié)構(gòu)了，以下是我們的LinkedList類的骨架：

骨架

2.向鏈表尾部添加元素

向鏈表尾部添加元素

3.刪除鏈表中任意位置的元素

4.在任意位置插入一個元素

從第一個位置添加

從任意位置添加

（4）樹（堆）

1. 樹的定義
樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合。

樹具有的特點有：
(1) 每個節(jié)點有0個或者多個子節(jié)點
(2) 沒有父節(jié)點的節(jié)點稱之為根節(jié)點
(3) 每一個非根節(jié)點有且只有一個父節(jié)點
(4) 除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的樹

? ? ?若一個結(jié)點有子樹，那么該結(jié)點稱為子樹根的“雙親”，子樹的根稱為該結(jié)點的“孩子”。有相同雙親的結(jié)點互為“兄弟”。一個結(jié)點的所有子樹上的任何結(jié)點都是該結(jié)點的后裔。從根結(jié)點到某個結(jié)點的路徑上的所有結(jié)點都是該結(jié)點的祖先。

結(jié)點的度：結(jié)點擁有的子樹的數(shù)目
葉子結(jié)點：度為0的結(jié)點
分支結(jié)點：度不為0的結(jié)點
樹的度：樹中結(jié)點的最大的度
層次：根結(jié)點的層次為1，其余結(jié)點的層次等于該結(jié)點的雙親結(jié)點的層次加1
樹的高度：樹中結(jié)點的最大層次
森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；刪去根，樹即成為森林。

2. 二叉樹

（1）二叉樹的定義
? ? ? ? ?二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。它有五種基本形態(tài)：二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。

（2）二叉樹的性質(zhì)

性質(zhì)1：二叉樹第i層上的結(jié)點數(shù)目最多為2^(i-1)(i>=1)
性質(zhì)2：深度為k的二叉樹至多有2^k-1個結(jié)點（k>=1）
性質(zhì)3：包含n個結(jié)點的二叉樹的高度至少為(log2n)+1
性質(zhì)4：在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1

（3）性質(zhì)4的證明
性質(zhì)4：在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1
證明：因為二叉樹中所有結(jié)點的度數(shù)均不大于2，不妨設(shè)n0表示度為0的結(jié)點個數(shù)，n1表示度為1的結(jié)點個數(shù)，n2表示度為2的結(jié)點個數(shù)。三類結(jié)點加起來為總結(jié)點個數(shù)，于是便可得到：n=n0+n1+n2?(1)
由度之間的關(guān)系可得第二個等式：n=n0*0+n1*1+n2*2+1即n=n1+2n2+1?(2)

將（1）（2）組合在一起可得到n0=n2+1

3.滿二叉樹
（1）滿二叉樹
定義：高度為h，并且由2h-1個結(jié)點組成的二叉樹，稱為滿二叉樹

（2）完全二叉樹

定義：一棵二叉樹中，只有最下面兩層結(jié)點的度可以小于2，并且最下層的葉結(jié)點集中在靠左的若干位置上，這樣的二叉樹稱為完全二叉樹。

特點：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。

（3）二叉查找樹

定義：二叉查找樹又被稱為二叉搜索樹。設(shè)x為二叉查找樹中的一個結(jié)點，x結(jié)點包含關(guān)鍵字key，結(jié)點x的key值計為key[x]。如果y是x的左子樹中的一個結(jié)點，則key[y]<=key[x]；如果y是x的右子樹的一個結(jié)點，則key[y]>=key[x]

在二叉查找樹中：
（1）若任意結(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值。
（2）任意結(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值。
（3）任意結(jié)點的左、右子樹也分別為二叉查找樹。
（4）沒有鍵值相等的結(jié)點。

4. 二叉樹的遍歷：前序、中序、后序（前中后指的是每個子節(jié)點的父節(jié)點的次序）