输入一串正整数最后输入-1为结束标志,构造二叉排序树的代码
时间: 2024-12-16 10:33:00 浏览: 5
在Python中,我们可以使用递归的方式来构建二叉排序树(Binary Search Tree,BST)从输入的一串正整数。这里是一个简单的例子,假设我们有一个名为`insert`的函数来插入节点,然后一个辅助函数`build_tree`来构建整个树:
```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)
else:
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
def build_tree(nums):
if not nums or nums[-1] == -1:
return None
root = TreeNode(nums.pop(0))
stack = [root]
while nums and stack:
node = stack.pop()
val = nums.pop(0)
if val > node.val:
node.right = insert(node.right, val)
else:
node.left = insert(node.left, val)
if nums:
stack.append(node.right)
stack.append(node.left)
return root
# 示例
nums_list = [5, 3, 7, 2, 4, -1] # 输入序列
tree_root = build_tree(nums_list)
```
这个代码首先定义了一个`TreeNode`类表示二叉树节点,然后`insert`函数负责将新值插入到适当的位置。`build_tree`函数利用栈来保持当前节点的左右子树未遍历完,当遇到 `-1` 结束标志时返回根节点。
阅读全文