数据结构编写二叉排序树的操作函数,并在main主函数中依次调用基本操作函数。 (1)建立二叉排序树。(2)二叉排序树的插入。(3)二叉排序树的查找。(4)树的遍历。
时间: 2024-12-25 08:27:34 浏览: 15
在Python中,我们可以创建一个简单的二叉搜索树(Binary Search Tree, BST)并实现所需的操作。这里我会给出一个基础版本的类定义以及相应的操作函数:
```python
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
class BinarySearchTree:
def __init__(self):
self.root = None
# 插入节点
def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self._insert_node(self.root, key)
def _insert_node(self, node, key):
if key < node.val:
if node.left is None:
node.left = Node(key)
else:
self._insert_node(node.left, key)
else:
if node.right is None:
node.right = Node(key)
else:
self._insert_node(node.right, key)
# 查找节点
def search(self, key):
return self._search_node(self.root, key)
def _search_node(self, node, key):
if node is None or node.val == key:
return node
elif key < node.val:
return self._search_node(node.left, key)
else:
return self._search_node(node.right, key)
# 中序遍历(返回左子树、根节点、右子树)
def inorder_traversal(self, node):
res = []
if node is not None:
res.extend(self.inorder_traversal(node.left))
res.append(node.val)
res.extend(self.inorder_traversal(node.right))
return res
# 主函数演示操作
def main():
bst = BinarySearchTree()
# 建立二叉排序树
keys = [50, 30, 70, 20, 40, 60, 80]
for key in keys:
bst.insert(key)
print("After insertion:")
print("In-order traversal:", bst.inorder_traversal(bst.root))
# 二叉排序树查找
target = 60
if bst.search(target) is not None:
print(f"Found {target}, at {bst.search(target).val}")
else:
print(f"{target} not found")
if __name__ == "__main__":
main()
```
阅读全文