Skip to main content
 首页 » 编程设计

java算法之自定义二叉查找树基本操作

2022年07月18日40虾米哥
/** 
 * @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