python语言:用链式存储结构建立一颗二叉排序树
时间: 2023-08-21 20:32:39 浏览: 45
好的,下面是Python代码实现:
```python
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val == key:
return root
elif root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
```
我们创建了一个名为`Node`的类来表示二叉树的节点。每个节点都有一个`left`和`right`指针,指向其左子树和右子树。`val`属性存储节点的值。
`insert`函数接受一个根节点和要插入的值。如果根节点为空,它将创建一个新的节点并将其设置为根节点。否则,它将递归地向左或向右子树插入新节点。如果值已经存在于树中,则不插入新节点。最后,它返回更新后的根节点。
相关问题
设计链式存储结构建立一颗二叉排序树
以下是建立一棵链式存储结构的二叉排序树的Python实现:
```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)
elif val > root.val:
root.right = insert(root.right, val)
return root
# 中序遍历函数(递增顺序)
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
# 查找函数
def search(root, val):
if not root:
return False
elif root.val == val:
return True
elif val < root.val:
return search(root.left, val)
else:
return search(root.right, val)
# 逆序中序遍历函数(递减顺序)
def reverse_inorder(root):
if root:
reverse_inorder(root.right)
print(root.val)
reverse_inorder(root.left)
```
使用示例:
```python
# 建立二叉排序树
root = None
nums = [5, 3, 7, 1, 9, 4, 6, 2, 8]
for num in nums:
root = insert(root, num)
# 中序遍历输出递增顺序的结点值
print("递增顺序:")
inorder(root)
# 查找结点
key1 = 4
if search(root, key1):
print(f"{key1} 找到了")
else:
print(f"{key1} 没找到")
# 插入结点
key2 = 10
if not search(root, key2):
root = insert(root, key2)
# 逆序中序遍历输出递减顺序的结点值
print("递减顺序:")
reverse_inorder(root)
```
链式存储结构构建二叉排序树python代码实现
以下是链式存储结构构建二叉排序树的Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert(val, self.root)
def _insert(self, val, node):
if val < node.val:
if node.left is None:
node.left = TreeNode(val)
else:
self._insert(val, node.left)
else:
if node.right is None:
node.right = TreeNode(val)
else:
self._insert(val, node.right)
def inorder_traversal(self):
if not self.root:
return []
return self._inorder_traversal(self.root, [])
def _inorder_traversal(self, node, res):
if node:
self._inorder_traversal(node.left, res)
res.append(node.val)
self._inorder_traversal(node.right, res)
return res
```
使用方法:
```python
bst = BinarySearchTree()
bst.insert(8)
bst.insert(3)
bst.insert(10)
bst.insert(1)
bst.insert(6)
bst.insert(14)
bst.insert(4)
bst.insert(7)
bst.insert(13)
print(bst.inorder_traversal())
```
输出结果:
```
[1, 3, 4, 6, 7, 8, 10, 13, 14]
```