二叉搜索树查找
在第五章《树》,我们学习了什么叫做二叉排序树,即二叉搜索树。很多时候,我们也可以将数据存放在平衡二叉排序树里。那么如何使用它来进行查找数据呢?
struct _node
{
int data;
struct _node *left;
struct _node *right;
} node, btree;
btree *search(btree *b, int x)
{
if (b == NULL)
{
return NULL;
}
else
{
if (b->data == x)
{
return b;
}
else if (x < b->data)
{
return (search(b->left));
}
else
{
return (search(b->right));
}
}
}
平衡二叉排序树的查找复杂度为O(logn),因此也具有较高的查找效率。