1、用递归的方法实现二叉树的操作 (1)以二叉链表表示二叉树,建立一棵二叉树(算法5.3); (2)输出二叉树的中序遍历结果(算法5.1); (3)输出二叉树的前序遍历结果; (4)输出二叉树的后序遍历结果; (5)

实现二叉树的查找、插入和删除操作。

1. 建立二叉树

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def create_tree():
    val = input()
    if val == '#':
        return None
    root = TreeNode(int(val))
    root.left = create_tree()
    root.right = create_tree()
    return root

2. 中序遍历

def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val, end=' ')
    inorder(root.right)

3. 前序遍历

def preorder(root):
    if not root:
        return
    print(root.val, end=' ')
    preorder(root.left)
    preorder(root.right)

4. 后序遍历

def postorder(root):
    if not root:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val, end=' ')

5. 查找、插入和删除操作

def find(root, val):
    if not root:
        return None
    if root.val == val:
        return root
    left = find(root.left, val)
    right = find(root.right, val)
    return left or right

def insert(root, val):
    node = TreeNode(val)
    if not root:
        return node
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def delete(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
        cur = root.right
        while cur.left:
            cur = cur.left
        root.val = cur.val
        root.right = delete(root.right, cur.val)
    elif root.val > val:
        root.left = delete(root.left, val)
    else:
        root.right = delete(root.right, val)
    return root