二叉搜索树的 JUNIT 测试
JUNIT test for binary search tree
我实现了二叉搜索树。我在JUNIT测试中的大部分测试都是通过的，包括这两个。我已经实现了 leavesIsCorrectWhenTreeIsPerfect() 和 insertValuesInAscendingOrderIncrementsHeight()。
这两个测试都通过了，但是我不知道它是否根据他们的描述要求正确编写。
//编辑：我添加了一个测试，可能对其中一个需要帮助的测试有帮助。
//TODO：帮助我了解我是否根据测试描述在 insertValuesInAscendingOrderIncrementsHeight() 和 leavesIsCorrectWhenTreeIsPerfect() 中编写了正确的测试代码。
请记住，我没有将所有测试都包含在测试中 class，因为我对树的实现已经完成。
在这里，我将我的树 class 和测试 class 包括在我需要帮助的测试中。
/**
* An Binary Search tree implementation.
* @param <T>
*/
public class Tree <T extends Comparable <T>> implements BSTInterface <T>{
private int size;
private Node root;
public class Node{
private Node Left;
private Node Right;
private T data;
public Node(T data){
this.data = data;
}
public Node getRight(){
return Right;
}
public Node getLeft() {
return Left;
}
public T getData() {
return data;
}
}
public Tree (){
size = 0;
root = null;
}
/**
* Test for presence of a value.
* @param elem
* @return true/false
*/
@Override
public boolean search(T elem) {
if(root == null ||elem == null){
return false;
}
Node node = root;
while(true){
if(node.data.compareTo(elem) > 0){
if(node.Right == null){
return false;
} else{
node = node.Right;
}
} else if(node.data.compareTo(elem) == 0){
break;
} else{
if(node.Left== null){
return false;
}
else{
node = node.Left;
}
}
}
return true;
}
/**
* Add value to tree; duplicates are not allowed.
* Return true if the element is not already present (and is thus inserted),
* false otherwise.
*
* @param elem
* @return true/false
*/
@Override
public boolean insert(T elem) {
if (elem == null){
return false;
}
if (root == null){
root = new Node(elem);
size++;
return true;
}
Node node = root;
while (true){
if (node.data.compareTo(elem) > 0) {
if (node.Right == null){
node.Right = new Node(elem);
size++;
break;
} else {
node = node.Right;
}
} else if (node.data.compareTo(elem) == 0) {
return false;
} else {
if (node.Left == null){
node.Left = new Node(elem);
size++;
break;
} else {
node = node.Left;
}
}
}
return true;
}
/**
* the number of elements in the tree
* @return size.
*/
@Override
public int size() {
return size;
}
/**
* The height of the tree.
* The empty tree and the tree with only the root node both have height 0.
* @return the height of the tree.
*/
@Override
public int height() {
return countHeight(root);
}
/**
* Helper method for height
*/
private int countHeight(Node node){
if(node == null) {
return 0;
}
if (node.Left == null && node.Right == null) {
return 0;
}
return 1 + Math.max(countHeight(node.getLeft()), countHeight(node.getRight()));
}
/**
* The number of leaves in the tree.
* @return the amount of leaves the tree has.
*/
@Override
public int leaves() {
return countLeaves(root);
}
/**
* Helper method for leaves
*/
private int countLeaves(Node node) {
if (node == null) {
return 0;
}
if (node.Left == null && node.Right == null) {
return 1;
}
return countLeaves(node.Left) + countLeaves(node.Right);
}
/**
* A string describing the tree
* @return
*/
public String toString(){
String str = "[" + helpToString(root);
if (str.length() > 1) {
str = str.substring(0, str.length() - 2);
} return str + "]";
}
/**
* Helper method for toString
*/
private String helpToString(Node node) {
String str = "";
if (node != null) {
str += helpToString(node.Right);
str += node.data + ", ";
str += helpToString(node.Left);
}
return str;
}
}
import org.junit.Test;
import org.junit.Before;
import org.junit.Rule;
import org.junit.rules.Timeout;
import static org.junit.Assert.*;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.CoreMatchers.*;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* Test class for a tree.
*/
public class TreeTest{
@Rule public Timeout globalTimeout = Timeout.seconds(5);
Tree<Integer> tree;
int[] elementsInTree;
int[] elementsNotInTree;
@Before
public void setUp() {
/**
* This tree should look like this:
*
* 8
* / \
* 3 10
* / \ \
* 1 6 14
* / \ /
* 4 7 13
*/
tree = new Tree<>();
elementsInTree = new int[] {8, 10, 14, 13, 3, 1, 6, 4, 7};
for (int elem : elementsInTree) {
tree.insert(elem);
}
elementsNotInTree = new int[] {34, -3, -10, 12, 74, 5};
}
@Test
public void heightIsLogOfNumLeavesTreeIsPerfect() {
// For a perfect tree, tree.height() == log2(tree.leaves()
// Arrange
Tree<Integer> tree = new Tree<>();
int[] elements = new int[] {8, 3, 10, 1, 6, 9, 14};
int numLeaves = 4;
int logNumLeaves = (int) Math.round(Math.log(numLeaves) / Math.log(2));
for (int elem : elements) {
tree.insert(elem);
}
// Act
int height = tree.height();
// Assert
assertThat(height, equalTo(logNumLeaves));
}
@Test
public void leavesIsCorrectWhenTreeIsPerfect() { //TEST
// A perfect tree has all leaves at the same depth, and all internal nodes
// (i.e. non-leaves) have two children
//
// This test should assert that a perfect tree with 2*n-1 nodes total,
// has exactly n leaves (i.e. that Tree.leaves() returns n).
//
// An example is the perfect three-node tree from the test above:
//
// (1338)
// / \
// (1337) (1396)
// You have to construct your own tree here, with n >= 4
Tree <Integer> tree = new Tree<>();
int n = 4;
for(int i = 0; i>=n; i++) {
tree.insert(i);
int numLeaves = 2*n-1;
int leaves = tree.leaves();
assertThat(leaves,equalTo(numLeaves));
}
}
// Tests for insert/height
@Test
public void insertValuesInAscendingOrderIncrementsHeight() { //TEST
// When inserting elements in ascending order, each element is inserted
// to the right of the deepest node, so the height should increment by
// 1 for each element inserted.
Tree <Integer> tree = new Tree<>();
int val = 100;
for(int i = 0; i < val; i++){
tree.insert(i);
}
int treeHeight = tree.height();
treeHeight++;
assertThat(tree.size(),equalTo(treeHeight));
}
}
for(int i = 0; i>=n; i++) {
tree.insert(i);
您的 for 循环条件始终为假。
在说明中使用“n”来描述具有 n 个叶子的树是很尴尬的，因为“n”传统上用于描述节点数。但是想象一棵底部有 4 个节点的树，然后是前一层的一半，然后是第一层的一半，你有一个有 1+2+4 个节点的树，或者总共 7 个节点，这与公式一致2*n-1 (2*4-1=7).
@Test
public void leavesIsCorrectWhenTreeIsPerfect() {
int n=4;
int[] balanced=new int[] {4,2,6,1,3,5,7};
for (int i=0; i<balanced.length; i++) {
tree.insert(balanced[i]);
}
int leaves = tree.leaves();
assertThat(balanced.length,equalTo(2*n-1));
assertThat(leaves,equalTo(n));
}
我实现了二叉搜索树。我在JUNIT测试中的大部分测试都是通过的，包括这两个。我已经实现了 leavesIsCorrectWhenTreeIsPerfect() 和 insertValuesInAscendingOrderIncrementsHeight()。
这两个测试都通过了，但是我不知道它是否根据他们的描述要求正确编写。
//编辑：我添加了一个测试，可能对其中一个需要帮助的测试有帮助。
//TODO：帮助我了解我是否根据测试描述在 insertValuesInAscendingOrderIncrementsHeight() 和 leavesIsCorrectWhenTreeIsPerfect() 中编写了正确的测试代码。
请记住，我没有将所有测试都包含在测试中 class，因为我对树的实现已经完成。
在这里，我将我的树 class 和测试 class 包括在我需要帮助的测试中。
/**
* An Binary Search tree implementation.
* @param <T>
*/
public class Tree <T extends Comparable <T>> implements BSTInterface <T>{
private int size;
private Node root;
public class Node{
private Node Left;
private Node Right;
private T data;
public Node(T data){
this.data = data;
}
public Node getRight(){
return Right;
}
public Node getLeft() {
return Left;
}
public T getData() {
return data;
}
}
public Tree (){
size = 0;
root = null;
}
/**
* Test for presence of a value.
* @param elem
* @return true/false
*/
@Override
public boolean search(T elem) {
if(root == null ||elem == null){
return false;
}
Node node = root;
while(true){
if(node.data.compareTo(elem) > 0){
if(node.Right == null){
return false;
} else{
node = node.Right;
}
} else if(node.data.compareTo(elem) == 0){
break;
} else{
if(node.Left== null){
return false;
}
else{
node = node.Left;
}
}
}
return true;
}
/**
* Add value to tree; duplicates are not allowed.
* Return true if the element is not already present (and is thus inserted),
* false otherwise.
*
* @param elem
* @return true/false
*/
@Override
public boolean insert(T elem) {
if (elem == null){
return false;
}
if (root == null){
root = new Node(elem);
size++;
return true;
}
Node node = root;
while (true){
if (node.data.compareTo(elem) > 0) {
if (node.Right == null){
node.Right = new Node(elem);
size++;
break;
} else {
node = node.Right;
}
} else if (node.data.compareTo(elem) == 0) {
return false;
} else {
if (node.Left == null){
node.Left = new Node(elem);
size++;
break;
} else {
node = node.Left;
}
}
}
return true;
}
/**
* the number of elements in the tree
* @return size.
*/
@Override
public int size() {
return size;
}
/**
* The height of the tree.
* The empty tree and the tree with only the root node both have height 0.
* @return the height of the tree.
*/
@Override
public int height() {
return countHeight(root);
}
/**
* Helper method for height
*/
private int countHeight(Node node){
if(node == null) {
return 0;
}
if (node.Left == null && node.Right == null) {
return 0;
}
return 1 + Math.max(countHeight(node.getLeft()), countHeight(node.getRight()));
}
/**
* The number of leaves in the tree.
* @return the amount of leaves the tree has.
*/
@Override
public int leaves() {
return countLeaves(root);
}
/**
* Helper method for leaves
*/
private int countLeaves(Node node) {
if (node == null) {
return 0;
}
if (node.Left == null && node.Right == null) {
return 1;
}
return countLeaves(node.Left) + countLeaves(node.Right);
}
/**
* A string describing the tree
* @return
*/
public String toString(){
String str = "[" + helpToString(root);
if (str.length() > 1) {
str = str.substring(0, str.length() - 2);
} return str + "]";
}
/**
* Helper method for toString
*/
private String helpToString(Node node) {
String str = "";
if (node != null) {
str += helpToString(node.Right);
str += node.data + ", ";
str += helpToString(node.Left);
}
return str;
}
}
import org.junit.Test;
import org.junit.Before;
import org.junit.Rule;
import org.junit.rules.Timeout;
import static org.junit.Assert.*;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.CoreMatchers.*;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* Test class for a tree.
*/
public class TreeTest{
@Rule public Timeout globalTimeout = Timeout.seconds(5);
Tree<Integer> tree;
int[] elementsInTree;
int[] elementsNotInTree;
@Before
public void setUp() {
/**
* This tree should look like this:
*
* 8
* / \
* 3 10
* / \ \
* 1 6 14
* / \ /
* 4 7 13
*/
tree = new Tree<>();
elementsInTree = new int[] {8, 10, 14, 13, 3, 1, 6, 4, 7};
for (int elem : elementsInTree) {
tree.insert(elem);
}
elementsNotInTree = new int[] {34, -3, -10, 12, 74, 5};
}
@Test
public void heightIsLogOfNumLeavesTreeIsPerfect() {
// For a perfect tree, tree.height() == log2(tree.leaves()
// Arrange
Tree<Integer> tree = new Tree<>();
int[] elements = new int[] {8, 3, 10, 1, 6, 9, 14};
int numLeaves = 4;
int logNumLeaves = (int) Math.round(Math.log(numLeaves) / Math.log(2));
for (int elem : elements) {
tree.insert(elem);
}
// Act
int height = tree.height();
// Assert
assertThat(height, equalTo(logNumLeaves));
}
@Test
public void leavesIsCorrectWhenTreeIsPerfect() { //TEST
// A perfect tree has all leaves at the same depth, and all internal nodes
// (i.e. non-leaves) have two children
//
// This test should assert that a perfect tree with 2*n-1 nodes total,
// has exactly n leaves (i.e. that Tree.leaves() returns n).
//
// An example is the perfect three-node tree from the test above:
//
// (1338)
// / \
// (1337) (1396)
// You have to construct your own tree here, with n >= 4
Tree <Integer> tree = new Tree<>();
int n = 4;
for(int i = 0; i>=n; i++) {
tree.insert(i);
int numLeaves = 2*n-1;
int leaves = tree.leaves();
assertThat(leaves,equalTo(numLeaves));
}
}
// Tests for insert/height
@Test
public void insertValuesInAscendingOrderIncrementsHeight() { //TEST
// When inserting elements in ascending order, each element is inserted
// to the right of the deepest node, so the height should increment by
// 1 for each element inserted.
Tree <Integer> tree = new Tree<>();
int val = 100;
for(int i = 0; i < val; i++){
tree.insert(i);
}
int treeHeight = tree.height();
treeHeight++;
assertThat(tree.size(),equalTo(treeHeight));
}
}
for(int i = 0; i>=n; i++) {
tree.insert(i);
您的 for 循环条件始终为假。
在说明中使用“n”来描述具有 n 个叶子的树是很尴尬的，因为“n”传统上用于描述节点数。但是想象一棵底部有 4 个节点的树，然后是前一层的一半，然后是第一层的一半，你有一个有 1+2+4 个节点的树，或者总共 7 个节点，这与公式一致2*n-1 (2*4-1=7).
@Test
public void leavesIsCorrectWhenTreeIsPerfect() {
int n=4;
int[] balanced=new int[] {4,2,6,1,3,5,7};
for (int i=0; i<balanced.length; i++) {
tree.insert(balanced[i]);
}
int leaves = tree.leaves();
assertThat(balanced.length,equalTo(2*n-1));
assertThat(leaves,equalTo(n));
}