设计实现以下代码。 (1)二叉排序树的创建 (2)二叉排序树中增加和删除关键字 (3)判别是否是二叉排序树 (4)二叉排序树的最大值和第k大的值
时间: 2023-12-06 18:38:05 浏览: 51
以下是关于二叉排序树的创建、增加和删除关键字、判别是否是二叉排序树、二叉排序树的最大值和第k大的值的介绍和演示:
1. 二叉排序树的创建
二叉排序树的创建可以通过递归的方式实现。具体步骤如下:
- 如果当前节点为空,则新建一个节点并将值赋给该节点。
- 如果当前节点不为空,则比较当前节点的值和要插入的值的大小关系。
- 如果要插入的值小于当前节点的值,则递归处理当前节点的左子树。
- 如果要插入的值大于等于当前节点的值,则递归处理当前节点的右子树。
下面是一个示例代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if not root:
root = TreeNode(val)
elif val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
```
2. 二叉排序树中增加和删除关键字
二叉排序树中增加和删除关键字的操作与创建操作类似,也可以通过递归的方式实现。具体步骤如下:
- 增加操作:在二叉排序树中增加一个关键字,可以通过调用创建操作实现。
- 删除操作:在二叉排序树中删除一个关键字,需要分为以下三种情况:
- 要删除的节点没有子节点,直接删除即可。
- 要删除的节点只有一个子节点,将该子节点替换要删除的节点即可。
- 要删除的节点有两个子节点,需要找到该节点右子树中的最小节点,将该节点的值赋给要删除的节点,然后删除该最小节点。
下面是一个示例代码:
```python
def delete(root, val):
if not root:
return root
if val < root.val:
root.left = delete(root.left, val)
elif val > root.val:
root.right = delete(root.right, val)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
min_node = root.right
while min_node.left:
min_node = min_node.left
root.val = min_node.val
root.right = delete(root.right, min_node.val)
return root
```
3. 判别是否是二叉排序树
判别是否是二叉排序树可以通过中序遍历的方式实现。具体步骤如下:
- 对二叉排序树进行中序遍历,得到一个有序的序列。
- 判断该序列是否为升序序列,如果是,则该二叉树是二叉排序树,否则不是。
下面是一个示例代码:
```python
def inorder(root, res):
if not root:
return
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
def is_bst(root):
res = []
inorder(root, res)
return res == sorted(res)
```
4. 二叉排序树的最大值和第k大的值
二叉排序树的最大值即为其最右侧的节点的值。第k大的值可以通过中序遍历的方式实现。具体步骤如下:
- 对二叉排序树进行中序遍历,得到一个有序的序列。
- 返回该序列中倒数第k个元素即可。
下面是一个示例代码:
```python
def find_max(root):
while root.right:
root = root.right
return root.val
def find_kth_largest(root, k):
res = []
inorder(root, res)
return res[-k]
```