python实现二叉树的顺序存储实现二叉树的链接存储 向二叉树中插入节点 从二叉树中删除节点

二叉树的顺序存储实现：
二叉树的顺序存储是指使用数组来存储二叉树，对于完全二叉树，可以按照从上到下、从左到右的顺序依次存储每个节点，对于某个节点的下标为i，则其左子节点的下标为2i，右子节点的下标为2i+1，父节点的下标为i//2。下面是一个简单的例子：

class ArrayBinaryTree:
    def __init__(self, max_size):
        self.max_size = max_size
        self.array = [None] * max_size
        self.root = 1

    def add(self, value):
        if self.array[self.root] is None:
            self.array[self.root] = value
        else:
            i = 1
            while i < self.max_size:
                if self.array[i] is None:
                    self.array[i] = value
                    break
                elif value < self.array[i]:
                    i = 2 * i
                else:
                    i = 2 * i + 1

    def preorder_traversal(self, i):
        if i < self.max_size and self.array[i] is not None:
            print(self.array[i], end=' ')
            self.preorder_traversal(2 * i)
            self.preorder_traversal(2 * i + 1)

    def inorder_traversal(self, i):
        if i < self.max_size and self.array[i] is not None:
            self.inorder_traversal(2 * i)
            print(self.array[i], end=' ')
            self.inorder_traversal(2 * i + 1)

    def postorder_traversal(self, i):
        if i < self.max_size and self.array[i] is not None:
            self.postorder_traversal(2 * i)
            self.postorder_traversal(2 * i + 1)
            print(self.array[i], end=' ')

二叉树的链接存储实现：
二叉树的链接存储是指使用节点来存储二叉树，每个节点包含一个数据域和两个指针域，分别指向左子节点和右子节点。下面是一个简单的例子：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def add(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            queue = [self.root]
            while queue:
                node = queue.pop(0)
                if node.left is None:
                    node.left = Node(value)
                    break
                elif node.right is None:
                    node.right = Node(value)
                    break
                else:
                    queue.append(node.left)
                    queue.append(node.right)

    def preorder_traversal(self, node):
        if node is not None:
            print(node.value, end=' ')
            self.preorder_traversal(node.left)
            self.preorder_traversal(node.right)

    def inorder_traversal(self, node):
        if node is not None:
            self.inorder_traversal(node.left)
            print(node.value, end=' ')
            self.inorder_traversal(node.right)

    def postorder_traversal(self, node):
        if node is not None:
            self.postorder_traversal(node.left)
            self.postorder_traversal(node.right)
            print(node.value, end=' ')

向二叉树中插入节点：
向二叉树中插入节点需要先找到插入位置，然后将新节点插入到该位置。如果二叉树为空，则新节点为根节点；否则，从根节点开始，如果新节点的值小于当前节点的值，则继续在当前节点的左子树中查找插入位置；否则，在当前节点的右子树中查找插入位置。下面是一个简单的例子：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(self.root, value)

    def _insert(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(node.right, value)

从二叉树中删除节点：
从二叉树中删除节点需要先找到要删除的节点，然后根据节点的情况进行删除。如果要删除的节点是叶子节点，则直接删除；如果要删除的节点只有一个子节点，则将该子节点替换要删除的节点；如果要删除的节点有两个子节点，则找到该节点的后继节点（即右子树中最小的节点），将后继节点的值赋给要删除的节点，然后删除后继节点。下面是一个简单的例子：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def delete(self, value):
        self.root = self._delete(self.root, value)

    def _delete(self, node, value):
        if node is None:
            return None
        elif value < node.value:
            node.left = self._delete(node.left, value)
        elif value > node.value:
            node.right = self._delete(node.right, value)
        else:
            if node.left is None and node.right is None:
                node = None
            elif node.left is None:
                node = node.right
            elif node.right is None:
                node = node.left
            else:
                min_node = self._find_min(node.right)
                node.value = min_node.value
                node.right = self._delete(node.right, min_node.value)
        return node

    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node