• java实现二叉搜索树

    1.前言

    二叉搜索树是一种特殊的二叉树，它的每一个节点都满足以下条件：

    1. 左子树中所有节点的值均小于该节点的值。
    2. 右子树中所有节点的值均大于该节点的值。
    3. 每个子树也都是二叉搜索树。

    通过这种特殊的结构，二叉搜索树能够实现快速的插入、查找和删除操作。在二叉搜索树中，插入一个新节点的时间复杂度为 O(log n)，查找或删除一个节点的时间复杂度同样为 O(log n)，其中 n 是树中节点的数量。

    因为其高效的查找和排序性质，二叉搜索树被广泛应用于各种领域，例如数据库索引、哈希表等数据结构的实现、模拟字典等应用中。

    2.原理分析

    2.1添加节点

    1. 首先，需要确定要插入的节点在树中的位置。从根节点开始，与要插入的节点进行比较。

    2. 如果要插入的节点的值小于当前节点的值，那么就将其作为当前节点的左子节点。如果当前节点的左子节点为空，直接插入；如果不为空，将当前节点指向其左子节点，并继续执行第一步。

    3. 如果要插入的节点的值大于当前节点的值，那么就将其作为当前节点的右子节点。如果当前节点的右子节点为空，直接插入；如果不为空，将当前节点指向其右子节点，并继续执行第一步。

    4. 重复执行步骤 2 和步骤 3，直到找到合适的空位置插入节点。

    2.2删除节点 

    1. 首先，我们需要找到要删除的节点。从根节点开始，比较要删除的值与当前节点的值，根据大小关系选择向左子树或右子树移动，直到找到与要删除的值相等的节点。

    2. 找到要删除的节点后，有以下几种情况：

      • 如果要删除的节点是叶节点（即没有左子树和右子树），直接将其从树中删除即可。

      • 如果要删除的节点只有左子树或只有右子树，我们需要用它的子节点来替代要删除的节点。

      • 如果要删除的节点既有左子树又有右子树，我们可以选择以下两种方式来替代要删除的节点：

        a. 在右子树中找到最小的节点，即右子树中的最左叶节点。将该节点的值复制到要删除的节点，并将该节点删除。这样可以保持二叉搜索树的性质。

        b. 在左子树中找到最大的节点，即左子树中的最右叶节点。将该节点的值复制到要删除的节点，并将该节点删除。同样，这样可以保持二叉搜索树的性质。

    3. 完成替代操作后，整个树的结构依然保持二叉搜索树的性质。

    2.3查找节点 

    1. 从根节点开始，将要查找的值与当前节点的值进行比较。

    2. 如果要查找的值等于当前节点的值，那么说明找到了目标节点，返回当前节点。

    3. 如果要查找的值小于当前节点的值，那么说明目标节点位于当前节点的左子树中。则将当前节点指向其左子节点，并继续执行第一步。

    4. 如果要查找的值大于当前节点的值，那么说明目标节点位于当前节点的右子树中。则将当前节点指向其右子节点，并继续执行第一步。

    5. 重复执行步骤 2、3 和 4，直到找到目标节点或者遍历完整个树（表示目标节点不存在）。

    3.代码实现 

    3.1准备工作

     1.创建节点类
    1. //创建节点类
    2.     private static class TreeNode{
    3.  
    4.         T value;
    5.         TreeNode left;
    6.         TreeNode right;
    7.  
    8.         //叶节点专属构造方法
    9.         public TreeNode(T value) {
    10.             this.value = value;
    11.             left = null;
    12.             right = null;
    13.         }
    14.  
    15.         //默认构造方法
    16.         public TreeNode(T value, TreeNode left, TreeNode right) {
    17.             this.value = value;
    18.             this.left = left;
    19.             this.right = right;
    20.         }
    21.     }
    2.基础属性
    1. public class TreeNodeTestextends Comparable>{
    2.  
    3.     private TreeNode root;//创建一个根节点
    4.  
    5.  
    6.  
    7.  
    8.     public TreeNodeTest() {
    9.         root = null;
    10.     }
    11.  
    12.     //指定一个根节点创建树
    13.     public TreeNodeTest(TreeNode root) {
    14.         this.root = root;
    15.     }

    3.2插入节点 

    1.   //插入节点
    2.     public void insert(T value){
    3.         root = insertRecursive(root, value);
    4.     }
    5.  
    6.  
    7.     //递归实现插入节点
    8.     private TreeNode insertRecursive(TreeNode root, T value) {
    9.         if (root == null){
    10.             return new TreeNode<>(value);
    11.         }
    12.         if (value.compareTo(root.value) < 0){
    13.             //小于此节点往此节点后面子节点继续找
    14.             root.left = insertRecursive(root.left,value);
    15.         }else if (value.compareTo(root.value) > 0){
    16.             root.right = insertRecursive(root.right,value);
    17.         }
    18.         return root;
    19.     }

    3.3查找节点

    1.  // 查找最小值节点
    2.     private TreeNode findMin(TreeNode node) {
    3.         if (node.left == null) {
    4.             return node;
    5.         }
    6.         return findMin(node.left);
    7.     }
    8.  
    9.     //查找节点
    10.     public boolean contains(T value) {
    11.         return containsRecursive(root, value);
    12.     }
    13.  
    14.  
    15.     //递归实现查找节点
    16.     private boolean containsRecursive(TreeNode root, T value) {
    17.         //递归的出口
    18.         if (root == null){
    19.             //意味着找到最后也没找到
    20.             return false;
    21.         }
    22.  
    23.         if (value.compareTo(root.value) == 0){
    24.             return true;
    25.         }
    26.  
    27.         if (value.compareTo(root.value) < 0){
    28.             return containsRecursive(root.left,value);
    29.         }else{
    30.             return containsRecursive(root.right,value);
    31.         }
    32.     }

    3.4删除节点

    1. // 删除节点
    2.     public void delete(T value) {
    3.         root = deleteRecursive(root, value);
    4.     }
    5.  
    6.  
    7.     // 递归实现删除节点
    8.     private TreeNode deleteRecursive(TreeNode root, T value) {
    9.         if (root == null) {
    10.             return null;
    11.         }
    12.  
    13.         if (value.compareTo(root.value) < 0) {
    14.             root.left = deleteRecursive(root.left, value);
    15.         } else if (value.compareTo(root.value) > 0) {
    16.             root.right = deleteRecursive(root.right, value);
    17.         } else {
    18.             // 找到要删除的节点
    19.             if (root.left == null && root.right == null) {
    20.                 // 叶节点，直接删除
    21.                 return null;
    22.             } else if (root.left == null) {
    23.                 // 只有右子树，用右子节点替代要删除的节点
    24.                 return root.right;
    25.             } else if (root.right == null) {
    26.                 // 只有左子树，用左子节点替代要删除的节点
    27.                 return root.left;
    28.             } else {
    29.                 // 左右子树都存在，找到右子树中最小的节点，替代要删除的节点
    30.                 TreeNode minNode = findMin(root.right);
    31.                 root.value = minNode.value;
    32.                 root.right = deleteRecursive(root.right, minNode.value);
    33.             }
    34.         }
    35.  
    36.         return root;
    37.     }

    3.5前中后序遍历

    1.  // 前序遍历
    2.     public void preOrderTraversal() {
    3.         preOrderTraversalRecursive(root);
    4.     }
    5.  
    6.     private void preOrderTraversalRecursive(TreeNode node) {
    7.         if (node != null) {
    8.             System.out.print(node.value + " ");
    9.             preOrderTraversalRecursive(node.left);
    10.             preOrderTraversalRecursive(node.right);
    11.         }
    12.     }
    13.  
    14.     // 中序遍历
    15.     public void inOrderTraversal() {
    16.         inOrderTraversalRecursive(root);
    17.     }
    18.  
    19.     private void inOrderTraversalRecursive(TreeNode node) {
    20.         if (node != null) {
    21.             inOrderTraversalRecursive(node.left);
    22.             System.out.print(node.value + " ");
    23.             inOrderTraversalRecursive(node.right);
    24.         }
    25.     }
    26.  
    27.     // 后序遍历
    28.     public void postOrderTraversal() {
    29.         postOrderTraversalRecursive(root);
    30.     }
    31.  
    32.     private void postOrderTraversalRecursive(TreeNode node) {
    33.         if (node != null) {
    34.             postOrderTraversalRecursive(node.left);
    35.             postOrderTraversalRecursive(node.right);
    36.             System.out.print(node.value + " ");
    37.         }
    38.     }

    4.全部代码

    1.  
    2. /*
    3. * 实现二叉树搜索树
    4. *
    5. * */
    6.  
    7.  
    8. //因为是二叉搜索树所以要引入Comparable接口要不然引用类型无法比较
    9. public class TreeNodeTestextends Comparable>{
    10.  
    11.     private TreeNode root;//创建一个根节点
    12.  
    13.  
    14.     //创建节点类
    15.     private static class TreeNode{
    16.  
    17.         T value;
    18.         TreeNode left;
    19.         TreeNode right;
    20.  
    21.         //叶节点专属构造方法
    22.         public TreeNode(T value) {
    23.             this.value = value;
    24.             left = null;
    25.             right = null;
    26.         }
    27.  
    28.         //默认构造方法
    29.         public TreeNode(T value, TreeNode left, TreeNode right) {
    30.             this.value = value;
    31.             this.left = left;
    32.             this.right = right;
    33.         }
    34.     }
    35.  
    36.     public TreeNodeTest() {
    37.         root = null;
    38.     }
    39.  
    40.     //指定一个根节点创建树
    41.     public TreeNodeTest(TreeNode root) {
    42.         this.root = root;
    43.     }
    44.  
    45.     //插入节点
    46.     public void insert(T value){
    47.         root = insertRecursive(root, value);
    48.     }
    49.  
    50.  
    51.     //递归实现插入节点
    52.     private TreeNode insertRecursive(TreeNode root, T value) {
    53.         if (root == null){
    54.             return new TreeNode<>(value);
    55.         }
    56.         if (value.compareTo(root.value) < 0){
    57.             //小于此节点往此节点后面子节点继续找
    58.             root.left = insertRecursive(root.left,value);
    59.         }else if (value.compareTo(root.value) > 0){
    60.             root.right = insertRecursive(root.right,value);
    61.         }
    62.         return root;
    63.     }
    64.     // 删除节点
    65.     public void delete(T value) {
    66.         root = deleteRecursive(root, value);
    67.     }
    68.  
    69.  
    70.     // 递归实现删除节点
    71.     private TreeNode deleteRecursive(TreeNode root, T value) {
    72.         if (root == null) {
    73.             return null;
    74.         }
    75.  
    76.         if (value.compareTo(root.value) < 0) {
    77.             root.left = deleteRecursive(root.left, value);
    78.         } else if (value.compareTo(root.value) > 0) {
    79.             root.right = deleteRecursive(root.right, value);
    80.         } else {
    81.             // 找到要删除的节点
    82.             if (root.left == null && root.right == null) {
    83.                 // 叶节点，直接删除
    84.                 return null;
    85.             } else if (root.left == null) {
    86.                 // 只有右子树，用右子节点替代要删除的节点
    87.                 return root.right;
    88.             } else if (root.right == null) {
    89.                 // 只有左子树，用左子节点替代要删除的节点
    90.                 return root.left;
    91.             } else {
    92.                 // 左右子树都存在，找到右子树中最小的节点，替代要删除的节点
    93.                 TreeNode minNode = findMin(root.right);
    94.                 root.value = minNode.value;
    95.                 root.right = deleteRecursive(root.right, minNode.value);
    96.             }
    97.         }
    98.  
    99.         return root;
    100.     }
    101.     // 查找最小值节点
    102.     private TreeNode findMin(TreeNode node) {
    103.         if (node.left == null) {
    104.             return node;
    105.         }
    106.         return findMin(node.left);
    107.     }
    108.  
    109.     //查找节点
    110.     public boolean contains(T value) {
    111.         return containsRecursive(root, value);
    112.     }
    113.  
    114.  
    115.     //递归实现查找节点
    116.     private boolean containsRecursive(TreeNode root, T value) {
    117.         //递归的出口
    118.         if (root == null){
    119.             //意味着找到最后也没找到
    120.             return false;
    121.         }
    122.  
    123.         if (value.compareTo(root.value) == 0){
    124.             return true;
    125.         }
    126.  
    127.         if (value.compareTo(root.value) < 0){
    128.             return containsRecursive(root.left,value);
    129.         }else{
    130.             return containsRecursive(root.right,value);
    131.         }
    132.     }
    133.  
    134.     // 前序遍历
    135.     public void preOrderTraversal() {
    136.         preOrderTraversalRecursive(root);
    137.     }
    138.  
    139.     private void preOrderTraversalRecursive(TreeNode node) {
    140.         if (node != null) {
    141.             System.out.print(node.value + " ");
    142.             preOrderTraversalRecursive(node.left);
    143.             preOrderTraversalRecursive(node.right);
    144.         }
    145.     }
    146.  
    147.     // 中序遍历
    148.     public void inOrderTraversal() {
    149.         inOrderTraversalRecursive(root);
    150.     }
    151.  
    152.     private void inOrderTraversalRecursive(TreeNode node) {
    153.         if (node != null) {
    154.             inOrderTraversalRecursive(node.left);
    155.             System.out.print(node.value + " ");
    156.             inOrderTraversalRecursive(node.right);
    157.         }
    158.     }
    159.  
    160.     // 后序遍历
    161.     public void postOrderTraversal() {
    162.         postOrderTraversalRecursive(root);
    163.     }
    164.  
    165.     private void postOrderTraversalRecursive(TreeNode node) {
    166.         if (node != null) {
    167.             postOrderTraversalRecursive(node.left);
    168.             postOrderTraversalRecursive(node.right);
    169.             System.out.print(node.value + " ");
    170.         }
    171.     }
    172.     public static void main(String[] args) {
    173.         TreeNodeTest tree = new TreeNodeTest<>();
    174.         tree.insert(5);
    175.         tree.insert(3);
    176.         tree.insert(7);
    177.         tree.insert(1);
    178.         tree.insert(4);
    179.         tree.insert(6);
    180.         tree.insert(8);
    181.  
    182.         System.out.println("前序遍历结果：");
    183.         tree.preOrderTraversal();
    184.  
    185.         System.out.println("\n中序遍历结果：");
    186.         tree.inOrderTraversal();
    187.  
    188.         System.out.println("\n后序遍历结果：");
    189.         tree.postOrderTraversal();
    190.  
    191.         System.out.println("\n是否包含值为 4 的节点：" + tree.contains(4));
    192.     }
    193. }
    194.  
    195.  
    196.  
    197.

  • 相关阅读:
    操作系统考研笔记
    containerd客户端比较
    docker容器中访问本地宿主机的服务
    matlab simulink 四旋翼跟拍无人机仿真
    抖音矩阵系统源码独立部署定制开发。tell me
    在 CentOS 8.2 上安装 MySQL C/C++ 客户端库 libmysqlclient.so
    java计算机毕业设计信用卡逾期数据处理分析系统源程序+mysql+系统+lw文档+远程调试
    Feign源码解析：初始化过程（二）
    springboot+rocketmq（5）:实现批量消息
    新能源充电桩工业4G路由器应用，推动绿色出行，响应环保理念
  • 原文地址：https://blog.csdn.net/m0_74749208/article/details/133893726