CS61B项目笔记(五)-Lab7-二叉查找树

Lab 7: BSTMap | CS 61B Spring 2021 (datastructur.es)

创建一个 BSTMap 类，它使用 BST（二叉搜索树）作为其核心数据结构来实现 Map61B 接口。您必须在名为 BSTMap.java 的文件中执行此操作。您的实现需要实现 Map61B 中给出的所有方法，但 remove 、 iterator 和 keySet 除外。对于这些方法，您应该抛出一个 UnsupportedOperationException

在创建 BSTMap 类并实现 Map61B 的所有方法之前，您的代码不会编译。您可以一次实现一个方法，方法是编写所有必需方法的方法签名，但为实现抛出 UnsupportedOperationExceptions ，直到您真正开始编写它们。

您的 BSTMap 还应该添加一个附加方法 printInOrder() （Map61B 接口中未给出），该方法按 Key 递增的顺序打印出 BSTMap。我们不会测试此方法的结果，但您会发现这对测试您的实现很有帮助！

资源

• Lecture 16 slides. 讲座 16 幻灯片。
• BST 代码来自我们的课程资源页面的Data Structures Into Java 第 109 和 111 页。
• 来自我们our optional textbook.的 BST 代码。
• ULLMap.java （已提供），一个基于 Map61B 实现的工作无序链接列表。

BSTMap

package bstmap;
import java.util.Iterator;
import java.util.Set;

public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V> {
    private Node root;             // root of BST

    private class Node {
        private K key;           // sorted by key
        private V val;         // associated data
        private Node left, right;  // left and right subtrees
        private int size;          // number of nodes in subtree

        public Node(K key, V val, int size) {
            this.key = key;
            this.val = val;
            this.size = size;
        }
    }

    /**
     * Initializes an empty symbol table.
     */
    public BSTMap() {
    }
    @Override
    public void clear() {
        root.size = 0;
//        clear(root);
        root = null;
    }

//    private Node clear(Node node) {
//        if (node == null) {
//            return null;
//        }
//        if (node.left != null) {
//            node.left = clear(node.left);
//        }
//        if (node.right != null) {
//            node.right = clear(node.right);
//        }
//        return null;
//    }
    @Override
    public boolean containsKey(K key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return conainsKey(root, key);
    }

    private boolean conainsKey(Node n, K key) {
        if (n == null) {
            return false;
        }
        int cmp = key.compareTo(n.key);
        if (cmp > 0) {
            return conainsKey(n.right, key);
        } else if (cmp < 0) {
            return conainsKey(n.left, key);
        } else {
            return true;
        }
    }

    @Override
    public V get(K key) {
        return get(root, key);
    }

    private V get(Node n, K key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        if (n == null) return null;
        int cmp = key.compareTo(n.key);
        if (cmp > 0) {
            return get(n.right, key);
        } else if (cmp < 0) {
            return get(n.left, key);
        } else {
            return n.val;
        }

    }

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

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

    @Override
    public void put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        root = put(root, key, value);
    }

    private Node put(Node node, K key, V value) {
        if (node == null) {
            return new Node(key, value, 1);
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = put(node.right, key, value);
        } else if (cmp < 0) {
            node.left = put(node.left, key, value);
        } else {
            node.val = value;
        }
        node.size = 1 + size(node.right) + size(node.left);
        return node;
    }

    public void printInOrder() {
        throw new IllegalArgumentException("argument to contains() is null");
    }
    @Override
    public Set<K> keySet() {
        throw new IllegalArgumentException("argument to contains() is null");
    }

    @Override
    public V remove(K key) {
        throw new IllegalArgumentException("argument to contains() is null");
    }

    @Override
    public V remove(K key, V value) {
        throw new IllegalArgumentException("argument to contains() is null");
    }

    @Override
    public Iterator<K> iterator() {
        throw new IllegalArgumentException("argument to contains() is null");
    }

//    private class MapIterator implements Iterator<K> {
//
//        /**
//         * Returns {@code true} if the iteration has more elements.
//         * (In other words, returns {@code true} if {@link #next} would
//         * return an element rather than throwing an exception.)
//         *
//         * @return {@code true} if the iteration has more elements
//         */
//        int size = size();
//        MapIterator() {
//
//        }
//        @Override
//        public boolean hasNext() {
//
//        }
//
//        /**
//         * Returns the next element in the iteration.
//         *
//         * @return the next element in the iteration
//         */
//        @Override
//        public K next() {
//            return null;
//        }
//    }
}

ULLMap

package bstmap;

import java.util.Iterator;
import java.util.Set;

/** A data structure that uses a linked list to store pairs of keys and values.
 *  Any key must appear at most once in the dictionary, but values may appear multiple
 *  times. Key operations are get(key), put(key, value), and contains(key) methods. The value
 *  associated to a key is the value in the last call to put with that key. */
public class ULLMap<K, V>  implements Map61B<K, V> {

    int size = 0;

    /** Returns the value corresponding to KEY or null if no such value exists. */
    public V get(K key) {
        if (list == null) {
            return null;
        }
        Entry lookup = list.get(key);
        if (lookup == null) {
            return null;
        }
        return lookup.val;
    }

    @Override
    public int size() {
        return size;
    }

    /** Removes all of the mappings from this map. */
    @Override
    public void clear() {
        size = 0;
        list = null;
    }

    /** Inserts the key-value pair of KEY and VALUE into this dictionary,
     *  replacing the previous value associated to KEY, if any. */
    public void put(K key, V val) {
        if (list != null) {
            Entry lookup = list.get(key);
            if (lookup == null) {
                list = new Entry(key, val, list);
            } else {
                lookup.val = val;
            }
        } else {
            list = new Entry(key, val, list);
            size = size + 1;
        }
    }

    /** Returns true if and only if this dictionary contains KEY as the
     *  key of some key-value pair. */
    public boolean containsKey(K key) {
        if (list == null) {
            return false;
        }
        return list.get(key) != null;
    }

    @Override
    public Iterator<K> iterator() {
        return new ULLMapIter();
    }

    /** Keys and values are stored in a linked list of Entry objects.
     *  This variable stores the first pair in this linked list. */
    private Entry list;

    /** Represents one node in the linked list that stores the key-value pairs
     *  in the dictionary. */
    private class Entry {

        /** Stores KEY as the key in this key-value pair, VAL as the value, and
         *  NEXT as the next node in the linked list. */
        Entry(K k, V v, Entry n) {
            key = k;
            val = v;
            next = n;
        }

        /** Returns the Entry in this linked list of key-value pairs whose key
         *  is equal to KEY, or null if no such Entry exists. */
        Entry get(K k) {
            if (k != null && k.equals(key)) {
                return this;
            }
            if (next == null) {
                return null;
            }
            return next.get(key);
        }

        /** Stores the key of the key-value pair of this node in the list. */
        K key;
        /** Stores the value of the key-value pair of this node in the list. */
        V val;
        /** Stores the next Entry in the linked list. */
        Entry next;

    }

    /** An iterator that iterates over the keys of the dictionary. */
    private class ULLMapIter implements Iterator<K> {

        /** Create a new ULLMapIter by setting cur to the first node in the
         *  linked list that stores the key-value pairs. */
        public ULLMapIter() {
            cur = list;
        }

        @Override
        public boolean hasNext() {
            return cur != null;
        }

        @Override
        public K next() {
            K ret = cur.key;
            cur = cur.next;
            return ret;
        }

        /** Stores the current key-value pair. */
        private Entry cur;

    }

    @Override
    public V remove(K key) {
        throw new UnsupportedOperationException();
    }

    @Override
    public V remove(K key, V value) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Set<K> keySet() {
        throw new UnsupportedOperationException();
    }

}

Map61B接口

package bstmap;

import java.util.Set;

/* Your implementation BSTMap should implement this interface. To do so,
 * append "implements Map61B<K,V>" to the end of your "public class..."
 * declaration, though you can use other formal type parameters if you'd like.
 */
public interface Map61B<K, V> extends Iterable<K> {

    /** Removes all of the mappings from this map. */
    void clear();

    /* Returns true if this map contains a mapping for the specified key. */
    boolean containsKey(K key);

    /* Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     */
    V get(K key);

    /* Returns the number of key-value mappings in this map. */
    int size();

    /* Associates the specified value with the specified key in this map. */
    void put(K key, V value);

    /* Returns a Set view of the keys contained in this map. Not required for Lab 7.
     * If you don't implement this, throw an UnsupportedOperationException. */
    Set<K> keySet();

    /* Removes the mapping for the specified key from this map if present.
     * Not required for Lab 7. If you don't implement this, throw an
     * UnsupportedOperationException. */
    V remove(K key);

    /* Removes the entry for the specified key only if it is currently mapped to
     * the specified value. Not required for Lab 7. If you don't implement this,
     * throw an UnsupportedOperationException.*/
    V remove(K key, V value);

}