樹(shù)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷分別用了什么數(shù)據(jù)結(jié)構(gòu)

樹(shù)的存儲(chǔ)可以分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但為了滿足多子樹(shù)的場(chǎng)景，樹(shù)的存儲(chǔ)方式利用了順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的，其方法有雙親表示法、孩子表示法、孩子兄弟表示法。

1、廣度優(yōu)先遍歷/寬度優(yōu)先搜索(https://www.zhihu.com/question/28549888)

• 英文縮寫為BFS，即Breadth First Search。
• 我們每一次搜索到一個(gè)點(diǎn)的時(shí)候，如果這個(gè)點(diǎn)不符合條件，那么搜索同一層中符合條件的點(diǎn)，再把這一層中符合要求的點(diǎn)一一拓展，按照上述形式搜索下去。
• 其過(guò)程檢驗(yàn)來(lái)說(shuō)是對(duì)每一層節(jié)點(diǎn)依次訪問(wèn)，訪問(wèn)完一層進(jìn)入下一層，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次。
• 先往隊(duì)列中插入左節(jié)點(diǎn)，再插右節(jié)點(diǎn)，這樣出隊(duì)就是先左節(jié)點(diǎn)后右節(jié)點(diǎn)了。
• 廣度優(yōu)先遍歷樹(shù)，需要用到隊(duì)列（Queue）來(lái)存儲(chǔ)節(jié)點(diǎn)對(duì)象,隊(duì)列的特點(diǎn)就是先進(jìn)先出

2、深度優(yōu)先搜索

• 英文縮寫為DFS，即Depth First Search。
• 我們每一次搜索到一個(gè)點(diǎn)的時(shí)候，如果這個(gè)點(diǎn)不符合條件，那么就return，返回到上一層（就是常說(shuō)的回朔），如果這個(gè)點(diǎn)符合條件，就一直搜索下去，直到?jīng)]有點(diǎn)可以搜索。
• 其過(guò)程簡(jiǎn)要來(lái)說(shuō)是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次。
• 深度優(yōu)先遍歷各個(gè)節(jié)點(diǎn)，需要使用到棧（Stack）這種數(shù)據(jù)結(jié)構(gòu)。

平衡二叉樹(shù) AVL

任一節(jié)點(diǎn)對(duì)應(yīng)的兩棵子樹(shù)的最大高度差為1，也被稱為高度平衡樹(shù)。查找、插入和刪除在平均和最壞情況下的時(shí)間復(fù)雜度都是O(log n)

數(shù)組和鏈表的區(qū)別

數(shù)組的特點(diǎn)
1）在內(nèi)存中，數(shù)組是一塊連續(xù)的區(qū)域。 拿上面的看電影來(lái)說(shuō)，這幾個(gè)人在電影院必須坐在一起。
2）數(shù)組需要預(yù)留空間，在使用前要先申請(qǐng)占內(nèi)存的大小，可能會(huì)浪費(fèi)內(nèi)存空間。 比如看電影時(shí)，為了保證10個(gè)人能坐在一起，必須提前訂好10個(gè)連續(xù)的位置。這樣的好處就是能保證10個(gè)人可以在一起。但是這樣的缺點(diǎn)是，如果來(lái)的人不夠10個(gè)，那么剩下的位置就浪費(fèi)了。如果臨時(shí)有多來(lái)了個(gè)人，那么10個(gè)就不夠用了，這時(shí)可能需要將第11個(gè)位置上的人挪走，或者是他們11個(gè)人重新去找一個(gè)11連坐的位置，效率都很低。如果沒(méi)有找到符合要求的作為，那么就沒(méi)法坐了。
3）插入數(shù)據(jù)和刪除數(shù)據(jù)效率低，插入數(shù)據(jù)時(shí)，這個(gè)位置后面的數(shù)據(jù)在內(nèi)存中都要向后移。刪除數(shù)據(jù)時(shí)，這個(gè)數(shù)據(jù)后面的數(shù)據(jù)都要往前移動(dòng)。 比如原來(lái)去了5個(gè)人，然后后來(lái)又去了一個(gè)人要坐在第三個(gè)位置上，那么第三個(gè)到第五個(gè)都要往后移動(dòng)一個(gè)位子，將第三個(gè)位置留給新來(lái)的人。 當(dāng)這個(gè)人走了的時(shí)候，因?yàn)樗麄円�連在一起的，所以他后面幾個(gè)人要往前移動(dòng)一個(gè)位置，把這個(gè)空位補(bǔ)上。
4）隨機(jī)讀取效率很高。因?yàn)閿?shù)組是連續(xù)的，知道每一個(gè)數(shù)據(jù)的內(nèi)存地址，可以直接找到給地址的數(shù)據(jù)。
5）并且不利于擴(kuò)展，數(shù)組定義的空間不夠時(shí)要重新定義數(shù)組。

鏈表的特點(diǎn)
1）在內(nèi)存中可以存在任何地方，不要求連續(xù)。 在電影院幾個(gè)人可以隨便坐。
2）每一個(gè)數(shù)據(jù)都保存了下一個(gè)數(shù)據(jù)的內(nèi)存地址，通過(guò)這個(gè)地址找到下一個(gè)數(shù)據(jù)。 第一個(gè)人知道第二個(gè)人的座位號(hào)，第二個(gè)人知道第三個(gè)人的座位號(hào)……
3）增加數(shù)據(jù)和刪除數(shù)據(jù)很容易。 再來(lái)個(gè)人可以隨便坐，比如來(lái)了個(gè)人要做到第三個(gè)位置，那他只需要把自己的位置告訴第二個(gè)人，然后問(wèn)第二個(gè)人拿到原來(lái)第三個(gè)人的位置就行了。其他人都不用動(dòng)。
3）查找數(shù)據(jù)時(shí)效率低，因?yàn)椴痪哂须S機(jī)訪問(wèn)性，所以訪問(wèn)某個(gè)位置的數(shù)據(jù)都要從第一個(gè)數(shù)據(jù)開(kāi)始訪問(wèn)，然后根據(jù)第一個(gè)數(shù)據(jù)保存的下一個(gè)數(shù)據(jù)的地址找到第二個(gè)數(shù)據(jù)，以此類推。 要找到第三個(gè)人，必須從第一個(gè)人開(kāi)始問(wèn)起。
4）不指定大小，擴(kuò)展方便。鏈表大小不用定義，數(shù)據(jù)隨意增刪。

各自的優(yōu)缺點(diǎn)
1）數(shù)組的優(yōu)點(diǎn)：隨機(jī)訪問(wèn)性強(qiáng)；查找速度快
2）數(shù)組的缺點(diǎn)：插入和刪除效率低；可能浪費(fèi)內(nèi)存；內(nèi)存空間要求高，必須有足夠的連續(xù)內(nèi)存空間；數(shù)組大小固定，不能動(dòng)態(tài)拓展

​ 1）鏈表的優(yōu)點(diǎn)：插入刪除速度快；內(nèi)存利用率高，不會(huì)浪費(fèi)內(nèi)存；大小沒(méi)有固定，拓展很靈活。
​ 2）鏈表的缺點(diǎn)；不能隨機(jī)查找，必須從第一個(gè)開(kāi)始遍歷，查找效率低

動(dòng)態(tài)數(shù)組

數(shù)組按照操作分為增刪改查
增
1）addLast(e)：添加的元素是在數(shù)組尾部操作，不需要移動(dòng)其他元素位置，直接添加即可。時(shí)間復(fù)雜度為O(1)。
2）addFirst(e)：添加的元素是在頭部操作，插入時(shí)其他元素要依次往后挪。時(shí)間復(fù)雜度為O(n)。
3）add(index,e)：根據(jù)索引添加元素，我們并不知道索引具體會(huì)插入在哪個(gè)位置。根據(jù)概率論分析，時(shí)間復(fù)雜度O(n/2) = O(n)。
4）除此之外我們還要考慮resize,當(dāng)數(shù)組進(jìn)行擴(kuò)容時(shí)，時(shí)間復(fù)雜度同樣為O(n)。

刪
1） removeLast(e)：同增加操作一樣，時(shí)間復(fù)雜度為O(1)。
2）removeFirst(e)：同增加操作一樣，時(shí)間復(fù)雜度為O(n)。
3）remove(index,e)：同增加操作一樣，時(shí)間復(fù)雜度O(n/2) = O(n)。
4） 一樣也要考慮到擴(kuò)容，時(shí)間復(fù)雜度為O(n)。

改
set(index,e)：根據(jù)索引修改元素。當(dāng)知道索引時(shí)，可以直接修改元素而不需要對(duì)其他元素進(jìn)行操作。故時(shí)間復(fù)雜度O(1)。

查
1）get(index)：通過(guò)索引查詢?cè)�素，直接查找。時(shí)間復(fù)雜度O(1)。
2）contains(e)：查看數(shù)組中是否包含該元素。由于不是通過(guò)索引查找，我們需要遍歷數(shù)組，增加了時(shí)間量。時(shí)間復(fù)雜度O(n)。
3）find(e)：查看數(shù)組中對(duì)應(yīng)的索引是多少。同contains一樣需要遍歷數(shù)組。時(shí)間復(fù)雜度O(n)。