二叉排序树的查找

二叉排序树的查找过程

二叉排序树查找的伪代码

第一种写法：

//递归三要素：
//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);
}

第二种写法：

//递归中：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);
	}
}

性能分析

完整代码

#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;
}