二叉树--二叉查找树定义

今天时间有限，就没有单独实现二叉树算法，简单实现了一个二叉查找树的类。

题目介绍

实现一个二叉树，实现以下两个功能：

• 保存一个节点，每个节点包含<key,value>键值对，若节点存在则更新节点的值，若节点不存在则将节点插入到合适的位置。

• 根据键值查找节点，若节点存在则返回节点的值，若节点不存在则返回null。

我们还是用昨天的图来看下二叉树涨什么样子吧：

二叉树遍历题目.png

实现思路

先看下二叉树核心定义：父节点的键一定大于左子树节点的键，小于右子树节点的键。而我们的键值不一定为整数，因此key就需要支持规范的比较操作。

实现代码

public class BinarySearchST<Key extends Comparable<Key>, Value> {

    private Node root;

    class Node {
        private Key key;
        private Value value;
        private Node left;
        private Node right;

    }

    public boolean isEmpty() {
        return null == root;
    }

    public Value get(Key key) {
        Node node = helper(key, root);
        return node == null ? null : node.value;
    }

    private Node helper(Key key, Node node) {
        if (null == node) {
            return null;
        }
        if (node.key.compareTo(key) == 0) {
            return node;
        } else if (key.compareTo(node.key) < 0) {
            return helper(key, node.left);
        } else {
            return helper(key, node.right);
        }
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    private Node put(Node node, Key key, Value value) {
        if (null == node) {
            node = new Node();
            node.key = key;
            node.value = value;
        } else 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 int getSize(Node node) {
        if (null != node) {
            return getSize(node.left) + getSize(node.right) + 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        BinarySearchST<String, String> binarySearchST = new BinarySearchST();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            String[] a = s.split(":");
            String key = a[0];
            String value = a[1];
            binarySearchST.put(key, value);
        }
        StdOut.println(binarySearchST.get("g"));
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms