二叉树链式存储结构python

二叉树链式存储结构，也称为二叉搜索树（Binary Search Tree, BST）和链式表示法，是将二叉树的节点通过链表连接起来的一种数据结构。在Python中，每个节点通常包含三个部分：一个键值、一个指向左子树的引用和一个指向右子树的引用。这种存储方式使得插入、删除和查找操作相对高效，因为它们都是基于比较节点的键值来进行的。

以下是二叉搜索树的链式存储结构的一个基本Python实现：

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

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

    # 插入节点
    def insert(self, key):
        if not self.root:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

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

    # 其他方法，如查找、删除等，可以根据需要实现
    # 示例：查找
    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None or node.key == key:
            return node
        elif key < node.key:
            return self._search(node.left, key)
        else:
            return self._search(node.right, key)