二叉搜索樹：每個元素都有一個唯一的值，而且所有元素的值各不相同；根節點左子樹中的值比根節點的值小；根節點右子樹中的值比根節點的值大；根節點的左右子樹也都是二叉搜索樹。
帶索引的二叉搜索樹（indexed binary search trees）：基於上面的二叉搜索樹，每個元素擁有一個LeftSize域，其值等於該節點左子樹的元素數加1，同時它給出了該節點在其子樹中的排名，如上面8的LeftSize為6，則它在其子樹中排名第六（1、3、4、6、7、8、10、13、14），同樣，10的LeftSize為1，它在其子樹中排名為1（10、13、14）。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+tv6y5svRy/fK97XEQyYjNDM7JiM0MzvKtc/Wo6i7+dPatv6y5sr3o6k6PC9wPgo8cD48L3A+CjxwcmUgY2xhc3M9"brush:java;">/* 二叉搜索樹的構造類，繼承自二叉樹類，將二叉搜索樹設為二叉樹的友元類，才能訪問二叉樹的私有成員*/
template
class BSTree : public BinaryTree {
public:
bool Search(const K& k, E& e) const;
BSTree& Insert(const E& e);
BSTree& Delete(const K& k, E& e);
void Ascend(){InOutput();}
};
/*
二叉搜索樹元素的順序是依照鍵值（key）來定的
搜索，根據鍵值k，在二叉搜索樹中查找擁有相等鍵值（key）的節點，找到後將節點的值（element）賦給e
算法復雜度O(h), h為搜索樹的高度。
*/
template
bool BSTree::Search(const K& k, E& e) const
{
BinaryTreeNode *p = root;
while(p)
if(k < p->data) p = p->LeftChild;
else if(k > p->data) p = p->RightChild;
else {
e = p->data;
return true;
}
return false;
}
/*插入，O(h)*/
template
BSTree& BSTree::Insert(const E& e)
{
BinaryTreeNode *p = root, //搜索指針
*pp = 0; //p的父節點
//找到要插入的位置
while(p) { //若為真，說明p中有值，是個節點
pp = p; //保存p
if(e < p->data) p = p->LeftChild;
else if(e > p->data) p = p->RightChild;
else throw BadInput(); //e已經存在
}
//這時p已經為null，不過pp保存了要插入的位置
BinaryTreeNode *r = new BinaryTreeNode(e);
if(root) {
if(e < pp->data) pp->LeftChild = r;
else pp->RightChild = r;}
else
root = r;
return *this;
}
/*刪除， O(h)*/
首先找到要刪除的節點，一個while搞定，由於要刪除的節點會有子節點，所以需要局部調整以下樹的結構。
這裡采取的策略是，用該節點左子樹中的最大值代替該節點的值，然後刪除該最大值的節點，若最大值節點
擁有LeftChild，則讓LeftChild成為最大值節點父節點的RightChild。
