用 java语言以测试驱动开发实现二叉树的构造及操作
时间: 2024-05-04 12:15:25 浏览: 39
下面是使用 Java 语言实现二叉树的构造及操作的代码,采用测试驱动开发的方式进行开发。
1. 定义二叉树节点类
```
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
```
2. 实现二叉树的插入操作
```
public class BinaryTree {
private TreeNode root;
public BinaryTree() {
this.root = null;
}
public void insert(int val) {
TreeNode newNode = new TreeNode(val);
if (root == null) {
root = newNode;
} else {
TreeNode current = root;
TreeNode parent;
while (true) {
parent = current;
if (val < current.val) {
current = current.left;
if (current == null) {
parent.left = newNode;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
}
}
```
3. 实现二叉树的查找操作
```
public class BinaryTree {
// ... 构造函数和插入操作
public TreeNode find(int val) {
TreeNode current = root;
while (current != null && current.val != val) {
if (val < current.val) {
current = current.left;
} else {
current = current.right;
}
}
return current;
}
}
```
4. 使用 JUnit 进行测试
```
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
public class BinaryTreeTest {
private BinaryTree binaryTree;
@BeforeEach
void setUp() {
binaryTree = new BinaryTree();
}
@Test
void testInsert() {
binaryTree.insert(5);
binaryTree.insert(3);
binaryTree.insert(7);
binaryTree.insert(1);
binaryTree.insert(4);
binaryTree.insert(6);
binaryTree.insert(8);
Assertions.assertEquals(5, binaryTree.find(5).val);
Assertions.assertEquals(3, binaryTree.find(3).val);
Assertions.assertEquals(7, binaryTree.find(7).val);
Assertions.assertEquals(1, binaryTree.find(1).val);
Assertions.assertEquals(4, binaryTree.find(4).val);
Assertions.assertEquals(6, binaryTree.find(6).val);
Assertions.assertEquals(8, binaryTree.find(8).val);
}
@Test
void testFind() {
binaryTree.insert(5);
binaryTree.insert(3);
binaryTree.insert(7);
Assertions.assertNull(binaryTree.find(1));
Assertions.assertEquals(5, binaryTree.find(5).val);
Assertions.assertEquals(3, binaryTree.find(3).val);
Assertions.assertEquals(7, binaryTree.find(7).val);
}
}
```