上一篇我們介紹了「二元樹」，且我們提到「二元搜尋樹是二元樹的一種」，這篇我們要來定義何謂二元搜尋樹！

定義「二元搜尋樹」

1. 如果根節點 root 存在左子節點，則 root -> data > root -> left -> data
2. 如果根節點 root 存在右子節點，則 root -> data < root -> right -> data
3. 二元搜尋樹的任一子樹也是二元搜尋樹

上述的定義是以遞迴的方式來說明，怎麼看出來的呢？
關鍵字其實就是「子樹」！

子樹

我們先談談樹的實作方式，大致可以分成兩種：

1. 迴圈（以 while loop 為多，因為通常不知道要做幾次）
2. 遞迴（複雜度為 O(h) ，其中 h = height of the tree）

有鑒於實作中會提到遞迴的做法，所以 子樹 的概念更顯的重要！！

遞迴在做的是什麼？
找相似的條件，做相似的事情

以二元樹 (代號 X) 來說，每一個節點都有兩個分岔，分岔後接的是一個 子節點
假設我們把 子節點 各看做成一棵樹的 根節點，那麼這顆新的樹就叫做 X 的子樹

二元樹 = 左子樹 + 根節點 + 右子樹
左子樹 = 左子樹的左子樹 + 左子樹的根節點 + 左子樹的右子樹
右子樹 = 右子樹的左子樹 + 右子樹的根節點 + 右子樹的右子樹

回到這裡：

遞迴在做的是什麼？
找相似的條件，做相似的事情

相似的條件是什麼？ 都是 樹（記住這件事情，會對為未來起很大的幫助！）

接下來，我們就實際來實作「樹」吧！