二叉树猜动物游戏如何在认输叶子节点插入用户输入的新动物节点

实现思路 #

当程序遍历到"I give up"认输叶子节点时，按以下流程插入新动物：

1. 引导用户输入正确的动物名称
2. 从父节点的猜测问题中提取本次猜错的旧动物名称
3. 让用户提供一个可区分新旧动物的yes/no判定问题
4. 询问用户新动物对该判定问题的回答是Y还是N
5. 将原认输叶子节点修改为新的判定问题节点，按答案对应关系添加新旧动物的结果节点作为子节点

前置修改 #

首先需要给你的BinaryTree类新增属性修改方法，用于修改节点内容和子节点：

class BinaryTree {
    private String data;
    private BinaryTree left;
    private BinaryTree right;
    // 保留你原有的构造方法
    public BinaryTree(String data) { this.data = data; }
    public BinaryTree(String data, BinaryTree left, BinaryTree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    // 保留你原有的get方法
    public String data() { return data; }
    public BinaryTree left() { return left; }
    public BinaryTree right() { return right; }
    public boolean isEmpty() { return data == null; }
    // 新增以下set方法
    public void setData(String data) { this.data = data; }
    public void setLeft(BinaryTree left) { this.left = left; }
    public void setRight(BinaryTree right) { this.right = right; }
}

main方法逻辑修改 #

调整遍历逻辑，新增父节点记录、认输节点判定和插入逻辑，替换你原有的main方法中遍历部分的代码：

public static void main(String[] args){
    // 保留你原来的questionTree初始化代码，这里省略不重复写
    BinaryTree questionTree = new BinaryTree("Is it a mammal?",
            // 你原来的树结构不变
    );

    boolean done = false;
    Scanner in = new Scanner(System.in);
    // 新增遍历变量，不直接修改根节点引用，方便后续重复开局
    BinaryTree current = questionTree;
    BinaryTree parent = null;

    while (!done){
        BinaryTree left = current.left();
        BinaryTree right = current.right();

        if (left.isEmpty() && right.isEmpty()){
            System.out.println(current.data());
            // 判定是否是认输节点
            if (current.data().contains("I give up")){
                // 吃掉Scanner缓冲区残留的换行符
                in.nextLine();
                // 1. 获取新动物名称
                System.out.print("请输入你想到的动物名称：");
                String newAnimal = in.nextLine().trim();
                // 2. 从父节点提取猜错的旧动物名
                String oldGuessQuestion = parent.data();
                String oldAnimal = oldGuessQuestion.replaceAll("[Ii]s it a |\\?", "").trim();
                // 3. 获取区分新旧动物的问题
                System.out.printf("请输入一个可以区分【%s】和【%s】的yes/no问题：", oldAnimal, newAnimal);
                String newQuestion = in.nextLine().trim();
                // 4. 获取新动物对该问题的答案
                String newAnswer;
                do {
                    System.out.printf("对于问题【%s】，%s的答案是Y还是N？", newQuestion, newAnimal);
                    newAnswer = in.next().toUpperCase();
                } while (!"Y".equals(newAnswer) && !"N".equals(newAnswer));
                // 5. 把当前认输节点改成新的判定节点
                current.setData(newQuestion);
                if ("Y".equals(newAnswer)) {
                    // Y分支对应新动物，N分支对应旧动物
                    current.setLeft(new BinaryTree("It is " + newAnimal + "!"));
                    current.setRight(new BinaryTree("It is " + oldAnimal + "!"));
                } else {
                    // Y分支对应旧动物，N分支对应新动物
                    current.setLeft(new BinaryTree("It is " + oldAnimal + "!"));
                    current.setRight(new BinaryTree("It is " + newAnimal + "!"));
                }
                System.out.println("已记录该动物，下次游玩即可生效~");
            }
            done = true;
        }else{
            String response;
            do{
                System.out.print(current.data() + " (Y/N) ");
                response = in.next().toUpperCase();
            }while (!"Y".equals(response) && !"N".equals(response));
            // 记录父节点和移动方向
            parent = current;
            if ("Y".equals(response)){
                current = left;
            }else{
                current = right;
            }
        }
    }
    in.close();
}

注意事项 #

• 如果需要支持多轮游戏，不要在走到叶子节点后把done设为true，可以增加外层循环，每轮结束后询问用户是否继续，将current重置为根节点questionTree即可
• 如果你的猜测问题格式和示例不一致，调整提取旧动物名的正则规则即可
• 如果动物名称包含空格，使用nextLine()读取可以正常识别，无需额外处理

内容的提问来源于stack exchange，提问作者Cyan Turnip