/** * @desc: 自定义二叉查找树: 插入键值对,根据key查找元素值,删除节点,取最大(小)的元素值, * 前序(中序,后序,层次)遍历,树的高度 * @author: 毛会懂 * @create: 2021-01-05 14:11:00 **/ public class MyBinaryFindTree<K extends Comparable<K>,V> { //头结点 private Node root; //元素个数 private Integer size; public MyBinaryFindTree() { this.root = null; size = 0; } //插入元素 public void put(K key, V value){ root = put(root,key,value); } //根据key,获取元素 public V get(K key){ return get(root,key); } //删除元素 public void delete(K key){ delete(root,key); } //元素的个数 public Integer size(){ return size; } //获取最大值 public V getMax(){ return getMax(root); } //获取最小值 public V getMin(){ return getMin(root); } //前序遍历 public Queue<Node> getPreList(){ Queue<Node> queue = new LinkedList<>(); getPreList(root,queue); return queue; } //中序遍历 public Queue<Node> getMidList(){ Queue<Node> queue = new ArrayBlockingQueue<>(30); getMidList(root,queue); return queue; } //后序遍历 public Queue<Node> getAfterList(){ Queue<Node> queue = new ArrayDeque<>(); getAfterList(root,queue); return queue; } //层次遍历 public Queue<Node> getLayerList(){ Queue<Node> queue = new ArrayDeque<>(); Queue<Node> temp = new ArrayDeque<>(); temp.add(root); while (!temp.isEmpty()){ //取队头的元素 Node element = temp.poll(); queue.add(element); if(element.left != null){ temp.add(element.left); } if(element.right != null){ temp.add(element.right); } } return queue; } //树的最大深度 public Integer getTop(){ return getTop(root); } private Node put(Node node,K key,V value){ if(node == null){ node = new Node(key,value,null,null); size++; return node; } if(key.compareTo(node.key) < 0){ //插入的结点小于当前结点,则继续查找左节点 node.left = put(node.left,key,value); }else if(key.compareTo(node.key) > 0){ //插入的结点大于当前结点,则继续查找右节点 node.right = put(node.right,key,value); }else{ //插入的结点等于当前结点, 则值替换 node.value = value; } return node; } private V get(Node node,K key){ if(node == null){ return null; } if(key.compareTo(node.key) < 0){ //查找的key在左节点 return get(node.left,key); }else if(key.compareTo(node.key) > 0){ //查找的key在右节点 return get(node.right,key); }else{ return node.value; } } private Node delete(Node node,K key){ if (node == null){ return null; } if(key.compareTo(node.key) < 0){ node.left = delete(node.left,key); }else if(key.compareTo(node.key) > 0){ node.right = delete(node.right,key); }else{ //待删除的结点为当前的node结点。 size--; //如果没有右子树,直接返回左子树 if(node.right == null){ return node.left; } //如果没有左子树,直接返回右子树 if(node.left == null){ return node.right; } //先找此结点右节点最小的结点,它的父结点指向为null。 Node minNode = node.right; while (minNode.left != null){ minNode = minNode.left; } //找最小结点的上一个结点 Node preMinNode = node; if(preMinNode.right.left !=null) { preMinNode = preMinNode.right; while (preMinNode.left.left != null) { preMinNode = preMinNode.left; } } preMinNode.left = null; //最小的结点左右结点重新指向 待删结点的左右结点。 minNode.left = node.left; minNode.right = node.right; //待删除的父结点指向最小的结点。 node = minNode; } return node; } //获取最大值 private V getMax(Node node){ if(node == null){ return null; } while (node.right != null){ node = node.right; } return node.value; } //获取最小值 private V getMin(Node node){ if(node == null){ return null; } if(node.left != null){ return getMin(node.left); }else{ return node.value; } } //前序遍历 private void getPreList(Node node,Queue<Node> queue){ if(node == null){ return; } queue.add(node); getPreList(node.left,queue); getPreList(node.right,queue); } //中序遍历 private void getMidList(Node node,Queue<Node> queue){ if(node == null){ return; } getMidList(node.left,queue); queue.add(node); getMidList(node.right,queue); } //后序遍历 private void getAfterList(Node node,Queue<Node> queue){ if(node == null){ return; } getAfterList(node.left,queue); getAfterList(node.right,queue); queue.add(node); } //树高 private Integer getTop(Node node){ if(node == null){ return 0; } Integer leftMax = 0; Integer rightMax = 0; if(node.left != null) { leftMax = getTop(node.left); } if(node.right != null){ rightMax = getTop(node.right); } return leftMax > rightMax ? leftMax + 1: rightMax + 1; } //遍历的时候用到,所以修饰符为public public class Node{ private K key; private V value; private Node left; private Node right; public Node(K key, V value, Node left, Node right) { this.key = key; this.value = value; this.left = left; this.right = right; } //遍历的时候用到 public K getKey(){ return key; } //遍历的时候用到 public V getValue(){ return value; } } }
验证代码:
public class Main {
//构造二叉查找树,并查找
public static void main(String[] args) {
MyBinaryFindTree<Integer,String> myTree = new MyBinaryFindTree<>();
myTree.put(10,"张10");
myTree.put(8,"张8");
myTree.put(15,"张15");
myTree.put(5,"张5");
myTree.put(3,"张3");
myTree.put(6,"张6");
myTree.put(12,"张12");
myTree.put(20,"张20");
myTree.put(4,"张4");
System.out.println("树的大小=" + myTree.size());
System.out.println("二叉查找树,查找元素3对应的值:" + myTree.get(3));
myTree.delete(6);
System.out.println("树的大小=" + myTree.size());
System.out.println("最大的值:" + myTree.getMax());
System.out.println("最小的值:" + myTree.getMin());
System.out.println("前序遍历:");
Queue<MyBinaryFindTree<Integer, String>.Node> preList = myTree.getPreList();
for (MyBinaryFindTree<Integer, String>.Node node : preList){
System.out.print(node.getValue() +" ");
}
System.out.println("---------");
System.out.println("中序遍历:");
Queue<MyBinaryFindTree<Integer, String>.Node> midList = myTree.getMidList();
for (MyBinaryFindTree<Integer, String>.Node node : midList){
System.out.print(node.getKey() +" ");
}
System.out.println("---------");
System.out.println("后序遍历:");
Queue<MyBinaryFindTree<Integer, String>.Node> afterList = myTree.getAfterList();
for (MyBinaryFindTree<Integer, String>.Node node : afterList){
System.out.print(node.getValue() +" ");
}
System.out.println("---------");
System.out.println("层次遍历:");
Queue<MyBinaryFindTree<Integer, String>.Node> layerList = myTree.getLayerList();
for (MyBinaryFindTree<Integer, String>.Node node : layerList){
System.out.print(node.getKey() +" ");
}
System.out.println("---------");
System.out.println("树高:" + myTree.getTop());
}
}
本文参考链接:https://www.cnblogs.com/maohuidong/p/14245590.html