二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
如果在每个节点添加一个leftSize域记录该节点的左子树元素个数，那么就得到了索引二叉搜索树。
对于 二叉搜索树 ，一般需要实现的是查找，插入，删除和按序输出四个操作，而索引二叉搜索树由于leftSize的存在，多具有一个返回第index的数对功能。
在实现二叉搜索树时，我们可以继承原有的链表描述的二叉树类：linkedBinaryTree（数据结构（7）二叉树 – giser吱吱的小站 (gislxz.top)）
但是原有的二叉树类定义时节点只有一个元素，而二叉搜索树每个节点是关键字和元素值。但幸好我们平时定义时用的都是template模板函数，使用pair偶对即可将原来单一元素扩展出两个位置给索引和真正的元素值
//二叉树节点的定义
template <class T>
struct binaryTreeNode
{
T element;//搜索二叉树用pair来存储关键字和元素
binaryTreeNode<T>* leftChild, // left subtree
* rightChild; // right subtree
binaryTreeNode() { leftChild = rightChild = NULL; }
binaryTreeNode(const T& theElement) :element(theElement)
{
leftChild = rightChild = NULL;
}
binaryTreeNode(const T& theElement,
binaryTreeNode* theLeftChild,
binaryTreeNode* theRightChild)
:element(theElement)
{
leftChild = theLeftChild;
rightChild = theRightChild;
}
};
//搜索二叉树的定义
template<class K, class E>
class binarySearchTree : public bsTree<K, E>,//继承搜索二叉树的抽象类，不继承也可以运行
public linkedBinaryTree<pair<const K, E> >//继承链表实现的二叉树类
public:
// methods of dictionary
bool empty() const { return treeSize == 0; }
int size() const { return treeSize; }
pair<const K, E>* find(const K& theKey) const;
void insert(const pair<const K, E>& thePair);
void erase(const K& theKey);
// additional method of bsTree
void ascend() { inOrderOutput(); }
};
pair结构的介绍
(11条消息) C++ pair的基本用法总结（整理）_sevenjoin的博客-CSDN博客_c++ pair
搜索二叉树最核心的功能一定是搜索，基于搜索树的特性，我们只要比较查找的关键字与当前节点关键字的大小即可，如果相同就找到了，小就去左节点，大就去右节点，直到查到或者到底返回不存在该元素。注意返回的是pair指针
template<class K, class E>
pair<const K, E>* binarySearchTree<K, E>::find(const K& theKey) const
{// Return pointer to matching pair.
// Return NULL if no matching pair.
// p starts at the root and moves through
// the tree looking for an element with key theKey
binaryTreeNode<pair<const K, E> >* p = root;//复制根节点
while (p != NULL)
// examine p->element
if (theKey < p->element.first)
p = p->leftChild;
else
if (theKey > p->element.first)
p = p->rightChild;
else // found matching pair
return &p->element;
// no matching pair
return NULL;
}插入操作与搜索相似，通过比较插入关键字再去向子节点，直到不存在相应的子节点就建立子节点插入，如果过程中发现关键字已存在就修改对应元素值。
代码细节是建立*p和*pp两个pair指针，一个指向子节点，一个慢一步留在父节点。
特别注意插入新节点时检查是否存在根节点
template<class K, class E>
void binarySearchTree<K, E>::insert(const pair<const K, E>& thePair)
{// Insert thePair into the tree. Overwrite existing
// pair, if any, with same key.
// find place to insert
binaryTreeNode<pair<const K, E> >* p = root,//p先复制根节点
* pp = NULL;
while (p != NULL)
{// examine p->element
pp = p;//pp比p慢一步，停留在父节点
// move p to a child
if (thePair.first < p->element.first)
p = p->leftChild;
else
if (thePair.first > p->element.first)
p = p->rightChild;
else
{// replace old value
p->element.second = thePair.second;
return;
}
}
// get a node for thePair and attach to pp
binaryTreeNode<pair<const K, E> >* newNode
= new binaryTreeNode<pair<const K, E> >(thePair);
if (root != NULL) // the tree is not empty
if (thePair.first < pp->element.first)
pp->leftChild = newNode;
else
pp->rightChild = newNode;
else
root = newNode; // insertion into empty tree
treeSize++;
}删除操作稍复杂，如果删除的节点只是树叶或者只有一颗子树那么很简单，如果有两棵子树就复杂一些。下面分别讨论
1.是树叶，就将父节点指向该节点设为NULL再释放此节点。如果该节点是根节点就设该树的根节点为NULL然后释放该节点。
2.仅有一个子树。如果是根节点就设其子树为根节点，如果不是根节点则修改其父节点的指针指向该节点的子树。
3.如果有两个子树，就将该节点的元素替换成左子树最大的元素或右子树最小的元素，然后把被替换的元素节点删除。至于查找最大元素或最小元素很简单，比如查找左子树最大的元素就先让当前指针到到左孩子，然后再对着右孩子一路查下去直到没有右孩子为止。
实际实现过程和插入类似，*p和*pp两个pair指针，一个指向子节点，一个慢一步留在当前节点。
template<class K, class E>
void binarySearchTree<K, E>::erase(const K& theKey)
{// Delete the pair, if any, whose key equals theKey.
// 先移动到需被删除的节点
binaryTreeNode<pair<const K, E> >* p = root,
* pp = NULL;
while (p != NULL && p->element.first != theKey)
{// move to a child of p
pp = p;
if (theKey < p->element.first)
p = p->leftChild;
else
p = p->rightChild;
}
if (p == NULL)
return; // no pair with key theKey
// restructure tree
// 处理两棵子树均不为空的情况
if (p->leftChild != NULL && p->rightChild != NULL)
{// two children
// convert to zero or one child case
// find largest element in left subtree of p
binaryTreeNode<pair<const K, E> >* s = p->leftChild,
* ps = p; // parent of s
while (s->rightChild != NULL)
{// move to larger element
ps = s;
s = s->rightChild;
}
// move largest from s to p, can't do a simple move
// p->element = s->element as key is const
binaryTreeNode<pair<const K, E> >* q =
new binaryTreeNode<pair<const K, E> >
(s->element, p->leftChild, p->rightChild);
if (pp == NULL)
root = q;
else if (p == pp->leftChild)
pp->leftChild = q;
else
pp->rightChild = q;
if (ps == p) pp = q;
else pp = ps;
delete p;
p = s;
}
// p has at most one child
// save child pointer in c
binaryTreeNode<pair<const K, E> >* c;
if (p->leftChild != NULL)
c = p->leftChild;
else
c = p->rightChild;
// delete p
if (p == root)
root = c;
else
{// is p left or right child of pp?
if (p == pp->leftChild)
pp->leftChild = c;
else pp->rightChild = c;
}
treeSize--;
delete p;
}这段代码写的非常妙，但有一部分也有些难懂。
if (pp == NULL)
root = q;
else if (p == pp->leftChild)
pp->leftChild = q;
else
pp->rightChild = q;
if (ps == p) pp = q;
else pp = ps;
delete p;
p = s;这一部分乍看完全看不懂在干嘛，其实是为了和后面讨论单子节点或无子节点时一并处理。新手分类讨论时一定是if（无子节点），else if（单子结点），else（双子节点）三大段写完，但是书上这样写首先把单子结点和无子节点统一处理，在通过上面这段代码把原来双子节点后半段的删除操作交由单子节点和无子节点代码段一并处理。
Comments NOTHING