用python输入一组数据,构建二叉搜索树,并遍历
时间: 2024-02-12 10:08:01 浏览: 64
好的,下面是Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
def inorder(root):
if not root:
return
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
# 构建二叉搜索树
root = None
data = [5, 3, 7, 2, 4, 6, 8]
for val in data:
root = insert(root, val)
# 遍历二叉搜索树
print("中序遍历结果为:")
inorder(root)
```
输出结果为:
```
中序遍历结果为:
2 3 4 5 6 7 8
```
首先我们定义了一个 `TreeNode` 类,表示二叉搜索树的节点。
然后我们定义了两个函数:
1. `insert` 函数用于插入节点,如果当前节点为空,直接返回一个新节点;否则根据节点值大小选择左或右子树递归插入节点,最终返回根节点。
2. `inorder` 函数用于中序遍历二叉搜索树,先遍历左子树,再输出当前节点值,最后遍历右子树。
接下来我们就可以通过输入一组数据,构建二叉搜索树并进行遍历了。
阅读全文