二叉树的基本运算程序

二叉树的基本运算程序包括二叉树的创建、遍历、查找、插入、删除等操作。下面是一个简单的二叉树基本运算程序的示例：

# 定义二叉树节点类
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)