style: ocean

实验二 树

实验内容

实验二 实现二叉树

参考教材p375,完成链树LinkedBinaryTree的实现（getRight,contains,toString,preorder,postorder）。用JUnit或自己编写驱动类对自己实现的LinkedBinaryTree进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息。课下把代码推送到代码托管平台

import java.util.*;

public class MyLinkedBinaryTree<T> implements BinaryTree<T>
{
    protected BTNode<T> root;

    public MyLinkedBinaryTree()
    {
        root = null;
    }

    public MyLinkedBinaryTree (T element)
    {
        root = new BTNode<T>(element);
    }

    public MyLinkedBinaryTree (BTNode rootNode){
        root = rootNode;
    }

    public MyLinkedBinaryTree (T element, MyLinkedBinaryTree<T> left,
                             MyLinkedBinaryTree<T> right)
    {
        root = new BTNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
    }

    @Override
    public T getRootElement()
    {
        if (root == null){
            return null;
        }
        return root.getElement();
    }

    @Override
    public MyLinkedBinaryTree<T> getLeft()
    {
        if (root == null){
            return null;
        }

        MyLinkedBinaryTree<T> result = new MyLinkedBinaryTree<T>();
        result.root = root.getLeft();

        return result;
    }

    @Override
    public T find (T target)
    {
        BTNode<T> node = null;

        if (root != null){
            node = root.find(target);
        }
        if (node == null){
            return null;
        }
        return node.getElement();
    }

    @Override
    public int size()
    {
        int result = 0;
        if (root != null){
            result = root.count();
        }
        return result;
    }


    @Override
    public Iterator<T> inorder()
    {
        ArrayIterator<T> iter = new ArrayIterator<T>();

        if (root != null){
            root.inorder (iter);
        }
        return iter;
    }

    @Override
    public Iterator<T> levelorder()
    {
        MyLinkedQueue<BTNode<T>> queue = new MyLinkedQueue<BTNode<T>>();
        ArrayIterator<T> iter = new ArrayIterator<T>();

        if (root != null)
        {
            queue.enqueue(root);
            while (!queue.isEmpty())
            {
                BTNode<T> current = queue.dequeue();

                iter.add (current.getElement());

                if (current.getLeft() != null){
                    queue.enqueue(current.getLeft());
                }
                if (current.getRight() != null){
                    queue.enqueue(current.getRight());
                }
            }
        }

        return iter;
    }

    @Override
    public Iterator<T> iterator()
    {
        return inorder();
    }
    @Override
    public MyLinkedBinaryTree<T> getRight() {
        if (root == null){
            return null;
        }

        MyLinkedBinaryTree<T> result = new MyLinkedBinaryTree<T>();
        result.root = root.getRight();

        return result;
    }
    @Override
    public boolean contains (T target) {
        Iterator<T> iter = this.inorder();
        while (iter.hasNext()){
            if (target.equals(iter.next())){
                return true;
            }
        }
        return false;
    }
    @Override
    public boolean isEmpty() {return root==null; }

    @Override
    public String toString() {
        Iterator iter = levelorder();
        return iter.toString();
    }
    @Override
    public Iterator<T> preorder() {
        ArrayIterator<T> iter = new ArrayIterator<>();
        if (root!=null){
            root.preorder(iter);
        }
        return iter;
    }
    @Override
    public Iterator<T> postorder() {
        ArrayIterator<T> iter = new ArrayIterator<>();
        if (root!=null){
            root.postorder(iter);
        }
        return iter;
    }
}

实现了LinkedBinaryTree的getRight，contains，toString，preorder，postorder等方法

实验二 中序先序序列构造二叉树

基于LinkedBinaryTree，实现基于（中序，先序）序列构造唯一一棵二㕚树的功能，比如教材P372，给出HDIBEMJNAFCKGL和ABDHIEJMNCFGKL,构造出附图中的树。用JUnit或自己编写驱动类对自己实现的功能进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息。课下把代码推送到代码托管平台

import java.util.HashMap;


public class exp2 {
    final static char[] inorder = "HDIBEMJNAFCKGL".toCharArray();
    final static char[] preorder = "ABDHIEJMNCFGKL".toCharArray();
    public static void main(String[] args) {
        MyLinkedBinaryTree<Character> root= new MyLinkedBinaryTree(genetree(preorder,inorder));
        System.out.println(root);
    }
    public static BTNode genetree(char[] pre, char[] in) {
        if (pre == null) return null;
        HashMap<Character, Integer> map = geneMap(in);
        return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
    }

    public static HashMap<Character,Integer> geneMap(char[] charArray){
        HashMap<Character,Integer> temp = new HashMap<>();
        int len = charArray.length;
        for (int i = 0; i < len;i++){
            temp.put(charArray[i],i);
        }
        return temp;
    }

    public static BTNode preIn(char[] pre, int preindex, int pj, char[] in, int inindex, int nj, HashMap<Character, Integer> position) {

        if (preindex > pj) return null;
        BTNode head = new BTNode(pre[preindex]);
        int index = position.get(pre[preindex]);
        head.left = preIn(pre, preindex + 1, preindex + index - inindex, in, inindex, index - 1, position);
        head.right = preIn(pre, preindex + index - inindex + 1, pj, in, index + 1, nj, position);
        return head;
    }
}

使用递归的方法，从根结点的两边开始构造子树，并如此循环。

实验二 决策树

完成PP16.6。提交测试代码运行截图，要全屏，包含自己的学号信息。课下把代码推送到代码托管平台

import java.util.Scanner;

public class BackPainExpert
{
    private MyLinkedBinaryTree<String> tree;

    //-----------------------------------------------------------------
    //  Sets up the diagnosis question tree.
    //-----------------------------------------------------------------
    public BackPainExpert()
    {
        String e1 = "一共有七种动物（小猫、小狗、小仓鼠、小鸭子、小鱼、小乌龟、大熊猫），\n你想好的动物能游泳吗?";
        String e2 = "你想好的动物萌吗？";
        String e3 = "你想好的动物能在水里生活吗?";
        String e4 = "你想好的动物会中暑吗?";
        String e5 = "你想好的动物灵活吗？";
        String e6 = "你想好的动物能在陆地上生活吗？";
        String e7 = "那一定是小鸭子吧