用二叉链表作为存储结构,输入键值序列建立一棵二叉排序树,然后中序遍历这棵二叉树。
时间: 2024-05-08 14:20:45 浏览: 114
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法
5星 · 资源好评率100%
二叉排序树是一种特殊的二叉树,它满足以下两个条件:
1. 对于任意一个节点,它的左子树中所有节点的键值都小于该节点的键值,它的右子树中所有节点的键值都大于该节点的键值。
2. 对于任意一个节点,它的左子树和右子树都是二叉排序树。
二叉排序树的中序遍历结果是有序的。因此,我们可以通过输入键值序列建立一棵二叉排序树,然后中序遍历这棵二叉树,即可得到键值序列的有序输出。
下面是用二叉链表实现的建立二叉排序树和中序遍历的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
node = self.root
while node:
if val < node.val:
if not node.left:
node.left = TreeNode(val)
break
else:
node = node.left
else:
if not node.right:
node.right = TreeNode(val)
break
else:
node = node.right
def inorder_traversal(self):
stack = []
res = []
node = self.root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
# 示例
bst = BST()
keys = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for key in keys:
bst.insert(key)
print(bst.inorder_traversal()) # 输出 [1, 3, 4, 6, 7, 8, 10, 13, 14]
```
在上面的代码中,我们定义了 `TreeNode` 类来表示树节点,包含 `val`、`left`、`right` 三个属性。`BST` 类表示二叉排序树,包含 `root` 属性表示根节点。`insert` 方法用于插入节点,`inorder_traversal` 方法用于中序遍历二叉排序树并返回结果。在 `insert` 方法中,我们按照二叉排序树的规则将新节点插入到树中。在 `inorder_traversal` 方法中,我们使用栈来实现中序遍历,先将根节点和它的所有左子节点入栈,然后依次出栈并访问节点,再访问它的右子节点。
最后,我们可以通过输入一个键值序列来建立二叉排序树,并对树进行中序遍历,得到有序输出。
阅读全文