数据结构二叉排序说树查找对应姓氏的编码
时间: 2023-07-08 10:35:16 浏览: 50
在二叉排序树中查找对应姓氏的编码,可以通过遍历树的方式实现。假设要查找的姓氏为 `target`,首先从根节点开始遍历,比较 `target` 和当前节点存储的姓氏的大小关系。如果 `target` 小于当前节点的姓氏,就继续遍历左子树;如果 `target` 大于当前节点的姓氏,就继续遍历右子树;如果 `target` 等于当前节点的姓氏,就返回当前节点的编码。
下面是一个实现查找对应姓氏编码的JAVA代码:
```java
public class BST {
private Node root;
private class Node {
private String key;
private int code;
private Node left, right;
public Node(String key, int code) {
this.key = key;
this.code = code;
}
}
public int searchCode(String target) {
Node x = root;
while (x != null) {
int cmp = target.compareTo(x.key);
if (cmp < 0) x = x.left;
else if (cmp > 0) x = x.right;
else return x.code;
}
return -1;
}
public void put(String key, int code) {
root = put(root, key, code);
}
private Node put(Node x, String key, int code) {
if (x == null) return new Node(key, code);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, code);
else if (cmp > 0) x.right = put(x.right, key, code);
else x.code = code;
return x;
}
public static void main(String[] args) {
BST bst = new BST();
bst.put("张三", 1);
bst.put("李四", 2);
bst.put("王五", 3);
System.out.println(bst.searchCode("李四")); // 2
System.out.println(bst.searchCode("赵六")); // -1
}
}
```
在这个二叉排序树中,我们使用整数作为编码,节点中存储的是姓氏和对应的编码。在 `searchCode` 函数中,我们使用 `while` 循环遍历树,直到找到对应的姓氏或者遍历到叶子节点为止。如果找到了对应的姓氏,就返回节点中存储的编码;如果没有找到,就返回 `-1` 表示未找到。在 `main` 函数中,我们演示了如何插入三个不同的姓氏和对应的编码,并且查找其中一个姓氏的编码。