「那我們回過頭來，把 insertRec 補完吧。」

「等我一下，我想一下邏輯……」

記得是從上而下、左而右比較大小；如果有位置就直接停下來「卡位」。

不知不覺間程式碼已經寫出來了：

    private fun insertRec(node: TreeNode<T>?, value: T): TreeNode<T> {
        if (node == null) return TreeNode(value)

        if (value < node.value) {
            node.left = insertRec(node.left, value)
        } else if (value > node.value) {
            node.right = insertRec(node.right, value)
        }
        return node
    }

寫的時候才注意到一個問題。

「嗯？你問大小相同怎麼處理？因為二元搜尋樹的規則是『左小右大』，不允許其他可能，所以重複的必須忽略。也就是說，每個節點的值都不會重複。」

「所以其他樹就可以囉？」

「這要看定義。你要寫其他資料結構的時候，一定要先確認規則。只有符合這些定義，才是那個結構；不然就只是『別的東西』。」

小孩搔搔頭：「對了，我其實是要看你用深度優先和廣度優先遍歷節點，沒有要搜尋。所以請你把每個節點印出來方便我檢驗。我給你一個小函式。」

fun showNodeValue(node: TreeNode<T>) {
    print("${node.value} ")
}

難怪我覺得怪怪的，沒有看到要搜尋的目標在哪。

因為和插入節點的邏輯相似，我很快就寫好了深度遍歷：

    //深度優先遍歷
    fun inorderTraversal(node: TreeNode<T>? = root) {
        if (node != null) {
            inorderTraversal(node.left)
            showNodeValue(node)
            inorderTraversal(node.right)
        }
    }

廣度遍歷比較不直覺，我一直在想怎麼在處理其他節點的時候還能記得前一個節點往下一層的路，最後才想到可以在離開節點的時候，把它的下一層孩子放進 Queue 裡，這樣就能處理完這層再到下一層：

    //廣度優先遍歷
    fun levelOrderTraversal() {
        val queue: ArrayDeque<TreeNode<T>> = ArrayDeque()
        root?.let { queue.add(it) }

        while (queue.isNotEmpty()) {
            val current = queue.removeFirst()
            showNodeValue(current)

            current.left?.let { queue.add(it) }
            current.right?.let { queue.add(it) }
        }
    }

無論如何，終於完成了。

「恭喜你呀，連 Tree 都掌握了，資料結構的怨念也消除的差不多了。希望今天是我們最後一天見面，我的加班代價可是很高的唷。」小孩擺出一副非常兇惡的樣子。

我才是，終於不用擔心自己會被關在這種恐怖的封閉空間了。

————完。