java程序員面試必備知識:二叉樹就是這麼簡單

本文撇開一些非常苦澀、難以理解的概念來講講二叉樹,僅入門觀看(或複習)....

首先,我們來講講什麼是樹:

  • 樹是一種非線性的數據結構,相對於線性的數據結構(鏈表、數組)而言,樹的平均運行時間更短(往往與樹相關的排序時間複雜度都不會高)

在現實生活中,我們一般的樹長這個樣子的:

java程序員面試必備知識:二叉樹就是這麼簡單

但是在編程的世界中,我們一般把樹“倒”過來看,這樣容易我們分析:

java程序員面試必備知識:二叉樹就是這麼簡單

一般的樹是有很多很多個分支的,分支下又有很多很多個分支,如果在程序中研究這個會非常麻煩。因為本來樹就是非線性的,而我們計算機的內存是線性存儲的,太過複雜的話我們無法設計出來的。

因此,我們先來研究簡單又經常用的---> 二叉樹

1.1樹的一些概念

我就拿上面的圖來進行畫來講解了:

java程序員面試必備知識:二叉樹就是這麼簡單

二叉樹的意思就是說:每個節點不能多於有兩個兒子,上面的圖就是一顆二叉樹。

  • 一棵樹至少會有一個節點(根節點)

  • 樹由節點組成,每個節點的數據結構是這樣的:

  • 因此,我們定義樹的時候往往是->定義節點->節點連接起來就成了樹,而節點的定義就是:一個數據、兩個指針(如果有節點就指向節點、沒有節點就指向null)

java程序員面試必備知識:二叉樹就是這麼簡單

  • 1.2靜態創建二叉樹

上面說了,樹是由若干個節點組成,節點連接起來就成了樹,而節點由一個數據、兩個指針組成

  • 因此,創建樹實際上就是創建節點,然後連接節點

首先,使用Java類定義節點:

java程序員面試必備知識:二叉樹就是這麼簡單

下面我們就拿這個二叉樹為例來構建吧:

java程序員面試必備知識:二叉樹就是這麼簡單

為了方便構建,我就給了它一個帶參數的構造方法和set、get方法了:

java程序員面試必備知識:二叉樹就是這麼簡單

那麼我們現在就創建了5個節點:

java程序員面試必備知識:二叉樹就是這麼簡單

它們目前的狀態是這樣子的:

java程序員面試必備知識:二叉樹就是這麼簡單

於是下面我們去把它連起來:

java程序員面試必備知識:二叉樹就是這麼簡單

連接完之後,那麼我們的樹就創建完成了。

java程序員面試必備知識:二叉樹就是這麼簡單

1.3遍歷二叉樹

上面說我們的樹創建完成了,那怎麼證明呢??我們如果可以像數組一樣遍歷它(看它的數據),那就說明它創建完成了

值得說明的是:二叉樹遍歷有三種方式

  • 先序遍歷

  • 先訪問根節點,然後訪問左節點,最後訪問右節點(根->左->右)

  • 中序遍歷

  • 先訪問左節點,然後訪問根節點,最後訪問右節點(左->根->右)

  • 後序遍歷

  • 先訪問左節點,然後訪問右節點,最後訪問根節點(左->右->根)

以上面的二叉樹為例:

  • 如果是先序遍歷:10->9->20->15->35

  • 如果是中序遍歷:9->10->15->20->35

  • 可能需要解釋地方:訪問完10節點過後,去找的是20節點,但20下還有子節點,因此訪問的是20的左兒子15節點。由於15節點沒有兒子了。所以就返回20節點,訪問20節點。最後訪問35節點

  • 如果是

    後序遍歷:9->15->35->20->10

  • 可能需要解釋地方:先訪問9節點,隨後應該訪問的是20節點,但20下還有子節點,因此訪問的是20的左兒子15節點。由於15節點沒有兒子了。所以就去訪問35節點,由於35節點也沒有兒子了,所以返回20節點,最終返回10節點

    一句話總結:先序(根->左->右),中序(左->根->右),後序(左->右->根)。如果訪問有孩子的節點,先處理孩子的,隨後返回

    無論先中後遍歷,每個節點的遍歷如果訪問有孩子的節點,先處理孩子的(邏輯是一樣的)

    • 因此我們很容易想到遞歸

    • 遞歸的出口就是:當沒有子節點了,就返回

    因此,我們可以寫出這樣的先序遍歷代碼

    java程序員面試必備知識:二叉樹就是這麼簡單

    結果跟我們剛才說的是一樣的:

    java程序員面試必備知識:二叉樹就是這麼簡單

    我們再用中序遍歷調用一遍吧:

    java程序員面試必備知識:二叉樹就是這麼簡單

    結果跟我們剛才說的是一樣的:

    java程序員面試必備知識:二叉樹就是這麼簡單

    有意思的是:通過先序和中序或者中序和後序我們可以還原出原始的二叉樹,但是通過先序和後續是無法還原出原始的二叉樹的

    • 也就是說:通過中序和先序或者中序和後序我們就可以確定一顆二叉樹了

    二、動態創建二叉樹

    上面我們是手動創建二叉樹的,一般地:都是給出一個數組給你,讓你將數組變成一個二叉樹,此時就需要我們動態創建二叉樹了。

    二叉樹中還有一種特殊的二叉樹:二叉查找樹(binary search tree)

    • 定義:當前根節點的左邊全部比根節點小,當前根節點的右邊全部比根節點大

    • 明眼人可以看出,這對我們來找一個數是非常方便快捷的

    往往我們動態創建二叉樹都是創建二叉查找樹

    java程序員面試必備知識:二叉樹就是這麼簡單

    2.1動態創建二叉樹體驗

    假設我們有一個數組:

    int[] arrays = {3, 2, 1, 4, 5};

    那麼創建二叉樹的步驟是這樣的:

    • 首先將3作為根節點

    java程序員面試必備知識:二叉樹就是這麼簡單

    • 隨後2進來了,我們跟3做比較,比3小,那麼放在3的左邊

    java程序員面試必備知識:二叉樹就是這麼簡單

    • 隨後1進來了,我們跟3做比較,比3小,那麼放在3的左邊,此時3的左邊有2了,因此跟2比,比2小,放在2的左邊

    java程序員面試必備知識:二叉樹就是這麼簡單

    • 隨後4進來了,我們跟3做比較,比3大,那麼放在3的右邊

    java程序員面試必備知識:二叉樹就是這麼簡單

    • 隨後5進來了,我們跟3做比較,比3大,那麼放在3的右邊,此時3的右邊有4了,因此跟4比,比4大,放在4的右邊

    java程序員面試必備知識:二叉樹就是這麼簡單

    那麼我們的二叉查找樹就建立成功了,無論任何一顆子樹,左邊都比根要小,右邊比根要大

    java程序員面試必備知識:二叉樹就是這麼簡單

    2.2代碼實現

    我們的代碼實現也很簡單,如果比當前根節點要小,那麼放到當前根節點左邊,如果比當前根節點要大,那麼放到當前根節點右邊。

    因為是動態創建的,因此我們得用一個類來表示根節點

    java程序員面試必備知識:二叉樹就是這麼簡單

    比較與根誰大,大的往右邊,小的往左邊:

    java程序員面試必備知識:二叉樹就是這麼簡單

    測試代碼:

    java程序員面試必備知識:二叉樹就是這麼簡單

    java程序員面試必備知識:二叉樹就是這麼簡單

    三、查詢二叉查找樹相關

    3.1查詢樹的深度

    查詢樹的深度我們可以這樣想:左邊的子樹和右邊的字數比,誰大就返回誰,那麼再接上根節點+1就可以了

    java程序員面試必備知識:二叉樹就是這麼簡單

    java程序員面試必備知識:二叉樹就是這麼簡單

    3.1查詢樹的最大值

    從上面先序遍歷二叉查找樹的時候,細心的同學可能會發現:中序遍歷二叉查找樹得到的結果是排好順序的~

    那麼,如果我們的二叉樹不是二叉查找樹,我們要怎麼查詢他的最大值呢

    可以這樣:

    java程序員面試必備知識:二叉樹就是這麼簡單

    • 左邊找最大值->遞歸

    • 右邊找最大值->遞歸

    java程序員面試必備知識:二叉樹就是這麼簡單

    四、最後

    無論是在遍歷樹、查找深度、查找最大值都用到了遞歸,遞歸在非線性的數據結構中是用得非常多的...

    樹的應用也非常廣泛,此篇簡單地說明了樹的數據結構,高級的東西我也沒弄懂,可能以後用到的時候會繼續深入...


    分享到:


相關文章: