2. 对给定的一组无序序列,建立一棵二叉检索树,并对建立的二叉检索树实现查找操作。调试程序并对相应的输出作出分析;
时间: 2024-01-24 15:17:05 浏览: 89
以下是建立二叉搜索树并实现查找操作的示例代码:
```python
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val == key:
return root
elif root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
def search(root, key):
if root is None or root.val == key:
return root
if root.val < key:
return search(root.right, key)
return search(root.left, key)
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
# 建立二叉搜索树
arr = [50, 30, 20, 40, 70, 60, 80]
r = Node(arr[0])
for i in range(1, len(arr)):
r = insert(r, arr[i])
# 实现查找操作
print("Inorder traversal:")
inorder_traversal(r)
s = 60
print("Search for", s)
if search(r, s):
print(s, "is found in the tree.")
else:
print(s, "is not found in the tree.")
```
输出结果为:
```
Inorder traversal:
20
30
40
50
60
70
80
Search for 60
60 is found in the tree.
```
分析:
1. 首先创建了一个 `Node` 类用于表示二叉树节点。
2. `insert` 方法用于插入节点并构建二叉搜索树。如果根节点为空,则直接返回一个新节点。否则,如果值已经存在于树中,则直接返回根节点。如果值比根节点的值大,则将其插入右子树中;否则插入左子树中。
3. `search` 方法用于查找给定的键。如果根节点为空或者根节点的值等于给定键,则直接返回根节点。否则,如果给定键比根节点的值大,则在右子树中递归查找;否则在左子树中递归查找。
4. `inorder_traversal` 方法用于中序遍历二叉搜索树。
5. 在主程序中,首先定义了一个序列 `arr`,然后将其插入到二叉搜索树中。最后,查找给定的键。输出结果表明,60 存在于二叉搜索树中。
阅读全文