二叉排序(BST)树

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

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

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

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

BST结点结构

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

查找

递归实现

Node* bstree_search(BSTree x, Type key)
{
  if (x==NULL || x->key==key)
    return x;
  if (key < x->key)
    return bstree_search(x->left, key);
  else
    return bstree_search(x->right, key);
}

非递归实现

Node* iterative_bstree_search(BSTree x, Type key)
{
  while ((x!=NULL) && (x->key!=key))
  {
    if (key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  return x;
}

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

Node* bstree_minimum(BSTree tree)
{
  if (tree == NULL)
    return NULL;
  while(tree->left != NULL)
    tree = tree->left;
  return tree;
}

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

Node* bstree_maximum(BSTree tree)
{
  if (tree == NULL)
    return NULL;
  while(tree->right != NULL)
    tree = tree->right;
  return tree;
}

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

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

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

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

插入

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

static Node* bstree_insert(BSTree tree, Node *z)
{
  Node *y = NULL;
  Node *x = tree;
  /* 查找z的插入位置 */
  while (x != NULL)
  {
    y = x; /* y 保留上一个的x 结点 */
    if (z->key < x->key)
       x = x->left;
    else
       x = x->right;
  }
  z->parent = y;
  if (y==NULL)
    tree = z;
  else if (z->key < y->key)
    y->left = z;
  else
    y->right = z;
  return tree;
}

Node* insert_bstree(BSTree tree, Type key)
{
  Node *z;
  if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
    return tree;
  return bstree_insert(tree, z);
}

删除

void DeleteBST(BitNode *T, int key)
{
    BitNode *q,*s;
    BitNode *node=searchBST(T,key,NULL,&s);
    if(node==NULL)
    {
        printf("\n此树中没有此节点\n");
        return ;
    }
    else
    {
        if(node->lchild==NULL && node->rchild==NULL)
        {
            printf("此节点是一个叶子节点\n");
            node->parent->lchild=node->parent->rchild=NULL;
            free(node);
        }
        else if(node->rchild==NULL)
        {
            printf("此节点只有左子树\n");
            q=node;
            node=node->lchild;
            if(q==q->parent->rchild)
                q->parent->rchild=node;
            else
                q->parent->lchild=node;

            free(q);
        }
        else if(node->lchild==NULL)
        {
            printf("此结点只有右子树\n");
            q=node;
            node=node->rchild;
            if(q==q->parent->rchild)
                q->parent->rchild=node;
            else
                q->parent->lchild=node;

            free(q);
        }
        else
        {
            q=node;
            s=node->lchild;
            while(s->rchild)
            {
                q=s;
                s=s->rchild;
            }
            node->data=s->data;
            if(q!=node)
                q->rchild=s->lchild;
            else
                q->lchild=s->lchild;
            free(s);
        }
    }
}

另一种写法

static Node* bstree_delete(BSTree tree, Node *z)
{
  Node *x=NULL;
  Node *y=NULL;

  /* 若z结点只有左子树或只有右子树或者是叶子节点 */
  if ((z->left == NULL) || (z->right == NULL) )
     y = z;
  else  /* z 结点的左右子树都不为空 */
     y = bstree_successor(z); /* 前驱结点 */

  if (y->left != NULL)
     x = y->left;
  else
     x = y->right;

  if (x != NULL)
     x->parent = y->parent;

  if (y->parent == NULL)
     tree = x;
  else if (y == y->parent->left)
     y->parent->left = x;
  else
     y->parent->right = x;

  if (y != z) 
     z->key = y->key;

  if (y!=NULL)
     free(y);
  return tree;
}

Node* delete_bstree(BSTree tree, Type key)
{
  Node *z, *node; 
  if ((z = bstree_search(tree, key)) != NULL)
     tree = bstree_delete(tree, z);
  return tree;
}

/* 销毁二叉树 */
void destroy_bstree(BSTree tree)
{
  if (tree==NULL)
    return ;
  if (tree->left != NULL)
    destroy_bstree(tree->left);
  if (tree->right != NULL)
    destroy_bstree(tree->right);
  free(tree);
}