二叉排序樹

二叉排序樹（Binary Sort Tree）：或者是一顆空樹，或者是具有下面性質的樹：（1）若它的左子樹不空，則左子樹上是以結點的值均小于它的根節點的值；（2）若它的右子樹不空，則右子樹上的是以結點的值均大于它的根節點的值；（3）它的左、右子樹也各自是二叉排序樹。

二叉排序樹的基本操作均能夠在O(h)時間内完畢（算法導論p165）。

相關操作代碼例如以下：

int InsertBST(BiTree &T, int key)//遞歸插入
{
  if (T == NULL)
  {
    T = new BiNode;
    T->data = key;
    T->lchild = T->rchild = NULL;
    return 1;
  }
  else
  {
    if (key == T->data)
      return 0;
    else if (key < T->data)
      return InsertBST(T->lchild, key);
    else
      return InsertBST(T->rchild, key);
  }
}

int InsertBST_(BiTree &T, int key)//疊代插入
{
  //find the insert position
  BiNode *f = T, *p = T;
  while (p != NULL)
  {
    if (key == p->data)
      return 0;
    f = p;  //記錄上一次訪問的結點
    p = key < p->data ? p->lchild : p->rchild;
  }

  //配置設定新結點
  BiNode *q = new BiNode;
  q->lchild = q->rchild = NULL;
  q->data = key;

  //插入
  if (T == NULL)  //若根為空
  {
    T = q;
    return 1;
  }
  if (key < f->data)
    f->lchild = q;
  else
    f->rchild = q;
  return 1;
}

BiNode *SearchBST(BiTree T, int key)//遞歸搜尋
{
  if (!T)
    return NULL;
  else
  {
    if (key == T->data)
      return T;
    else if (key < T->data)
      return SearchBST(T->lchild, key);
    else
      return SearchBST(T->rchild, key);
  }
}

BiNode* SearchBST_(BiTree T, int key)//疊代搜尋
{
  while (T != NULL)
  {
    if (key == T->data)
      break;
    T = key < T->data ? T->lchild : T->rchild;
  }
  return T;
}

int DeleteNode(BiNode *&p)
{
  BiNode *q;
  //從二叉排序樹中删除結點p，并重接它的的左或右子樹
  if (p == NULL)  return 0;
  if (p->lchild == NULL)   //左子樹空則僅僅需重接右子樹
  {
    q = p; p = p->rchild; delete q;
  }
  else if (p->rchild == NULL)   //右子樹空則僅僅需重接左子樹
  {
    q = p; 
    p = p->lchild; 
    delete q;
  }
  else  //左右子樹均不空
  {
    BiNode *s;
#if 0 
    //用p的直接前驅取代p，然後删除p的直接前驅
    q = p; s = p->lchild;//轉左，然後向右到盡頭
    while (s->rchild)
    {
      q = s; s = s->rchild;
    }
    p->data = s->data;  //s指向被删除結點,q指向被删除結點的前驅
    if (q != p)
      q->rchild = s->lchild;  //重接q的右子樹
    else
      q->lchild = s->lchild;  //重接q的左子樹
#else
    //用p的直接後繼取代p，然後删除p的直接後繼
    q = p; s = p->rchild;
    while (s->lchild)
    {
      q = s; s = s->lchild;
    }
    p->data = s->data;
    if (p != p)
      q->lchild = s->rchild;
    else
      q->rchild = s->rchild;
#endif
    delete s;
  }
  return 1;
}

int DeleteBST(BiTree &T, int key)
{
  if (T == NULL)
    return 0;
  else
  {
    if (key == T->data)
      return DeleteNode(T);
    else if (key < T->data)
      return DeleteBST(T->lchild, key);
    else
      return DeleteBST(T->rchild, key);
  }
}

void CreateBST(BiTree &T, int a[], int n)
{
  T = NULL;
  for (int i = 0; i < n; i++)
  {
    InsertBST_(T, a[i]);
  }
}

void DestoryBST(BiTree &T)
{
  if (T == NULL)
    return;
  DestoryBST(T->lchild);
  DestoryBST(T->rchild);
  delete T; T = NULL;
}

void InOrderTraverse(BiTree T)//=O(n)時間複雜度
{
  if (T == NULL)
    return;
  InOrderTraverse(T->lchild);
  cout << T->data << " ";
  InOrderTraverse(T->rchild);
}      

測試代碼：

int main()
{
  const int n = 10;
  int a[n] = {3, 2, 8, 6, 1, 4, 5, 7, 1, 3};
  BiTree T;
  CreateBST(T, a, n);
  InOrderTraverse(T);
  cout << endl;

  BiNode *p;
  for (int i = 1; i < 10; i++)
  {
    p = SearchBST_(T, i);
    if (p != NULL)
      cout << p->data << endl;
  }

  int b[5]={0, 2, 6, 1, 7};
  int ret;
  for (int i = 0; i < 5; i++)
  {
    ret = DeleteBST(T, b[i]);
    if (ret == 0)
      cout << "删除 " << b[i] << " 失敗" << endl;
    else
    {
      cout << "删除 " << b[i] << " 後: " ;
      InOrderTraverse(T);
      cout << endl;
    }
  }

  DestoryBST(T);
  getchar();
  return 0;
}