算法复习（4）-二进制排序树

二进制排序树（BST，二进制排序树）的定义:

如果其左子树不为空，则左子树上所有关键字的值小于root关键字的值. 如果其右子树不为空，则右子树上的所有关键字的值均大于root关键字的值的左子树和右子树均是二进制排序树.

说明: 根据二进制排序树的定义二叉排序树查找算法，如果输出二进制排序树的中序遍历序列二叉排序树查找算法，则该序列将递增且有序.

二进制排序树的存储结构:

二进制排序树通常存储在二进制链表中，其节点类型定义与常规二进制树相似.

typedef struct TreeNode {
  int key;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode;

BTNode *BSTSearch(BTNode *bt, int key) {
  if (bt == NULL)
    return NULL;
  else  {
    if (bt->key == key)
      return bt;
    else if (key < bt->key)
      return BSTSearch(bt->lchild, key);
    else
      return BSTSearch(bt->rchild, key);
  }
}

二进制排序树是一个查找表. 要插入关键字，必须首先找到插入位置. 对于二进制排序树中不存在的关键字，搜索失败的位置是关键字的插入位置.

int BSTInsert(BTNode *&bt, int key)//因为插入，bt要改变，所以要用引用型指针
{
  if (bt == NULL)  {
    bt = (BTNode *)malloc(sizeof(BTNode));
    bt->lchild = bt->rchild = NULL;
    bt->key = key;
    return 1;
  }
  else {
    if (bt->key == key)
      return 0;
    else if (bt->key < key)
      return BSTInsert(bt->lchild, key);
    else 
      return BSTInsert(bt->rchild, key);
  }
}

描述: 在二进制排序树中插入的关键字存储在新创建的叶子上. 由于找到的插入位置始终位于空指针字段上，因此在空指针字段上连接的新节点必须是叶子节点.

构建二元排序树只需要构建一棵空树，然后将关键字一一插入到空树中即可构建二叉排序树.

void CreateBST(BTNode *&bt, int key[ ], int n) {
  int i;
  bt = NULL;
  for (i = 0; i < n; ++i)
    BSTInsert(bt, key[i]);
}

假定二元排序树上的已删除节点为p，f为父节点，则删除节点p的过程分为以下三种情况.

p节点是叶节点. 您可以直接删除p节点. 只有左子树没有右子树，或者只有右子树没有左子树. 在这种情况下，您只需要删除p并将原始指针指向其唯一的左或右子树. 假设p节点同时具有左和右子树. 此时，可以将这种情况转换为1）或2）中的情况，方法是: 首先跟随p的左子树根节点的右指针，然后继续向右直到到达p的最右端. 它的右子树A节点r（也可以沿着p的右子树根节点的左指针向左移动，直到到达其左子树的最左节点）. 然后将p中的关键字替换为r中的关键字. 最后，如果r是叶节点，则按照1）中的方法删除r；如果r是非叶节点，请按照2）中的方法删除r（此时r不能是具有两个子树的节点）.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-167955-1.html