纯C,支持添加和删除节点,各种次序(迭代而非递归)遍历整个树,开销小,适合Windows/Linux和嵌入式系统使用。
Demo演示了两组操作,一组是通过空格或左键,演示把一组malloc()出来的一组地址加入tree,然后逐个删除。为了重现操作,方便调试程序,使用了A盘存储临时文件。我的系统上A盘是RAMDisk,如果没有A盘,你可以用subst命令模拟一个。另一组通过INSERT和DELETE键操作。按一下INSERT,就会把插入点用蓝色加亮,再按一下INSERT完成插入操作。插入之后树的局部或整体有可能会被调整,以保证满足AVL树的定义。删除操作类似,第一次按DELETE加亮被删除的节点,再次按DELETE完成删除操作。

有什么用途呢?主要用来作排序和查找。

排序:把一组待排序的数据插入到一颗AVL树,再按中序遍历输出,就可以得到升序或降序的结果。

查找:把本机跟外界的所有TCP连接的socket,以本地端口:远程IP和端口组成KEY,放到一个AVL树里面,就能很快找到对应的socket。建立新连接时插入新的节点,连接断开时删除对应的节点。对于这样离散的数据,用数组管理太大了,用链表效率不高。用映射(MAP)是可以,但需要C++、C#或者Java等语言才有MAP类。
程序截图如下:

上传的附件
  AvlTree.rar