資料結構複習(十) : 二元搜索樹

前一章講到二元樹這麼一個特殊結構，可能有同學覺得奇怪了，學這二元樹究竟在現實中有甚麼用處呢?為什麼還要特地學這麼一個麻煩的結構? 這章節就來講講"樹"這一個結構中最實用的二元搜索樹(Binary Search Tree)!!

樹的結構
typedef struct TNode * Position;   //重新命名單個節點地址指針
typedef Position BinTree;    //重新命名根結點地址指針
struct TNode{
  ElementType Data;
  BinTree Left;
  BinTree Right;
};

二元搜索樹是一種"有約束"的二元樹，又稱二元排序樹、二元查找樹、有序二元樹，從字面上就能知道"約束"什麼了吧!就是 "排序"，定義如下:

當二元搜索樹不為空時滿足以下條件:
1. 所有"根"節點左邊的值皆小於根
2. 所有"根"節點右邊的值皆大於根
3. 所有子樹皆為二元搜索樹

所有左比根小，所有右比根大

聰明的同學一眼就能看出，當我們對二元搜索樹進行"中序"遍歷時能夠得到一個由小到大的有序序列。

二元搜索樹的方法:
1. Position FindMin(BinTree BST);   //找到最大最小值
2. Position FindMax(BinTree BST);
3. Position Find(BinTree ,ElementType X);   //查找X，並回傳節點地址
4. BinTree Insert(BinTree BST,ElementType X);  //插入
5. BinTree Delete(BinTree BST, ElementType X);  //刪除值為X節點

1. 找到最大最小 FindMax、FindMin

根据二元搜索樹的特性，我們可以知道最大，肯定在最右邊的端點，最小一定是最大值，反之，最左邊端點一定是最小值。

Position FindMin(BinTree BST){
  if(!BST) return NULL;          //如果是空樹，返回NULL
  else if(!BST->Left) return BST;  //返回當沒有左子時，代表是最左端點
  else return FindMin(BST->Left);     //遞歸左邊
}

當然由於只是單純的不斷向左(右)尋找，你可以把遞歸改成迴圈

Position FindMax(BinTree BST){
  if(BST){
    while(BST->Right){    //如果右邊還有孩子
      BST = BST->Right;   //不斷向右
    }
  }
  return BST;
}

2. 查找 Find

查找是二元搜索樹最擅長的了，由於樹內的資料是有序的，查找的時間複雜度為****O(樹的高度)*** 不是O(logN)喔!，如何查找呢?

對要查找X傳入後
1. 如果根結點值小於X代表左子樹全部小於X，可以跟根的右子做比較了!!
2. 反之，則在左子樹內進行搜尋
3. 如果根 == X 返回根結點地址
4. 如果比較到最後 根==NULL 代表找不到了，返回NULL

是不是很有二分搜查法的味道!!下面是查找的代碼與二分查找法的傳送門。

數據結構外傳(一) : 二分查找法

Position Find(BinTree BST, ElementType X){
  if(!BST) return NULL;  //查找失敗
  
  if(X>BST->Data)
    return Find(BST->Right,X);   //在右子樹查找
  else if(X<BST->Data)
    return Find(BST->Left,X);    //在左子樹查找
  else
    return BST;          //X==BST->Data
}

當然!你也可以用迴圈實現

Position Find(BinTree BST, ElementType X){
  while(BST){
    if(X>BST->Data)
      BST = BST->Right;
    else if(X<BST->Data)
      BST = BST->Left;
    else if(X == BST->Data)
      break;    //找到了，跳出迴圈
  }
  return BST;   //如果找不到BST == NULL
}

3. 插入 Insert

插入就沒有查找這麼容易了，由於二元搜索樹是"有序"的，插入時可不能隨便亂插。插入的關鍵就是要找到相應的位置(Find)，如果BST插入X時有找到X，則代表數重複了，可以放棄插入動作，如果沒有找到，則查找終止的位置就是X應該插入的位置。

BinTree Insert(BinTree BST,ElementType X){
  if(!BST){   //如果Position沒有節點，建立一個新的節點
    BST = (BinTree)malloc(sizeof(struct TNode));
    BST->Data = X;
    BST->Left = BST->Right = NULL;
  }else{
    if(X<BST->Data)   //如果X<根，遞歸尋找左節點，直到找不到了
      BST->Left = Insert(BST->Left,X);
    else
      BST->Right = Insert(BST->Right,X);
    //如果 X == BST->Data 不做事
  }
  
  return BST;
}

寫的真的是很漂亮，我第一次看的時候被驚豔到了!!

4. 刪除 Delete

刪除操作比其他操作更為複雜，要刪除的節點在"樹"中的位置決定了所需要採取的操作，總共有三種可能性。

1. 刪除葉節點
2. 刪除有一個孩子的節點
3. 刪除有兩個孩子的節點

1. 刪除的是葉節點 : 那就直接刪除，最簡單
2. 刪除一個孩子的節點: 將父節點的指針改指向孩子節點

3. 刪除兩個孩子的節點 : 有左右兩顆子樹，因此有兩種填充被刪除節點的方法。(1)是找出左子樹最大的節點(2)是找出右子樹最小的節點，有趣的是，被找來填充的節點，最多只會有一個孩子，因此可以用上面刪除方法1、2來斷開連結。

實現上述三種方法代碼如下:

BinTree Delete(BinTree BST, ElementType X){
  Position temp;
  if(!BST)
    printf("沒有找到節點");
  else{
    if(X<BST->Data)
      BST->Left = Delete(BST->Left,X);  //向左遞歸找節點刪除
    else if(X>BST->Data)
      BST->Right = Delete(BST->Right,X);  //向右遞歸找節點刪除
    else{   //BST就是要刪除的節點
      if(BST->Left && BST->Right){        //如果BST有兩個子節點
        temp = FindMax(BST->Left);       //找到左子樹最大的節點填進去
        BST->Data = temp->Data;
        BST->Left = Delete(BST->Left,BST->Data);   //把左子樹最大值刪除
      }else{      //被刪除節點只有一個孩子或沒有孩子
        temp = BST;   
        if(!BST->Left)       //只有右孩子or沒孩子
          BST = BST->Right;
        else
          BST = BST->Left;
        free(temp);
      }
    }
  }
  return BST;
}

插入與刪除的代碼都很值得研究研究，寫的相當漂亮!

總結:

二元搜索樹在插入、刪除、查找皆有很不錯的成績，是相當常見的一種資料結構，三種動作時間複雜度為 O(樹的高度)，當此二元搜索樹是完全二元樹時，所有的動作時間複雜度為O(logN)。然而，插入的是已經排序好的數列，例如{1,2,3,4,5}，整個二元樹會退化為一個串列，以上三個動作時間複雜度變成O(N)，有沒有方法解決?當然有，這就是下次要講的平衡二元搜索樹中的AVL。

完整程式碼 :

輸出結果:

參考資料:

1. 《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
2. https://www.icourse163.org/course/ZJU-93001

資料結構複習(九): 二叉樹遍歷