二进制树搜索算法java实现
时间: 2023-07-25 15:31:36 浏览: 44
以下是二进制树搜索算法的Java实现,包括二进制编码的生成、节点的插入和查找操作。
```java
public class BinarySearchTree {
private Node root;
// 节点类
private class Node {
int key;
Node left;
Node right;
public Node(int key) {
this.key = key;
this.left = null;
this.right = null;
}
}
// 生成二进制编码
private String toBinaryString(int n) {
StringBuilder sb = new StringBuilder();
while (n > 0) {
sb.append(n % 2);
n /= 2;
}
return sb.reverse().toString();
}
// 插入节点
public void insert(int key) {
Node newNode = new Node(key);
if (root == null) {
root = newNode;
return;
}
String keyStr = toBinaryString(key);
Node currentNode = root;
Node parentNode = null;
while (currentNode != null) {
parentNode = currentNode;
if (keyStr.compareTo(toBinaryString(currentNode.key)) < 0) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
if (keyStr.compareTo(toBinaryString(parentNode.key)) < 0) {
parentNode.left = newNode;
} else {
parentNode.right = newNode;
}
}
// 查找节点
public Node search(int key) {
String keyStr = toBinaryString(key);
Node currentNode = root;
while (currentNode != null) {
if (keyStr.compareTo(toBinaryString(currentNode.key)) == 0) {
return currentNode;
} else if (keyStr.compareTo(toBinaryString(currentNode.key)) < 0) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
return null;
}
}
```
在上述代码中,toBinaryString函数用于将整数转换为二进制字符串,insert函数用于插入新节点,search函数用于查找节点。其中,插入和查找操作的时间复杂度均为O(log n)。