java - 给定树，如何实现 BFS，但未命名节点

Question

我有这个问题，我们得到了一个创建和填充树的 java 代码。

自从我使用 java 数据结构以来已经有一段时间了，所以我搜索了几个实现，现在我了解了如何实现 BFS。但我不完全理解教授提供的代码，而且她没有回复她的电子邮件。

在https://tutorialedge.net/artificial-intelligence/breadth-first-search-java/上的教程中， 每个节点都有一个名称，（station1，station2，...）但是在 btNode 中的讲师提供的代码中类，在插入方法中，我看到创建了新的节点而没有给它们命名。有没有办法像教程一样引用所述节点？或者我需要如何修改源代码来添加名称？我想我可以像教程中那样对其进行硬编码，但我想看看是否还有其他方法。谢谢你，祝你有美好的一天！请检查下面提供的代码

二叉树类

package cs351_uninformed_search;

public class binaryTree {

    protected btNode root;
    btNode startNode;
    btNode goalNode;

    /* Constructor */
    public binaryTree() {
        root = null;
    }

    /* Function to check if tree is empty */
    public boolean isEmpty() {
        return root == null;
    }

    /* Functions to insert data */
    public void insert(int data) {
        root = insert(root, data);
    }

    /* Function to insert data recursively */
    private btNode insert(btNode node, int data) {
        if (node == null)
            node = new btNode(data);
        else {
            if (data <= node.getData())
                node.left = insert(node.left, data);
            else
                node.right = insert(node.right, data);
        }
        return node;
    }

}

btNode 类

package cs351_uninformed_search;

public class btNode {

    btNode left, right;
    int data;
    boolean visted;

    /* Constructor */
    public btNode() {
        left = null;
        right = null;
        data = 0;
    }

    /* Constructor */
    public btNode(int n) {
        left = null;
        right = null;
        data = n;
    }

    /* Function to get left node */
    public btNode getLeft() {
        return left;
    }

    /* Function to set left node */
    public void setLeft(btNode n) {
        left = n;
    }

    /* Function to get right node */
    public btNode getRight() {
        return right;
    }

    /* Function to set right node */
    public void setRight(btNode n) {
        right = n;
    }

    /* Function to get data from node */
    public int getData() {
        return data;
    }

    /* Function to set data to node */
    public void setData(int d) {
        data = d;
    }

    public void setvisted() {
        visted = false;
    }

    public boolean getvisted() {
        return visted;
    }

}

测试班

package cs351_uninformed_search;
import java.util.Random;

public class test {

    public static void main(String[] args) {

        /* Creating object of BST */
        binaryTree bst = new binaryTree();
        System.out.println("Binary Search Tree Test\n");
        int flag = 0;

        Random r = new Random(100);

        while (flag < 20) {
            bst.insert(r.nextInt(500));
            flag++;
        }

        BTreePrinter.printNode(bst.root);

        System.out.println("Hello from CS351: This is the first programming assignment!");
        System.out.println("You will practice the uninformed search algorithm");
        System.out.println("The goal of you is to find node with value 288 and"
                + "print the path from root to it");
        System.out.println("Warm up your JAVA ^^");
        System.out.println("Task 1: Please use the BFS to find the path."
                + "You should implement the method in binaryTree.java class,"
                + "and test the method in test.java class");

        // test your first method here

        System.out.println("Task 2: Please use the DFS to find the path."
                + "You should implement the method in binaryTree.java class,"
                + "and test the method in test.java class");
    }

}

BTreePrinter 类

package cs351_uninformed_search;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BTreePrinter {
    public static <T extends Comparable<?>> void printNode(btNode root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static <T extends Comparable<?>> void printNodeInternal(List<btNode> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<btNode> newNodes = new ArrayList<btNode>();
        for (btNode node : nodes) {
            if (node != null) {
                System.out.print(node.data);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }
            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");
        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
                BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (nodes.get(j).left != null)
                    System.out.print("/");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                    System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }
            System.out.println("");
        }
        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < count; i++)
            System.out.print(" ");
    }

    private static <T extends Comparable<?>> int maxLevel(btNode node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }

}

我想打印包含值 288 的目标节点并打印它的路径。我想我知道如何实现 BFS 以使我到达那里，我只需要知道如何引用链接的教程之类的节点？

谢谢你，祝你有美好的一天！！！

标签： javabreadth-first-search