JAVA用二叉树查询数组中的数
时间: 2024-04-30 16:18:06 浏览: 16
可以使用二叉搜索树(BST)来查询数组中的数。BST 中的每个节点都有两个子节点,左侧子节点的值小于当前节点,右侧子节点的值大于当前节点。对于一个给定的数组,我们可以将数组的每个元素插入到 BST 中,然后使用 BST 进行查询。
以下是一个使用 Java 实现的二叉搜索树:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class BST {
TreeNode root;
public void insert(int val) {
root = insert(root, val);
}
private TreeNode insert(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else if (val > node.val) {
node.right = insert(node.right, val);
}
return node;
}
public boolean search(int val) {
return search(root, val);
}
private boolean search(TreeNode node, int val) {
if (node == null) {
return false;
}
if (val == node.val) {
return true;
} else if (val < node.val) {
return search(node.left, val);
} else {
return search(node.right, val);
}
}
}
public class Main {
public static void main(String[] args) {
int[] arr = {4, 2, 1, 3, 6, 5, 7};
BST bst = new BST();
for (int num : arr) {
bst.insert(num);
}
System.out.println(bst.search(5)); // true
System.out.println(bst.search(8)); // false
}
}
```
在上面的代码中,我们首先定义了一个 `TreeNode` 类,它表示二叉树的节点。然后定义了一个 `BST` 类,它包含一个指向根节点的引用 `root`,并实现了 `insert` 方法和 `search` 方法。`insert` 方法用于将一个数值插入到 BST 中,`search` 方法用于在 BST 中查找一个数值。
在 `insert` 方法中,我们首先检查根节点是否为 `null`。如果是,则创建一个新的节点并将其设置为根节点。否则,我们将数值与根节点进行比较,如果小于根节点,则将其插入到左子树中,否则将其插入到右子树中。最后返回根节点。
在 `search` 方法中,我们首先检查当前节点是否为 `null`。如果是,则返回 `false`。否则,我们将数值与当前节点进行比较,如果相等,则返回 `true`。否则,如果数值小于当前节点,则在左子树中继续查找,否则在右子树中继续查找。
在 `main` 方法中,我们创建了一个包含七个数值的数组,并将其插入到 BST 中。然后我们分别使用 `search` 方法查找数值 5 和 8。第一个查找返回 `true`,第二个查找返回 `false`。