二叉排序树

向右看齐 2024-04-18 21:24 10阅读 0赞

### 一、基本介绍 ###

BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值　　小，右子节点的值比当前节点的值大。  
　　说明：如果有相同的值，可以将该节点放在左子节点或右子节点

![1007094-20190911204637178-1553149531.png][]

### 二、二叉排序树的删除 ###

1）删除叶子节点 (比如：2, 5, 9, 12)  
　　2）删除只有一颗子树的节点 (比如：1)  
　　3）删除有两颗子树的节点. (比如：7, 3，10 )

### 三、二叉排序树删除的代码　 ###

1     //删除结点
     2     public void delNode(int value) {
     3         if(root == null) {
     4             return;
     5         }else {
     6             //1.需求先去找到要删除的结点  targetNode
     7             Node targetNode = search(value);
     8             //如果没有找到要删除的结点
     9             if(targetNode == null) {
    10                 return;
    11             }
    12             //如果我们发现当前这颗二叉排序树只有一个结点
    13             if(root.left == null && root.right == null) {
    14                 root = null;
    15                 return;
    16             }
    17             
    18             //去找到targetNode的父结点
    19             Node parent = searchParent(value);
    20             //如果要删除的结点是叶子结点
    21             if(targetNode.left == null && targetNode.right == null) {
    22                 //判断targetNode 是父结点的左子结点，还是右子结点
    23                 if(parent.left != null && parent.left.value == value) { //是左子结点
    24                     parent.left = null;
    25                 } else if (parent.right != null && parent.right.value == value) {
        //是由子结点
    26                     parent.right = null;
    27                 }
    28             } else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点
    29                 int minVal = delRightTreeMin(targetNode.right);
    30                 targetNode.value = minVal;
    31                 
    32                 
    33             } else { // 删除只有一颗子树的结点
    34                 //如果要删除的结点有左子结点 
    35                 if(targetNode.left != null) {
    36                     if(parent != null) {
    37                         //如果 targetNode 是 parent 的左子结点
    38                         if(parent.left.value == value) {
    39                             parent.left = targetNode.left;
    40                         } else { //  targetNode 是 parent 的右子结点
    41                             parent.right = targetNode.left;
    42                         } 
    43                     } else {
    44                         root = targetNode.left;
    45                     }
    46                 } else { //如果要删除的结点有右子结点 
    47                     if(parent != null) {
    48                         //如果 targetNode 是 parent 的左子结点
    49                         if(parent.left.value == value) {
    50                             parent.left = targetNode.right;
    51                         } else { //如果 targetNode 是 parent 的右子结点
    52                             parent.right = targetNode.right;
    53                         }
    54                     } else {
    55                         root = targetNode.right;
    56                     }
    57                 }
    58                 
    59             }
    60             
    61         }
    62     }

**　查找要删除结点的父结点****　　**

1 //查找要删除结点的父结点
     2 /**
     3  * 
     4  * @param value 要找到的结点的值
     5  * @return 返回的是要删除的结点的父结点，如果没有就返回null
     6  */
     7 public Node searchParent(int value) {
     8     //如果当前结点就是要删除的结点的父结点，就返回
     9     if((this.left != null && this.left.value == value) || 
    10             (this.right != null && this.right.value == value)) {
    11         return this;
    12     } else {
    13         //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
    14         if(value < this.value && this.left != null) {
    15             return this.left.searchParent(value); //向左子树递归查找
    16         } else if (value >= this.value && this.right != null) {
    17             return this.right.searchParent(value); //向右子树递归查找
    18         } else {
    19             return null; // 没有找到父结点
    20         }
    21     }
    22     
    23 }

查找要删除的节点

1     //查找要删除的结点
     2     /**
     3      * 
     4      * @param value 希望删除的结点的值
     5      * @return 如果找到返回该结点，否则返回null
     6      */
     7     public Node search(int value) {
     8         if(value == this.value) { //找到就是该结点
     9             return this;
    10         } else if(value < this.value) {
        //如果查找的值小于当前结点，向左子树递归查找
    11             //如果左子结点为空
    12             if(this.left  == null) {
    13                 return null;
    14             }
    15             return this.left.search(value);
    16         } else { //如果查找的值不小于当前结点，向右子树递归查找
    17             if(this.right == null) {
    18                 return null;
    19             }
    20             return this.right.search(value);
    21         }
    22         
    23     }

### 四、整体代码　 ###

1 public class BinarySortTreeDemo {
      2 
      3     public static void main(String[] args) {
      4         int[] arr = {
        7, 3, 10, 12, 5, 1, 9, 2};
      5         BinarySortTree binarySortTree = new BinarySortTree();
      6         //循环的添加结点到二叉排序树
      7         for(int i = 0; i< arr.length; i++) {
      8             binarySortTree.add(new Node(arr[i]));
      9         }
     10         
     11         //中序遍历二叉排序树
     12         System.out.println("中序遍历二叉排序树~");
     13         binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
     14         
     15         //测试一下删除叶子结点
     16         
     17        
     18         binarySortTree.delNode(12);
     19        
     20      
     21         binarySortTree.delNode(5);
     22         binarySortTree.delNode(10);
     23         binarySortTree.delNode(2);
     24         binarySortTree.delNode(3);
     25            
     26         binarySortTree.delNode(9);
     27         binarySortTree.delNode(1);
     28         binarySortTree.delNode(7);
     29         
     30         
     31         System.out.println("root=" + binarySortTree.getRoot());
     32         
     33         
     34         System.out.println("删除结点后");
     35         binarySortTree.infixOrder();
     36     }
     37 
     38 }
     39 
     40 //创建二叉排序树
     41 class BinarySortTree {
     42     private Node root;
     43     
     44     
     45     
     46     
     47     public Node getRoot() {
     48         return root;
     49     }
     50 
     51     //查找要删除的结点
     52     public Node search(int value) {
     53         if(root == null) {
     54             return null;
     55         } else {
     56             return root.search(value);
     57         }
     58     }
     59     
     60     //查找父结点
     61     public Node searchParent(int value) {
     62         if(root == null) {
     63             return null;
     64         } else {
     65             return root.searchParent(value);
     66         }
     67     }
     68     
     69     //编写方法: 
     70     //1. 返回的 以node 为根结点的二叉排序树的最小结点的值
     71     //2. 删除node 为根结点的二叉排序树的最小结点
     72     /**
     73      * 
     74      * @param node 传入的结点(当做二叉排序树的根结点)
     75      * @return 返回的 以node 为根结点的二叉排序树的最小结点的值
     76      */
     77     public int delRightTreeMin(Node node) {
     78         Node target = node;
     79         //循环的查找左子节点，就会找到最小值
     80         while(target.left != null) {
     81             target = target.left;
     82         }
     83         //这时 target就指向了最小结点
     84         //删除最小结点
     85         delNode(target.value);
     86         return target.value;
     87     }
     88     
     89     
     90     //删除结点
     91     public void delNode(int value) {
     92         if(root == null) {
     93             return;
     94         }else {
     95             //1.需求先去找到要删除的结点  targetNode
     96             Node targetNode = search(value);
     97             //如果没有找到要删除的结点
     98             if(targetNode == null) {
     99                 return;
    100             }
    101             //如果我们发现当前这颗二叉排序树只有一个结点
    102             if(root.left == null && root.right == null) {
    103                 root = null;
    104                 return;
    105             }
    106             
    107             //去找到targetNode的父结点
    108             Node parent = searchParent(value);
    109             //如果要删除的结点是叶子结点
    110             if(targetNode.left == null && targetNode.right == null) {
    111                 //判断targetNode 是父结点的左子结点，还是右子结点
    112                 if(parent.left != null && parent.left.value == value) { //是左子结点
    113                     parent.left = null;
    114                 } else if (parent.right != null && parent.right.value == value) {
        //是由子结点
    115                     parent.right = null;
    116                 }
    117             } else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点
    118                 int minVal = delRightTreeMin(targetNode.right);
    119                 targetNode.value = minVal;
    120                 
    121                 
    122             } else { // 删除只有一颗子树的结点
    123                 //如果要删除的结点有左子结点 
    124                 if(targetNode.left != null) {
    125                     if(parent != null) {
    126                         //如果 targetNode 是 parent 的左子结点
    127                         if(parent.left.value == value) {
    128                             parent.left = targetNode.left;
    129                         } else { //  targetNode 是 parent 的右子结点
    130                             parent.right = targetNode.left;
    131                         } 
    132                     } else {
    133                         root = targetNode.left;
    134                     }
    135                 } else { //如果要删除的结点有右子结点 
    136                     if(parent != null) {
    137                         //如果 targetNode 是 parent 的左子结点
    138                         if(parent.left.value == value) {
    139                             parent.left = targetNode.right;
    140                         } else { //如果 targetNode 是 parent 的右子结点
    141                             parent.right = targetNode.right;
    142                         }
    143                     } else {
    144                         root = targetNode.right;
    145                     }
    146                 }
    147                 
    148             }
    149             
    150         }
    151     }
    152     
    153     //添加结点的方法
    154     public void add(Node node) {
    155         if(root == null) {
    156             root = node;//如果root为空则直接让root指向node
    157         } else {
    158             root.add(node);
    159         }
    160     }
    161     //中序遍历
    162     public void infixOrder() {
    163         if(root != null) {
    164             root.infixOrder();
    165         } else {
    166             System.out.println("二叉排序树为空，不能遍历");
    167         }
    168     }
    169 }
    170 
    171 //创建Node结点
    172 class Node {
    173     int value;
    174     Node left;
    175     Node right;
    176     public Node(int value) {
    177         
    178         this.value = value;
    179     }
    180     
    181     
    182     //查找要删除的结点
    183     /**
    184      * 
    185      * @param value 希望删除的结点的值
    186      * @return 如果找到返回该结点，否则返回null
    187      */
    188     public Node search(int value) {
    189         if(value == this.value) { //找到就是该结点
    190             return this;
    191         } else if(value < this.value) {
        //如果查找的值小于当前结点，向左子树递归查找
    192             //如果左子结点为空
    193             if(this.left  == null) {
    194                 return null;
    195             }
    196             return this.left.search(value);
    197         } else { //如果查找的值不小于当前结点，向右子树递归查找
    198             if(this.right == null) {
    199                 return null;
    200             }
    201             return this.right.search(value);
    202         }
    203         
    204     }
    205     //查找要删除结点的父结点
    206     /**
    207      * 
    208      * @param value 要找到的结点的值
    209      * @return 返回的是要删除的结点的父结点，如果没有就返回null
    210      */
    211     public Node searchParent(int value) {
    212         //如果当前结点就是要删除的结点的父结点，就返回
    213         if((this.left != null && this.left.value == value) || 
    214                 (this.right != null && this.right.value == value)) {
    215             return this;
    216         } else {
    217             //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
    218             if(value < this.value && this.left != null) {
    219                 return this.left.searchParent(value); //向左子树递归查找
    220             } else if (value >= this.value && this.right != null) {
    221                 return this.right.searchParent(value); //向右子树递归查找
    222             } else {
    223                 return null; // 没有找到父结点
    224             }
    225         }
    226         
    227     }
    228     
    229     @Override
    230     public String toString() {
    231         return "Node [value=" + value + "]";
    232     }
    233 
    234 
    235     //添加结点的方法
    236     //递归的形式添加结点，注意需要满足二叉排序树的要求
    237     public void add(Node node) {
    238         if(node == null) {
    239             return;
    240         }
    241         
    242         //判断传入的结点的值，和当前子树的根结点的值关系
    243         if(node.value < this.value) {
    244             //如果当前结点左子结点为null
    245             if(this.left == null) {
    246                 this.left = node;
    247             } else {
    248                 //递归的向左子树添加
    249                 this.left.add(node);
    250             }
    251         } else { //添加的结点的值大于 当前结点的值
    252             if(this.right == null) {
    253                 this.right = node;
    254             } else {
    255                 //递归的向右子树添加
    256                 this.right.add(node);
    257             }
    258             
    259         }
    260     }
    261     
    262     //中序遍历
    263     public void infixOrder() {
    264         if(this.left != null) {
    265             this.left.infixOrder();
    266         }
    267         System.out.println(this);
    268         if(this.right != null) {
    269             this.right.infixOrder();
    270         }
    271     }
    272     
    273 }

[1007094-20190911204637178-1553149531.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b7f14c6121574fbf988251e8c1a18dd5.png