二叉搜索树

二叉搜索树定义

对于任意结点，其关键字不小于其左子树的最大关键字，不大于其右子树中的最小关键字。

示例：

BST_Demo.svg

  • 二叉搜索树构建 ```c / 31_二叉树——构建二叉查找树/ Status binSerchAddElem_T(BinaryTree& cur, BiTreeNodeElementType elem) { // 方法是向已有二叉搜索树中加入元素，若当前二叉树为空，则构建新的二叉树 // 结点为空时创建结点并设置值，从父节点迭代到左孩子或右孩子时执行 if (!cur) {

    1.   cur = (BinaryTree)malloc(sizeof(BinaryTreeNode));
    2.   if (!cur)
    3.   {
    4.       printf("构建失败！");
    5.       return ERROR;
    6.   }
    7.   cur->data = elem;
    8.   cur->left = NULL;
    9.   cur->right = NULL;
    10.   cur->ltag = false;
    11.   cur->rtag = false;
    12.   return OK;

    } // 元素小于当前结点值，创建左结点 if (elem < cur->data) {

    1.   if (!binSerchAddElem_T(cur->left, elem))
    2.   {
    3.       return ERROR;
    4.   }

    } // 元素大于等于当前结点值，创建右结点 else {

    1.   if (!binSerchAddElem_T(cur->right, elem))
    2.   {
    3.       return ERROR;
    4.   }

    }

    return OK; }

/ 32_二叉树——构建二叉查找树/ void buildBinarySearchTree(BinaryTree& bst, BiTreeNodeElementType arr, int length) { // 批量加元素即可 for (int i = 0; i < length; i++) { binSerchAddElem_T(bst, (arr + i)); } }

  2.    - 概念
  3.       - 或为空树。
  4.       - 左子树不空，左子树上所有结点值均小于根结点值；
  5.       - 右子树不空，右子树上所有结点值均大于根结点值。
  6.    - 构建过程。
  7.       - 顺着二叉搜索树，逐一于当前结点进行比较；
  8.          - 若小于当前结点的值，则与其左孩子根结点值比较；
  9.          - 否则与右孩子根结点值比较。
  10.       - 重复比较过程，直到当前结点为空。创建结点，将元素值赋值到新结点中。
  11. - 二叉搜索树删除单个结点
  12.    - 性质不变：删除某个结点后，仍然保持二叉搜索树的结构特性（**中序遍历为非递减序列**）。
  13.    - 关键影响因素 => 在BST中**待删除结点的位置**。
  14.    - 删除操作的关键：对不同位置结点的删除操作处理，如何**保证**删除后的**性质不变性**。
  15.    - 根据对不同情况的处理（主要是**根据后继结点**的处理思路），分为以下几种情况（定义**待删除结点z**，其**左孩子left**， **右孩子right**，**中序后继结点Y**，**Y的右孩子为X**）
  16.       - z无左子树，右子树可有可无（00, 01）<br />![BST_Delete_1.svg](https://cdn.nlark.com/yuque/0/2021/svg/21873585/1624244711510-14c663c5-2eff-4e8a-85f1-e233bc1529f2.svg#align=left&display=inline&height=316&margin=%5Bobject%20Object%5D&name=BST_Delete_1.svg&originHeight=316&originWidth=679&size=10398&status=done&style=none&width=679)
  17.          - 直接将**右孩子替换Z的位置**
  18.       - z有且仅有左孩子（10）<br />![BST_Delete_2.svg](https://cdn.nlark.com/yuque/0/2021/svg/21873585/1624244727466-935f2c6f-af01-4bb9-a2f5-da6ecfdaf3ce.svg#align=left&display=inline&height=326&margin=%5Bobject%20Object%5D&name=BST_Delete_2.svg&originHeight=326&originWidth=766&size=10382&status=done&style=none&width=766)
  19.          - 直接将**左孩子替换Z的位置**
  20.       - z有两个孩子（11），则需要先找到Z的中序后继结点Y
  21.          - Z的右孩子根结点无左子树，则Y == Z->right<br />![BST_Delete_3.svg](https://cdn.nlark.com/yuque/0/2021/svg/21873585/1624244733786-ffc7390b-9277-4208-a497-d6243e6aa6eb.svg#align=left&display=inline&height=476&margin=%5Bobject%20Object%5D&name=BST_Delete_3.svg&originHeight=476&originWidth=1086&size=16675&status=done&style=none&width=1086)
  22.             - Y替换Z的位置，并且**左指针**指向Z的左孩子
  23.          - Z的右孩子根结点有左子树，则后继Y在其左子树中。<br />![BST_Delete_4.svg](https://cdn.nlark.com/yuque/0/2021/svg/21873585/1624244751232-48430e58-dbda-4ff1-97ac-574873f47b7c.svg#align=left&display=inline&height=696&margin=%5Bobject%20Object%5D&name=BST_Delete_4.svg&originHeight=696&originWidth=1815&size=31934&status=done&style=none&width=1815)
  24.             - 首先用**Y的右子树X**的位置替换Y的位置；
  25.             - 用结点**Y的右指针指向right**；
  26.             - Y的**左指针指向left**，并**替换Z的位置**。
  27.    - 注意事项
  28.       - 替换位置，即是需要找到其父结点指向该结点的指针，父结点可能通过**左指针或右指针**指向该结点；
  29.       - 找Z的中序后继结点Y的操作，关键在于Z的**右子树根结点是否有左子树**。
  30.    - 代码实现
  31. ```c
  32. /* 33_二叉树——二叉搜索树删除指定结点*/
  33. Status deleteBiSearchElem_T(BinaryTree& bst, BinaryTree& toDel)
  34. {
  35.     // 先找到其父结点
  36.     BinaryTree parent = parentBiNode_T(bst, toDel);
  37.     // 若父结点不存在，则当前即为根结点，直接删除结点并置空
  38.     if (!parent)
  39.     {
  40.         bst = NULL;
  41.         delete toDel;
  42.         toDel = NULL;
  43.         return OK;
  44.     }
  45.     // 四种情况
  46.     // 1. 待删除结点z无左孩子，用右孩子替换
  47.     if (!toDel->left)
  48.     {
  49.         // 当前结点与父节点的关系
  50.         if (parent->left == toDel) {
  51.             parent->left = toDel->right;
  52.         }
  53.         else
  54.         {
  55.             parent->right = toDel->right;
  56.         }
  57.         delete toDel;
  58.         toDel = NULL;
  59.         return OK;
  60.     }
  61.     // 2. 待删除结点z仅有左孩子
  62.     else if (toDel->left && !toDel->right)
  63.     {
  64.         if (parent->left == toDel)
  65.         {
  66.             parent->left = toDel->left;
  67.         }
  68.         else
  69.         {
  70.             parent->right = toDel->left;
  71.         }
  72.         return OK;
  73.     }
  74.     // 3. 待删除结点z有两个孩子
  75.     else
  76.     {
  77.         // 待删除结点的后继
  78.         BinaryTree post = inorderPost_T(bst, toDel);
  79.         // 无左孩子，右子树根结点即是后继
  80.         if (post == toDel->right)
  81.         {
  82.             // 左孩子先替换为待删除结点的左孩子
  83.             post->left = toDel->left;
  84.             // 将后继替换待删除
  85.             if (parent->left == toDel)
  86.             {
  87.                 parent->left = post;
  88.             }
  89.             else
  90.             {
  91.                 parent->right = post;
  92.             }
  93.         }
  94.         // 否则后继在其z->right的左子树中
  95.         else
  96.         {            
  97.             // 后继的父结点p
  98.             BinaryTree pParent = parentBiNode_T(bst, post);
  99.             if (pParent->left == post)
  100.             {
  101.                 pParent->left = post->right;
  102.             }
  103.             else
  104.             {
  105.                 pParent->right = post->right;
  106.             }
  107.             // 将后继替换待删除结点，并连接待删除的右子树
  108.             if (parent->left == toDel)
  109.             {
  110.                 parent->left = post;
  111.             }
  112.             else
  113.             {
  114.                 parent->right = post;
  115.             }
  116.             post->left = toDel->left;
  117.             post->right = toDel->right;
  118.             delete toDel;
  119.             toDel = NULL;
  120.         }
  121.         return OK;
  122.     }
  123. }
  125. /* 34_二叉树——查找二叉树中某个结点中序后继，找不到返回NULL*/
  126. BinaryTree inorderPost_T(BinaryTree bt, BinaryTree cur)
  127. {
  128.     if (!bt || !cur)
  129.     {
  130.         return NULL;
  131.     }
  133.     // 1. 有右子树，后继在其右子树中
  134.     BinaryTree post = cur->right;
  135.     if (post)
  136.     {
  137.         while (post->left)
  138.         {
  139.             post = post->left;
  140.         }
  141.         return post;
  142.     }
  143.     // 2. 无右子树
  144.     BinaryTree parent = NULL;
  145.     BinaryTree p = cur;
  146.     // 找到当前为父结点左孩子的结点
  147.     do
  148.     {
  149.         parent = parentBiNode_T(bt, p);
  150.         p = parent;
  151.     } while (parent && parent->left != p);
  152.     return parent;
  153. }