二叉排序树的查找过程
二叉排序树查找的伪代码
第一种写法：
代码语言：javascript复制//递归三要素：
//1.结束条件：未找到 找到
//2.递归内容：比较大小，决定去左还是右子树里面查找
//3.返回值：没找到，返回双亲节点 找到，返回对应节点
BiNode* searchBST(BiNode* root, int key)
{
if (root == NULL)
return root;
if(root->data==key)
return root;
return key<(root->data)? searchBST(root->lchild, key):searchBST(root->rchild,key);
}第二种写法：
代码语言：javascript复制//递归中：T是当前节点 f是当前节点的双亲节点
//如果没查到Key值，p记录的是最后一次访问的节点
//如果查到key值，p记录的是找到的节点
bool searchBST(BiNode* T, int key, BiNode* f, BiNode*& p)//这里p要用引用或二级指针，否则最后回溯返回的时候，返回的是初始值
//而我们要返回的是查找顶点的双亲节点
{
//递归三要素：
//1.结束条件：查到到空节点，查无此值 查到节点
//2.递归内容：比较大小，进入左子树或者右子树进行查找
//3.返回值：真或假
if (!T)
{
p = f;
return false;
}
if (T->data == key)
{
p = T;
return true;
}
if (key < T->data)
{
return searchBST(T->lchild, key, T, p);
}
else
{
return searchBST(T->rchild, key, T, p);
}
}性能分析
完整代码
代码语言：javascript复制#include<iostream>
using namespace std;
struct BiNode {
int data;
BiNode* lchild;
BiNode* rchild;
BiNode(int key):data(key),lchild(NULL),rchild(NULL){}
};
//递归三要素：
//1.结束条件：未找到 找到
//2.递归内容：比较大小，决定去左还是右子树里面查找
//3.返回值：没找到，返回双亲节点 找到，返回对应节点
BiNode* searchBST(BiNode* root, int key)
{
if (root == NULL)
return root;
if(root->data==key)
return root;
return key<(root->data)? searchBST(root->lchild, key):searchBST(root->rchild,key);
}
void insertBST(BiNode*& root, int key)
{
//如果为空树，就进行初始化
//或者找到了合适的插入位置
if (root == NULL)
{
root = new BiNode(key);
}
else
{
//如果不为空树，进行插入的时候需要比较大小
//左小右大--左子树都小于根节点，右子树都大于根节点
//递归三要素：结束条件 干什么 返回值 （只考虑当前层做什么，不展开考虑）
//1.当发现当前遍历到的节点为空，结束递归
//2.通过比较大小，寻找合适的插入位置
//3.无返回值
if (key < root->data)
{
insertBST(root->lchild, key);
}
else
{
insertBST(root->rchild, key);
}
}
}
//二叉树中序遍历得到二叉树的有序序列
void display(BiNode* root)
{
//结束条件：当前节点为空
if (!root)return;
//干什么:中序遍历
display(root->lchild);
cout << root->data << " ";
display(root->rchild);
}
//二叉树的构建
void BiSortTree(int v[], int len)
{
BiNode* root = NULL;
for (int i = 0; i < len; i )
{
insertBST(root, v[i]);
}
display(root);
cout << endl;
BiNode* ret = searchBST(root, 58);
cout << "下面查找key为58的值，如果找到就打印输出：" << endl;
cout << ret->data << endl;
}
//测试-------------------
void test()
{
int v[10] = { 62,88,58,47,35,73,51,99,37,93 };
BiSortTree(v, 10);
}
int main()
{
test();
system("pause");
return 0;
}
