每个结点的C(i)为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为，其平均查找长度为(n+1)/2(和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比
打开IDE
二叉排序树类实现如下
#include "stdafx.h"//二叉排序树#include#include #include 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);};//二叉排序树的类实现//构造二叉链表表示的二叉树Tint 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);}//先序遍历二叉树Tint 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;}//中序遍历二叉树Tint 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 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 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< < 效果如下
代码下载