• 数据结构——二叉搜索树的实现、删除（最大值和最小值、最大值和最小值）

    目录

    一、二叉搜索树的实现、删除

    1、最大值和最小值

    2、最大值和最小值

    二、二叉搜索树的删除

    1、删除节点的思路

    2、情况一: 没有子节点

    3、情况二: 一个子节点

    4、情况三: 两个子节点

    5、删除节点完整代码

    一、二叉搜索树的实现、删除

    1、最大值和最小值

    2、最大值和最小值

    代码如下面实现

    二、二叉搜索树的删除

    1、删除节点的思路

    • 删除节点要从查找要删的节点开始, 找到节点后, 需要考虑三种情况:

      • 该节点是叶结点(没有子节点) 没有子节点的根节点

      • 该节点有一个子节点

      • 该节点有两个子节点.

    2、情况一: 没有子节点

    - 我们需要检测current的left以及right是否都为null.
    - 都为null之后还要检测一个东西, 就是是否current就是根, 都为null, 并且为跟根, 那么相当于要清空二叉树(当然, 只是清空了根, 因为只有它).
    - 否则就把父节点的left或者right字段设置为null即可.

    3、情况二: 一个子节点

    - 要删除的current结点, 只有2个连接(如果有两个子结点, 就是三个连接了), 一个连接父节点, 一个连接唯一的子节点.
    - 需要从这三者之间: 爷爷 - 自己 - 儿子, 将自己(current)剪短, 让爷爷直接连接儿子即可.
    - 这个过程要求改变父节点的left或者right, 指向要删除节点的子节点.
    - 当然, 在这个过程中还要考虑是否current就是根.

    4、情况三: 两个子节点

    • 如果我们要删除的节点有两个子节点, 甚至子节点还有子节点, 需要从下面的子节点中找到一个节点, 来替换当前的节点.

    • 这个节点==> 应该是current节点下面所有节点中最接近current节点的.

      • 要么比current节点小一点点, 要么比current节点大一点点.

      • 总结最接近current, 你就可以用来替换current的位置.

    • 这个节点怎么找呢?

      • 比current小一点点的节点, 一定是current左子树的最大值.

      • 比current大一点点的节点, 一定是current右子树的最小值.

    • 前驱&后继

      • 而在二叉搜索树中, 这两个特别的节点, 有两个特比的名字.

      • 比current小一点点的节点, 称为current节点的前驱.

      • 比current大一点点的节点, 称为current节点的后继.

    • 也就是为了能够删除有两个子节点的current, 要么找到它的前驱, 要么找到它的后继.

    5、删除节点完整代码

    1.  class Node {
    2.             constructor(data) {
    3.                 this.left = null;
    4.                 this.data = data;
    5.                 this.right = null;
    6.             }
    7.         }
    8.         class BST {
    9.             constructor() {
    10.                 this.root = null;
    11.             }
    12.             // 1.插入
    13.             insert(ele) {
    14.                 // 创建新节点
    15.                 let newnode = new Node(ele);
    16.                 // console.log(newnode);
    17.                 if (this.root == null) { // 空树
    18.                     this.root = newnode
    19.                 } else {
    20.                     this.insertNode(this.root, newnode)
    21.                 }
    22.             }
    23.             insertNode(root, newnode) {
    24.                 if (newnode.data < root.data) { // 放左边
    25.                     if (root.left == null) {
    26.                         root.left = newnode
    27.                     } else {
    28.                         this.insertNode(root.left, newnode)
    29.                     }
    30.                 } else { //放右边
    31.                     if (root.right == null) {
    32.                         root.right = newnode
    33.                     } else {
    34.                         this.insertNode(root.right, newnode)
    35.                     }
    36.                 }
    37.             }
    38.             // 2.前序遍历
    39.             preOrderTraversal() {
    40.                 this.preOrderTraversalNode(this.root)
    41.             }
    42.             preOrderTraversalNode(root) {
    43.                 if (root != null) { // {left:node,data:11,right:node} != null
    44.                     // 1.根
    45.                     console.log(root.data); //11 7  15
    46.                     // 2.前序遍历左子树
    47.                     this.preOrderTraversalNode(root.left)
    48.                     // 3.前序遍历右子树
    49.                     this.preOrderTraversalNode(root.right)
    50.                 }
    51.             }
    52.             // 3.中序遍历
    53.             inOrderTraversal() {
    54.                 this.inOrderTraversalNode(this.root)
    55.             }
    56.             inOrderTraversalNode(root) {
    57.                 if (root != null) {
    58.                     // 1.中序遍历左子树
    59.                     this.inOrderTraversalNode(root.left)
    60.                     // 2.根
    61.                     console.log(root.data);
    62.                     // 3.中序遍历右子树
    63.                     this.inOrderTraversalNode(root.right)
    64.                 }
    65.             }
    66.             // 4.后序遍历
    67.             postOrderTraversal() {
    68.                 this.postOrderTraversalNode(this.root)
    69.             }
    70.             postOrderTraversalNode(root) {
    71.                 if (root != null) {
    72.                     // 1.后序遍历左子树
    73.                     this.postOrderTraversalNode(root.left)
    74.  
    75.                     // 2.后序遍历右子树
    76.                     this.postOrderTraversalNode(root.right)
    77.                     // 3.根
    78.                     console.log(root.data);
    79.                 }
    80.             }
    81.             // 5.最值
    82.             getMin() {
    83.                 if (this.root == null) {
    84.                     return
    85.                 } else {
    86.                     let current = this.root;
    87.  
    88.                     while (current.left != null) {
    89.                         current = current.left
    90.                     }
    91.                     return current.data
    92.                 }
    93.             }
    94.             getMax() {
    95.                 if (this.root == null) {
    96.                     return
    97.                 } else {
    98.                     let current = this.root;
    99.  
    100.                     while (current.right != null) {
    101.                         current = current.right
    102.                     }
    103.                     return current.data
    104.                 }
    105.             }
    106.             remove(ele) {
    107.                 if (this.root == null) return
    108.                 let current = this.root,
    109.                     parent, isLeftChild;
    110.                 // 找到删除节点和父节点,判断是左子节点吗?
    111.                 while (ele != current.data) {
    112.                     if (ele < current.data) {
    113.                         //左边找
    114.                         parent = current;
    115.                         current = current.left;
    116.                         isLeftChild = true;
    117.                     } else {
    118.                         parent = current;
    119.                         current = current.right;
    120.                         isLeftChild = false;
    121.                     }
    122.                 }
    123.                 let delNode = current;
    124.                 // console.log(`当前删除的元素是${current.data},删除元素的父节点是${parent.data},是左孩子吗?${isLeftChild}`);
    125.                 // 1.删除叶结点   左右子树都为空
    126.                 if (delNode.left == null && delNode.right == null) {
    127.                     if (delNode == this.root) {
    128.                         this.root = null;
    129.                     } else {
    130.                         if (isLeftChild) {
    131.                             //左孩子
    132.                             parent.left = null;
    133.                         } else {
    134.                             parent.right = null;
    135.                         }
    136.                     }
    137.                 } else if (delNode.left != null && delNode.right == null) { //2.只有一个左子节点的节点
    138.                     if (delNode == this.root) {
    139.                         this.root = delNode.left
    140.                     } else {
    141.                         if (isLeftChild) {
    142.                             parent.left = delNode.left
    143.                         } else {
    144.                             parent.right = delNode.left
    145.                         }
    146.                     }
    147.                 } else if (delNode.left == null && delNode.right != null) { //只有一个右子节点的节点
    148.                     if (delNode == this.root) {
    149.                         this.root = delNode.right
    150.                     } else {
    151.                         if (isLeftChild) {
    152.                             parent.left = delNode.right
    153.                         } else {
    154.                             parent.right = delNode.right
    155.                         }
    156.                     }
    157.                 } else { //删除有两个子节点    
    158.                     let houji = this.gethouji(delNode);//后继为右子树中的最小值
    159.                     if (delNode == this.root) {
    160.                         this.root = houji;
    161.                     } else {
    162.                         if (isLeftChild) {
    163.                             parent.left = houji;
    164.                         } else {
    165.                             parent.right = houji;
    166.                         }
    167.                     }
    168.                     houji.left = delNode.left;
    169.                 }
    170.             }
    171.             gethouji(delNode) {
    172.                 let current = delNode.right; //后继
    173.                 let houjiparent = delNode;
    174.                 while (current.left != null) {
    175.                     houjiparent = current;
    176.                     current = current.left;
    177.                 }
    178.                 if (current != delNode.right) { //当后继为删除节点的右节点
    179.                     houjiparent.left = current.right;
    180.                     current.right = delNode.right
    181.                 }
    182.                 return current
    183.             }
    184.             seacrh(ele) {
    185.                 if (this.root == null) return
    186.                 let current = this.root;
    187.                 while (current) {
    188.                     if (ele < current.data) {
    189.                         //左边找
    190.                         current = current.left
    191.                     } else if (ele > current.data) {
    192.                         current = current.right;
    193.                     } else {
    194.                         return true
    195.                     }
    196.                 }
    197.                 return false
    198.             }
    199.         }
    200.         let bst = new BST();
    201.         bst.insert(11)
    202.         bst.insert(7)
    203.         console.log(bst.seacrh(9));
    204.         console.log(bst.seacrh(100));
  • 相关阅读:
    MLX90640 红外热成像传感器测温模块开发笔记（二）
    Java-day15(Java常用类)
    这款国产ftp服务器 可实现安全、稳定的文件传输
    Niagara - UE5中的粒子系统
    HarmonyOS列表组件
    计算机网络
    【Linux】进程概念万字详解（上篇）
    网络编程01
    CMake教程-第 9 步：打包安装程序
    RabbitMq深度学习
  • 原文地址：https://blog.csdn.net/qq_52301431/article/details/126528944