就是假设各个节点关键字不一样的不为空的二叉树
1.如果左子树不为空,则左子树的关键字小于根节点
2.如果右子树不为空,则右子树的关键字大于根节点
3.左右子树都为二叉树
知道了这个下面我们来看看它的迭代和递归算法
递归
算法描述:
1.如果为空二叉树则查找失败
2.不为空
a.关键字小于根节点,查找左子树,不必查找右子树
b.关键字大于根节点,查找右子树,不洗查找左子树
c.关键字等于根节点,查找成功。
代码实现
template <class T>
ResultCode BSTree<T>::Search(T & x) const {
return Search(root,x);
}
template <class T>
ResultCode BSTree<T>::Search(BTNode<T> *p, T & x) const{
if (!p) return NotPresent;
else if (x<p->element) return Search(p->lChild,x);
else if(x>p->element) return Search(p->rChild,x);
else {
x=p->element;return Success;
}
}
迭代
算法描述:
使用while循环,从根结点开始搜索,将待查元素x与当前元素比较。
若x等于该结点的值,则搜索成功终止;
若x小于该结点的值,则继续搜索左子树;
否则继续搜索右子树。
只有搜索到空子树时,才失败终止。
template <class T>
ResultCode BSTree<T>::Search(T & x) const {
BTNode<T> *p=root;
while (p) {
if ( x < p->element) p=p->lChild;
else if (x > p->element) p=p->rChild;
else {
x=p->element;
return Success;
}
}
return NotPresent;
}