二叉查找树简单实现

一塔 2021-03-21 PM 9℃ 0条

构造二叉查找树

/**
 * 二叉查找树
 * @param <Key> 键
 * @param <Value> 值
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;  //二叉查找树根节点


    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.N;
        }
    }

    //get方法
    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node root, Key key) {
        if (root == null) {
            return null;
        }
        int cmp = key.compareTo(root.key);
        if (cmp < 0) {
            return get(root.left, key);
        } else if (cmp > 0) {
            return get(root.right, key);
        } else {
            return root.val;
        }
    }

    //put方法
    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
        if (x == null) {
            return new Node(key, val, 1);
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, val);
        } else if (cmp > 0) {
            x.right = put(x.right, key, val);
        } else {
            x.val = val;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    /**
     * 节点
     */
    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        private int N;

        public Node(Key key, Value val, int n) {
            this.key = key;
            this.val = val;
            N = n;
        }
    }
}

人类,实现comparable接口

public class Man implements Comparable<Man> {
    private int age;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Man o) {
        return this.age - o.age;
    }
}

Value,身体状态,树存储的值

public class PhysicalStatus {
    private String status;

    public String getStatus() {
        return status;
    }

    public void setStatus(String status) {
        this.status = status;
    }

    @Override
    public String toString() {
        return "PhysicalStatus{" +
                "status='" + status + '\'' +
                '}';
    }
}

测试:

public class BSTTest {

    @Test
    public void test() {
        BST<Man, PhysicalStatus> bst = new BST<>();
        Man man = new Man();
        man.setAge(20);

        Man man1 = new Man();
        man1.setAge(10);

        PhysicalStatus physical = new PhysicalStatus();
        physical.setStatus("正值壮年");

        PhysicalStatus physical1 = new PhysicalStatus();
        physical1.setStatus("祖国的花朵");

        bst.put(man, physical);
        bst.put(man1, physical1);

        PhysicalStatus physicalStatus = bst.get(man1);
        System.out.println(physicalStatus);
    }
}

打印

PhysicalStatus{status='祖国的花朵'}

示例来自:算法第4版

标签: 算法

非特殊说明,本博所有文章均为博主原创。

评论啦~