使用java实现二叉查找树的插入，修改和删除方法-白红宇

使用java实现二叉查找树的插入，修改和删除方法

阅读量：6604 次

发布时间：2019-06-24

本文共 8114 字，大约阅读时间需要 27 分钟。

目前使用的是根据key的hashcode来进行排序，并且没有考虑hash碰撞的问题

1 package com.zhou.tree;  2   3 import java.util.Comparator;  4 import java.util.HashMap;  5 import java.util.Map;  6   7 /**  8  * @Description:  9  * @author: zhoum 10  * @Date: 2019-05-16 11  * @Time: 9:44 12  */ 13 public class BinarySearchTree
     
       { 14  15     private Node root; 16  17     private class Node{ 18  19         private K key; 20  21         private V value; 22  23         private Node left,right,parent; 24  25         public Node(K k,V v,Node parent) { 26             this.key = k; 27             this.value = v; 28             this.parent = parent; 29         } 30     } 31  32     public BinarySearchTree() {} 33  34     public void put(K k,V v){ 35         if( k == null){ return; } 36         if(root == null){ 37             root = new Node(k,v,null); 38             return; 39         } 40         insert(root,k,v); 41  42     } 43  44     private void insert(Node node,K k,V v){ 45         if(k.hashCode() == node.key.hashCode() && k.equals(node.key)){ 46             node.value = v; 47         }else if(k.hashCode() > node.key.hashCode()){ 48             if(node.right == null){ 49                 Node n = new Node(k,v,node); 50                 node.right = n; 51             }else { 52                 insert(node.right,k,v); 53             } 54         }else { 55             if(node.left == null){ 56                 Node n = new Node(k,v,node); 57                 node.left = n; 58             }else { 59                 insert(node.left,k,v); 60             } 61         } 62     } 63  64  65     public V get(K k){ 66         if(root == null || k == null){ 67             return null; 68         } 69         return get(root,k).value; 70     } 71  72     private Node get(Node node,K k){ 73         if(node == null){ 74             return null; 75         }else if(node.key.hashCode() == k.hashCode() && node.key.equals(k)){ 76             return node; 77         }else if(k.hashCode() > node.key.hashCode()){ 78             if(node.right == null){ 79                 return null; 80             } 81             return get(node.right,k); 82         }else { 83             if(node.left == null){ 84                 return null; 85             } 86             return get(node.left,k); 87         } 88  89     } 90     public boolean delete(K k){ 91         Node node = get(root , k); 92         if(node == null){ 93             return false; 94         } 95         //被删除节点右孩子为空 96         if(node.right == null){ 97             //根节点 98             if(node.parent == null){ 99                if(node.left == null){100                    root = null;101                    return true;102                }103                 root = node.left;104                 root.parent = null;105                 return true;106             }107             if(node.parent.left != null && node.key.equals(node.parent.left.key)){108                 if(node.left == null){109                     node.parent.left = null;110                 }else {111                     node.parent.left = node.left;112                     node.left.parent = node.parent;113                 }114 115             }else if(node.parent.right != null && node.key.equals(node.parent.right.key)){116                 if(node.left == null){117                     node.parent.right = null;118                 }else {119                     node.parent.right = node.left;120                     node.left.parent = node.parent;121                 }122 123             }124             return true;125 126         }127         //被删除节点左孩子为空128         if(node.left == null){129             //如果为根节点130             if(node.parent == null){131                 if(node.right == null){132                     root = null;133                     return true;134                 }135                 root = node.right;136                 root.parent = null;137                 return true;138             }139             if(node.parent.left.key.equals(node.key) ){140                 if(node.right == null){141                     node.parent.left = null;142                 }else {143                     node.parent.left = node.right;144                     node.right.parent = node.parent;145                 }146             }else if(node.parent.right.key.equals(node.key)){147                 if(node.right == null){148                     node.parent.right = null;149                 }else {150                     node.parent.right = node.right;151                     node.right.parent = node.parent;152                 }153 154             }155             return true;156         }157 158         //被删除节点有两孩子159         Node deleteNode = get(root , k);160         Node minNode = get(root , getMin(deleteNode.right));161         deleteNode.right.parent = deleteNode.left.parent = minNode;162         if(deleteNode.parent == null){163             if(minNode.key.equals(deleteNode.right.key)){164                     minNode.left = deleteNode.left;165                     root = minNode;166                     deleteNode.left.parent = minNode;167                     minNode.parent = null;168             }else {169                 if(minNode.right != null){170                     minNode.right.parent = minNode.parent;171                     minNode.parent.left = minNode.right;172                 }173                 minNode.right = deleteNode.right;174                 minNode.left = deleteNode.left;175                 deleteNode.right.parent = deleteNode.left.parent =  minNode;176                 minNode.parent = null;177                 root = minNode;178             }179 180         }else {181             if(minNode.key.equals(deleteNode.right.key)){182                 minNode.left = deleteNode.left;183                 minNode.parent = deleteNode.parent;184                 deleteNode.left.parent = minNode;185                 if(deleteNode.parent.right.key.equals(deleteNode.key)){186                     deleteNode.parent.right = minNode;187                 } else {188                     deleteNode.parent.left = minNode;189                 }190             }else {191                 minNode.right.parent = minNode.parent;192                 minNode.parent.left = minNode.right;193                 minNode.left = deleteNode.left;194                 minNode.right = deleteNode.right;195                 deleteNode.left.parent = deleteNode.right.parent = minNode;196                 minNode.parent = deleteNode.parent;197                 if(deleteNode.parent.left.key.equals(deleteNode.key)){198 199                     deleteNode.parent.left = minNode;200                 }else {201                     deleteNode.parent.right = minNode;202                 }203             }204         }205         return true;206     }207 208     private K getMin(Node node){209         if(node == null){210             return null;211         }212         if(node.left == null){213             return node.key;214         }215         return getMin(node.left);216     }217 218     @Override219     public String toString() {220         Map
      
        map = new HashMap<>();221         setString(map,root);222        return map.toString();223     }224 225     private void setString(Map
       
         map,Node node){226         if(node != null){227             map.put(node.key,node.value);228         }229         if(node.left != null){230             setString(map,node.left);231         }232         if(node.right != null){233             setString(map,node.right);234         }235     }236 237 238 }

测试方法

1 public class Test { 2  3     public static void main(String[] args) { 4  5         BinarySearchTree
     
       b  = new BinarySearchTree<>(); 6         b.put("aaa","123"); 7         b.put("abc","85"); 8         b.put("trf","69"); 9         b.put("u","48");10         b.put("jf","1");11         b.put("dg","36");12         b.put("aaa","999");13         System.out.println(b.delete("aaa"));14 15         System.out.println(b);16 17     }18 }

在执行delete前数据的模型为