2018-2019-20172309 《程序设计与数据结构（下）》实验二报告

课程：《程序设计与数据结构（下）》
班级：1723
姓名： 王志伟
学号：20172309
实验教师：王志强老师
实验日期：2018年11月2日
必修/选修： 必修

实验内容：

实验一：实现二叉树。

1.参考教材p212,完成链树LinkedBinaryTree的实现（getRight,contains,toString,preorder,postorder）.

2.用JUnit或自己编写驱动类对自己实现的LinkedBinaryTree进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息.

3.课下把代码推送到代码托管平台.

实验二：前序、中序遍历构造二叉树。

1.基于LinkedBinaryTree，实现基于（中序，先序）序列构造唯一一棵二㕚树的功能，比如给出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,构造出附图中的树.

2.用JUnit或自己编写驱动类对自己实现的功能进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息.

3.课下把代码推送到代码托管平台.

实验三：理解决策树。

1.自己设计并实现一颗决策树

2.提交测试代码运行截图，要全屏，包含自己的学号信息

3.课下把代码推送到代码托管平台

实验四：运用表达式树。

1.完成PP11.3

2.提交测试代码运行截图，要全屏，包含自己的学号信息

3.课下把代码推送到代码托管平台

实验五：实现二叉查找树。

1.完成PP11.3

2.提交测试代码运行截图，要全屏，包含自己的学号信息

3.课下把代码推送到代码托管平台

实验六：红黑树分析。

参考点击这里对Java中的红黑树（TreeMap，HashMap）进行源码分析，并在实验报告中体现分析结果。

（文件位于：C:Program FilesJavajdk-11.0.1libsrcjava.basejavautil）

实验过程及结果：

实验一：

这个实验是要求我们实现几个方法，然后进行测试。

1.得到右子树：getright（）

 public LinkedBinaryTree<T> getRight()
    {
       return right;
    }
//这个类是一个二叉树类，里面属性left、right，分别代表左子树和右子树，要想得到右子树，直接return right;即可！

2.是否含有元素的方法：contains（T targeElement）

这里编写了两个方法，值得注意的是：一个是公有的（public），另一个是私有的（private）。说明公有的方法用于外部类调用，而这个私有类的方法被用于用于公有方法。

public boolean contains(T targetElement) 
    {
        return findNode(targetElement,root)!=null;//调用私有方法findNode（）
    }

private BinaryTreeNode<T> findNode(T targetElement, 
                                        BinaryTreeNode<T> next)
    {//这个方法在树中查找目标元素，没找到时，分别在其左右子树中查找、**运用了递归**！
        if (next == null)
            return null;
        
        if (next.getElement().equals(targetElement))
            return next;
        
        BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());
        
        if (temp == null)
            temp = findNode(targetElement, next.getRight());
        
        return temp;
    }

输出的方法：toString（）

这个输出方法通过构建两个无序列表，分别应于放置结点和对应的级数，好用于计算后面输出的空格数。其中最难的是每一层相邻的两个结点之间的空格数。

public String toString() 
    {
        UnorderedListADT<BinaryTreeNode<T>> nodes =
                new UnorderedListArrayList<BinaryTreeNode<T>>();
        UnorderedListADT<Integer> levelList =
                new UnorderedListArrayList<Integer>();
        BinaryTreeNode<T> current;
        String result = "";
        int printDepth = this.getHeight();
        int possibleNodes = (int)Math.pow(2, printDepth + 1);
        int countNodes = 0;
        
        nodes.addToRear((BinaryTreeNode<T>) root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);
        
        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removefirst();
            currentLevel = levelList.removefirst();
            if (currentLevel > previousLevel)
            {
                result = result + "

";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }
            
        }
        return result;
    }

前序、后序遍历方法：preOrder（）

前序遍历的顺序是：先遍历该结点，然后是他们的孩子。
因此用伪代码表示为：//详细代码见here

  Visit node;//前序遍历
  preOrder(leftChild); 
  preOrder(rightChild);

  postOrder(leftChild);
  postOrder(rightChild);
  visit node;//后序遍历

运行结果：

实验二：

1.实验二是说给定咋们中序遍历和后序遍历的结果，让后让咋们生成一棵树。科普：当给定前序和后序遍历会结果得不到一棵树，因为分不清左右结点

2.我们基于一个事实：中序遍历一定是 { 左子树节点集合 }，root，{ 右子树节点集合 }。

3.后序序遍历的作用就是找到每颗子树的root位置。

 public void generateTree(T[] A,T[] B){//A、B两个数组分别是放前序、后序遍历结果的。
        BinaryTreeNode<T> temp = getTree(A, B);
        root=temp;
    }
    private BinaryTreeNode<T> getTree(T[] inOrder,T [] postOrder){
        int length = postOrder.length;
        T rootElement = postOrder[postOrder.length-1];
       BinaryTreeNode<T> temp = new BinaryTreeNode<T>(rootElement);
       
        if (length==1)
            return temp;
        else{
            int index = 0;
            while (inOrder[index]!=rootElement)
                index++;

            if (index>0){//分界结点的左边又可以生成一个子中序遍历数组和后序遍历数组。之后运用递归。
                T [] leftInOrder = (T[])new Object[index];
                for(int i=0;i<leftInOrder.length;i++)
                    leftInOrder[i]=inOrder[i];
                T [] leftPostOrder = (T[])new Object[index];
                for (int i=0;i<leftPostOrder.length;i++)
                    leftPostOrder[i] = postOrder[i];
                temp.setLeft(getTree(leftInOrder,leftPostOrder));
            }
            if (length-index-1>0){//右边也一样，生成子两个数组，运用递归。
                T [] rightInOrder = (T[])new Object[length-index-1];
                for (int i=0;i<length-index-1;i++)
                    rightInOrder[i]=inOrder[i+index+1];
                T [] rightPostOrder = (T[])new Object[length-index-1];
                for (int i=0;i<length-index-1;i++)
                    rightPostOrder[i]=postOrder[i+index];
                temp.setRight(getTree(rightInOrder,rightPostOrder));
            }
        }
        return temp;
    }

运行结果：

实验三：

这个实验就是自己制作一棵决策树，我们只要修改TXT文件就OK！
修改后的文件为：
运行结果为：

实验四：

该实验是要求我们用树的性质将一个中缀表达式转换成后缀表达式，并得到计算结果。
因此我们大概可以想到：它的答题构架是这样的

    public ExpressionTree getPostfixTree(String expression){//传进去的是一个中缀表达式
    
    。。。一大串代码。。。
    
    return EXpressionTree;//经过一大串代码得到一颗表达式树。
    
    }

经过我TM打十把王者的时间，把它写好了。

 ExpressionTree operand1,operand2;
        char operator;
        String tempToken;

        Scanner parser = new Scanner(expression);

        while(parser.hasNext()){
            tempToken = parser.next();
            operator=tempToken.charAt(0);

            if ((operator == '+') || (operator == '-') || (operator=='*') ||
                    (operator == '/')){
                if (ope.empty())
                    ope.push(tempToken);//当储存符号的栈为空时，直接进栈
                else{
                    String a =ope.peek()+"";//因为当ope.peek()='-'时，计算机认为ope.peek()=='-'为false，所以要转化为string 使用equals（）方法
                    if (((a.equals("+"))||(a.equals("-")))&&((operator=='*')||(operator=='/')))
                        ope.push(tempToken);//当得到的符号的优先级大于栈顶元素时，直接进栈
                    else {
                        String s = String.valueOf(ope.pop());
                        char temp = s.charAt(0);
                            operand1 = getOperand(treeExpression);
                            operand2 = getOperand(treeExpression);
                            treeExpression.push(new ExpressionTree
                                    (new ExpressionTreeOp(1, temp, 0), operand2, operand1));
                            ope.push(operator);
                    }//当得到的符号的优先级小于栈顶元素或者优先级相同时时，数字栈出来两个运算数，形成新的树进栈
                }
            }
            else
                treeExpression.push(new ExpressionTree(new ExpressionTreeOp
                        (2,' ',Integer.parseInt(tempToken)), null, null));
        }
        while(!ope.empty()){
           String a = String.valueOf(ope.pop());
           operator = a.charAt(0);
            operand1 = getOperand(treeExpression);
            operand2 = getOperand(treeExpression);
            treeExpression.push(new ExpressionTree
                    (new ExpressionTreeOp(1, operator, 0), operand2, operand1));
        }
        return treeExpression.peek();

运行结果为：

生成树后，我们发现把这颗树直接后序遍历就可以得到后缀表达式。详细代码click here

实验五：

实验要求为完成findMax（）、removeMax（）、findMin()方法。
我们必须明白，二叉查找树具有左子树小于父结点，右子树大于或等于父结点的性质。因此树的最左侧会放置最小元素、而最右侧会放置最大元素。
代码如下：

去除最小元素方法。

public T removeMin() throws EmptyCollectionException 
    {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else 
        {
            if (root.left == null) 
            {
                result = root.element;
                root = root.right;
            }
            else 
            {
                BinaryTreeNode2<T> parent = root;
                BinaryTreeNode2<T> current = root.left;
                while (current.left != null) 
                {
                    parent = current;
                    current = current.left;
                }
                result =  current.element;
                parent.left = current.right;
            }

            modCount--;
        }
 
        return result;
    }

去除最大元素方法。

    public T removeMax() throws EmptyCollectionException
    {
        T result= null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree!");
        else{
            if (root.right == null){
                result = root.element;
                root=root.left;
            }
            else{
                BinaryTreeNode2<T> parent = root;
                BinaryTreeNode2<T> current = root.right;
                while(current.right != null){
                    parent = current;
                    current = current.right;
                }
                result = current.element;
                parent.right = current.left;
            }
            modCount--;
        }

        return result;
    }

找到最大元素方法。

    public T findMax() throws EmptyCollectionException {
        if (isEmpty())
            System.out.println("BinarySearchTree is empty!");

        return findmax(root).element;
    }

实验结果：

实验六：

首先来介绍什么是Map：

在数组中我们是通过数组下标来对其内容索引的，而在Map中我们通过对象来对对象进行索引，用来索引的对象叫做key，其对应的对象叫做value。这就是我们平时说的键值对.

他们有一个显著的特征：HashMap通过hashcode对其内容进行快速查找，而 TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

先看看他们两的类头：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

AbstractMap抽象类和SortedMap接口
- AbstractMap抽象类：(HashMap继承AbstractMap)覆盖了equals()和hashCode()方法以确保两个相等映射返回相同的哈希码。如果两个映射大小相等、包含同样的键且每个键在这两个映射中对应的值都相同，则这两个映射相等。映射的哈希码是映射元素哈希码的总和，其中每个元素是Map.Entry接口的一个实现。因此，不论映射内部顺序如何，两个相等映射会报告相同的哈希码。
- SortedMap接口：（TreeMap继承自SortedMap）它用来保持键的有序顺序。SortedMap接口为映像的视图(子集)，包括两个端点提供了访问方法。除了排序是作用于映射的键以外，处理SortedMap和处理SortedSet一样。添加到SortedMap实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供一个Comparator接口的实现。TreeMap类是它的唯一一份实现。
两种常规Map实现
- HashMap：基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()]，为了优化HashMap空间的使用，您可以调优初始容量和负载因子。
  - HashMap(): 构建一个空的哈希映像
  - HashMap(Map m): 构建一个哈希映像，并且添加映像m的所有映射
  - HashMap(int initialCapacity): 构建一个拥有特定容量的空的哈希映像
  - HashMap(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子的空的哈希映像
- TreeMap：基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。
  - TreeMap():构建一个空的映像树
  - TreeMap(Map m): 构建一个映像树，并且添加映像m中所有元素
  - TreeMap(Comparator c): 构建一个映像树，并且使用特定的比较器对关键字进行排序
    -TreeMap(SortedMap s): 构建一个映像树，添加映像树s中所有映射，并且使用与有序映像s相同的比较器排序
两种常规Map性能
HashMap：适用于在Map中插入、删除和定位元素。
Treemap：适用于按自然顺序或自定义顺序遍历键(key)。
总结
HashMap通常比TreeMap快一点(树和哈希表的数据结构使然)，建议多使用HashMap，在需要排序的Map时候才用TreeMap。

HashMap代码分析：

HashMap类源代码：

public class HashMap<K,V>extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    /**
     * The default initial capacity - MUST be a power of two.
     * 默认的容量必须为2的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     *默认最大值
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     * 负载因子 
    */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     * 到这里就发现了，HashMap就是一个Entry[]类型的数组了。
     */
    transient Entry<K,V>[] table;

HashMap类构造函数源代码：

/**    
  * Constructs an empty <tt>HashMap</tt> with the specified initial    
  * capacity and load factor.     
  * @param  initialCapacity the initial capacity   
  * @param  loadFactor      the load factor    
  * @throws IllegalArgumentException if the initial capacity is negative    
  *   or the load factor is nonpositive
  */
   // 初始容量（必须是2的n次幂），负载因子
   public HashMap(int initialCapacity, float loadFactor) {     
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);    
     if (initialCapacity > MAXIMUM_CAPACITY)   
         initialCapacity = MAXIMUM_CAPACITY;      
     if (loadFactor <= 0 || Float.isNaN(loadFactor))          
         throw new IllegalArgumentException("Illegal load factor: " +  loadFactor);     
        // Find a power of 2 >= initialCapacity
       int capacity = 1;
       // 获取最小于initialCapacity的最大值，这个值是2的n次幂，所以我们定义初始容量的时候尽量写2的幂
       while (capacity < initialCapacity)
      // 使用位移计算效率更高
      capacity <<= 1;       
      this.loadFactor = loadFactor;
      //哈希表的最大容量的计算，取两个值中小的一个  
      threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
      //创建容量为capacity的Entry[]类型的数组
      table = new Entry[capacity];
       useAltHashing = sun.misc.VM.isBooted() && (capacity >=                   Holder.ALTERNATIVE_HASHING_THRESHOLD);       
init();
    }

HashMap 的实例有两个參数影响其性能：初始容量 和载入因子。容量是哈希表中桶的数量。初始容量仅仅是哈希表在创建时的容量。载入因子是哈希表在其容量自己主动添加之前能够达到多满的一种尺度。当哈希表中的条目数超出了载入因子与当前容量的乘积时，则要对该哈希表进行rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
HashMap底层是哈希表实现
HashMap--put方法

public V put(K key, V value) {
      //key为null的entry总是放在数组的头节点上,也就是上面说的"桶"中
      if (key == null)
        return putForNullKey(value);
      // 获取key的哈希值
      int hash = hash(key);
      // 通过key的哈希值和table的长度取模确定‘桶’（bucket）的位置
      int i = indexFor(hash, table.length);
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
          Object k;
         //假设key映射的entry在链表中已存在，则entry的value替换为新value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

addEntry(hash,key,value,i)方法：

//bucketIndex  桶的索引值，桶中仅仅能存储一个值（一个Entry 对象）也就是头节点
 void addEntry(int hash, K key, V value, int bucketIndex) {
    // 假设数组中存储的元素个数大于数组的临界值（这个临界值就是 数组长度*负载因子的值 ）则进行扩容
      if ((size >= threshold) && (null != table[bucketIndex])) {
    // 扩容，将大小扩为原来的两倍
       resize(2 * table.length);
        hash = (null != key) ?
 hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
       }
      createEntry(hash, key, value, bucketIndex);
    }

总结：

HashMap 是链式数组（存储链表的数组）实现查询速度能够。并且能高速的获取key相应的value；
查询速度的影响因素有容量和负载因子，容量大负载因子小查询速度快但浪费空间，反之则相反。
数组的index值是（key keyword， hashcode为key的哈希值。 len 数组的大小）：hashcode%len的值来确定，假设容量大负载因子小则index同样（index同样也就是指向了同一个桶）的概率小。链表长度小则查询速度快。反之index同样的概率大链表比較长查询速度慢。
对于HashMap以及其子类来说。他们是採用hash算法来决定集合中元素的存储位置，当初始化HashMap的时候系统会创建一个长度为capacity的Entry数组，这个数组里能够存储元素的位置称为桶（bucket）,每个桶都有其指定索引，系统能够依据索引高速訪问该桶中存储的元素。
不管何时HashMap 中的每一个桶都仅仅存储一个元素（Entry 对象）。
因为Entry对象能够包括一个引用变量用于指向下一个Entry，因此可能出现HashMap 的桶（bucket）中仅仅有一个Entry,但这个Entry指向还有一个Entry 这样就形成了一个Entry 链。
通过上面的源代码发现HashMap在底层将key_value对当成一个总体进行处理（Entry 对象）这个总体就是一个Entry对象，当系统决定存储HashMap中的key_value对时，全然没有考虑Entry中的value，而不过依据key的hash值来决定每一个Entry的存储位置。

实验过程中遇到的问题：

问题一.为什么为实现某一个功能，一般都写两个方法：Public、Private方法，然后我们用就调用这个pubic方法？比如上面的实验二中的generateTree（）方法与getTree（）方法？
- 经过查资料知道这样做主要有两个好处：
  - 一. 从代码上看，以上面的实验二方法为例、两者的传入数据虽然相同，都是两个数组。但是他们的返回值不同，也就是说：有返回值的方法，使用该方法时能够得到一些类型的数据再来利用。
  - 二. 从整体上看，这是一种保护机制，不让自己这个类以外的方法去随便使用这个类的数据，可以保护他的数据，只能通过调用自己类的方法去操纵这些数据。这样会很安全。
问题二.实验三TXT文件中的数字是什么东西？
- 经过与侯泽洋讨论才知道，这个东西是用于构建树的，而数字是它们每个数字的索引。
  像是这样：
- 还有一个问题就是为什么他的顺序是
```
   3 7 8
   4 9 10
   5 11 12
   1 3 4
   2 5 6
   0 1 2//这样的
```
```
 0 1 2
 2 5 6
 1 3 6
 5 11 12
 4 9 10
 3 7 8//而非得是倒着来呢？
```
- 其实这样是很合理的，因为我们构建一颗决策树时，是先构建子树，然后再把子树联合起来的。所以是倒着来的。
问题三及问题四.进行实验四的时候出现：

-然后经过自习调试才发现是判断条件出现了问题：当ope.peek()=“+”时，他认为ope.peek()=="+"为false，我也不知道怎么回事！
- 经过修改：ope.Peek（）.equals("+")解决了这个问题。
- 但是在后面又出现了问题：结果表明又是符号优先级出现问题！但是我保证、后面的答案也证明我的逻辑没错！
- 经过调试，还是发现那个判断条件出现了问题！！！烦的一批！！！
  - 之后我直接把所有的数据转换成String类型再来判断、才解决了问题！