一、实验环境

IDEA

二、设计需求分析

【问题描述】

设计一个与二叉树基本操作相关的演示操作，

【基本要求】

1. 创建二叉树，按照用户需要的二叉树构建二叉树；

2. 将创建的二叉树，以树形形式输出；

3. 分别以先序、中序、后序、层序四种遍历访问二叉树；

4. 输出二叉树的叶子结点及叶子结点的个数；

5. 输出二叉树的高度；

三、实际设计思路

实作创建字母二叉树和数字二叉树两种二叉树，不同型别的二叉树实作的功能各有不同，充分运用类和物件、继承、多型、抽象类、界面等思想

四、物件与功能剖析

想要实作这样一个既可以构造字母二叉树也可以构造数字二叉树，并且每种型别的二叉树可以实作不同的功能，通过选择可以显示不同的选单的二叉树操作程序，首先需要分析大体方面，这里打算分成3大方面

【树结构相关】（BinaryTree包）

二叉树节点类（TreeNode）； 二叉树类（Tree）；

字母二叉树类（LetterTree）； 数字二叉树类（NumTree）；

（注：二叉树类包含着两种型别的二叉树共同需要实作的方法，后者继承前者）

【功能相关】（Function包，内包含Heap包）

退出类（Exit）； 创建二叉树类（ConstructTree）；

打印二叉树类（PrintTree）； 二叉树高度类（GetHeight）；

叶子结点个数类（GetLeafSize）； 叶子结点打印类（LeafNode）；

前序遍历类（PreorderTraversal）； 中序遍历类（InorderTraversal）；

后序遍历类（PostorderTraversal）； 层序遍历类（LevelOrderTraversal）；

Heap包：

建大堆（CreateBigHeap）； TopK（堆）类（TopK）；

（注：里面绝大多数功能需要用到构造的二叉树的根节点，因此将各个类通过界面IFunction联系起来，重写该界面中的抽象方法，呼叫功能时就会发生向上转型，实作多型）

【主函式相关】（Main类）

实作二叉树型别的选择，通过输入字符串，将其变成阵列然后进行构造二叉树，通过一个回圈选择各个功能，总而言之，Main类将之前的类巧妙的联系在了一起，

五、代码实作及算法思路分析

BinaryTree包

【二叉树节点类（TreeNode）】

为了使该节点可以接收字母型别的资料，也可以接收数字型别的资料，因此加了泛型，在程序运行的时候T就会被擦除成Object型别，该型别是所有类的父类

代码如下：

package BinaryTree;

public class TreeNode<T> {
    public T val;
    public TreeNode<T> left; //左孩子
    public TreeNode<T> right; //右孩子
    public TreeNode (T x) {   //一个自变量的构造方法
        this.val=x;
    }
}

【二叉树类（Tree）】

Tree类被NumTree类和LetterTree类继承，是一个抽象类，该类不可以被实体化，其存在的方法就是被继承

代码如下：

package BinaryTree;
import Function.IFunction;

public abstract class Tree {
    protected IFunction[] iFunctions;//该阵列可以接受不同型别的二叉树的不同功能
    public abstract void menu();//需要被重写达到多型，从而拿到不同的选单
    //choice 表示iFunction 阵列的下标，其值不同，实作的功能也不会相同
    public void getFunction(int choice,TreeNode root){
        this.iFunctions[choice].work(root);
    }
    public abstract int func(); //功能的选择
}

【字母二叉树类（LetterTree）】

代码如下：

package BinaryTree;
import Function.*;
import java.util.Scanner;

public class LetterTree extends Tree{
    public LetterTree() {
        //初始化父类的iFunction的阵列
        iFunctions = new IFunction[] {
                new Exit(),               //退出
                new PreorderTraversal(),  //前序遍历
                new InorderTraversal(),   //中序遍历
                new PostorderTraversal(), //后序遍历
                new LevelOrderTraversal(),//层序遍历
                new LeafNode(),           //叶子节点打印
                new GetLeafSize(),        //叶子结点个数
                new GetHeight(),          //二叉树高度
                new PrintTree()           //打印二叉树
        };
    }
    //重写父类的抽象方法menu
    @Override
    public void menu() {
        System.out.println("============== 字母二叉树 ================");
        System.out.println("====== 0.退出        1.前序遍历     =======");
        System.out.println("====== 2.中序遍历    3.后序遍历      =======");
        System.out.println("====== 4.层序遍历    5.叶子结点打印  =======");
        System.out.println("====== 6.叶子结点个数 7.二叉树高度   =======");
        System.out.println("======          8.打印二叉树        =======");
        System.out.println("请选择你想要进行的操作：");
    }
    //重写父类的抽象方法func，实作功能的选择
    @Override
    public int func() {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int choice = scanner.nextInt();
            if(choice >= 0 && choice <= 8) {
                return choice;
            }else {
                System.out.println("选择错误，请重新进行选择！");
            }
        }
    }
}

【数字二叉树类（NumTree）】

代码如下：

package BinaryTree;
import Function.*;
import Function.Heap.CreateBigHeap;
import Function.Heap.TopK;
import java.util.Scanner;

public class NumTree extends Tree{
    public NumTree(){
        //初始化父类的iFunction的阵列
        iFunctions = new IFunction[]{
                new Exit(),              //退出
                new GetHeight(),         //二叉树高度
                new LeafNode(),          //叶子结点打印
                new GetLeafSize(),       //叶子节点个数
                new PrintTree(),          //二叉树的打印
                new TopK(),              //值最大的K个数
                new CreateBigHeap()      //创建大根堆
        };
    }
    //重写父类的抽象方法menu
    @Override
    public void menu() {
        System.out.println("=============== 数字二叉树 =============");
        System.out.println("====== 0.退出         1.二叉树高度  =====");
        System.out.println("====== 2.叶子结点打印  3.叶子结点个数=====");
        System.out.println("====== 4.二叉树打印    5.TopK(堆)   =====");
        System.out.println("=======        6.  建大堆          =====");
        System.out.println("请选择你想要进行的操作：");
    }
    //重写父类的抽象方法func，实作功能的选择
    @Override
    public int func() {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int choice = scanner.nextInt();
            if(choice >= 0 && choice <= 6) {
                return choice;
            }else {
                System.out.println("选择错误，请重新进行选择！");
            }
        }
    }
}

Function包

【退出类（Exit）】

代码如下：

package Function;
import BinaryTree.TreeNode;

public class Exit<T> implements IFunction<T>{
    @Override
    public void work(TreeNode<T> root) {
        System.out.println("成功退出！");
        System.exit(0);
    }
}

【创建二叉树类（ConstructTree）】

需要呼叫类内的方法constructTree(T[] numbs)，输入的参量为一个阵列，该阵列可能是字符阵列也可能是数字字符，但是原理都是一样的，按照层序遍历的方法来将二叉树变成一个二叉树，若某节点的子节点为空，那么就在对应的地方填null，

具体思想：用一个队列nodeQueue来存盘该层的所有节点，然后用父节点的数量的两倍来遍历输入的阵列（从上一层结束的地方开始），并从队列中取出（位于上一层的）对应的父节点（此时已从队列中删去，因为用的方法为poll()而不是peek()），对于每一个值，创建相应的子节点链接到父节点，并加入到队列中，依次不断回圈，直到遍历完整个阵列，

代码如下：

package Function;
import BinaryTree.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

public class ConstructTree<T> {
    public TreeNode<T> constructTree(T[] numbs){
        if (numbs.length == 0) return new TreeNode<T>(null);
        Deque<TreeNode<T>> nodeQueue = new LinkedList<>();
        // 创建一个根节点
        TreeNode<T> root = new TreeNode<T>(numbs[0]);
        nodeQueue.offer(root);
        TreeNode<T> cur;
        // 记录当前行节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2）
        int lineNodeNum = 2;
        // 记录当前行中数字在阵列中的开始位置
        int startIndex = 1;
        // 记录阵列中剩余的元素的数量
        int restLength = numbs.length - 1;
        while(restLength > 0) {
            // 只有最后一行可以不满，其余行必须是满的
            // 若输入的阵列的数量是错误的，直接跳出程序
            for (int i = startIndex; i < startIndex + lineNodeNum; i = i + 2) {
                // 说明已经将numbs中的数字用完，此时应停止遍历，并可以直接回传root
                if (i == numbs.length) return root;
                cur = nodeQueue.poll();
                if (numbs[i] != null) {
                    assert cur != null;
                    cur.left = new TreeNode<T>(numbs[i]);
                    nodeQueue.offer(cur.left);
                }
                // 同上，说明已经将numbs中的数字用完，此时应停止遍历，并可以直接回传root
                if (i + 1 == numbs.length) return root;
                if (numbs[i + 1] != null) {
                    assert cur != null;
                    cur.right = new TreeNode<T>(numbs[i + 1]);
                    nodeQueue.offer(cur.right);
                }
            }
            startIndex += lineNodeNum;
            restLength -= lineNodeNum;
            lineNodeNum = nodeQueue.size() * 2;
        }
        return root;
    }
}

【打印二叉树类（PrintTree）】

具体思想：用一个二维的字符串阵列来储存每个位置应该打印什么样的输出，

首先，先确定树的形状，设定在最后一行的每个数字之间的间隔为3个空格，而在之上的每一层的间隔，越往上，间隔是越大的，而且是一个简单的线性增加的关系，

为绘制出这样的形状，我们需要获得树的层数，根据树的层数，确定二维阵列的大小，即高度和宽度，之后，用先序遍历的方式，遍历树的每个节点，并进行相对应的写入操作，

代码如下：

package Function;
import BinaryTree.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

public class ConstructTree<T> {
    public TreeNode<T> constructTree(T[] numbs){
        if (numbs.length == 0) return new TreeNode<T>(null);
        Deque<TreeNode<T>> nodeQueue = new LinkedList<>();
        // 创建一个根节点
        TreeNode<T> root = new TreeNode<T>(numbs[0]);
        nodeQueue.offer(root);
        TreeNode<T> cur;
        // 记录当前行节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2）
        int lineNodeNum = 2;
        // 记录当前行中数字在阵列中的开始位置
        int startIndex = 1;
        // 记录阵列中剩余的元素的数量
        int restLength = numbs.length - 1;
        while(restLength > 0) {
            // 只有最后一行可以不满，其余行必须是满的
            // 若输入的阵列的数量是错误的，直接跳出程序
            for (int i = startIndex; i < startIndex + lineNodeNum; i = i + 2) {
                // 说明已经将numbs中的数字用完，此时应停止遍历，并可以直接回传root
                if (i == numbs.length) return root;
                cur = nodeQueue.poll();
                if (numbs[i] != null) {
                    assert cur != null;
                    cur.left = new TreeNode<T>(numbs[i]);
                    nodeQueue.offer(cur.left);
                }
                // 同上，说明已经将numbs中的数字用完，此时应停止遍历，并可以直接回传root
                if (i + 1 == numbs.length) return root;
                if (numbs[i + 1] != null) {
                    assert cur != null;
                    cur.right = new TreeNode<T>(numbs[i + 1]);
                    nodeQueue.offer(cur.right);
                }
            }
            startIndex += lineNodeNum;
            restLength -= lineNodeNum;
            lineNodeNum = nodeQueue.size() * 2;
        }
        return root;
    }
}

【二叉树高度类（GetHeight）】

用递回的方法求二叉树的高度

思想：一棵树的高度为左子树和右子树中较高的高度加一，当节点为空，则高度为0

时间复杂度：O(N)

代码如下：

package Function;
import BinaryTree.TreeNode;

public class GetHeight<T> implements IFunction<T>{
    public int getHeight(TreeNode<T> root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }
    @Override
    public void work(TreeNode<T> root) {
        System.out.println("二叉树高度：" + getHeight(root));
    }
}

【叶子点个数类（GetLeafSize）】

用递回的方法求叶子结点个数

思想：一棵树的叶子节点的个数是根节点的左子树的叶子节点的个数和右子树的叶子节点的个数之和(在这里采取的是前序遍历的方法进行叶子结点的寻找，因此遍历的图和前序遍历的差不多，只是在那个基础上顺便判断了一下是否为叶子结点而已,如果是count加一)

时间复杂度：O(N)

代码如下：

package Function;
import BinaryTree.TreeNode;

public class GetLeafSize<T> implements IFunction<T>{
    @Override
    public void work(TreeNode<T> root) {
        GetSize<T> get = new GetSize<>();
        int count = get.size(root);
        System.out.println("叶子结点个数：" + count);
    }
}
class GetSize<T> {
    //具体进行计算的方法
    public static int count;//计算叶子节点的变量
    public int size(TreeNode<T> root) {
        if (root == null) return 0;
        //叶子节点的条件就是左右节点都为空
        if (root.left == null && root.right == null) {
            count++;
        }
        size(root.left);
        size(root.right);
        return count;
    }
}

【叶子结点打印类（LeafNode）】

用递回的方法，用一顺序结构list来存盘结果

思想：若节点为空就直接回传，若不为空就判断左右孩子是否都为空，成立说明是叶子节点，将其值放入list中；根节点不为空，就依次遍历左子树和右子树的所有节点进