У меня есть эта проблема, нам дали код 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, чтобы попасть туда, мне просто нужно знать, как обращаться к узлам, таким как учебное пособие, связанное?
спасибо и хорошего дня !!!