在众多查找方法中,二叉排序树查找是比较好的一种查找,其效率比顺序查找,折半查找,插值查找,斐波纳契查找等都要好。
二叉排序树的建立
首先要了解而叉排序树如何建立,给定一组数组,建立一个而叉排序树
#include <iostream>
typedef struct BitNode{
int data;
struct BitNode *lchild, *rchild;
}BitNode, *BiTree;
bool BSTInsert(BitNode * &p, int element)
{
if(NULL == p) // 空树
{
p = new BitNode;
p->data = element;
p->lchild = p->rchild = NULL;
return true;
}
if(element == p->data) // BST中不能有相等的值
return false;
if(element < p->data) // 递归
return BSTInsert(p->lchild, element);
return BSTInsert(p->rchild, element); // 递归
}
void createBst(BitNode * &T, int a[], int n){
T = NULL;
int i;
for(i = 0; i < n; i++){
BSTInsert(T, a[i]);
}
}
//先序遍历
void preOrderTraverse(BiTree T)
{
if(T)
{
printf("%d ", T->data);
preOrderTraverse(T->lchild);
preOrderTraverse(T->rchild);
}
}
//中序遍历
void inOrderTraverse(BiTree T)
{
if(T)
{
inOrderTraverse(T->lchild);
printf("%d ", T->data);
inOrderTraverse(T->rchild);
}
}
int main(){
int a[10] = {1,3,5,2,9,4,6,0,7,8};
BiTree T;
createBst(T, a, 10);
preOrderTraverse(T);
printf("\n");
inOrderTraverse(T);
return 0;
}
看看结果:
第一个是先序遍历的结果,第二个是中序遍历的结果
先序遍历:中->左->右
中序遍历:左->中->右
二叉树建立后的样子是这样的:
二叉排序树的查找操作
查找操作代码在原代码中修改
#include <iostream>
static int i = 0;
typedef struct BitNode{
int data;
struct BitNode *lchild, *rchild;
}BitNode, *BiTree;
bool BSTInsert(BitNode * &p, int element)
{
if(NULL == p) // 空树
{
p = new BitNode;
p->data = element;
p->lchild = p->rchild = NULL;
return true;
}
if(element == p->data) // BST中不能有相等的值
return false;
if(element < p->data) // 递归
return BSTInsert(p->lchild, element);
return BSTInsert(p->rchild, element); // 递归
}
void createBst(BitNode * &T, int a[], int n){
T = NULL;
int i;
for(i = 0; i < n; i++){
BSTInsert(T, a[i]);
}
}
//查找
void searchBst(BiTree T, int key){
//记录第几次查找到
++i;
if(T){
if(key == T->data){
printf("第%d次查询\n", i);
printf("查得:%d", T->data);
} else if(key < T->data)
searchBst(T->lchild, key);
else
searchBst(T->rchild, key);
}
}
int main(){
int a[10] = {1,3,5,2,9,4,6,0,7,8};
BiTree T;
createBst(T, a, 10);
searchBst(T, 8);
return 0;
}
结果如下:
二叉排序树很好理解,同时也是面试题中较常出现的,是应该掌握的知识点。(上述例子,由于只是为了演示,没有考虑内存泄露的问题)