二叉查找树是树的一种，可以用于搜索与表达式计算。它规定每个节点最多只能有两个儿子，且左儿子都小于它，右儿子都大于它。搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).
虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.
下面是我使用C语言实现的一个二叉查找树的程序，支持插入元素、在树种寻找某个元素、寻找最大/小元素、删除等操作。你可以用程序指令执行不同的操作。
看下面的程序运行截图：
C语言二叉查找树程序截图
关于打印程序我采用的是先序遍历，先打印出父节点，再打印它的子节点。且每个子节点都相对于它们的父节点一个\t的距离，这样看起来，树的结构更新清晰。
下面是程序的main函数中的代码：
/* 程序退出命令 */int quit = 0;int main(){SearchTree root = NULL;char cmd;int input;Position temp;printf("基本操作命令:*****I插入 D删除 F寻找 S最小 L最大 P和回车打印树 Q退出*****\n");/* 读取用户命令执行操作 */while(1){scanf("%c",&cmd);switch(cmd){case 'I':case 'i':{scanf("%d",&input);root = Insert(input,root);}break;case 'D':case 'd':{scanf("%d",&input);root = Delete(input,root);}break;case '\n':{PrintTree(root,0);}break;case 'F':case 'f':{scanf("%d",&input);printf(Find(input,root)?"找到了\n":"没找到\n");}break;case 'S':case 's':{temp = FindMin(root);temp?printf("找到了是%d\n",temp->key):printf("没找到\n");}break;case 'L':case 'l':{temp = FindMax(root);temp?printf("找到了是%d\n",temp->key):printf("没找到\n");}break;case 'Q':case 'q':{quit = 1;}break;default:{}break;}if(quit)break;}/* 释放这棵树 */MakeEmpty(root);return 0;}
你可以在这里下载整个程序，包含了树操作的一些细节。二叉查找树的例程很好了诠释了递归的思想，如果你能理解程序里面递归的运用，那么以后自己再写递归程序也就更加得心应手了。
参考资料：《数据结构与算法分析 C语言实现》。
维基百科：二叉查找树
若非注明，均为原创文章，转载请注明： 转载自大笨兔
本文链接地址: C语言算法：实现二叉查找树的各个操作
我也相信爱可以排除万难;只是，万难之后，又有万难。这是我更相信的。
