二叉排序树(Binary Sort Tree,BST)又称为二叉查找树,二叉搜索树,具有以下性质:

  1. 如果左子树不为空,则左子树上所有结点的值都小于根结点的值.
  2. 如果右子树不为空,则右子树上所有结点的值均大于根结点的值.
  3. 左右子树也分别为二叉排序树.
  4. 树中没有相同的结点.

如果用中序遍历二叉排序树,则遍历结果是一个递增序列.

与二分查找类似，查找过程中和关键字比较的次数不超过树的深度。当二叉排序树形态比较对称，此时与折半查找相似，时间复杂度为$O(\log_{2}n)$，最坏情况下二叉排序树是一颗单树(只有左子树或只有右子树)，时间复杂度为$O(n)$。

BST结点结构

1
typedef int Type;
2
typedef struct BSTreeNode{
3
  Type   key;                  /* 关键字(键值) */
4
  struct BSTreeNode *left;     /* 左孩子 */
5
  struct BSTreeNode *right;    /* 右孩子 */
6
  struct BSTreeNode *parent;   /* 父结点 */
7
}Node, *BSTree;

查找

递归实现

1
Node* bstree_search(BSTree x, Type key)
2
{
3
  if (x==NULL || x->key==key)
4
    return x;
5
  if (key < x->key)
6
    return bstree_search(x->left, key);
7
  else
8
    return bstree_search(x->right, key);
9
}

非递归实现

1
Node* iterative_bstree_search(BSTree x, Type key)
2
{
3
  while ((x!=NULL) && (x->key!=key))
4
  {
5
    if (key < x->key)
6
      x = x->left;
7
    else
8
      x = x->right;
9
  }
10
  return x;
11
}

查找最小结点：返回tree为根结点的二叉树的最小结点。

1
Node* bstree_minimum(BSTree tree)
2
{
3
  if (tree == NULL)
4
    return NULL;
5
  while(tree->left != NULL)
6
    tree = tree->left;
7
  return tree;
8
}

查找最大结点：返回tree为根结点的二叉树的最大结点。

1
Node* bstree_maximum(BSTree tree)
2
{
3
  if (tree == NULL)
4
    return NULL;
5
  while(tree->right != NULL)
6
    tree = tree->right;
7
  return tree;
8
}

找结点的后继结点。即，查找二叉树中数据值大于该结点的最小结点。

1
Node* bstree_successor(Node *x)
2
{
3
  /* 如果x存在右孩子，则x的后继结点为:以其右孩子为根的子树的最小结点 */
4
  if (x->right != NULL)
5
    return bstree_minimum(x->right);
6
  /* 如果x没有右孩子。则x有以下两种可能：
7
  1. x是一个左孩子，则x的后继结点为: 它的父结点。
8
  2. x是一个右孩子，则查找x的最低父结点，并且该父结点要具有左孩子，找到的这个最低父结点就是x的后继结点。
9
  */
10
	Node* y = x->parent;
11
  while ((y!=NULL) && (x==y->right)) /* x==y->right 说明x是一个右结点 */
12
  {
13
     x = y;
14
     y = y->parent;
15
  }
16
  return y;
17
}

找结点的前驱结点。即，查找二叉树中数据值小于该结点的最大结点。

1
Node* bstree_predecessor(Node *x)
2
{
3
  /* 如果x存在左孩子，则x的前驱结点为:以其左孩子为根的子树的最大结点 */
4
  if (x->left != NULL)
5
    return bstree_maximum(x->left);
6
  /* 如果x没有左孩子。则x有以下两种可能：
7
  1. x是一个右孩子，则x的前驱结点为它的父结点。
8
  2. x是一个左孩子，则查找x的最低父结点，并且该父结点要具有右孩子，找到的这个最低父结点就是x的前驱结点。
9
  */
10
	Node* y = x->parent;
11
  while ((y!=NULL) && (x==y->left))
12
  {
13
     x = y;
14
     y = y->parent;
15
  }
16
  return y;
17
}

插入

结点的插入具有递归性,最终结点将作为叶子结点(意味着结点的left,right指针为 null)插入到树中。

1
static Node* bstree_insert(BSTree tree, Node *z)
2
{
3
  Node *y = NULL;
4
  Node *x = tree;
5
  /* 查找z的插入位置 */
6
  while (x != NULL)
7
  {
8
    y = x; /* y 保留上一个的x 结点 */
9
    if (z->key < x->key)
10
       x = x->left;
11
    else
12
       x = x->right;
13
  }
14
  z->parent = y;
15
  if (y==NULL)
16
    tree = z;
17
  else if (z->key < y->key)
18
    y->left = z;
19
  else
20
    y->right = z;
21
  return tree;
22
}
23
24
Node* insert_bstree(BSTree tree, Type key)
25
{
26
  Node *z;
27
  if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
28
    return tree;
29
  return bstree_insert(tree, z);
30
}

删除

1
void DeleteBST(BitNode *T, int key)
2
{
3
    BitNode *q,*s;
4
    BitNode *node=searchBST(T,key,NULL,&s);
5
    if(node==NULL)
6
    {
7
        printf("\n此树中没有此节点\n");
8
        return ;
9
    }
10
    else
11
    {
12
        if(node->lchild==NULL && node->rchild==NULL)
13
        {
14
            printf("此节点是一个叶子节点\n");
15
            node->parent->lchild=node->parent->rchild=NULL;
16
            free(node);
17
        }
18
        else if(node->rchild==NULL)
19
        {
20
            printf("此节点只有左子树\n");
21
            q=node;
22
            node=node->lchild;
23
            if(q==q->parent->rchild)
24
                q->parent->rchild=node;
25
            else
26
                q->parent->lchild=node;
27
28
            free(q);
29
        }
30
        else if(node->lchild==NULL)
31
        {
32
            printf("此结点只有右子树\n");
33
            q=node;
34
            node=node->rchild;
35
            if(q==q->parent->rchild)
36
                q->parent->rchild=node;
37
            else
38
                q->parent->lchild=node;
39
40
            free(q);
41
        }
42
        else
43
        {
44
            q=node;
45
            s=node->lchild;
46
            while(s->rchild)
47
            {
48
                q=s;
49
                s=s->rchild;
50
            }
51
            node->data=s->data;
52
            if(q!=node)
53
                q->rchild=s->lchild;
54
            else
55
                q->lchild=s->lchild;
56
            free(s);
57
        }
58
    }
59
}

另一种写法

1
static Node* bstree_delete(BSTree tree, Node *z)
2
{
3
  Node *x=NULL;
4
  Node *y=NULL;
5
6
  /* 若z结点只有左子树或只有右子树或者是叶子节点 */
7
  if ((z->left == NULL) || (z->right == NULL) )
8
     y = z;
9
  else  /* z 结点的左右子树都不为空 */
10
     y = bstree_successor(z); /* 前驱结点 */
11
12
  if (y->left != NULL)
13
     x = y->left;
14
  else
15
     x = y->right;
16
17
  if (x != NULL)
18
     x->parent = y->parent;
19
20
  if (y->parent == NULL)
21
     tree = x;
22
  else if (y == y->parent->left)
23
     y->parent->left = x;
24
  else
25
     y->parent->right = x;
26
27
  if (y != z) 
28
     z->key = y->key;
29
30
  if (y!=NULL)
31
     free(y);
32
  return tree;
33
}
34
35
Node* delete_bstree(BSTree tree, Type key)
36
{
37
  Node *z, *node; 
38
  if ((z = bstree_search(tree, key)) != NULL)
39
     tree = bstree_delete(tree, z);
40
  return tree;
41
}
42
43
/* 销毁二叉树 */
44
void destroy_bstree(BSTree tree)
45
{
46
  if (tree==NULL)
47
    return ;
48
  if (tree->left != NULL)
49
    destroy_bstree(tree->left);
50
  if (tree->right != NULL)
51
    destroy_bstree(tree->right);
52
  free(tree);
53
}