「二叉樹可以解決什麼問題」?

01-06

電子信息專業應屆生，苦逼找工作中。
面試被問到「二叉樹可以解決什麼問題」，一時語塞，後來想想確實學演算法的時候沒有聯繫實際深入思考，只局限於明白邏輯，甚至連實現過程都只是看了看書上的偽代碼，現在想趁畢業前補補。問題來了，1二叉樹可以解決什麼問題？2應該用什麼姿勢學演算法？

很明顯，題主沒有學的比較好。

或者沒參加過acm的相關訓練。只是一個平時跟著學做些課後題然後混畢業的。

二叉樹，本質上，是對鏈表和數組的一個折中。。

比如，我有一個任務，需要輸入

10萬個數據（32位整數），然後有兩個操作：

1.添加(刪除)一個整數。

2.詢問第x大的數據。

比如，我給你 1, 8, 13, 10（等等一堆數據）.......

然後我詢問第3大的數據，

然後我插入 18

然後我詢問第4大的數據

我再插入 9

我再詢問第2大的數據

不停的重複1,2

重複10萬次。。

應該如何實現。

你會發現，用有序鏈表，不行，查找（包括1需要找到對應位置，以及2查找）成本大O(N)，但具體這個插入操作成本小O(1)。

用有序數組，查找（2的查找）成本小O(1)。但1的插入操作成本很大O(N)。

所以，我們折中使用排序二叉樹（二叉樹僅僅作為排序二叉樹的基礎），查找（包括1需要找到對應位置，以及2查找）成本挺小O(logN)。具體這個插入操作成本也挺小O(logN)。

具體的應用就是由排序二叉樹（由於普通排序二叉樹可能會有不平衡的情況）引申出來的紅黑樹（linux中ext3文件系統管理），avl樹「windows對進程地址空間的管理」。

回答不出來也不怪你。畢竟這些知識絕對是超綱了。

這是一個口子小但可以扯的很多的題目，你能大概講個二叉樹的遍歷也就算可以了。只是和某些acm的選手來說，你會很吃虧。因為acm選手是知道並且用過紅黑樹之類的東西的。

應該用什麼姿勢學演算法？

演算法在具體工作中用的真的不多，就剩半年，你也不可能學到acm選手的程度。。所以建議，去實習吧，關於演算法，把你們以前的那本演算法教材給撿起來複習複習，每一個具體的演算法例子都給用代碼敲一遍，跑一跑，大學也就基本結束了。。。。。不要太多留戀了，半年很快的。實習工作找不到？總能找到的，只是可能待遇不好。轉正的工資不怎麼樣而已。

演算法學的好又能怎麼樣。

比如我，吃著火鍋，裝著b，結果還不是混的很慘。匿名了。

最後謝邀。

============================4月2日修改==============================

感謝諸位大神捧場。

點贊挺多了，我就對「二叉樹，本質上，是對鏈表和數組的一個折中」補充幾個腦洞：

建立在如下推論上：假定把數組看成N叉樹，那麼鏈表就是1叉樹，由於數組只有1層，二叉樹有logN層，而鏈表有N層，"logN對1" 以及 "N對logN" 都是無限大的關係。。。相當於我們在1 ~ N之間找了一個logN作為兩者的折中。。。。。。

進一步的腦洞是，如果我們是a叉樹，那麼結果就是 $log(a)N = frac{log(2)N}{log(2)a}$ 層，但

考慮分母部分。

a = 1時，log(2)1 = 0
a = 2時，log(2)2 = 1
a = N時，log(2)N = N

恰好構成了 0， 1， N的三個經典數字。。。。

查找和插入一共所需的次數可以簡化為：每層數量+總層數 = $a + frac{log(2)N}{log(2)a}$ 當a是大於等於1的整數時，a取2是最划算的。。。所以綜合以上推斷，個人得出，"二叉樹，本質上，是對鏈表和數組的一個折中"。這對於查找和插入是類似1：1（同一數量級）的需求，用二叉樹（排序二叉樹等）是很划算的。如果不是同一數量級可以考慮，增大a或者減少a，具體問題具體分析，這是個工程問題。得考慮編碼難度，演算法常數，可維護性等多方面需求。不再一一分析。

以上僅僅是個人奉獻的腦洞，沒有任何成熟的理論支撐。感謝看到這裡。

昨天在玩仙劍5前傳，走到蚩尤冢的時候遇到了一個拼圖小遊戲(爪機答，晚上換電腦上圖)，我一看這不是八數碼嗎，於是開心的玩了半個小時沒解出來。所以我打開everything，找到四年前擼oi的時候寫的A*，編譯運行輸入數據，照著輸出的路徑玩過了小遊戲。這和二叉樹什麼關係呢，我用Treap實現的集合(set)，用Heap實現的優先隊列(priority_queue)

(逃

------------上圖的分割線----------

就是這貨

目標狀態

-----------講道理八數碼確實只用廣搜就夠了，畢竟狀態少(9!種) @江雪兒，這是我高中學A*時順便寫的

講道理A*就是個改變搜索順序並且保證最優的優先隊列BFS(逃

講道理15數碼用A*會爆內存，某OJ的標準解法是IDA*

講道理什麼線段樹啊搜索樹啊排序樹啊博弈樹啊紅黑樹啊都是以二叉樹為基礎的至於學演算法各大oj刷一刷就好

堆排序，大根堆，小根堆。

哈夫曼樹，用於壓縮。

檢索樹，保持先根序遞增的。

另外其他樹，可以用左兒子又兄弟表示成二叉樹形式。

二叉樹，是接觸樹這個數據結構的第一種樹，便於理解，也讓你對其他樹有個認識，比如紅黑樹，B+樹，還有進程樹，語法樹，熟悉二叉樹，對於深入學習樹這一結構是有很大好處的。

二叉樹主要應用在以二叉樹為基礎的各種數據結構上。首先，二叉搜索樹（BST）和堆這兩種相當常用的數據結構就是基於二叉樹。BST是Treeset和Treemap的基礎，可以幫助構建有序的集合。Heap是優先隊列的基礎，可以幫助排序。其他高級數據結構如二叉索引樹(BIT)和線段樹(Segment tree)也是以二叉樹為基礎。機器學習中的決策樹，在二元決策問題的時候也可以通過二叉樹來實現。個人覺得二叉樹主要應用還是在有序集合或數列上的應用。

涉及到樹的話、大部分都是為了方便插入刪除和查找吧= =

我水平太渣T T。這個東西除了能幹上面的事以及折磨我們這些acm炮灰之外、我貌似想不出什麼其他用途了。

堆排序不就是依靠二叉樹嘛題主傻了