二叉搜索树（Binary Search Trees）

二叉搜索树：每个元素都有一个唯一的值，而且所有元素的值各不相同；根节点左子树中的值比根节点的值小；根节点右子树中的值比根节点的值大；根节点的左右子树也都是二叉搜索树。

带索引的二叉搜索树（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.2cto.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。