以下是一个小项目，用C语言实现了 二叉排序树 的创建、查找、插入、删除、计算总结点数、中序遍历输出和计算平均查找长度。
（昨天的代码没能成功算平均查找长度，立了flag说之后填坑，没想到今天就成功啦！！！哈哈代码如下：）
1 #include <iostream> 2 using namespace std; 3 typedef int KeyType; 4 typedef struct node 5 { 6 KeyType key; 7 struct node *lchild,*rchild; 8 int level; 9 }BSTNode; 10 typedef BSTNode *BSTree; 11 12 BSTree CreateBST(); 13 void SearchBST(BSTree T,KeyType Key); 14 void InsBST(BSTree *Tptr,KeyType Key); 15 void DelBSTNode(BSTree *Tptr,KeyType Key); 16 void InorderBST(BSTree T); 17 int nodeCount(BSTNode *p); 18 double step=0; 19 20 21 BSTree CreateBST(){ 22 BSTree T; 23 KeyType Key; 24 T=NULL; 25 printf("输入关键字以建立二叉搜索树，以'0'结束 \n"); 26 printf("请输入一个整数关键字: \n"); 27 scanf("%d",&Key); 28 while(Key) 29 { 30 InsBST(&T,Key); 31 printf("请输入下一个整数关键字: \n"); 32 scanf("%d",&Key); 33 } 34 printf("\n二叉排序树创建成功 \n"); 35 return T; 36 } 37 38 void SearchBST(BSTree T,KeyType Key) 39 { 40 BSTNode *p=T; 41 while(p) 42 { 43 if(p->key==Key) 44 { 45 printf("\n已找到输入的数据 \n"); 46 return; 47 } 48 p=(Key<p->key)?p->lchild:p->rchild; 49 } 50 printf("\n未找到输入的数据 \n"); 51 } 52 53 void InsBST(BSTree *T,KeyType Key) 54 { 55 BSTNode *f,*p; 56 p=(*T);//!!? 57 58 while (p) //查找要插入的位置 59 { 60 if(p->key==Key) 61 { 62 printf("\n待插入数据在树中已存在\n"); 63 return; 64 } 65 f=p; 66 p=(Key<p->key)?p->lchild:p->rchild; 67 } 68 p=new BSTNode; 69 p->key=Key; 70 p->lchild=p->rchild=NULL; 71 if((*T)==NULL) 72 { 73 p->level=1; 74 (*T)=p; 75 } 76 else 77 if(Key<f->key) 78 { 79 f->lchild=p; 80 p->level=f->level+1; 81 } 82 else 83 { 84 f->rchild=p; 85 p->level=f->level+1; 86 } 87 88 } 89 90 void DelBSTNode(BSTree *T,KeyType Key) 91 { 92 BSTNode *parent=NULL,*p,*q,*child; 93 p=*T; 94 while(p) //查找要删除结点 95 { 96 if(p->key==Key)break; 97 parent=p; 98 p=(Key<p->key)?p->lchild:p->rchild; 99 } 100 if(!p) 101 { 102 printf("\n没有找到要删除的结点 \n"); 103 return; 104 } 105 q=p; 106 if(q->lchild&&q->rchild) //如果左右子树都不为空 107 for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild); 108 printf("直接后继: %d ",p->key); //查找右子树最左端结点（即中序直接后继） 109 child=(p->lchild)?p->lchild:p->rchild; 110 if(!parent) 111 *T=child; 112 else //若左右子树至少有一个为空 113 { 114 if(p==parent->lchild) 115 parent->lchild=child; 116 else 117 parent->rchild=child; 118 if(p!=q) 119 q->key=p->key; 120 } 121 delete(p); 122 123 } 124 125 void InorderBST(BSTree T) 126 { 127 if(T!=NULL) 128 { 129 InorderBST(T->lchild); 130 printf("\t%d",T->key); 131 printf("(level:%d)",T->level); 132 InorderBST(T->rchild); 133 } 134 } 135 136 137 138 139 int nodeCount(BSTNode *p) //计算结点总数，同时将每一个结点的查找长度累加 140 { 141 if(p == NULL) 142 { 143 return 0; 144 } 145 else 146 { 147 step+=p->level; 148 return 1 + nodeCount(p->lchild) +nodeCount(p->rchild); 149 } 150 151 } 152 153 154 void main() 155 { 156 BSTree T; 157 int choice,n=0; 158 KeyType Key; 159 T=CreateBST(); 160 while(1) 161 { 162 printf("\n 二叉排序树 "); 163 printf("\n***************************"); 164 printf("\n 1---创建二叉排序树 "); 165 printf("\n 2---查找二叉排序树 "); 166 printf("\n 3---插入结点 "); 167 printf("\n 4---删除节点 "); 168 printf("\n 5---输出平均查找长度 "); 169 printf("\n 6---中序输出排序树 "); 170 printf("\n 0---退出 \n"); 171 printf("***************************"); 172 printf("\n\n请输入操作序号: "); 173 scanf("%d",&choice); 174 switch(choice) 175 { 176 case 1:T=CreateBST();break; 177 case 2:printf("\n请输入要查找的数据: "); 178 scanf("%d",&Key); 179 getchar(); 180 SearchBST(T,Key); 181 printf("\n查找完毕\n ");break; 182 case 3:printf("\n请输入要插入的数据: "); 183 scanf("%d",&Key); 184 getchar(); 185 InsBST(&T,Key); 186 printf("\n插入完毕\n ");break; 187 case 4:printf("\n请输入要删除的数据: "); 188 scanf("%d",&Key); 189 getchar(); 190 DelBSTNode(&T,Key); 191 printf("\n删除完毕\n ");break; 192 case 5: 193 step=0; 194 n=nodeCount(T); 195 printf("\n平均查找长度为:%f \n ",step/(n*1.0));break; 196 case 6: 197 InorderBST(T); 198 printf("\n\n 二叉排序树输出完成\n ");break; 199 case 0: 200 return; 201 default:printf("\n输入有误！请重新输入\n "); 202 } 203 } 204 }