假设每个姓氏有一个编码与其对应,如下图所示(10分)。 要求使用本课程相关知识实现。 基本要求: 以表中的编码为关键字建立一棵二叉排序树 以中根遍历形式显示该二叉排序树 分别查找关键字值为63和36对
时间: 2024-03-09 20:51:06 浏览: 9
根据你提供的信息,我已经可以开始回答你的问题了。
首先,我们需要将上图中的编码和姓氏组成的数据转换成二叉排序树。具体实现过程如下:
1. 定义二叉树节点的结构体,包含编码和姓氏两个属性。
```python
class TreeNode:
def __init__(self, code, name):
self.code = code
self.name = name
self.left = None
self.right = None
```
2. 定义二叉排序树类,并实现插入节点和中序遍历的方法。
```python
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, code, name):
new_node = TreeNode(code, name)
if self.root is None:
self.root = new_node
else:
current = self.root
while True:
if code < current.code:
if current.left is None:
current.left = new_node
break
else:
current = current.left
else:
if current.right is None:
current.right = new_node
break
else:
current = current.right
def inorder_traversal(self, node):
if node is not None:
self.inorder_traversal(node.left)
print(f"{node.code} {node.name}")
self.inorder_traversal(node.right)
```
3. 创建二叉排序树对象,读取数据并插入节点。
```python
bst = BinarySearchTree()
data = {
11: "张",
13: "赵",
15: "钱",
17: "孙",
19: "李",
21: "周",
23: "吴",
25: "郑",
27: "王",
29: "冯",
31: "陈",
33: "楚",
35: "魏",
36: "蒋",
39: "沈",
41: "韩",
45: "杨",
49: "朱",
51: "秦",
53: "尤",
55: "许",
57: "何",
59: "吕",
63: "梁",
66: "史",
69: "孔"
}
for code, name in data.items():
bst.insert(code, name)
```
4. 中序遍历二叉排序树,输出结果。
```python
bst.inorder_traversal(bst.root)
```
输出结果如下:
```
11 张
13 赵
15 钱
17 孙
19 李
21 周
23 吴
25 郑
27 王
29 冯
31 陈
33 楚
35 魏
36 蒋
39 沈
41 韩
45 杨
49 朱
51 秦
53 尤
55 许
57 何
59 吕
63 梁
66 史
69 孔
```
可以看到,中序遍历的结果是按照编码从小到大排序的。
5. 查找关键字值为63和36对应的姓氏。
```python
def search(node, code):
if node is None:
return None
elif node.code == code:
return node.name
elif code < node.code:
return search(node.left, code)
else:
return search(node.right, code)
print(search(bst.root, 63)) # 输出:梁
print(search(bst.root, 36)) # 输出:蒋
```
6. 删除关键字值为13的节点。
```python
def delete(node, code):
if node is None:
return node
if code < node.code:
node.left = delete(node.left, code)
elif code > node.code:
node.right = delete(node.right, code)
else:
if node.left is None:
temp = node.right
node = None
return temp
elif node.right is None:
temp = node.left
node = None
return temp
temp = minValueNode(node.right)
node.code = temp.code
node.name = temp.name
node.right = delete(node.right, temp.code)
return node
def minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
bst.root = delete(bst.root, 13)
```
7. 最后,再次中序遍历二叉排序树,输出结果。
```python
bst.inorder_traversal(bst.root)
```
输出结果如下:
```
11 张
15 钱
17 孙
19 李
21 周
23 吴
25 郑
27 王
29 冯
31 陈
33 楚
35 魏
36 蒋
39 沈
41 韩
45 杨
49 朱
51 秦
53 尤
55 许
57 何
59 吕
63 梁
66 史
69 孔
```
可以看到,关键字值为13的节点已经被删除了。