如何在Python中实现基于指针的数据结构？以二叉树转链表为例

Great question! I've run into this exact issue while working through Skiena's book too—Python's lack of explicit pointers can feel tricky at first, but once you get the hang of it, objects and references work perfectly as a stand-in. Let's break this down step by step.

核心原理：用对象引用代替指针 #

Python doesn't have C/C++-style explicit pointers, but every variable stores an object reference—this is functionally identical to a pointer: it points to an object in memory, and modifying an object's attributes is like dereferencing a pointer to update the target value. For example, where you'd use node->left in C, you'll use node.left in Python, where left is an attribute storing a reference to another node object.

1. Implementing Binary Tree Nodes #

Start with the basics: define a binary tree node class, where left and right attributes act as your "pointers" to child nodes:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None  # Equivalent to a NULL pointer for left child
        self.right = None # Equivalent to a NULL pointer for right child

Building a tree is as simple as assigning node objects to these attributes:

# Create a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

This is exactly analogous to a tree built with pointers in C.

2. Implementing Linked List Nodes #

Linked lists work the same way—use a next attribute to simulate the pointer to the next node:

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next = None  # "Pointer" to the next list node

Constructing a list just means linking next attributes to other ListNode instances.

3. Practical Example: Flattening a Binary Tree to a Linked List #

Let's tackle the exact problem you mentioned from Chapter 3: converting a binary tree to a singly linked list (e.g., in-order traversal order). We'll use a recursive approach, modifying node right attributes to act as the list's next pointers, and setting left to None to clean up.

Here's the implementation:

def flatten_binary_tree(root):
    # Helper function to return the tail of the flattened sublist
    def helper(node):
        if not node:
            return None
        
        # Recursively flatten left and right subtrees
        left_tail = helper(node.left)
        right_tail = helper(node.right)
        
        # If left subtree exists, link it to the current node's right
        if left_tail:
            left_tail.right = node.right
            node.right = node.left
            node.left = None
        
        # Return the tail of the flattened list for this subtree
        return right_tail if right_tail else left_tail if left_tail else node
    
    helper(root)

Test it with our sample tree:

flatten_binary_tree(root)

# Traverse and print the resulting linked list
current = root
while current:
    print(current.value, end=" -> ")
    current = current.right
# Output: 1 -> 4 -> 2 -> 3 -> 

This logic mirrors the pointer-based approach in C exactly—we're just using . instead of ->, and None instead of NULL.

Key Notes #

• Using None for empty pointers: None in Python is the direct equivalent of NULL in C, marking a reference that doesn't point to any object.
• Reference behavior: Python passes objects by reference, so modifying an object's attributes (like node.right) inside a function changes the original object—just like passing a pointer to a function in C.
• Avoid circular references: Be careful not to create loops (e.g., node.next = node), as this can cause memory leaks.

内容的提问来源于stack exchange，提问作者Arun Ajay