Python 数据结构和算法：在 Python 中如何实现链表和树结构？

在Python中，你可以使用类来实现链表和树结构。下面分别介绍如何实现链表和树。

链表实现

单链表

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

# 使用示例
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)

双向链表

class DoubleNode:
    def __init__(self, data=None):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = DoubleNode(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        new_node.prev = last_node

# 使用示例
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(1)
doubly_linked_list.append(2)
doubly_linked_list.append(3)

树结构实现

二叉树

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

# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

二叉搜索树

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

    def insert(self, key):
        if key < self.val:
            if self.left is None:
                self.left = BinarySearchTree(key)
            else:
                self.left.insert(key)
        elif key > self.val:
            if self.right is None:
                self.right = BinarySearchTree(key)
            else:
                self.right.insert(key)

# 使用示例
bst = BinarySearchTree(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(4)

这些示例提供了基本的数据结构，你可以根据需要进行扩展。链表和树的实现通常会涉及到节点的插入、删除、查找等操作，具体实现方式可能因应用场景而有所不同。