二元搜尋樹的抽象資料結構
二元搜尋樹 (binary search tree) 是樹 (tree) 的一種，二元樹會分為左子樹和右子樹兩部分。在初階的資料結構教材中，不會對二元搜尋樹進行平衡的動作，這樣的樹實用性偏低，但易於實作，會拿來做為樹的第一個實例。本文會實做一個未平衡的二元搜尋樹。
二元搜尋樹的抽象資料結構如下：
T is a BST (binary search tree)
sub IsEmpty(T): bool
sub Height(T): size
sub Contains(T, value): bool
sub Max(T): result
sub Min(T): result
sub Add(T, value): void
sub Remove(T, value): void由其抽象資料結構可知二元搜尋樹有以下的行為：
IsEmpty(T)：檢查樹是否為空Height(T)：取得樹的高度Contains(T, value)：檢查特定值是否存在於樹中Max(T)：取得樹的最大值Min(T)：取得樹的最小值Add(T, value)：將單一值加入樹Remove(T, value)：將單一值移出樹
宣告二元搜尋樹類別
以下是二元搜尋樹的類別的虛擬碼：
class Node:
data <- empty
left <- null as pointer to Node
right <- null as pointer to Node
class Tree:
root <- null as pointer to Node
cmp <- a predicate function這時候內部節點會有 left 和 right 兩個指向其他節點的指標，和先前的線性資料結構的內部結點相異。
市面上常見的教材會把二元搜尋樹的比較條件寫死在程式碼中，這樣寫比較易理解，但程式碼的重用性較低。在此處，我們將大小比較的程式抽出來，寫在函式 cmp 中。cmp 會根據兩個值的大小關係回傳 1、0、-1，藉此判斷兩個值的關係。只要該程式語言支援函數式程式的特性都可以用這種手法寫，以 C 語言來說，C 語言支援指向函式的指標 (pointer to function)，故可用這個寫法。
以下是等效的 C 語言實作：
typedef struct node_t node_t;
struct node_t {
int data;
node_t *left;
node_t *right;
};
typedef struct tree_t tree_t;
struct tree_t {
node_t *root;
cmpFn cmp;
};二元搜尋樹的建構函式
以下是以 C 語言實作的二元搜尋樹的建構函式：
typedef short (*cmp_fn)(int a, int b);
tree_t * tree_new(cmp_fn cmp)
{
tree_t *self = (tree_t *) malloc(sizeof(tree_t));
if (!self)
return self;
self->root = NULL;
self->cmp = cmp;
return self;
}二元搜尋樹的解構函式
以下是 C 語言的二元搜尋樹的解構函式：
static void _tree_delete(node_t *node);
void tree_delete(void *self)
{
if (!self)
return;
node_t *root = ((tree_t *) self)->root;
_tree_delete(root);
free(self);
}
static void _tree_delete(node_t *node)
{
if (!node) {
return;
}
_tree_delete(node->left);
_tree_delete(node->right);
free(node);
}要先以遞迴逐一走訪並釋放內部節點後再釋放二元樹物件本身；走訪的方式是採後序走訪 (postorder traversal)，後文會介紹二元搜尋樹的走訪。
檢查二元搜尋樹是否為空
藉由檢查根節點是否為空 null 即可知樹是否為空。以下是 C 語言實作：
bool tree_is_empty(const tree_t *self)
{
assert(self);
return !(self->root) ? true : false;
}檢查二元搜尋樹的高度
當節點為空時，高度是 0。
反之，分別檢查左子樹和右子樹的高度後，取較大值，再加 1 (本身高度)，最後回傳答案。
從根節點開始遞迴走訪即可知道整顆樹的高度。樹會大量使用遞迴，如果對遞迴程式不熟，最好先回頭看一下基礎的遞迴程式怎麼寫。以下是 C 語言實作：
static size_t _tree_height(const node_t *node);
size_t tree_height(const tree_t *self)
{
assert(self);
return _tree_height(self->root);
}
static size_t _tree_height(const node_t *node)
{
if (!node)
return 0;
size_t l = (!(node->left)) ? 0 : _tree_height(node->left);
size_t r = (!(node->right)) ? 0 : _tree_height(node->right);
size_t h = l > r ? l : r;
return h + 1;
}檢查特定值是否存在於二元搜尋樹中
若節點為空，表示沒有符合 value 的值，故回傳 false。
若節點不為空，則以 cmp 比較兩者間的關係。若兩數相符，則回傳 true；若節點值大於 value，則繼續搜尋左子樹以找出是否有符合 value 的值；若節點小於 value，則繼續搜尋右子樹以找出是否有符合 value 的值。
從根節點開始遞迴走訪，即可找出整顆樹中是否有符合 value 的值。
以下是 C 語言程式碼：
static bool _tree_contains(node_t *node, int value, cmp_fn cmp);
bool tree_contains(const tree_t *self, int value)
{
assert(self);
return _tree_contains(self->root, value, self->cmp);
}
static bool _tree_contains(node_t *node, int value, cmp_fn cmp) {
if (!node)
return false;
if (cmp(value, node->data) == 0) {
return true;
}
else if (cmp(value, node->data) < 0) {
return _tree_contains(node->left, value, cmp);
}
else if (cmp(value, node->data) > 0) {
return _tree_contains(node->right, value, cmp);
}
return false;
}取得二元搜尋樹的最小 (極左) 值
註：在本範例程式中，極左極不一定是最小值，需注意。
最小 (極左) 值一定是在整顆樹最左側的節點，故只要從根節點逐一向左走訪至盡頭即可。以下是 C 程式實作：
int tree_min(const tree_t *self)
{
assert(!tree_is_empty(self));
node_t *p = self->root;
while (p->left) {
p = p->left;
}
return p->data;
}取得二元搜尋樹的最大 (極右) 值
註：在本範例程式中，極右極不一定是最大值，需注意。
最大 (極右) 值一定是在整顆樹最右側的節點，故只要從根節點逐一向右走訪至盡頭即可。以下是 C 程式實作：
int tree_max(const tree_t *self)
{
assert(!tree_is_empty(self));
node_t *p = self->root;
while (p->right) {
p = p->right;
}
return p->data;
}將值加入二元搜尋樹中
當節點本身為空 null 時，直接在節點處新增子樹 tree 即可。
當節點不為空時，會根據 value 和節點值的關係來決定下一個步驟。當節點值大於 value 時，繼續搜尋左子樹，找出適合加入節點的位置；當節點值小於 value 時，繼續搜尋右子樹，找出適合加入節點的位置。
當節點值等於 value 時，有兩種處理方式，一種是拋棄該值，一種是將該值指定至左右子樹之一；指定子樹時，需固定方向。基本上要看值的數量重不重要來決定實做的方式。
以下是 C 語言實作：
static bool _tree_insert(node_t **node, int value, cmp_fn cmp);
bool tree_insert(tree_t *self, int value)
{
assert(self);
return _tree_insert(&(self->root), value, self->cmp);
}
static bool _tree_insert(node_t **node, int value, cmp_fn cmp)
{
if (!(*node)) {
*node = node_new(value);
if (!(*node)) {
return false;
}
return true;
}
if (cmp(value, (*node)->data) < 0) {
return _tree_insert(&((*node)->left), value, cmp);
}
else if (cmp(value, (*node)->data) >= 0) {
return _tree_insert(&((*node)->right), value, cmp);
}
return false;
}這裡補上 node_new 相關的實作：
static node_t * node_new(int value)
{
node_t *node = (node_t *) malloc(sizeof(node_t));
if (!node)
return node;
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}將值移出二元搜尋樹
若節點為空，不需執行移出值的動作，直接跳出函式即可。
若節點不為空，則需依照節點值和 value 間的關係來決定下步。當節點值大於 value 時，繼續搜尋左子樹，以找出符合條件的可刪除值；反之，當節點值小於 value 時，繼續搜尋右子樹，以找出符合條件的可刪除值。
當節點值符合 value 時，會依照該節點和子樹間的關決決定下一步。當左子樹為空時，直接以右子樹取代節點所在的位置；反之，當右子樹為空時，直接以左子樹取代節點所在的位置。當左右子樹皆不為空時，找出右子樹的最小值，取代原節點的值；之後要繼續搜尋右子樹，刪除該最小值。會以右子樹的最小值是為了保持樹的值之間的相對關係，也可以左子樹的最大值來補值，讀者可試著練習看看。
以下是 C 語言實作：
static bool _tree_remove(node_t **node, int value, cmp_fn cmp);
bool tree_remove(tree_t *self, int value)
{
if (tree_is_empty(self)) {
return false;
}
return _tree_remove(&(self->root), value, self->cmp);
}
static bool _tree_remove(node_t **node, int value, cmp_fn cmp)
{
if (!(*node)) {
return false;
}
if (cmp(value, (*node)->data) < 0) {
return _tree_remove(&((*node)->left), value, cmp);
}
else if (cmp(value, (*node)->data) > 0) {
return _tree_remove(&((*node)->right), value, cmp);
}
if (!((*node)->left)) {
node_t *temp = (*node)->right;
free(*node);
*node = temp;
}
else if (!((*node)->right)) {
node_t *temp = (*node)->left;
free(*node);
*node = temp;
}
else {
int min = _tree_min((*node)->right);
(*node)->data = min;
if (!_tree_remove(&((*node)->right), min, cmp)) {
return false;
}
}
return true;
}這裡補上 _tree_min 部分的實作：
static int _tree_min(const node_t *node)
{
assert(node);
if (node->left)
return _tree_min(node->left);
return node->data;
}將二元搜尋樹用於排序 (sorting) 和搜尋 (searching) 問題
二元搜尋樹也可用於排序 (sorting) 和搜尋 (searching) 問題。當我們放入元素時，這些元素已經按照特定的順序排列好，只要以中序走訪 (in-order traversal) 走訪整個二元樹，就可以得到排序後的串列。在前文中提及的 Contains(T, value) 函式，其實就是搜尋問題的實例。
演算法上的效率
假定 T 是一個二元搜尋樹，本範例的二元搜尋樹在演算法上的效率如下：
IsEmpty(T)：O(1)Height(T)：最差為O(n)，最佳為O(log(n))Contains(T, value)：O(Height(T))Max(T)：O(Height(T))Min(T):O(Height(T))Add(T, value)：O(Height(T))Remove(T, value)：O(Height(T))
二元樹的效率會和樹的高度相關，樹越高，運行時間越久。理想上，二元樹的高度的成長率為 O(log(n))，但本文的二元樹採初階的實作方式，沒有對樹進行平衡，在最差的情形下該二元樹可能會退化成鏈結串列，這時候樹高度的成長率變成 O(n)。