挑战实例：Java实现复杂算法并进行测试

原创青旅半醒 2024-11-28 05:03 30阅读 0赞

以下是一个使用Java实现二叉查找树（Binary Search Tree，BST）并且进行单元测试的例子。

1. 首先定义二叉查找树的节点类：

```java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

TreeNode(int val) {
        this.val = val;
    }
}
```

2. 然后实现二叉查找树的插入和搜索方法：

```java
class BST {
    TreeNode root;

// 插入方法
    void insert(int val) {
        root = insertRec(root, val);
    }

// 递归插入方法
    private TreeNode insertRec(TreeNode node, int val) {
        if (node == null || val < node.val) {
            node.left = insertRec(node.left, val);
        } else if (val > node.val && node.right != null) {
            node.right = insertRec(node.right, val);
        } else {
            return node;
        }
    }

// 搜索方法
    boolean search(int val) {
        return searchRec(root, val);
    }

// 递归搜索方法
    private boolean searchRec(TreeNode node, int val) {
        if (node == null || node.val == val) {
            return true;
        } else if (val < node.val && node.left != null) {
            return searchRec(node.left, val);
        } else if (val > node.val && node.right != null) {
            return searchRec(node.right, val);
        }
        return false;
    }
}
```

3. 最后编写单元测试来验证上述实现的正确性：

```java
import org.junit.jupiter.api.Test;

class BSTTest {
    BST bst = new BST();

@Test
    void testInsert() {
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);

// 测试插入后是否能通过搜索找到节点
        assert bst.search(3) : "Failed to find node inserted at 3";
        assert bst.search(5) : "Failed to find node inserted at 5";
        assert !bst.search(2) : "Found incorrect node for search value 2";
    }

@Test
    void testSearch() {
        // 测试插入节点后搜索返回正确结果
        bst.insert(1);
        bst.insert(4);

assert bst.search(1) : "Failed to find node inserted at 1";
        assert bst.search(4) : "Failed to find node inserted at 4";
        assert !bst.search(2) : "Found incorrect node for search value 2";
    }
}
```

以上就是使用Java实现二叉查找树并进行单元测试的一个完整示例。