定义抽象数据类型搜索 搜索策略代码实现 插入 插入策略代码实现 删除 删除策略代码实现 二叉搜索树的高度

定义

二叉搜索树是一棵二叉树，可能为空；一棵非空的二叉搜索树具有以下特点：

每个元素都有一个关键字，并且任意两个元素的关键字都不相同；因此，所有的关键字都是唯一的；在根节点的左子树中，元素的关键字（如果有的话）都小于根节点的关键字；在根节点的右子树中，元素的关键字（如果有的话）都大于根节点的关键字；根节点的左右子树都是二叉搜索树。

抽象数据类型

抽象数据类型 bsTree { 实例 二叉树中，每一个节点都有一个数对，其中一个是关键字，另一个成员是数值； 所有关键字都不相同； 任何一个节点的左子树的关键字都小于该节点的关键字；右子树的关键字都大于该节点的关键字； 操作 find(k):返回关键字为k的数对 insert(p):插入数对p erase(k):删除关键字为k的数对 ascend():按关键字升序输出所有数对 }

程序如下：

template <class K,class E> class bsTree:public dictionary<k,E> { public: virtual void ascend()=0; }

搜索

搜索策略

查找根，若根为空，返回，查找失败，若不空，则与 theKey 相比较；如果与根相等，查找成功，如果 theKey 比较小，则在左子树中查找，否则在右子树中查找子树继续遵循该策略，直到查找结束为止

代码实现

程序复杂度为O（h），h为树的高度 程序如下：

template <class K,class E> pair<const K ,E>* binarySearchTree<K,E>::find(const K& theKey) const { binaryTreeNode<pair<const K,E>> *p=root; while(*p!=NULL) { if(theKey < p->element.first) p=p->leftChild; else if(theKey > p->element.first) p=p->rightChild; else return &p->element; } return NULL; }

插入

插入策略

查找要插入的新元素 thePair 的关键字是否与树中某个元素的关键字相同：

如果搜索成功：就用thePair.second(即thePair的值）代替原先元素的值。如果搜索失败：就将新元素作为中断节点的孩子插入二叉搜索树。

代码实现

template<class K,class E> void binarySearchTree<K,E>::insert(const pair<const K,E>& thePair) { binaryNode<pair<const K,E>> *p=root; *pp=NULL; while(p!=NULL)//搜寻 { pp=p;//保存父节点 if(thePair.first < p->element.first) p=p->leftChild; else if(thePair.first > p->element.first) p=p->rightChild; else { p->element.second=thePair.second;//覆盖(第一种情况) return 0; } } //第二种情况 binaryTreeNode<pair<const K,E>> *newNode= new binaryTreeNode<pair<const K,E>>(thePair); if(root!=NULL) if(thePair.first<pp->element.first) pp->leftChild=newNode； else pp->rightChild=newNode; else root=newNode; treeSize++; }

删除

删除策略

假设要删除的节点是p，考虑三种情况：

p是树叶：释放该叶节点的空间，若是根节点，则令根为NULL；p只有一棵非空子树： a）p是根节点，则p的唯一子树成为新的搜索树的根节点 b）p有父节点pp，则修改pp的指针域，使它只想p的唯一孩子，然后释放p p有两棵非空子树： a）首先用p的左子树的最大值或者右子树的最小值将p替换掉； b）然后将替换掉的那个元素节点删除

代码实现

算法复杂度为O（h）

template<class K,class E> void binarySearchTree<K,E>::erase(const K& theKey) { binaryTreeNode<pair<const K,E>>*p =root, *pp=NULL; //搜索 while(p!=NULL && p->element.first != theKey) { pp=p; if(theKey < p->element.first) p=p->leftChild; else p=p->rightChild; } if(p==NULL)//没找到 return 0; //找到了，开始删除过程 if(p->leftChild!=NULL && p->rightChild != NULL) { //先看有两棵子树的情况 binaryTreeNode<pair<const K,E>>*s =p->leftChild,//p的左孩子 *ps=p;//将p的父初始化为p while(s->rightChild != NULL) {//沿着右孩子方向移动，直到最后一个，一定是最大值，此时存在s中 ps=s; s=s->rightChild; } //此时已经找到p的左子树的最大值s //新建一个具有p节点的指针，但是有s节点的值的节点，将该节点直接赋给要删除的p节点，则完成了删除策略的一步 binaryTreeNode<pair<const K,E>>*q =new binaryTreeNode<pair<const K,E>> (s->element,p->leftChild,p->rightChild); //接下来进行赋值，分为两种情况：第一种p是根节点，第二种p不是根节点 if(pp=NULL)//p是根节点，那么p有两棵子树，取左子树的最大值来替换p，这个最大值分为两种情况：p的左儿子最大和p的左儿子的最右孩子最大 root=q; else //p不是根节点 if(p==pp->leftChild) pp->leftChild=q; else pp->rightChild=q; if(ps==p) pp=q;//左孩子最大的节点的父节点和要删除的节点相同，即左儿子最大，此时这个最大值节点没有右孩子，直接让p的父亲pp指向p的两个孩子（左孩子s和右孩子），然后删除p %else pp=ps;//将ps直接给pp相当于直接更换了pp的指向，使其指向p的孩子 delete p; %p=s; else { ps->rightChild=s->leftChild; delete s; } } else { //最多有一棵子树的情况 binaryTreeNode<pair<const K,E>> *c if(p->leftChild !=NULL)//左子树不空，右子树空 c=p->leftChild; else c=p->rightChild; //左子树空 if(p==root) root=c; else //p有父节点 { if(p==pp->leftChild) pp->leftChild=c; else pp-rightChild=c; } delete p; } treeSize--; }

二叉搜索树的高度

一棵n个元素的二叉搜索树，其高度可以是n，这时搜索，插入和删除操作的时间均为O（n），如果随机插入和删除时，平均高度是O（log n）。

摘自《数据结构算法与应用》，有部分修改，上述过程如有错误，还请指正！ 相关博客： 二叉查找树的插入和删除详解 二叉搜索树的定义、查找、插入和删除