14.1.1 二叉搜索树搜索树是一种适合于
描述字典的树形结构。特别是对于顺序访问或按排名访问，散列表实现时间性能差，使用搜索树实现则会有更好的时间性能。
二叉搜索树是一棵可能为空的二叉树，一棵非空的二叉搜索树满足：
所有的关键字都是唯一的。小于根的关键字。大于根的关键字。
有重复值的二叉搜索树即放弃二叉搜索树中所有元素拥有不同关键字的要求：
小于等于该元素的关键字大于等于该元素的关键字索引二叉搜索树：
二叉搜索树
在每个节点中添加一个leftSize——该节点左子树的元素个数
leftSize(x)：给出了一个元素在x为根的子树中排名(0起始)
抽象数据类型bsTree
{实例:
二叉树，每个节点有一个数对，数对的一个成员是关键字，另一个是数值；
所有元素的关键字各不相同；
任何节点左子树的关键字小于该节点的关键字；
任何节点右子树的关键字大于该节点的关键字。
操作:
find(k):返回关键字为k的数对
insert(p):将数对p插入到搜索树中
erase(k):删除关键字为k的数对
ascend():按照关键字的升序排列输出所有数对
}抽象数据类型indexedBSTree
{实例:
与bsTree的实例相同，只是每一个节点有一个leftSize域
操作:
find(k):返回关键字为k的数对
get(index):返回第index个数对
insert(p):插入数对p
erase(k):删除关键字为k的数对
delete(index):删除第index个数对
ascend():按关键字的升序输出所有数对
}templateclass bsTree:public dictionary{public:
//按关键字的升序输出所有数对
virtual void ascend() = 0;
}; templateclass indexedBSTree:public bsTree{public:
//按照给定的索引，返回其数对的指针
virtual pair* get(int)const = 0;
//按照给定的索引，删除其数对
virtual void delete(int) = 0;
}; 类二叉搜索树：链式存储
- 链式存储的二叉搜索树类binarySearchTree
- 类binarySearchTree是类linkedBinaryTree的派生类
- 元素类型：pair
- 数对p的关键字：p.first
- 数对p的值：p.second
binarySearchTreetemplateclass binarySearchTree:public bsTree,
public linkedBinaryTree>{public:
//返回关键字theKey匹配的数对的指针，若不存在则返回NULL
pair*find(const K& theKey)const;
//插入一个数对thePair，如果存在关键字相同的数对，则覆盖
void insert(const pair& thePair);
//删除关键字theKey匹配的数对
void erase(const K& theKey);
void ascend()
{//按照关键字的升序排列输出所有数对
inOrderOutput();
}
}; ascend
find搜索先从根开始。
如果根为空，那么搜索树不包含任何元素，查找失败.
如果theKey 小于根节点的关键字，在左子树中搜索theKey。
如果theKey 大于根节点的关键字，在右子树中搜索theKey。
如果theKey 等于根节点的关键字，则查找成功。
templatepair*find(const K& theKey) const
{BinaryTreeNode>* p = root;
while (p != NULL)
{if (p->element.first >theKey)
{//如果theKey 小于根节点的关键字，在左子树中搜索theKey
p = p->leftChild;
}
else if (p->element.first< theKey)
{//如果theKey 大于根节点的关键字，在右子树中搜索theKey
p = p->rightChild;
}
else
{//如果theKey 等于根节点的关键字，则查找成功
return &p->element;
}
}
//无匹配的元素
return NULL;
} insert在二叉搜索树中插入一个新元素thePair：
首先搜索，验证thePair.first是否存在
如果搜索成功，那么关键字为thePair.first的元素将被新元素的值（thePair.second）覆盖
如果搜索不成功，那么新元素将被插入到搜索的中断点。
templatevoid bianrySearchTree::insert(const pair& thePair)
{BinaryTreeNode>* p = root;
BinaryTreeNode>* pp = NULL;
//pp相当于一个影子跟屁虫，记p的父节点，与p同步下移，保证插入
//寻找插入点
while (p != NULL)
{pp = p;
if (thePair.first >p->element.first)
{//要插入的元素大，放右节点去
p = p->rightChild;
}
else if (thePair.first< p->element.first)
{//要插入的元素小，放左节点去
p = p->leftChild;
}
else
{//恰好相等，不需要插入
p->element.second = thePair.second;//覆盖旧值
}
}
//为新元素建立新节点，与pp相连
BinaryTreeNode>* newNode = new BinaryTreeNode>(thePair);
if (root != NULL)
{//新元素比父节点大，为pp的右孩子
if (thePair.first >pp->element.first)
pp->rightChild = newNode;
//新元素比父节点小，为pp的左孩子
else
pp->leftChild = newNode;
}
else
{//空树，直接插入到根节点
root = newNode;
}
} erase情况①：被删除元素的节点p是树叶
- 直接丢弃树叶节点
情况②：被删除元素的节点p只有一个非空子树
情况③：被删除元素的节点p有两个非空子树
- 可以用它
左子树的大元素或者右子树的最小元素来替换它
左子树的大元素或者右子树的最小元素一定是叶子或者一个度为1的节点- 而后转换为删除元素的节点p只有一个非空子树或删除元素的节点p是树叶
templatevoid bianrySearchTree::erase(const K& theKey)
{BinaryTreeNode>* p = root;//搜索指针
BinaryTreeNode>* pp = NULL;//p的父节点指针
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;//未找到
//对树进行重构
//处理p有两个孩子的情形
if (p->leftChild != NULL && p->rightChild != NULL)
{//在p的左子树寻找大元素
BinaryTreeNode>* s = p->leftChild;
BinaryTreeNode>* ps = p;//s的父节点
//移动到大的元素
while (s->rightChild != NULL)
{ps = s;
s = s->rightChild;
}
//将大元素从s移动到p
BinaryTreeNode>*q = new BinaryTreeNode(s->element, p->leftChild, p->rightChild);
//与p关联的指针修改为与q关联
if (pp == NULL)
root = q;
else if (p == pp->leftChild)
pp->leftChild = q;
else
pp->rightChild = q;
//p指向新的删除节点s，pp为p的父节点
if (ps == p)
pp = q;
else
pp = ps;
delete p;
p = s;
}
//处理p只有一个孩子的情形，【直接用该孩子替换当前元素】
binaryTreeNode* c;//在c中保存孩子指针
if (p->leftChild != NULL)
c = p->leftChild;
else
c = p->rightChild;
//删除节点位于根节点
if (p == root)
root = c;//根节点更新为孩子节点
//删除节点不是根节点
else
{if (p == pp->leftChild) //p是pp的左孩子
pp->leftChild = c;
else //p是pp的右孩子
pp->rightChild = c;
}
treesize--;
delete p;
} 关键字为【1，2，3，……n】的元素按顺序插入到一棵空的二叉搜索树时
大：搜索、插入和删除操作所需要的时间：O(n)
平均：搜索、插入和删除操作所需要的时间：O(logn)
实现dBinarySearchTree类时，只需把binarySearchTree::insert的while循环改为：
while (p)
{pp = p;
if(thePair.first<= p->element.first)
p=p->leftChild;
else p=p->rightChild;
}即添加相等判断=
详见实验11
实现类indexedBSTree时，节点设计，增加leftSize域
templatestruct binaryTreeNode
{T element;
binaryTreeNode* leftChild;
binaryTreeNode* rightChild;
int leftSize;
binaryTreeNode(const T& theElement)
{element = theElement;
leftChild = NULL;
rightChild = NULL;
leftSize = 0;
}
binaryTreeNode(const T& theElement, binaryTreeNode* theLeft, binaryTreeNode* theRight, int LeftSize)
{element = theElement;
leftChild = theLeft;
rightChild = theRight;
//规定为该节点左子树的元素个数
leftSize = LeftSize;
}
}; insert、delete操作：注意节点的
leftSize的更新
get(index)操作（图解）
8是第3个元素，30是第9个元素
get(index)返回第index个元素
index = x.leftSize，第index个元素是x.elementindex< x.leftSize，第index个元素是x的左子树的第index个元素index >x.leftSize，第index个元素是x的右子树的第index - (x.leftSize + 1)个元素
//按名次搜索函数
templateint bianrySearchTree::Search(int a)
{binaryTreeNode>* p = root;
while (p != NULL && p->leftSize != a)
{if (p->leftSize >a)
{//该节点的索引比b大，证明b在左孩子中
p = p->leftChild;
}
else if (p->leftSize< a)
{//该节点的索引比b小，证明b在右孩子中
a = a - p->leftSize - 1;
p = p->rightChild;
}
}
//没找到
if (p == NULL)
return 0;
//找到了
else
return sum;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
