用java实现:假设每个姓氏有一个编码与其对应 以表中的编码为关键字建立一棵二叉排序树 以中根遍历形式显示该二叉排序树 分别查找关键字值为63和36对应的姓氏(要找到)并如何显示对应的姓氏, 删除关键字值为13的节点(不改变排序二叉树的性质)
时间: 2024-03-11 22:47:58 浏览: 102
用java实现二叉树的创建和遍历.doc
好的,我了解了你的问题。下面是用Java实现要求的代码:
首先,我们需要定义一个姓氏节点的类,包含姓氏和对应的编码:
```java
class SurnameNode {
int code;
String surname;
SurnameNode left, right;
public SurnameNode(int code, String surname) {
this.code = code;
this.surname = surname;
left = right = null;
}
}
```
然后,我们需要定义一个二叉排序树的类,包含插入、查找、删除、中序遍历等操作:
```java
class BST {
SurnameNode root;
public BST() {
root = null;
}
// 插入节点
public void insert(int code, String surname) {
root = insertNode(root, code, surname);
}
private SurnameNode insertNode(SurnameNode root, int code, String surname) {
if (root == null) {
root = new SurnameNode(code, surname);
return root;
}
if (code < root.code) {
root.left = insertNode(root.left, code, surname);
} else if (code > root.code) {
root.right = insertNode(root.right, code, surname);
}
return root;
}
// 查找节点
public String search(int code) {
SurnameNode node = searchNode(root, code);
if (node != null) {
return node.surname;
} else {
return null;
}
}
private SurnameNode searchNode(SurnameNode root, int code) {
if (root == null || root.code == code) {
return root;
}
if (code < root.code) {
return searchNode(root.left, code);
} else {
return searchNode(root.right, code);
}
}
// 删除节点
public void delete(int code) {
root = deleteNode(root, code);
}
private SurnameNode deleteNode(SurnameNode root, int code) {
if (root == null) {
return root;
}
if (code < root.code) {
root.left = deleteNode(root.left, code);
} else if (code > root.code) {
root.right = deleteNode(root.right, code);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
root.code = minValue(root.right);
root.surname = search(root.code);
root.right = deleteNode(root.right, root.code);
}
return root;
}
private int minValue(SurnameNode node) {
int min = node.code;
while (node.left != null) {
min = node.left.code;
node = node.left;
}
return min;
}
// 中序遍历
public void inorder() {
inorderTraversal(root);
}
private void inorderTraversal(SurnameNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.code + ":" + root.surname + " ");
inorderTraversal(root.right);
}
}
}
```
最后,我们可以在主函数中创建二叉排序树并进行操作:
```java
public static void main(String[] args) {
BST bst = new BST();
bst.insert(24, "张");
bst.insert(13, "王");
bst.insert(63, "李");
bst.insert(36, "赵");
bst.insert(73, "钱");
bst.insert(50, "孙");
System.out.println("中序遍历:");
bst.inorder();
System.out.println();
int code1 = 63;
String surname1 = bst.search(code1);
System.out.println("编码为" + code1 + "的姓氏是:" + surname1);
int code2 = 36;
String surname2 = bst.search(code2);
System.out.println("编码为" + code2 + "的姓氏是:" + surname2);
bst.delete(13);
System.out.println("删除节点后的中序遍历:");
bst.inorder();
}
```
输出结果为:
```
中序遍历:
13:王 24:张 36:赵 50:孙 63:李 73:钱
编码为63的姓氏是:李
编码为36的姓氏是:赵
删除节点后的中序遍历:
24:张 36:赵 50:孙 63:李 73:钱
```
阅读全文