数据结构(二)

**数据结构（二）**

在上一篇文章中，我们介绍了基本的数据结构，如数组、链表等。在本篇文章中，我们将继续讨论一些更复杂的数据结构，包括栈、队列、树和图。

###1. 栈栈是一种特殊的线性表，它遵循后进先出（LIFO）的原则。也就是说，在栈中最后添加的元素将在首先被移除。

####1.1 栈的定义栈可以用数组或链表来实现。栈中的元素都有一个索引，称为栈顶（top）。栈顶是栈中最新添加的元素。

####1.2 栈的操作栈支持以下几个基本操作：

* **push(x)**：将元素 x 添加到栈顶。
* **pop()**：移除栈顶元素，并返回该元素的值。
* **peek()**：返回栈顶元素的值，但不移除它。
* **isEmpty()**：检查栈是否为空。

####1.3 栈的实现我们可以使用链表来实现栈。每个结点都包含一个元素和一个指向下一个结点的指针。

class Node:
 def __init__(self, value):
 self.value = value self.next = Noneclass Stack:
 def __init__(self):
 self.top = None def push(self, value):
 node = Node(value)
 if self.top is None:
 self.top = node else:
 node.next = self.top self.top = node def pop(self):
 if self.isEmpty():
 raise IndexError("Stack is empty")
 value = self.top.value self.top = self.top.next return value def peek(self):
 if self.isEmpty():
 raise IndexError("Stack is empty")
 return self.top.value def isEmpty(self):
 return self.top is None

###2. 队列队列是一种特殊的线性表，它遵循先进先出（FIFO）的原则。也就是说，在队列中最先添加的元素将在首先被移除。

####2.1 队列的定义队列可以用数组或链表来实现。队列中的元素都有一个索引，称为队头（front）。队头是队列中最新添加的元素。

####2.2 队列的操作队列支持以下几个基本操作：

* **enqueue(x)**：将元素 x 添加到队尾。
* **dequeue()**：移除队首元素，并返回该元素的值。
* **peekFront()**：返回队首元素的值，但不移除它。
* **isEmpty()**：检查队列是否为空。

####2.3 队列的实现我们可以使用链表来实现队列。每个结点都包含一个元素和一个指向下一个结点的指针。

class Node:
 def __init__(self, value):
 self.value = value self.next = Noneclass Queue:
 def __init__(self):
 self.front = None self.rear = None def enqueue(self, value):
 node = Node(value)
 if self.isEmpty():
 self.front = self.rear = node else:
 self.rear.next = node self.rear = node def dequeue(self):
 if self.isEmpty():
 raise IndexError("Queue is empty")
 value = self.front.value self.front = self.front.next if self.front is None:
 self.rear = None return value def peekFront(self):
 if self.isEmpty():
 raise IndexError("Queue is empty")
 return self.front.value def isEmpty(self):
 return self.front is None

###3. 树树是一种特殊的数据结构，它由一组结点组成，每个结点都有一个值和零到多个子结点。

####3.1 树的定义树可以用链表或数组来实现。每个结点都包含一个值和一个指向子结点的指针。

####3.2 树的操作树支持以下几个基本操作：

* **insert(value)**：将元素 value 添加到树中。
* **search(value)**：查找树中是否存在元素 value。
* **delete(value)**：从树中移除元素 value。
* **preorder()**：输出树的前序遍历结果。
* **inorder()**：输出树的中序遍历结果。
* **postorder()**：输出树的后序遍历结果。

####3.3 树的实现我们可以使用链表来实现树。每个结点都包含一个值和一个指向子结点的指针。

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Noneclass Tree:
 def __init__(self):
 self.root = None def insert(self, value):
 node = Node(value)
 if self.isEmpty():
 self.root = node else:
 self._insert(node, self.root)

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

 def search(self, value):
 return self._search(value, self.root)

 def _search(self, value, root):
 if root is None or root.value == value:
 return True elif root.value < value:
 return self._search(value, root.right)
 else:
 return self._search(value, root.left)

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

 def _delete(self, value, root):
 if root is None or root.value == value:
 return root elif root.value < value:
 root.right = self._delete(value, root.right)
 else:
 root.left = self._delete(value, root.left)
 return root def preorder(self):
 self._preorder(self.root)

 def _preorder(self, root):
 if root is not None:
 print(root.value, end=" ")
 self._preorder(root.left)
 self._preorder(root.right)

 def inorder(self):
 self._inorder(self.root)

 def _inorder(self, root):
 if root is not None:
 self._inorder(root.left)
 print(root.value, end=" ")
 self._inorder(root.right)

 def postorder(self):
 self._postorder(self.root)

 def _postorder(self, root):
 if root is not None:
 self._postorder(root.left)
 self._postorder(root.right)
 print(root.value, end=" ")

 def isEmpty(self):
 return self.root is None

###4. 图图是一种特殊的数据结构，它由一组结点和边组成，每个结点都有一个值，边连接两个结点。

####4.1 图的定义图可以用链表或数组来实现。每个结点都包含一个值和一个指向邻居结点的指针。

####4.2 图的操作图支持以下几个基本操作：

* **insert(value)**：将元素 value 添加到图中。
* **search(value)**：查找图中是否存在元素 value。
* **delete(value)**：从图中移除元素 value。
* **preorder()**：输出图的前序遍历结果。
* **inorder()**：输出图的中序遍历结果。
* **postorder()**：输出图的后序遍历结果。

####4.3 图的实现我们可以使用链表来实现图。每个结点都包含一个值和一个指向邻居结点的指针。

class Node:
 def __init__(self, value):
 self.value = value self.neighbors = []

class Graph:
 def __init__(self):
 self.nodes = {}

 def insert(self, value):
 node = Node(value)
 self.nodes[value] = node def search(self, value):
 return value in self.nodes def delete(self, value):
 if value in self.nodes:
 del self.nodes[value]

 def preorder(self):
 for node in self.nodes.values():
 print(node.value, end=" ")
 for neighbor in node.neighbors:
 print(neighbor.value, end=" ")
 print()

 def inorder(self):
 for node in self.nodes.values():
 for neighbor in node.neighbors:
 print(neighbor.value, end=" ")
 print(node.value, end=" ")

 def postorder(self):
 for node in self.nodes.values():
 for neighbor in node