步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）
在一般情况下，设 P（n，i）且它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6
= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。 P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2
∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
n -1
∴ P（n）= ∑ P（n,i）/ n <= 2(1+I/n)lnn
i=0
因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)
每个结点的C(i)为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为，其平均查找长度为(n+1)/2(和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比
打开IDE
二叉排序树类实现如下
#include "stdafx.h"
//二叉排序树
#include <iostream>
#include <iomanip>
#include<stdlib.h>
using namespace std;
//二叉树的链式存储结构表示
typedef struct BinaryTree
{ int data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
//二叉树的类定义
class BiSearchT
{private:
BiTree root;
public:
//构造函数
BiSearchT():root(NULL) {}
//构造二叉链表表示的二叉树T
int CreateSubTree(BiTree &t,int *all,int i);
//先序遍历二叉树T
int PreOrderTraverse(BiTree t,int (*Visit)(int e));
//中序遍历二叉树T
int InOrderTraverse(BiTree t,int (*Visit)(int e));
//插入算法
int InsertBST(BiTree *t,int e);
//在二叉排序树中删除一个节点
void Delete(BiTree *p);
//二叉排序树的删除
bool DeleteBST(BiTree *t,int key);
//二叉排序树上的查找递归算法
bool SearchBST(BiTree t,int key,BiTree f,BiTree *p);
};
//二叉排序树的类实现
//构造二叉链表表示的二叉树T
int BiSearchT::CreateSubTree(BiTree &t,int *all,int i)
{if((all[i]==0)||i>16)
{t=NULL;
return 1;}
t=(BiNode *)malloc(sizeof(BiNode));
if(t==NULL) return 0;
t->data=all[i];
CreateSubTree(t->l,all,2*i);
CreateSubTree(t->r,all,2*i+1);
}
//先序遍历二叉树T
int BiSearchT::PreOrderTraverse(BiTree t,int (*Visit)(int d))
{
if(t){
if(Visit(t->data))
if(PreOrderTraverse(t->l,Visit))
if(PreOrderTraverse(t->r,Visit)) return 1;
return 0;
} else return 1;
}
//中序遍历二叉树T
int BiSearchT::InOrderTraverse(BiTree t,int (*Visit)(int d))
{
if(t){
if(InOrderTraverse(t->l,Visit))
if(Visit(t->data))
if(InOrderTraverse(t->r,Visit)) return 1;
return 0;
}else return 1;
}
//二叉排序树上的查找递归算法
bool BiSearchT::SearchBST(BiTree t,int key,BiTree f,BiTree *p)
{if(!t) {*p=f;return false;}//递归的终结条件
else if(key==t->data){ *p=t;return true;}
else if(key<t->data) SearchBST(t->l,key,t,p);
else SearchBST(t->r,key,t,p);//继续在右子树中查找
}
//插入算法
int BiSearchT::InsertBST(BiTree *t,int e){
BiTree p;
BiTree s;
if(!SearchBST(*t,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *t=s;
else if(e<p->data) p->l=s;
else p->r=s;
return true;
}
else return false;
}
//在二叉排序树中删除一个节点
void BiSearchT::Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r)//在右子树删除
{q=(*p);
(*p)=(*p)->l;
free(q);}
else if(!(*p)->l)//在左子树删除
{q=(*p);
(*p)=(*p)->r;
free(q);}
else
{q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;}
}
//二叉排序树的删除
bool BiSearchT::DeleteBST(BiTree *t,int key)
{if(*t!=NULL)
{if (key==(*t)->data) Delete(t);
else
if(key<(*t)->data) DeleteBST(&((*t)->l),key);
else DeleteBST(&((*t)->r),key);
return true;}
else return false;
}
代码调用如下
//输出二叉排序树的数据域值
int printelem(int d)
{cout<<setw(4)<<d;
return 1;
}
//二叉排序树类的测试
void main()
{cout<<"运行结果:\n";
BiTree root;
BiTree sroot=NULL;
BiTree croot=NULL;
int all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0};
int i,a[10]={45,23,12,3,33,27,56,90,120,62};
int n=7,b[]={10,7,6,9,20,12,22};
BiSearchT my;
my.CreateSubTree(root,all,1);
cout<<"先序遍历(root,all):\n";
my.PreOrderTraverse(root,printelem);
cout<<"\n中序遍历(root,all):\n";
my.InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
my.InsertBST(&sroot,a[i]);
cout<<"\n中序遍历(sroot,a):\n";
my.InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
my.DeleteBST(&sroot,a[i]);
cout<<"\nNow sroot has nodes:\n";
my.InOrderTraverse(sroot,printelem);
for(i=0;i<n;i++)
my.InsertBST(&croot,b[i]);
cout<<"\n中序遍历(croot,b):\n";
my.InOrderTraverse(croot,printelem);
my.InsertBST(&croot,8);
cout<<"\n中序遍历(croot,b):\n";
my.InOrderTraverse(croot,printelem);
my.DeleteBST(&croot,7);
cout<<"\n中序遍历(croot,b):\n";
my.InOrderTraverse(croot,printelem);
cin.get();}
效果如下
代码下载
http://download.csdn.net/detail/yincheng01/4789037