二叉查找树C语言实现

二叉查找树C语言实现

二叉查找树描述

二叉查找树的性质：对于树中的每个结点X，它的左子树中所有关键字值小于X的关键值，而它的右子树中所有关键字大于X的关键值。由于树的递归定义，通常是递归的编写查找树的常用操作例程。对这些常用例程中，主要需要考虑的是插入和删除节点。下面将简要说明。（二叉查找树的平均深度是O(logN)，所以一般不需要担心栈空间用尽。）

Insert：为了将X插入到树T中，可以像用Find那样沿着树查找。如果找到X，则什么也不用做。否则，将X插入到遍历的路径上的最后一点上。如下图所示，为了插入5，因而遍历该树，就好像在运行Find。在具有关键字4的节点处需要向右行进，但4的右子树不存在，因此5不在这棵树上，从而这个位置就是所要插入的位置。

Delete：一旦发现要删除的节点，考虑以下三种情况：如果该节点是一片树叶，那么它可以被立即删除；如果节点只有一个儿子，则该节点可以在其父节点调整指针绕过该节点后被删除，如下图：删除只有一个左孩子节点的元素：4。

复杂的情况是处理具有两个儿子的节点。一般的删除策略是用其右子树关键字最小的元素或左子树关键字最大的元素代替该节点的数据并递归的删除那个节点。因为右子树中最小节点不可能有左孩子（左子树的最大值节点则不可能有右孩子），所以第二次Delete变要容易一些。下图是一颗初始的二叉查找树即删除关键字为2的节点后的状态。