将(45,24,55,12,37,53,60,28,40,70)中关键字依次插入初态为空的二叉排序树中,给出树的先序序列。代码
时间: 2024-04-30 15:18:54 浏览: 8
二叉排序树的插入过程实际上就是不断地比较大小并往左或右子树递归插入的过程。先序遍历二叉树的顺序是:根节点 -> 左子树 -> 右子树。因此,我们在插入完所有关键字之后,对二叉排序树进行先序遍历即可得到先序序列。
以下是使用 Python 语言实现二叉排序树插入和先序遍历的代码:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义二叉排序树类
class BST:
def __init__(self):
self.root = None
# 向二叉排序树中插入关键字
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
cur = self.root
while cur:
if val < cur.val:
if not cur.left:
cur.left = TreeNode(val)
return
cur = cur.left
else:
if not cur.right:
cur.right = TreeNode(val)
return
cur = cur.right
# 先序遍历二叉排序树
def preorder(self, node):
if not node:
return []
res = [node.val]
res += self.preorder(node.left)
res += self.preorder(node.right)
return res
# 创建一个空的二叉排序树
bst = BST()
# 将关键字依次插入二叉排序树中
lst = [45, 24, 55, 12, 37, 53, 60, 28, 40, 70]
for val in lst:
bst.insert(val)
# 输出二叉排序树的先序序列
print(bst.preorder(bst.root))
```
输出结果为:`[45, 24, 12, 37, 28, 40, 55, 53, 60, 70]`。