二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据成员,且小于右子树所有节点的数据成员。排序二叉树的中序遍历结果是从小到大排列的。
二叉排序树的查找和插入比较好理解,主要来看一下删除时的情况。
如果需要查找并删除如图8-6-8中的37, 51, 73,93这些在二叉排序树中是叶子的结点,那是很容易的,毕竟删除它们对整棵树来说,其他结点的结构并未受到影响。
对于要删除的结点只有左子树或只有右子树的情况,相对也比较好解决。那就是结点删除后,将它的左子树或右子树整个移动到删除结点的位置即可,可以理解为独子继承父业。比如图8-6-9,就是先删除35和99两结点,再删除58结点的变化图,最终,整个结构还是一个二叉排序树。
但是对于要删除的结点既有左子树又有右子树的情况怎么办呢?比如图8-6-10中的47结点若要删除了,它的两儿子和子孙们怎么办呢?
前人总结的比较好的方法就是,找到需要删除的结点p的直接前驱(或直接后继)s,用s来替换结点p,然后再删除此结点s,如图8-6-12所示。
注意:这里的前驱和后继是指中序遍历时的顺序。
Deletion
There are three possible cases to consider:
• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Remove the node and replace it with its child.
• Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-
order predecessor node, R. Replace the value of N with the value of R, then delete R.
As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most
child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.
下面来看代码:(参考《linux c 编程一站式学习》
/*************************************************************************
> File Name: binarysearchtree.h
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:05:55 PM CST
************************************************************************/
#ifndef BST_H
#define BST_H
typedef struct node *link;
struct node
{
unsigned char item;
link left, right;
};
link search(link t, unsigned char key);
link insert(link t, unsigned char key);
link delete(link t, unsigned char key);
void print_tree(link t);
#endif
/*************************************************************************
> File Name: binarysearchtree.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:08:08 PM CST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include "binarysearchtree.h"
static link make_node(unsigned char item)
{
link p = malloc(sizeof(*p));
p->item = item;
p->left = p->right = NULL;
return p;
}
static void free_node(link p)
{
free(p);
}
link search(link t, unsigned char key)
{
if (!t)
return NULL;
if (t->item > key)
return search(t->left, key);
if (t->item < key)
return search(t->right, key);
/* if (t->item == key) */
return t;
}
link insert(link t, unsigned char key)
{
if (!t)
return make_node(key);
if (t->item > key) /* insert to left subtree */
t->left = insert(t->left, key);
else /* if (t->item <= key), insert to right subtree */
t->right = insert(t->right, key);
return t;
}
link delete(link t, unsigned char key)
{
link p;
if (!t)
return NULL;
if (t->item > key) /* delete from left subtree */
t->left = delete(t->left, key);
else if (t->item < key) /* delete from right subtree */
t->right = delete(t->right, key);
else /* if (t->item == key) */
{
if (t->left == NULL && t->right == NULL)
{
/* if t is a leaf node */
free_node(t);
t = NULL;
}
else if (t->left) /* if t has left subtree */
{
/* replace t with the rightmost node in left subtree */
for (p = t->left; p->right; p = p->right);
t->item = p->item; /* 将左子树下最靠右的节点值赋予想要删除的节点 */
t->left = delete(t->left, t->item);
}
else /* if t has right subtree */
{
/* replace t with the leftmost node in right subtree */
for (p = t->right; p->left; p = p->left);
t->item = p->item;
t->right = delete(t->right, t->item);
}
}
return t;
}
void print_tree(link t)
{
if (t)
{
printf("(");
printf("%d", t->item);
print_tree(t->left);
print_tree(t->right);
printf(")");
}
else
printf("()");
}
/*************************************************************************
> File Name: main2.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:22:57 PM CST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "binarysearchtree.h"
#define RANGE 100
#define N 6
void print_item(link p)
{
printf("%d", p->item);
}
int main(void)
{
int i, key;
link root = NULL;
srand(time(NULL));
for (i = 0; i < N; i++)
{
root = insert(root, rand() % RANGE); /* 第一次循环root从NULL变成根节点值,接下去
的循环虽然迭代root,但在插入节点过程中root的值始终不变 */
printf("root = 0x%x\n", (unsigned int)root);
}
printf("\t\\tree");
print_tree(root);
printf("\n\n");
while (root)
{
key = rand() % RANGE;
if (search(root, key))
{
printf("delete %d in tree\n", key);
root = delete(root, key); /* root虽然迭代,但返回的仍是先前的值,即根节点的值保持不变
直到全部节点被删除,root变成NULL即0x0 */
printf("root = 0x%x\n", (unsigned int)root);
printf("\t\\tree");
print_tree(root); /* 传递给函数的一直是根节点的值,直到树清空,root变成NULL */
printf("\n\n");
}
}
return 0;
}
输出为:
如果我们使用了The Tree Preprocessor,可以将以括号展示的排序二叉树转换成树形展示,如下图
以前此工具可以在 http://www.essex.ac.uk/linguistics/clmt/latex4ling/trees/tree/ 下载,现已找不到链接,我将其上传到csdn,需要的可以去下载。
http://download.csdn.net/detail/simba888888/5334093
最后提一下,我们希望构建出来的二叉排序树是比较平衡的,即其深度与完全二叉树相同,那么查找的时间复杂度研究度O(logn),近似于折半查找,
但如果出现构造的树严重不平衡,如完全是左斜树或者右斜树,那么查找时间复杂度为O(n),近似于顺序查找。那如何让二叉排序树平衡呢?
事实上还有一种平衡二叉树(AVL树),也是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。
补充:delete() 在《data structure and algorithm analysis in c》 中的实现,个人觉得比较清晰,也挺好理解的,如下:
link FindMin(link T)
{
if (T != NULL)
while (T->left != NULL)
T = T->left;
return T;
}
link delete(unsigned char X, link T)
{
link tmp;
if (T == NULL)
{
printf("Tree is empty!\n");
return NULL;
}
if (X < T->key) //go left
T->left = delete(X, T->left);
else if (X > T->key) // go right
T->right = delete(X, T->right);
/* found elem to be deleted*/
else if (T->left && T->right) //have two children
{
// replace with smallest in right subtree
tmp = FindMin(T->right);
T->key = tmp->key;
T->right = delete(T->key, T->right);
}
else //one or zero children
{
tmp = T;
if (T->left == NULL)
T = T->right;
else if (T->right == NULL)
T = T->left;
free(tmp);
}
return T;
}
参考:
《大话数据结构》
《linux c 编程一站式学习》
《Data Structures》