对一组输入数据构建相应的二叉排序树,并利用其中序遍历对数据进行升序排序。 【输入形式】 数据个数,数据。(以空格分割) 【输出形式】 排序之后的数据。(以空格分割)
时间: 2024-05-13 09:17:08 浏览: 74
以下是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
curr = self.root
while True:
if val < curr.val:
if not curr.left:
curr.left = TreeNode(val)
return
curr = curr.left
else:
if not curr.right:
curr.right = TreeNode(val)
return
curr = curr.right
def inorder_traversal(self):
res = []
stack = []
curr = self.root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res
n, *nums = map(int, input().split())
bst = BinarySearchTree()
for num in nums:
bst.insert(num)
res = bst.inorder_traversal()
print(*res)
```
算法思路:
1. 定义 `TreeNode` 类,表示二叉排序树的节点;
2. 定义 `BinarySearchTree` 类,表示二叉排序树,实现插入节点和中序遍历功能;
3. 读入数据并构建二叉排序树;
4. 对二叉排序树进行中序遍历,即可得到升序排列的结果。
阅读全文