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

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

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

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

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

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

平衡二叉樹 AVL

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

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

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

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

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

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

動態(tài)數(shù)組

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

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

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

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