二叉树的基本运算pta
时间: 2024-10-09 16:00:36 浏览: 22
二叉树是一种常见的数据结构,其每个节点最多有两个子节点,通常称为左子节点和右子节点。基本的二叉树运算是指对这种结构进行的一些基本操作:
1. **插入**(Insertion):将新的元素添加到二叉树中,通常按照某种规则保持树的有序性,如搜索二叉树(BST),新节点会被插入到适当的空位,保证左子树的所有节点值都小于当前节点,右子树所有大于当前节点。
2. **查找**(Search):给定一个目标值,从根节点开始遍历树,如果找到等于目标的节点则返回,否则返回空或null。
3. **删除**(Deletion):移除指定的节点,这比插入更复杂,因为需要考虑子节点的情况。有四种情况:
- 节点没有子节点:直接删除。
- 只有一个子节点:替换当前节点为该子节点。
- 有两个子节点:找到子树中最大(或最小)的值替换当前节点,并删除这个最大(或最小)节点。
4. **前序遍历**(Preorder Traversal)、**中序遍历**(Inorder Traversal)和**后序遍历**(Postorder Traversal):按顺序访问每一个节点,用于序列化二叉树或打印节点值。
5. **高度查找**(Height Search):找出二叉树的最大深度或最小深度。
6. **平衡调整**(Balancing):对于自平衡二叉树(如AVL树、红黑树等)来说,当树失去平衡时,会自动通过旋转操作使其恢复平衡。
相关问题
二叉树的基本运算程序
二叉树的基本运算程序包括二叉树的创建、遍历、查找、插入、删除等操作。下面是一个简单的二叉树基本运算程序的示例:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 创建二叉树
def create_tree(s):
if not s:
return None
stack = []
root = None
is_left = True
for i in s:
if i == '(':
stack.append(node)
is_left = True
elif i == ',':
is_left = False
elif i == ')':
stack.pop()
else:
node = TreeNode(i)
if not root:
root = node
elif is_left:
stack[-1].left = node
else:
stack[-1].right = node
return root
# 前序遍历
def preorder_traversal(root):
if not root:
return
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
# 中序遍历
def inorder_traversal(root):
if not root:
return
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
# 后序遍历
def postorder_traversal(root):
if not root:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
# 查找节点
def find_node(root, val):
if not root:
return None
if root.val == val:
return root
left = find_node(root.left, val)
if left:
return left
right = find_node(root.right, val)
if right:
return right
return None
# 插入节点
def insert_node(root, val):
if not root:
return TreeNode(val)
if not root.left:
root.left = TreeNode(val)
elif not root.right:
root.right = TreeNode(val)
else:
insert_node(root.left, val)
return root
# 删除节点
def delete_node(root, val):
if not root:
return None
if root.val == val:
if not root.left:
return root.right
if not root.right:
return root.left
min_node = root.right
while min_node.left:
min_node = min_node.left
root.val = min_node.val
root.right = delete_node(root.right, min_node.val)
elif root.val > val:
root.left = delete_node(root.left, val)
else:
root.right = delete_node(root.right, val)
return root
# 获取二叉树高度
def get_height(root):
if not root:
return 0
left_height = get_height(root.left)
right_height = get_height(root.right)
return max(left_height, right_height) + 1
# 释放二叉树
def free_tree(root):
if not root:
return
free_tree(root.left)
free_tree(root.right)
del root
# 测试
s = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"
root = create_tree(s)
print("前序遍历:", end='')
preorder_traversal(root)
print()
print("中序遍历:", end='')
inorder_traversal(root)
print()
print("后序遍历:", end='')
postorder_traversal(root)
print()
node = find_node(root, 'H')
if node:
print("H结点的左孩子结点值:", node.left.val)
print("H结点的右孩子结点值:", node.right.val)
print("二叉树的高度:", get_height(root))
root = delete_node(root, 'H')
print("删除H结点后的中序遍历:", end='')
inorder_traversal(root)
print()
free_tree(root)
```
二叉树的基本运算代码
以下是二叉树的基本运算的示例代码(使用 Python 语言实现):
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
# 创建二叉树
def create_tree():
x = input("请输入节点值(空值表示该节点不存在):")
if not x:
return None
root = TreeNode(x)
root.left = create_tree()
root.right = create_tree()
return root
# 前序遍历二叉树
def preorder_traversal(root):
if not root:
return
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
# 中序遍历二叉树
def inorder_traversal(root):
if not root:
return
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
# 后序遍历二叉树
def postorder_traversal(root):
if not root:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
# 插入节点
def insert_node(root, value):
if not root:
return TreeNode(value)
if value < root.val:
root.left = insert_node(root.left, value)
elif value > root.val:
root.right = insert_node(root.right, value)
return root
# 删除节点
def delete_node(root, value):
if not root:
return None
if value < root.val:
root.left = delete_node(root.left, value)
elif value > root.val:
root.right = delete_node(root.right, value)
else:
if not root.left:
return root.right
if not root.right:
return root.left
min_node = root.right
while min_node.left:
min_node = min_node.left
root.val = min_node.val
root.right = delete_node(root.right, min_node.val)
return root
# 查找节点
def find_node(root, value):
if not root:
return None
if value == root.val:
return root
elif value < root.val:
return find_node(root.left, value)
else:
return find_node(root.right, value)
# 修改节点
def modify_node(root, old_value, new_value):
node = find_node(root, old_value)
if node:
node.val = new_value
# 计算二叉树深度
def get_depth(root):
if not root:
return 0
left_depth = get_depth(root.left)
right_depth = get_depth(root.right)
return max(left_depth, right_depth) + 1
# 判断二叉树是否为空
def is_empty(root):
return not root
# 测试代码
if __name__ == "__main__":
root = create_tree()
print("前序遍历:")
preorder_traversal(root)
print("中序遍历:")
inorder_traversal(root)
print("后序遍历:")
postorder_traversal(root)
root = insert_node(root, 5)
print("插入节点后的中序遍历:")
inorder_traversal(root)
root = delete_node(root, 4)
print("删除节点后的中序遍历:")
inorder_traversal(root)
node = find_node(root, 3)
if node:
print("查找到节点:", node.val)
else:
print("未找到节点")
modify_node(root, 3, 6)
print("修改节点后的中序遍历:")
inorder_traversal(root)
print("二叉树的深度为:", get_depth(root))
print("二叉树是否为空:", is_empty(root))
```
注意,以上代码只是示例代码,实际应用中可能需要根据具体需求进行修改。
阅读全文