VC++2012编程演练数据结构《21》二叉排序树

大灰狼

二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；
　步骤：若根结点的关键字值等于查找的关键字，成功。
　　否则，若小于根结点的关键字值，递归查左子树。
　　若大于根结点的关键字值，递归查右子树。
　　若子树为空，查找不成功。
　　平均情况分析（在成功查找两种的情况下）
　　在一般情况下，设 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

二叉排序树类实现如下

[cpp] view plaincopy

• #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==0)||i>16)  
•   {t=NULL;  
•    return 1;}  
• t=(BiNode *)malloc(sizeof(BiNode));  
• if(t==NULL) return 0;  
• t->data=all;  
• 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;  
• }  
  

代码调用如下

[cpp] view plaincopy

• //输出二叉排序树的数据域值  
• 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);  
• cout<<"\n中序遍历(sroot,a):\n";  
• my.InOrderTraverse(sroot,printelem);  
• for(i=0;i<3;i++)  
•   my.DeleteBST(&sroot,a);  
• cout<<"\nNow sroot has nodes:\n";  
• my.InOrderTraverse(sroot,printelem);  
• for(i=0;i<n;i++)  
•    my.InsertBST(&croot,b);  
• 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();}  
  

效果如下