實驗二 20162312

實作二叉樹

要求：參考教材p375,完成鍊樹LinkedBinaryTree的實作（getRight,contains,toString,preorder,postorder）用JUnit或自己編寫驅動類對自己實作的LinkedBinaryTree進行測試，送出測試代碼運作截圖，要全屏，包含自己的學号資訊,課下把代碼推送到代碼托管平台.

實驗思路：getright仿照書上getleft格式即可；contains方法調用find方法，傳回值則是boolean類型；preorder和postorder方法則和inorder方法有些類似，都是調用BTnode類并遞歸；

實驗截圖：

中序先序序列構造二叉樹

要求：基于LinkedBinaryTree，實作基于（中序，先序）序列構造唯一一棵二㕚樹的功能，比如教材P372，給出HDIBEMJNAFCKGL和ABDHIEJMNCFGKL,構造出附圖中的樹

用JUnit或自己編寫驅動類對自己實作的功能進行測試，送出測試代碼運作截圖，要全屏，包含自己的學号資訊

課下把代碼推送到代碼托管平台

實驗思路：将左子樹中的元素的先序表達式放入新的數組

決策樹

要求：完成PP16.6,送出測試代碼運作截圖，要全屏，包含自己的學号資訊,課下把代碼推送到代碼托管平台.

實驗思路：主要是改書上的代碼，但要對樹的構造比較清楚，并且自己設定的内容邏輯要和樹的構造相符。

表達式樹

要求：完成PP16.8,送出測試代碼運作截圖，要全屏，包含自己的學号資訊,課下把代碼推送到代碼托管平台

實驗思路：沒有完成

二叉查找樹

要求：完成PP17.1,送出測試代碼運作截圖，要全屏，包含自己的學号資訊,課下把代碼推送到代碼托管平台.

實驗思路：很容易補全findMax(),findMin()方法.

紅黑樹分析

要求：參考http://www.cnblogs.com/rocedu/p/7483915.html對Java中的紅黑樹（TreeMap，HashMap）進行源碼分析，并在實驗報告中展現分析結果

實驗思路：分析源代碼并上網參考相關資料

什麼是紅黑樹

• 每個節點要麼是紅色，要麼是黑色。
• 根節點必須是黑色
• 紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）。
• 對于每個節點，從該點至null（樹尾端）的任何路徑，都含有相同個數的黑色節點。

左旋及代碼實作

//Rotate Left
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}
           

右旋及代碼實作

//Rotate Right
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}
           

方法剖析：

• 方法get(Object key)方法根據指定的key值傳回對應的value，該方法調用了getEntry(Object key)得到相應的entry，然後傳回entry.value。

  是以getEntry()是算法的核心。算法思想是根據key的自然順序（或者比較器順序）對二叉查找樹進行查找，直到找到滿足k.compareTo(p.key) == 0的entry。

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    ......
    if (key == null)//不允許key值為null
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然順序
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)//向左找
            p = p.left;
        else if (cmp > 0)//向右找
            p = p.right;
        else
            return p;
    }
    return null;
}
           

• 方法put(K key, V value)方法是将指定的key, value對添加到map裡。該方法首先會對map做一次查找，看是否包含該元組，如果已經包含則直接傳回，

  查找過程類似于getEntry()方法；如果沒有找到則會在紅黑樹中插入新的entry，如果插入之後破壞了紅黑樹的限制，還需要進行調整（旋轉，改變某些節點的顔色）。

public V put(K key, V value) {
    ......
    int cmp;
    Entry<K,V> parent;
    if (key == null)
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然順序
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0) t = t.left;//向左找
        else if (cmp > 0) t = t.right;//向右找
        else return t.setValue(value);
    } while (t != null);
    Entry<K,V> e = new Entry<>(key, value, parent);//建立并插入新的entry
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);//調整
    size++;
    return null;
}
           

• 方法remove的作用是删除key值對應的entry，該方法首先通過上文中提到的getEntry(Object key)方法找到key值對應的entry，

  然後調用deleteEntry(Entry<K,V> entry)删除對應的entry。由于删除操作會改變紅黑樹的結構，有可能破壞紅黑樹的限制，是以有可能要進行調整。