樹的深度優先遍曆和廣度優先遍曆分別用了什麽數據結構

樹的存儲(chu) 可以分為(wei) 順序存儲(chu) 和鏈式存儲(chu) 結構，但為(wei) 了滿足多子樹的場景，樹的存儲(chu) 方式利用了順序存儲(chu) 和鏈式存儲(chu) 的，其方法有雙親(qin) 表示法、孩子表示法、孩子兄弟表示法。

1、廣度優(you) 先遍曆/寬度優(you) 先搜索(https://www.zhihu.com/question/28549888)

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

2、深度優(you) 先搜索

• 英文縮寫為DFS，即Depth First Search。
• 我們每一次搜索到一個點的時候，如果這個點不符合條件，那麽就return，返回到上一層（就是常說的回朔），如果這個點符合條件，就一直搜索下去，直到沒有點可以搜索。
• 其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點隻能訪問一次。
• 深度優先遍曆各個節點，需要使用到棧（Stack）這種數據結構。

平衡二叉樹 AVL

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

數組和鏈表的區別

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

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

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

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

動態數組

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

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

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

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