帮我写判断二叉链表存储的二叉树是否是二叉排序树的代码,要求先写方法中序遍历二叉树,将遍历结果存储到队列中,然后遍历队列判断是否有序
时间: 2024-09-30 07:14:33 浏览: 22
为了判断一个二叉链表表示的二叉树是否是二叉排序树(BST),我们可以按照以下步骤编写代码:
首先,我们需要创建一个辅助方法来进行中序遍历,并将节点值存入队列。假设我们的二叉链表节点有一个`value`字段和指向左右孩子的指针`left`和`right`。
```python
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder_traversal(root, queue):
if root is not None:
inorder_traversal(root.left, queue)
queue.append(root.value) # 将当前节点值放入队列
inorder_traversal(root.right, queue)
# 示例:
# 创建一个二叉树节点列表 (可以根据实际链表构建)
nodes = [TreeNode(5), TreeNode(3), TreeNode(7), TreeNode(2), TreeNode(4), TreeNode(6), TreeNode(8)]
root = nodes[0]
queue = []
inorder_traversal(root, queue)
```
接下来,我们遍历队列并检查是否有序。如果队列中的每个元素都大于等于前一个元素,则说明是BST;反之则不是。
```python
def is_bst_sorted(root, queue):
prev_value = float('-inf') # 初始化前一个节点值为负无穷大
while queue:
current_value = queue.pop(0) # 取出队首元素
if current_value < prev_value:
return False # 当前值小于前一个值,不是BST
prev_value = current_value # 更新前一个值
return True # 队列为空,所有节点按顺序访问,说明是BST
# 判断队列是否为BST
is_bst = is_bst_sorted(root, queue)
```
阅读全文