二叉搜索树实现问题
Binary Search Tree implementation problem
我已经构建了这个 BST 并尝试遵循 java 代码约定 我决定修复一些访问修饰符并添加一些 getter 和 setter 但现在我的整个代码都给了我执行过程中出现了很多问题，我不知道为什么。
这是我的节点class。
/**
* A class that implements a binary tree's node. It contains the data inside each node of the tree.
*/
public class Node {
private int data;
private Node left;
private Node right;
/**
* Constructor initializing the data of the node.
*
* @param data The numeric value of each node as an Integer.
*/
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
这是树class。
import java.util.ArrayList;
import java.util.List;
/** Class implementation of a binary tree , containing helper classes and methods. */
public class BinaryTree {
private Node root;
private List<Integer> nodes = new ArrayList<>();
/** Constructor initializing the root node of the tree. */
public BinaryTree() {
root = null;
}
public Node getRoot() {
return root;
}
private Node insertNode(Node node, int dataBeingInserted) {
if (node == null) {
node = new Node(dataBeingInserted);
return node;
}
if (node.getData() > dataBeingInserted) {
insertNode(node.getLeft(), dataBeingInserted);
} else if (node.getData() < dataBeingInserted) {
insertNode(node.getRight(), dataBeingInserted);
}
return node;
}
/**
* Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
* initialized.
*
* @param dataBeingInserted The number to be inserted as an integer.
*/
public void insertNode(int dataBeingInserted) {
root = insertNode(root, dataBeingInserted);
}
private Node searchTree(Node node, int dataBeingSearched) {
if (node == null || node.getData() == dataBeingSearched) {
return node;
}
if (node.getData() > dataBeingSearched) {
return searchTree(node.getLeft(), dataBeingSearched);
}
return searchTree(node.getRight(), dataBeingSearched);
}
/**
* Method that recursively searches for our element through the tree. If the value is present in
* the root node , or there aren't any nodes in the tree , the method returns the root node. If
* the value we're looking for is smaller than the root node's value , we search for our value in
* the left subtree , otherwise we search for it in the right subtree.
*
* @param dataBeingSearched User's value.
* @return Recursive call of the method.
*/
public Node searchTree(int dataBeingSearched) {
return searchTree(root, dataBeingSearched);
}
private String inorderTraversal(Node node) {
if (node == null) {
return "";
}
inorderTraversal(node.getLeft());
nodes.add(node.getData());
inorderTraversal(node.getRight());
return nodes.toString();
}
/**
* An implementation of the In-order traversal. First the left subtree is visited and printed
* accordingly, then we visit and print the root and after that we visit and print the right
* subtree.
*/
public String inorderTraversal() {
return inorderTraversal(root);
}
}
这些是我写的一些测试，只是为了尝试一些东西。
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;
/** Binary tree operations tests. */
class BinaryTreeTests {
/** Testing whether the answer is correct if we search for the root value of the tree. */
@Test
void isSearchWorking() {
BinaryTree tree = new BinaryTree();
tree.insertNode(10);
tree.insertNode(30);
tree.insertNode(35);
tree.insertNode(29);
assertEquals(tree.getRoot(), tree.searchTree(20));
}
/** Testing whether the root changes it's value from null after a single insertion. */
@Test
void isInsertWorking() {
BinaryTree tree = new BinaryTree();
assertNotNull(tree.getRoot());
}
@Test
void inOrderTraversalPrint() {
BinaryTree tree = new BinaryTree();
tree.insertNode(10);
tree.insertNode(30);
tree.insertNode(35);
tree.insertNode(29);
assertEquals("[10, 20, 29, 30, 35]", tree.inorderTraversal());
}
@Test
void inOrderTraversalSameElement() {
BinaryTree tree = new BinaryTree();
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
assertEquals("[1]", tree.inorderTraversal());
}
}
所以在我将节点 class 中的数据、左右变量设置为 public 之前，一切正常，现在它们是私有的，只有最后一次测试通过了一些原因。
isInsertWorking() 给我的预期不是
inOrderTraversalPrint() 只给我 [10] 而不是 [10, 20, 29, 30, 35]
isSearchWorking() 表示预期节点为空。
我目前不知道如何处理这些事情，我认为我的递归可能不正确，但我想不出解决它们的方法。
主要问题出在我已修复的 insertNode() 函数中。 searchTree() 函数中有一个错误，而且我在调用 inorderTraversal() 时清除了列表 nodes，因为可以在两次 inorderTraversal() 调用之间修改树。
import java.util.ArrayList;
import java.util.List;
/**
* A class that implements a binary tree's node. It contains the data inside each node of the tree.
*/
class Node {
private int data;
private Node left;
private Node right;
/**
* Constructor initializing the data of the node.
*
* @param data The numeric value of each node as an Integer.
*/
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
/** Class implementation of a binary tree , containing helper classes and methods. */
class BinaryTree {
private Node root;
private List<Integer> nodes = new ArrayList<>();
/** Constructor initializing the root node of the tree. */
public BinaryTree() {
root = null;
}
public Node getRoot() {
return root;
}
private Node insertNode(Node node, int dataBeingInserted) {
if (node == null)
return new Node(dataBeingInserted);
if (node.getData() == dataBeingInserted)
return root;
if (node.getData() < dataBeingInserted) {
if (node.getRight() != null)
return insertNode(node.getRight(), dataBeingInserted);
else
node.setRight(new Node(dataBeingInserted));
} else if (node.getData() > dataBeingInserted) {
if (node.getLeft() != null)
return insertNode(node.getLeft(), dataBeingInserted);
else
node.setLeft(new Node(dataBeingInserted));
}
return root;
}
/**
* Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
* initialized.
*
* @param dataBeingInserted The number to be inserted as an integer.
*/
public void insertNode(int dataBeingInserted) {
root = insertNode(root, dataBeingInserted);
}
private Node searchTree(Node node, int dataBeingSearched) {
if (node == null || node.getData() == dataBeingSearched) {
return node;
}
if (node.getData() > dataBeingSearched) {
return searchTree(node.getLeft(), dataBeingSearched);
} else {
return searchTree(node.getRight(), dataBeingSearched);
}
}
/**
* Method that recursively searches for our element through the tree. If the value is present in
* the root node , or there aren't any nodes in the tree , the method returns the root node. If
* the value we're looking for is smaller than the root node's value , we search for our value in
* the left subtree , otherwise we search for it in the right subtree.
*
* @param dataBeingSearched User's value.
* @return Recursive call of the method.
*/
public Node searchTree(int dataBeingSearched) {
return searchTree(root, dataBeingSearched);
}
private String inorderTraversal(Node node) {
if (node == null) {
return "";
}
inorderTraversal(node.getLeft());
nodes.add(node.getData());
inorderTraversal(node.getRight());
return nodes.toString();
}
/**
* An implementation of the In-order traversal. First the left subtree is visited and printed
* accordingly, then we visit and print the root and after that we visit and print the right
* subtree.
*/
public String inorderTraversal() {
nodes.clear(); // clear the previous state
return inorderTraversal(root);
}
}
我已经构建了这个 BST 并尝试遵循 java 代码约定 我决定修复一些访问修饰符并添加一些 getter 和 setter 但现在我的整个代码都给了我执行过程中出现了很多问题，我不知道为什么。
这是我的节点class。
/**
* A class that implements a binary tree's node. It contains the data inside each node of the tree.
*/
public class Node {
private int data;
private Node left;
private Node right;
/**
* Constructor initializing the data of the node.
*
* @param data The numeric value of each node as an Integer.
*/
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
这是树class。
import java.util.ArrayList;
import java.util.List;
/** Class implementation of a binary tree , containing helper classes and methods. */
public class BinaryTree {
private Node root;
private List<Integer> nodes = new ArrayList<>();
/** Constructor initializing the root node of the tree. */
public BinaryTree() {
root = null;
}
public Node getRoot() {
return root;
}
private Node insertNode(Node node, int dataBeingInserted) {
if (node == null) {
node = new Node(dataBeingInserted);
return node;
}
if (node.getData() > dataBeingInserted) {
insertNode(node.getLeft(), dataBeingInserted);
} else if (node.getData() < dataBeingInserted) {
insertNode(node.getRight(), dataBeingInserted);
}
return node;
}
/**
* Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
* initialized.
*
* @param dataBeingInserted The number to be inserted as an integer.
*/
public void insertNode(int dataBeingInserted) {
root = insertNode(root, dataBeingInserted);
}
private Node searchTree(Node node, int dataBeingSearched) {
if (node == null || node.getData() == dataBeingSearched) {
return node;
}
if (node.getData() > dataBeingSearched) {
return searchTree(node.getLeft(), dataBeingSearched);
}
return searchTree(node.getRight(), dataBeingSearched);
}
/**
* Method that recursively searches for our element through the tree. If the value is present in
* the root node , or there aren't any nodes in the tree , the method returns the root node. If
* the value we're looking for is smaller than the root node's value , we search for our value in
* the left subtree , otherwise we search for it in the right subtree.
*
* @param dataBeingSearched User's value.
* @return Recursive call of the method.
*/
public Node searchTree(int dataBeingSearched) {
return searchTree(root, dataBeingSearched);
}
private String inorderTraversal(Node node) {
if (node == null) {
return "";
}
inorderTraversal(node.getLeft());
nodes.add(node.getData());
inorderTraversal(node.getRight());
return nodes.toString();
}
/**
* An implementation of the In-order traversal. First the left subtree is visited and printed
* accordingly, then we visit and print the root and after that we visit and print the right
* subtree.
*/
public String inorderTraversal() {
return inorderTraversal(root);
}
}
这些是我写的一些测试，只是为了尝试一些东西。
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;
/** Binary tree operations tests. */
class BinaryTreeTests {
/** Testing whether the answer is correct if we search for the root value of the tree. */
@Test
void isSearchWorking() {
BinaryTree tree = new BinaryTree();
tree.insertNode(10);
tree.insertNode(30);
tree.insertNode(35);
tree.insertNode(29);
assertEquals(tree.getRoot(), tree.searchTree(20));
}
/** Testing whether the root changes it's value from null after a single insertion. */
@Test
void isInsertWorking() {
BinaryTree tree = new BinaryTree();
assertNotNull(tree.getRoot());
}
@Test
void inOrderTraversalPrint() {
BinaryTree tree = new BinaryTree();
tree.insertNode(10);
tree.insertNode(30);
tree.insertNode(35);
tree.insertNode(29);
assertEquals("[10, 20, 29, 30, 35]", tree.inorderTraversal());
}
@Test
void inOrderTraversalSameElement() {
BinaryTree tree = new BinaryTree();
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
tree.insertNode(1);
assertEquals("[1]", tree.inorderTraversal());
}
}
所以在我将节点 class 中的数据、左右变量设置为 public 之前，一切正常，现在它们是私有的，只有最后一次测试通过了一些原因。
isInsertWorking() 给我的预期不是
inOrderTraversalPrint() 只给我 [10] 而不是 [10, 20, 29, 30, 35]
isSearchWorking() 表示预期节点为空。
我目前不知道如何处理这些事情，我认为我的递归可能不正确，但我想不出解决它们的方法。
主要问题出在我已修复的 insertNode() 函数中。 searchTree() 函数中有一个错误，而且我在调用 inorderTraversal() 时清除了列表 nodes，因为可以在两次 inorderTraversal() 调用之间修改树。
import java.util.ArrayList;
import java.util.List;
/**
* A class that implements a binary tree's node. It contains the data inside each node of the tree.
*/
class Node {
private int data;
private Node left;
private Node right;
/**
* Constructor initializing the data of the node.
*
* @param data The numeric value of each node as an Integer.
*/
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
/** Class implementation of a binary tree , containing helper classes and methods. */
class BinaryTree {
private Node root;
private List<Integer> nodes = new ArrayList<>();
/** Constructor initializing the root node of the tree. */
public BinaryTree() {
root = null;
}
public Node getRoot() {
return root;
}
private Node insertNode(Node node, int dataBeingInserted) {
if (node == null)
return new Node(dataBeingInserted);
if (node.getData() == dataBeingInserted)
return root;
if (node.getData() < dataBeingInserted) {
if (node.getRight() != null)
return insertNode(node.getRight(), dataBeingInserted);
else
node.setRight(new Node(dataBeingInserted));
} else if (node.getData() > dataBeingInserted) {
if (node.getLeft() != null)
return insertNode(node.getLeft(), dataBeingInserted);
else
node.setLeft(new Node(dataBeingInserted));
}
return root;
}
/**
* Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
* initialized.
*
* @param dataBeingInserted The number to be inserted as an integer.
*/
public void insertNode(int dataBeingInserted) {
root = insertNode(root, dataBeingInserted);
}
private Node searchTree(Node node, int dataBeingSearched) {
if (node == null || node.getData() == dataBeingSearched) {
return node;
}
if (node.getData() > dataBeingSearched) {
return searchTree(node.getLeft(), dataBeingSearched);
} else {
return searchTree(node.getRight(), dataBeingSearched);
}
}
/**
* Method that recursively searches for our element through the tree. If the value is present in
* the root node , or there aren't any nodes in the tree , the method returns the root node. If
* the value we're looking for is smaller than the root node's value , we search for our value in
* the left subtree , otherwise we search for it in the right subtree.
*
* @param dataBeingSearched User's value.
* @return Recursive call of the method.
*/
public Node searchTree(int dataBeingSearched) {
return searchTree(root, dataBeingSearched);
}
private String inorderTraversal(Node node) {
if (node == null) {
return "";
}
inorderTraversal(node.getLeft());
nodes.add(node.getData());
inorderTraversal(node.getRight());
return nodes.toString();
}
/**
* An implementation of the In-order traversal. First the left subtree is visited and printed
* accordingly, then we visit and print the root and after that we visit and print the right
* subtree.
*/
public String inorderTraversal() {
nodes.clear(); // clear the previous state
return inorderTraversal(root);
}
}