设计递归算法将关键字序列{39,11,68,46,75,23,71,8,86,34}构造成一颗二叉排序树
时间: 2024-03-02 07:53:02 浏览: 48
二叉排序树(一个关键字)
好的,我可以为您设计一个递归算法来构造二叉排序树:
1. 定义一个函数,输入为一个无序的关键字序列和当前子树的根节点,输出为一颗二叉排序树。
2. 在函数内部,判断输入的序列是否为空,如果为空则返回空树。
3. 如果序列不为空,则取出序列的第一个元素作为根节点的值,并创建一个新的节点作为根节点。
4. 遍历序列的剩余部分,将小于根节点值的元素放入左子树中,大于根节点值的元素放入右子树中。
5. 递归地调用函数,对左子树和右子树分别进行构造,返回根节点即可。
下面是完整的代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def construct_bst(nums):
if not nums:
return None
root_val = nums[0]
root = TreeNode(root_val)
left_nums = [num for num in nums if num < root_val]
right_nums = [num for num in nums if num > root_val]
root.left = construct_bst(left_nums)
root.right = construct_bst(right_nums)
return root
```
您可以将关键字序列作为参数传递给函数,调用函数即可构造一颗二叉排序树。
阅读全文