Python编程实现双链表，栈，队列及二叉树的方法示例

Python编程实现双链表，栈，队列及二叉树是数据结构中非常重要的内容。本文将详细介绍Python实现双链表、栈、队列及二叉树的方法示例。

双链表实现方法示例

定义节点类

首先，我们需要定义一个节点类，该类包含三个属性：

1. data：表示节点值
2. prev：表示前一个节点
3. next：表示下一个节点

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

定义双链表类

使用节点类定义双链表类，该类包含以下几个方法：

1. __init__：初始化链表
2. append：在链表尾部追加一个节点
3. prepend：在链表头部插入一个节点
4. insert_after_node：在指定节点后插入一个节点
5. insert_before_node：在指定节点前插入一个节点
6. delete_node：删除指定节点
7. print_forward：正序打印链表
8. print_backward：反序打印链表

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            new_node.prev = None
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current
            new_node.next = None

    def prepend(self, data):
        new_node = Node(data)

        if self.head is None:
            new_node.next = None
            self.head = new_node
        else:
            self.head.prev = new_node
            new_node.next = self.head
            self.head = new_node
            new_node.prev = None

    def insert_after_node(self, node, data):
        new_node = Node(data)

        new_node.next = node.next
        node.next = new_node
        new_node.prev = node
        if new_node.next is not None:
            new_node.next.prev = new_node

    def insert_before_node(self, node, data):
        new_node = Node(data)

        new_node.prev = node.prev
        node.prev = new_node
        new_node.next = node
        if new_node.prev is not None:
            new_node.prev.next = new_node
        else:
            self.head = new_node

    def delete_node(self, node):
        if self.head == node:
            self.head = node.next

        if node.next is not None:
            node.next.prev = node.prev
        if node.prev is not None:
            node.prev.next = node.next

    def print_forward(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

    def print_backward(self):
        current = self.head
        while current.next:
            current = current.next
        while current:
            print(current.data)
            current = current.prev

双链表方法示例

示例一：向双链表中添加节点

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(1)
doubly_linked_list.append(2)
doubly_linked_list.append(3)

打印链表：

doubly_linked_list.print_forward()
# 输出
1
2
3

示例二：从双链表中删除节点

node = doubly_linked_list.head.next
doubly_linked_list.delete_node(node)

打印链表：

doubly_linked_list.print_forward()
# 输出
1
3

栈实现方法示例

定义栈类

使用列表实现栈，包含以下三个方法：

1. __init__：初始化栈
2. push：入栈
3. pop：出栈

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            return None
        else:
            return self.stack.pop()

    def is_empty(self):
        return len(self.stack) == 0

栈方法示例

示例一：使用栈实现括号匹配

def is_parenthesis_balanced(parenthesis_string):
    stack = Stack()
    for char in parenthesis_string:
        if char in '({[':
            stack.push(char)
        else:
            if stack.is_empty():
                return False
            current_char = stack.pop()
            if current_char == '(':
                if char != ')':
                    return False
            if current_char == '{':
                if char != '}':
                    return False
            if current_char == '[':
                if char != ']':
                    return False
    if stack.is_empty():
        return True
    else:
        return False

print(is_parenthesis_balanced('{(a+b)*(c-d)}'))
# 输出
True

print(is_parenthesis_balanced('([a+b))'))
# 输出
False

示例二：使用栈实现十进制转二进制

def decimal_to_binary(decimal_number):
    stack = Stack()

    while decimal_number > 0:
        remainder = decimal_number % 2
        stack.push(remainder)
        decimal_number = decimal_number // 2

    binary_string = ""
    while not stack.is_empty():
        binary_string += str(stack.pop())

    return binary_string

print(decimal_to_binary(12345))
# 输出
'11000000111001'

队列实现方法示例

定义队列类

使用列表实现队列，包含以下三个方法：

1. __init__：初始化队列
2. enqueue：入队
3. dequeue：出队

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        if self.is_empty():
            return None
        else:
            return self.queue.pop(0)

    def is_empty(self):
        return len(self.queue) == 0

队列方法示例

示例一：使用队列实现烫手山芋游戏

def hot_potato(players, num):
    queue = Queue()
    for player in players:
        queue.enqueue(player)

    while queue.is_empty() is False:
        for i in range(n):
            queue.enqueue(queue.dequeue())

        eliminated_player = queue.dequeue()
        print('Player {} is eliminated'.format(eliminated_player))

        if queue.size() == 1:
            return queue.dequeue()

print(hot_potato(['John', 'Bob', 'Mike', 'Alice', 'Bill'], 4))
# 输出
Player Mike is eliminated
Player Alice is eliminated
Player Bob is eliminated
Player Bill is eliminated
John

示例二：使用队列进行BFS（广度优先搜索）

def bfs(graph, start_node):
    visited = []
    queue = Queue()

    visited.append(start_node)
    queue.enqueue(start_node)

    while not queue.is_empty():
        current_node = queue.dequeue()
        print(current_node)

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.append(neighbor)
                queue.enqueue(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')
# 输出
A
B
C
D
E
F

二叉树实现方法示例

定义二叉树节点类

定义二叉树节点，包含以下属性：

1. data：当前节点的数据
2. left_child：左子节点指针
3. right_child：右子节点指针

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

二叉树方法示例

示例一：插入节点到二叉树中

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

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

    def _insert(self, data, current):
        if data < current.data:
            if current.left_child is None:
                current.left_child = Node(data)
            else:
                self._insert(data, current.left_child)
        elif data > current.data:
            if current.right_child is None:
                current.right_child = Node(data)
            else:
                self._insert(data, current.right_child)
        else:
            print("The value is already present in the tree")

binary_tree = BinaryTree()
binary_tree.insert(6)
binary_tree.insert(10)
binary_tree.insert(3)
binary_tree.insert(4)
binary_tree.insert(5)
binary_tree.insert(8)
binary_tree.insert(2)

示例二：前序遍历二叉树

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

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

    def _insert(self, data, current):
        if data < current.data:
            if current.left_child is None:
                current.left_child = Node(data)
            else:
                self._insert(data, current.left_child)
        elif data > current.data:
            if current.right_child is None:
                current.right_child = Node(data)
            else:
                self._insert(data, current.right_child)
        else:
            print("The value is already present in the tree")

    def preorder_traversal(self):
        self._preorder_traversal(self.root)

    def _preorder_traversal(self, current):
        if current is not None:
            print(current.data)
            self._preorder_traversal(current.left_child)
            self._preorder_traversal(current.right_child)

binary_tree = BinaryTree()
binary_tree.insert(6)
binary_tree.insert(10)
binary_tree.insert(3)
binary_tree.insert(4)
binary_tree.insert(5)
binary_tree.insert(8)
binary_tree.insert(2)

binary_tree.preorder_traversal()
# 输出
6
3
2
4
5
10
8