二叉排序树的删除_二叉排序树的删除图示_二叉排序树删除节点(3)

4.二叉排序树的查找

由二叉排序树的定义可知,在二叉排序树上进行查找与二分查找类似。即：当二叉排序树不为空时，首先将给定值与根结点的关键值相比较，若相等，则查找成功。否则，将依据给定值和根节点关键值之间的大小关系，分别在左右子树上继续进行查找，其查找过程的算法如下：

BSTree SearchBST(BSTree bst,short key)
{
	if(bst==NULL)
	{
		return NULL;
	}
	if(bst->key==key)
	{
		return bst;
	}
	else if(bst->key>key)
	{
		return SearchBST(bst->lchild,key);
	}
	else 
	{
		return SearchBST(bst->rchild,key);
	}
}

5、二叉排序树的查找分析

根据二叉排序树的查找算法可以看出，二叉排序树的查找和二分查找类似，和关键字比较次数不超过树的深度，然而二分查找长度n的表判定树是唯一的，而含有n个结点二叉排序树却不唯一。对于含有同样关键字序列的一组结点，结点插入的先后次序不同，所构成的二叉排序树的形态和深度不同。而二叉排序树的平均查找长度ASL与二叉树的形态相关，二叉排序树的各分支越均衡，树的深度越浅，其平均查找长度ASL越小。

就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无需移动大量的结点。因此，对于需要经常做插入、删除、查找运算的表，宜采用二叉排序树，因此二叉排序树又称为二叉查找树。二叉排序树的删除

6、总结

上面是我在精读数据结构时，对二叉排序树的一点总结，也参考了相关的书籍，望各位读者多多指教。二叉排序树的删除

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25167-3.html