本文共 4253 字，大约阅读时间需要 14 分钟。

实验二 报告

一、实验内容概述

本次实验的主要内容包括以下几个方面：

二、详细实验内容

1. 实现LinkedBinaryTree

本实验的核心是实现一个基于链表的二叉树数据结构。主要完成以下方法：

• getRight：获取右孩子节点。
• contains：检查树中是否存在指定节点。
• toString：生成树的字符串表示。
• preorder：生成前序遍历结果。
• postorder：生成后序遍历结果。

代码实现如下：

import java.util.*;public class MyLinkedBinaryTree
   
     implements BinaryTree
    
      {    protected BTNode root;    public MyLinkedBinaryTree() {        root = null;    }    public MyLinkedBinaryTree(T element) {        root = new BTNode(element);    }    public MyLinkedBinaryTree(BTNode rootNode) {        root = rootNode;    }    public MyLinkedBinaryTree(T element, MyLinkedBinaryTree
     
       left, MyLinkedBinaryTree
      
        right) {        root = new BTNode(element);        root.setLeft(left.root);        root.setRight(right.root);    }    // ... （其他方法如getLeft、find、size等）}
      
     
    
   

2. 中序先序序列构造二叉树

基于前序和中序序列，使用递归方法构造二叉树。具体实现如下：

public class exp2 {    final static char[] inorder = "HDIBEMJNAFCKGL".toCharArray();    final static char[] preorder = "ABDHIEJMNCFGKL".toCharArray();    public static void main(String[] args) {        MyLinkedBinaryTree root = new MyLinkedBinaryTree(genetree(preorder, inorder));        System.out.println(root);    }    public static BTNode genetree(char[] pre, char[] in) {        HashMap map = geneMap(in);        return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, map);    }    public static HashMap geneMap(char[] charArray) {        HashMap temp = new HashMap();        for (int i = 0; i < charArray.length; i++) {            temp.put(charArray[i], i);        }        return temp;    }    public static BTNode preIn(char[] pre, int preIndex, int preJ, char[] in, int inIndex, int inJ, HashMap map) {        if (preIndex > preJ) return null;        BTNode head = new BTNode(pre[preIndex]);        int index = map.get(pre[preIndex]);        head.left = preIn(pre, preIndex + 1, preIndex + index - inIndex, in, inIndex, index - 1, map);        head.right = preIn(pre, preIndex + index - inIndex + 1, preJ, in, index + 1, inJ, map);        return head;    }}

3. 决策树

完成PP16.6实验，设计一个诊断小动物的二叉树。树的结构如下：

public class BackPainExpert {    private MyLinkedBinaryTree tree;    public BackPainExpert() {        // ... （树的初始化代码）    public void diagnose() {        Scanner scan = new Scanner(System.in);        MyLinkedBinaryTree current = tree;        while (current.size() > 1) {            System.out.println(current.getRootElement());            String answer = scan.nextLine().equalsIgnoreCase("N");            current = current.getLeft();        }        System.out.println(current.getRootElement());    }}

4. 表达式树

完成PP16.8实验，实现表达式树的构造与计算。代码实现如下：

public class ExpressionTree {    private String exp;    private BTNode root;    public void geneTree(String s) {        ArrayList oper = new ArrayList();        for (int i = 0; i < s.length(); i++) {            char c = s.toCharArray()[i];            if (Character.isDigit(c)) {                exp += c + " ";            } else {                oper.add(new BTNode(exp));                exp = "";                oper.add(c + " ");            }        }        // ... （后续代码）    public Integer getResult() {        ArrayList strList = getStringList(toStr());        ArrayList rpn = getRPN(strList);        return calculate(rpn);    }}

5. 二叉搜索树

完成PP17.1实验，实现二叉搜索树的基本操作。代码如下：

public class LinkedBinarySearchTree
   
    > extends MyLinkedBinaryTree
    
      {    public void add(T item) {        if (root == null) {            root = new BSTNode(item);        } else {            ((BSTNode) root).add(item);        }    }
    
   

6. 源码分析

参考教材和相关文档，分析TreeMap的源码。主要分析put和getEntry方法：

public V put(K key, V value) {    TreeMapEntry t = root;    // ... （完整代码）}public V get(Object key) {    Entry p = getEntry(key);    return (p == null ? null : p.value);}

三、总结与展望

本次实验主要完成了多个与二叉树相关的开发任务，包括数据结构实现、算法设计、树的构造与分析等内容。通过本次实验，我对Java高级数据结构的实现有了更深入的理解，也掌握了二叉树在实际应用中的构造与操作方法。未来，我将继续深入学习Java集合框架的源码分析，进一步提升自身的技术能力。