2.3.3 双链表

双链表和链表一样，只不过每个节点有两个链接——一个指向后一个节点，一个指向前一个节点。此外，除了第一个节点，双链表还需要记录最后一个节点。


每个结点为DLinkNode类对象，包括存储元素的列表data、存储前驱结点指针属性prior和后继结点的指针属性next。

（一）双链表基本运算
因为双链表知道自己的第一个节点和最后一个节点所在，所以访问它们都只需要1步，也就是需花O(1)时间。
因此，我们不仅能在O(1)时间内从双链表开头读取、插入和删除数据，还可以在O(1)时间内在其结尾完成相同的操作。

代码实现：

# 双链表结点类
class DLinkNode:def __init__(self, data=None):     	# 构造方法，data = None在某些情况下允许参数为空self.data = data                  	# data属性self.next = None                  	# next属性self.prior = None                 	# prior属性# 双链表类
class DLinkList:def __init__(self):               	# 构造方法self.dhead = DLinkNode()          	# 头结点dheadself.dhead.next = Noneself.dhead.prior = None# 头插法def CreateListF(self, a):# 遍历列表a中的元素for i in range(0, len(a)):# 创建结点s，并插入链表头s = DLinkNode(a[i])# 1. 修改新节点s的后继指针，让它指向头节点的第一个元素s.next = self.dhead.next# 2. 修改原头节点的后继节点的前驱指针（如果存在），让它指向新插入的节点sif self.dhead.next is not None:self.dhead.next.prior = s# 3. 修改头节点的后继指针，让它指向新的节点sself.dhead.next = s# 4. 修改新节点s的前驱指针，让它指向头节点s.prior = self.dhead# 尾插法def CreateListR(self, a):# t始终指向尾结点，开始时指向头结点t = self.dhead# 遍历列表a中的元素for i in range(0, len(a)):# 创建结点s，并插入链表尾s = DLinkNode(a[i])# 1. 修改尾节点t的后继指针t.next = s# 2. 修改s节点的前驱指针s.prior = t# 3. 更新t节点t = s# 遍历结束后，更新节点t的后继指针为空t.next = None# 查找元素def geti(self, i):p = self.dhead  # 从头节点开始j = -1  # 从头节点计数while p is not None and j < i:  # 遍历链表直到找到序号为 i 的节点p = p.nextj += 1return p  # 返回找到的节点（如果存在）# 插入元素# 在序号为 i 的位置插入元素def Insert(self, i, data):# 建立新节点 ss = DLinkNode(data)# 找到序号为 i-1 的节点 pp = self.geti(i - 1)# 检测 p 是否为空assert p is not None# 修改 s 节点的 next 属性，使其指向 p 的后继s.next = p.next# 如果 p 的后继节点不为空，修改后继节点的 prior 属性if p.next is not None:p.next.prior = s# 修改 p 节点的 next 属性，使其指向 sp.next = s# 修改 s 节点的 prior 属性，使其指向 ps.prior = p# 删除元素# 在线性表中删除序号 i 位置的元素def Delete(self, i):# 找到序号为 i 的节点 pp = self.geti(i)# 检查 p 是否为空，确保节点存在assert p is not None# 修改 p 的前驱节点的 next 指针，使其跳过 p，指向 p 的后继节点p.prior.next = p.next# 如果 p 的后继节点不为空，修改它的 prior 指针，使其指向 p 的前驱节点if p.next is not None:p.next.prior = p.prior# 示例数据
L = DLinkList()
L.CreateListF([1,2,3,4,5,6])
L.CreateListR([1,2,3,4,5,6])
L.Insert(3,8)
L.Delete(2)# 打印链表
node = L.dhead.next  # 跳过头节点
while node is not None:print(node.data, end = " ")node = node.next
print()

2.3.4 循环链表

循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。

循环单链表的插入和删除结点操作与非循环单链表的相同，所以两者的许多基本运算算法是相似的，主要区别如下：
初始只有头结点head，在循环单链表的构造方法中需要通过head.next=head语句置为空表。
循环单链表中涉及查找操作时需要修改表尾判断的条件，例如，用p遍历时，尾结点满足的条件是 p.next == head 而不是 p.next == None。

代码实现：

# 定义结点类
class LinkNode:def __init__(self, data = None):# data属性self.data = data# next属性self.next = None# 定义循环链表类
class CLinkList:def __init__(self):# 指定头结点self.head = LinkNode()# 初始化链表头结点，将链表置空self.head.next = self.head# 尾插法def CreateListR(self, a):# t始终指向尾结点，开始时指向头结点t = self.head# 遍历列表a中的元素for i in range(0, len(a)):# 创建结点s，并插入链表尾s = LinkNode(a[i])# 1. 修改尾节点t的后继指针t.next = s# 2. 更新t节点t = s# 遍历结束后，更新节点t的后继指针为头结点t.next = self.head# 查找元素def geti(self, i):p = self.head  # 从头节点开始j = -1  # 从头节点计数，头节点的索引为 -1，因为头节点不存储实际数据while p.next != self.head and j < i:  # 遍历链表直到找到序号为 i 的节点p = p.nextj += 1return p  # 返回找到的节点（如果存在）# 插入元素# 在序号为 i 的位置插入元素def Insert(self, i, data):# 建立新节点 ss = LinkNode(data)# 找到序号为 i-1 的节点 pp = self.geti(i - 1)# 检测 p 不为头结点if p.next != self.head:# 修改 s 节点的 next 属性，使其指向 p 的后继s.next = p.next# 修改 p 节点的 next 属性，使其指向 sp.next = s# 删除元素# 在线性表中删除序号 i 位置的元素def Delete(self, i):# 找到序号为 i-1 的节点 pp = self.geti(i - 1)# 检测 p 不为头结点if p.next != self.head:# 修改它的 next 指针，使其指向 p 的后继节点的后继结点p.next = p.next.next# 示例数据
L = CLinkList()
L.CreateListR([1,2,3,4,5,6])
L.Insert(3,8)
L.Delete(2)# 打印链表
node = L.head.next  # 跳过头节点
while node != L.head:print(node.data, end = " ")node = node.next
print()

习题

6.有一个递增有序的整数顺序表 L，设计一个算法将整数 x 插入适当位置，以保持该表的有序性，并给出算法的时间和空间复杂度。
例如，L = (1, 3, 5, 7)，插入 x = 6 后，L = (1, 3, 5, 6, 7)。

算法思路：
从头到尾遍历顺序表 L，找到第一个比 x 大的元素，将 x 插入到该元素之前。
如果 x 比所有元素都大，则将其插入到表的末尾。

def insert_ordered(L, x):# 从头遍历顺序表，找到第一个比 x 大的元素位置for i in range(len(L)):if L[i] > x:L.insert(i, x)  # 插入到该位置return L# 如果 x 比所有元素都大，插入到最后L.append(x)return L# 示例
L = [1, 3, 5, 7]
x = 6
print(insert_ordered(L, x))  # 输出: [1, 3, 5, 6, 7]

时间复杂度为O(n)，空间复杂度为O(1)。

算法思路:
使用二分查找找到要插入的位置。
将 x 插入到该位置，保持顺序表的有序性。

def insert_ordered_binary(L, x):# 初始化二分查找的左右边界left, right = 0, len(L) - 1# 二分查找，找到插入位置while left <= right:mid = (left + right) // 2if L[mid] < x:left = mid + 1  # 插入位置在右侧else:right = mid - 1  # 插入位置在左侧# 插入 x 到合适的位置L.insert(left, x)return L# 示例
L = [1, 3, 5, 7]
x = 6
print(insert_ordered_binary(L, x))  # 输出: [1, 3, 5, 6, 7]

时间复杂度为O(n)，空间复杂度为O(1)。

7. 有一个整数顺序表 L，设计一个尽可能高效的算法删除其中所有值为负整数的元素（假设 L 中有负整数的元素可能有多个），删除后元素的相对次序不改变，
   并给出算法的时间和空间复杂度。例如，L = (1, 2, -1, -2, 3, -3)，删除后 L = (1, 2, 3)。

算法思路：
遍历顺序表，使用一个新的列表存储非负整数元素。
将原表中所有非负整数按顺序放入新列表，最后用新列表覆盖原列表。

def remove_negatives(L):# 使用列表推导式保留非负整数L = [item for item in L if item >= 0]return L# 示例
L = [1, 2, -1, -2, 3, -3]
print(remove_negatives(L))  # 输出: [1, 2, 3]

时间复杂度为O(n)，空间复杂度为O(n)。

8.有一个整数顺序表 L，设计一个尽可能高效的算法将所有负整数的元素移到其他元素的前面，并给出算法的时间和空间复杂度。
例如，L = (1, 2, -1, -2, 3, -3, 4)，移动后 L = (-1, -2, -3, 1, 2, 3, 4)。

思路：
使用两个指针 i 和 j。其中 i 用于遍历整个列表，j 用于记录负数应该放的位置。
如果 L[i] 是负数，将其与 L[j] 交换，并将 j 向右移动一位。
遍历完列表后，负数已经排在前面，非负数排在后面。

def move_negatives_to_front(L):j = 0  # 记录负数应放的位置# 遍历数组for i in range(len(L)):if L[i] < 0:  # 如果是负数# 交换 L[i] 和 L[j]，将负数移动到前面L[i], L[j] = L[j], L[i]j += 1return L# 示例
L = [1, 2, -1, -2, 3, -3, 4]
result = move_negatives_to_front(L)
print(result)  # 输出: [-1, -2, -3, 1, 2, 3, 4]

时间复杂度为O(n)，空间复杂度为O(1)。

15题
使用两个指针：prev 用于指向当前节点的前驱节点，curr 用于指向当前节点。
遍历链表，检查当前节点 curr 的值：
如果 curr.data == x，则将 prev.next 指向 curr.next，从而跳过并删除当前节点 curr。
如果 curr.data != x，则将 prev 移动到 curr，继续遍历。
重复以上步骤，直到遍历完链表。

class Node:def __init__(self, data=None):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None# 删除链表中所有值为 x 的节点def remove_all(self, x):# 处理头节点为 x 的情况while self.head and self.head.data == x:self.head = self.head.next# 遍历链表删除值为 x 的节点prev, curr = None, self.headwhile curr:if curr.data == x:prev.next = curr.nextelse:prev = currcurr = curr.next# 添加节点到链表尾部def append(self, data):new_node = Node(data)if self.head is None:self.head = new_nodeelse:last = self.headwhile last.next:last = last.nextlast.next = new_node# 打印链表def print_list(self):curr = self.headwhile curr:print(curr.data, end=" ")curr = curr.nextprint()# 示例
L = LinkedList()
L.append(1)
L.append(2)
L.append(3)
L.append(1)
L.remove_all(1)
L.print_list()  # 输出: 2 3

时间复杂度为O(n)，空间复杂度为O(1)。

16题
遍历链表，并且把每个负数节点插入到链表头部，这样遍历完之后，所有负数就会排在前面，其他元素顺序不变。
使用指针 curr 遍历链表。
如果 curr.data < 0（即当前节点为负数），则将其移到链表头部。
如果不是负数，则继续遍历。

class Node:def __init__(self, data=None):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None# 将负整数移到链表前面def move_negatives_to_front(self):if not self.head or not self.head.next:return  # 空链表或只有一个节点curr = self.headprev = Nonewhile curr and curr.next:if curr.next.data < 0:# 把负数节点移到链表头部temp = curr.nextcurr.next = temp.nexttemp.next = self.headself.head = tempelse:curr = curr.next# 添加节点到链表尾部def append(self, data):new_node = Node(data)if self.head is None:self.head = new_nodeelse:last = self.headwhile last.next:last = last.nextlast.next = new_node# 打印链表def print_list(self):curr = self.headwhile curr:print(curr.data, end=" ")curr = curr.nextprint()# 示例
L = LinkedList()
L.append(1)
L.append(2)
L.append(-1)
L.append(-2)
L.append(3)
L.append(-3)
L.append(4)
L.move_negatives_to_front()
L.print_list()  # 输出: -3 -2 -1 1 2 3 4

时间复杂度为O(n)，空间复杂度为O(1)。

17题
遍历链表 A 并将所有元素加入到并集 C 中。
遍历链表 B，对于 B 中的每个元素，如果它不在链表 C 中，将其添加到链表 C 中。
我们可以使用辅助函数来判断链表中是否已经包含某个元素。

class Node:def __init__(self, data=None):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None# 判断链表中是否包含某个元素def contains(self, value):curr = self.headwhile curr:if curr.data == value:return Truecurr = curr.nextreturn False# 添加元素到链表尾部def append(self, data):new_node = Node(data)if self.head is None:self.head = new_nodeelse:last = self.headwhile last.next:last = last.nextlast.next = new_node# 打印链表def print_list(self):curr = self.headwhile curr:print(curr.data, end=" ")curr = curr.nextprint()# 计算两个链表的并集def union(self, B):C = LinkedList()# 添加 A 中的所有元素到 Ccurr = self.headwhile curr:C.append(curr.data)curr = curr.next# 添加 B 中的元素，如果 C 中不包含它curr = B.headwhile curr:if not C.contains(curr.data):C.append(curr.data)curr = curr.nextreturn C# 示例
A = LinkedList()
A.append(1)
A.append(3)
A.append(2)B = LinkedList()
B.append(5)
B.append(1)
B.append(4)
B.append(2)C = A.union(B)
C.print_list()  # 输出: 1 3 2 5 4

时间复杂度为O(n+m)，空间复杂度为O(n+m)。

第三章 栈和队列

本章将学习两种新的数据结构：栈和队列。其实它们对你来说并不陌生。栈和队列也是线性表的一种，本质上都是数组，只不过有一些限制。但这些限制正是他们的优点。
具体来说，栈和队列是处理临时数据的优雅方法。无论是操作系统架构，还是打印队列，抑或是遍历数据，都可以使用栈和队列作为临时容器。
你可以把临时数据想象成餐馆的点单。在上菜之后，顾客点了什么就无所谓了。你大可以把单子扔掉，无须一直保存这份信息。临时数据是那些在处理后就不再重要的数据，用过之后即可丢弃。栈和队列正是处理这种临时数据的数据结构。不过你会发现，它们对于数据的顺序有着特别的要求。

3.1 栈

生活中的栈

存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如我们现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈。

计算机中的栈

我们把生活中的栈的概念引入到计算机中，就是供数据休息的地方，它是一种数据结构，数据既可以进入到栈中，又可以从栈中出去。
栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。

3.1.1 栈的定义

栈的定义

栈（stack）是一种只能在同一端进行插入或删除操作的线性表。
表中允许进行插入、删除操作的一端称为栈顶（top），表的另一端称为栈底（bottom）。
栈的插入操作通常称为进栈或入栈（push），栈的删除操作通常称为退栈或出栈（pop）。

栈的特点：

后进先出，即后进栈的元素先出栈。
每次进栈的元素都作为新栈顶元素，每次出栈的元素只能是当前栈顶元素。
你可以把栈想象成一叠盘子。你只能看到最上面的一个盘子。同理，你只能往最上面放盘子，而且不能从下面拿盘子。​（至少不应该这样做。​）

示例：

一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）。
A.edcba
B.decba
C.dceab
D.abcde
答案：C
解析：方法一：用栈模拟，不可能有出栈序列ab，因此选C。
方法二：利用判断准则：输入序列为1，2，…，n，（p1，p2，…，pn）是1，2，…，n 的一种排列，利用一个栈得到输出序列（p1，p2，…，pn）的充分必要条件是不存在这样的i、j、k 满足i<j<k 的同时也满足pj<pk<pi 。

$1$~$n$共产生$\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$种合法出栈序列。
合法出栈序列：对于 $1,2,\dots ,n$ 这些元素，按顺序依次入栈，在任何时刻，出栈的元素顺序必须满足栈的“后进先出”（LIFO）规则。
一个合法的出栈序列意味着，在整个入栈和出栈的过程中，出栈的数量不能超过已入栈的数量。
比如：不能在没有入栈的情况下尝试出栈。
推导过程：
Step 1：入栈与出栈的路径匹配
每一个入栈操作可以看作“向右走一步”，每一个出栈操作可以看作“向上走一步”。
总共需要 𝑛 次入栈和 𝑛次出栈，因此一共是 2𝑛 步。
Step 2：合法路径的条件
在任何时候，出栈的次数不能超过入栈的次数。这相当于在一个二维平面上，从 (0, 0) 点开始，每一步要么向右走，要么向上走，但路径不能越过主对角线（即不能出现更多的出栈操作超过已入栈的次数）。
Step 3：卡特兰数的计算
所有不受限制的路径数是 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$（即从 2n 步中选择 n 步向上走的方案数）。
但我们需要排除那些越过主对角线的非法路径。通过一些高等组合学方法可以证明，合法路径的数量正好是：$\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$。

练习题：

1.已知一个栈的进栈序列是1，2，3，…，n，其输出序列是p1，p2，…，pn，若p1=n，则pi 的值为（ ）。
A.i
B.n-i
C.n-i+1
D.不确定
答案：C
解析：输出序列唯一：n，…，3，2，1
2.一个栈的入栈序列为1,2,3, …,n ，其出栈序列是p1,p2,p3,…,pn。若p2=3，则p3可能取值的个数是（ ）。
A.n-3
B.n-2
C.n-1
D.无法确定
答案：C
解析：p3除了3外都可能。

3.1.2 栈的顺序存储结构及其基本运算算法实现

# 顺序栈类
class SqStack:def __init__(self):self.data = []    # 存放栈中元素# 判断栈是否为空def empty(self):if len(self.data) == 0:return Truereturn False# 进栈def push(self,data):self.data.append(data)# 出栈def pop(self):assert not self.empty()return self.data.pop()# 取栈顶元素def gettop(self):assert not self.empty()return self.data[-1]# return self.data[len(data)-1]# 主程序
if __name__ == "__main__":sq = SqStack()# 判断栈是否为空sq.empty()# 进栈sq.push('a')sq.push('b')sq.push('c')# 打印顺序栈print(sq.data)# 获取栈顶元素print(sq.gettop())# 出栈print(sq.pop())print(sq.pop())print(sq.pop())

3.1.3 栈的链式存储结构及其基本运算算法实现

# 链栈结点
class LinkNode:def __init__(self, data = None):self.data = data    # data属性self.next = None    # next属性# 链栈类
class LinkStack:def __init__(self):self.head = LinkNode()    # 头结点self.head.next = None     # 初始化链栈头结点，将链栈置空# 判断栈是否为空def empty(self):if self.head.next == None:return Truereturn False# 进栈def push(self, data):p = LinkNode(data)p.next = self.head.nextself.head.next = p# 出栈def pop(self):assert self.head.next is not Nonep = self.head.nextself.head.next = p.nextreturn p.data# 取栈顶元素def gettop(self):assert self.head.next is not Nonereturn self.head.next.dataif __name__ == "__main__":stack = LinkStack()# 判断栈是否为空stack.empty()# 进栈stack.push('d')stack.push('e')stack.push('f')# 打印链栈node = stack.head.nextwhile node is not None:print(node.data, end= " ")node = node.nextprint()# 获取栈顶元素print(stack.gettop())# 出栈print(stack.pop())print(stack.pop())print(stack.pop())

例题

例3.4 设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对（假设表达式中可能含有圆括号、中括号和大括号）。并用相关数据进行测试。

算法设计:
使用栈（Stack）来检查括号是否配对：
1.遇到左括号（(、[、{）时，将它压入栈。
2.遇到右括号（)、]、}）时，检查栈顶是否是与该右括号匹配的对应左括号：

 如果匹配，弹出栈顶元素。如果不匹配，表达式不合法。

3.遍历完整个表达式后，如果栈为空，表示所有括号匹配正确；否则表示有未匹配的括号。

from Data_S_ch3_Stack import SqStack
def isMatch(expression):# 创建顺序栈st = SqStack()# 初始化指针 i ，i 遍历 expressioni = 0# 遍历 expression 中的元素，匹配表达式中的括号while i < len(expression):data = expression[i]if data == '(' or data == '[' or data == '{':st.push(data)else:if data == ')':# 如果栈为空，或者栈顶元素不匹配当前括号，返回 Falseif st.empty() or st.gettop() != '(':return Falsest.pop()if data == ']':if st.empty() or st.gettop() != '[':return Falsest.pop()if data == '}':if st.empty() or st.gettop() != '{':return Truest.pop()i += 1# 最后判断栈是否为空，若为空则所有括号匹配成功return st.empty()# 主程序
expressions = ["(a + b) * [c - d]",         # 合法"{a + [b * (c - d)]}",       # 合法"[{(a + b) * c} - d]",       # 合法"(a + b] * {c - d}",         # 不合法，括号不匹配"(a + b) * [c - d",          # 不合法，缺少右括号"[(])",                      # 不合法，顺序错误
]for expr in expressions:result = isMatch(expr)print(f"表达式: {expr} -> {'合法' if result else '不合法'}")

例3.5 设计一个算法利用顺序栈判断用户输入的字符串表达式是否为回文。并用相关数据进行测试。

算法设计：
1.用 i 从头开始遍历 str，将前半部分字符依次进栈。
2.若 n 为奇数，i 增加1跳过中间的字符。
3. i 继续遍历其他后半部分字符，每访问一个字符，则出栈一个字符，两者进行比较，若不相等返回 False。
4.当 str 遍历完毕返回 True。

from Data_S_ch3_Stack import SqStack
def isPalindrome(str):# 建立顺序栈st = SqStack()n = len(str)# 用指针 i 遍历 str ，将 str 的前半部分字符进栈for i in range(n // 2):st.push(str[i])# 如果字符串长度为奇数，跳过中间字符start = (n // 2) + (n % 2)# 从字符串的后半部分开始遍历，与栈顶元素逐一比较，若不相等返回 Falsefor i in range(start, n):if st.empty() or st.pop() != str[i]:return False# 如果栈为空，说明匹配成功return st.empty()# 主程序
test_strings = ["madam",    # 回文"level",    # 回文"racecar",  # 回文"hello",    # 非回文"abcba",    # 回文"abca",     # 非回文
]# 遍历测试每个字符串
for str in test_strings:result = isPalindrome(str)print(f"字符串 '{str}' -> {'是回文' if result else '不是回文'}")

例3.8 设计一个算法利用栈的基本运算将一个整数链栈中所有元素逆置。
例如链栈st中元素从栈底到栈顶为（1，2，3，4），逆置后为（4，3，2，1）。

算法设计：
利用数组来反转顺序：
将链栈 st 的所有元素依次弹出，保存在数组 a 中。
然后再将数组 a 中的元素，依次压回原链栈 st，此时顺序已经被反转。

from Data_S_ch3_Stack import LinkStack
def Reverse(st):# 初始化数组 aa = []# 将出栈的元素放到列表 a 中while not st.empty():a.append(st.pop())# 将列表 a 的所有元素进栈for j in range(len(a)):st.push(a[j])return st# 主程序
# 初始化链栈，并压入元素 1, 2, 3, 4
st = LinkStack()
st.push(1)
st.push(2)
st.push(3)
st.push(4)print("逆置前：")
node = st.head.next
while node is not None:print(node.data, end=" ")node = node.next
print()     # 输出：栈内容（从栈顶到栈底）： [4, 3, 2, 1]# 逆置链栈
Reverse(st)print("逆置后：")
node = st.head.next
while node is not None:print(node.data, end=" ")node = node.next
print()      # 输出：栈内容（从栈顶到栈底）： [1, 2, 3, 4]

例3.9 有一个含1～n的n个整数的序列a，通过一个栈可以产生多种出栈序列，
设计一个算法采用链栈判断序列b（为1～n的某个排列）是否为一个合适的出栈序列，并用相关数据进行测试。

思路分析
模拟栈的操作：
1.只能按顺序从序列 a 中入栈。
2.栈顶元素可以随时弹出，构成序列 b。
3.如果序列 b 不是合法的出栈序列，即某一步操作无法通过栈顶元素匹配得到，就返回 False。

算法设计
使用一个链栈来模拟入栈、出栈的过程：
1.遍历序列 b，将 a 中的元素逐个入栈。
2.每次入栈后检查，如果栈顶元素等于 b 中的当前元素，则执行出栈操作，直到无法匹配为止。
3.最后判断：如果成功匹配所有的 b 中元素，则 b 是合法的出栈序列；否则不是。

from Data_S_ch3_Stack import LinkStack
def isSerial(a, b):"""判断序列 b 是否是序列 a 的一个合法出栈序列:param a: 输入序列（1 到 n 的递增序列）:param b: 出栈序列（为 1 到 n 的某个排列）:return: True 表示合法，False 表示不合法"""# 初始化链栈st = LinkStack()# 初始化指针 i 和 j ，i 遍历 a， j 遍历 bi , j = 0, 0# 遍历序列 a，并尝试匹配 b 中的元素while i < len(a):st.push(a[i])i += 1# 如果栈顶元素等于 b[j]，弹出栈顶元素，匹配下一个 b[j]while not st.empty() and st.gettop() == b[j]:st.pop()j += 1# 如果成功匹配完 b 中的所有元素，则返回 True，否则返回 Falsereturn st.empty()# 主程序
# 初始化输入序列 a
a = [1, 2, 3, 4]# 合法的出栈序列
b1 = [4, 3, 2, 1]
b2 = [2, 1, 4, 3]
b3 = [1, 3, 4, 2]# 非法的出栈序列
b4 = [3, 1, 2, 4]# 测试合法性
if isSerial(a, b1):print(b1, "是合法的出栈序列")
else:print(b1, "不是合法的出栈序列")if isSerial(a, b2):print(b2, "是合法的出栈序列")
else:print(b2, "不是合法的出栈序列")if isSerial(a, b3):print(b3, "是合法的出栈序列")
else:print(b3, "不是合法的出栈序列")if isSerial(a, b4):print(b4, "是合法的出栈序列")
else:print(b4, "不是合法的出栈序列")

3.1.4 栈的应用——表达式求值

中缀表达式：仅包含“+”、“-”、“*”、“/”、正整数和小括号的合法数学表达式—中缀表达式。例如： (56-20)/(4+2)
后缀表达式：就是运算符在操作数的后面，已经考虑了运算符的优先级，不包含括号，只含操作数和运算符。也称为逆波兰表达式（RPN）。不需要考虑运算优先级和括号，按照从左到右的顺序依次计算即可。例如：56,20,’-’,4,2,’+’,’/’
表达式求值过程:

1. 将表达式exp转换成后缀表达式postexp。
2. 对该后缀表达式求值。

将表达式exp转换成后缀表达式postexp转换规则：

1. 操作数直接加入后缀表达式（postfix）。
2. 左括号直接入栈，用来标记开始处理括号中的内容。
3. 右括号：弹出栈中元素直到遇到左括号 (。
4. 运算符：
   - 如果栈为空或栈顶为左括号，则直接入栈。
   - 如果当前运算符优先级高于栈顶运算符，则入栈。
   - 如果当前运算符优先级低于或等于栈顶运算符，则弹出栈顶运算符并加入后缀表达式，然后将当前运算符入栈。
5. 字符串扫描完毕,则退栈opor的所有运算符并存放到postexp中

后缀表达式postexp求值,计算规则：

1. 遇到数字：将数字压入栈中。
2. 遇到运算符：从栈中弹出两个数字，计算结果后将结果压入栈中。
   - 注意：栈是后进先出（LIFO），所以先弹出的数字是右操作数，后弹出的是左操作数。
3. opand栈中唯一的数值即为表达式值

练习题：

若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：
（1）从S1中依次弹出两个操作数a和b；
（2）从S2中弹出一个运算符op；
（3）执行相应的运算b op a；
（4）将运算结果压入S1中。
假定S1中的操作数依次是5，8，3，2（2在栈顶），S2中的运算符依次是*，-，+（+在栈顶）。调用3次F()后，S1栈顶保存的值是（ ）。
A.-15
B.15
C.-20
D.20
答案：B
解析：第一次调用 F()：从 S1 中弹出 2 和 3。从 S2 中弹出 +。计算：3 + 2 = 5。将 5 压入 S1。
第二次调用 F()：从 S1 中弹出 5 和 8。从 S2 中弹出 -。计算：8 - 5 = 3。将 3 压入 S1。
第三次调用 F()：从 S1 中弹出 3 和 5。从 S2 中弹出 *。计算：5 * 3 = 15。将 15 压入 S1。
此时S1中的操作数为15，栈顶值为15。

假设栈初始为空，将中缀表达式a/b+(cd-ef)/g转换为等价的后缀表达式的过程中， 当扫描到f时，栈中的元素依次是（ ）。
A．+ ( * -
B．+ ( - *
C．/ + ( * - *
D．/ + - *
答案：B
解析： 遇到 a，直接加入后缀表达式，因为是操作数。后缀表达式：a。栈：空。
遇到 /，运算符 / 入栈。后缀表达式：a。栈：[/]。
遇到 b，直接加入后缀表达式，因为是操作数。后缀表达式：a b。栈：[/]。
遇到 +，弹出 / 并加入后缀表达式，因为 / 的优先级高于 +。然后 + 入栈。后缀表达式：a b /。栈：[+]。
遇到 (，左括号直接入栈，用于处理括号内的表达式。后缀表达式：a b /。栈：[+, (]。
遇到 c，直接加入后缀表达式，因为是操作数。后缀表达式：a b / c。栈：[+, (]。
遇到 *，运算符 * 入栈，因为括号内的运算符优先。后缀表达式：a b / c。栈：[+, (, *]。
遇到 d，直接加入后缀表达式，因为是操作数。后缀表达式：a b / c d。栈：[+, (, *]。
遇到 -，弹出 * 并加入后缀表达式，然后 - 入栈。后缀表达式：a b / c d *。栈：[+, (, -]。
遇到 e，直接加入后缀表达式，因为是操作数。后缀表达式：a b / c d * e。栈：[+, (, -]。
遇到 *，运算符 * 入栈，因为 * 的优先级高于减号。后缀表达式：a b / c d * e。栈：[+, (, -, *]。
遇到 f，此时的栈状态为：[+, (, -, *]。

代码实现:

# 设计表达式求值的类
class ExpressClass:# 构造方法def __init__(self, str):self.exp = str    # 存放中缀表达式self.postexp = [] # 存放后缀表达式# 返回后缀表达式def getpostexp(self):return self.postexp# 将中缀表达式转换为后缀表达式def Trans(self):precedence = {'+': 1, '-': 1, '*': 2, '/': 2}  # 运算符优先级# 初始化运算符栈opor = SqStack()  # 运算符栈，用于存储运算符和括号# 遍历表达式 exp 的每个字符i = 0  # 初始化索引 i，用于遍历表达式while i < len(self.exp):ch = self.exp[i]  # 提取当前字符# 处理左括号 (，左括号直接入栈if ch == "(":opor.push(ch)# 右括号处理：弹出到左括号为止elif ch == ")":while not opor.empty() and opor.gettop() != "(":e = opor.pop()  # 弹出栈顶运算符self.postexp.append(e)  # 加入到后缀表达式中opor.pop()  # 弹出左括号 "("# 运算符处理elif ch in precedence:while (not opor.empty() and opor.gettop() != '(' andprecedence[opor.gettop()] >= precedence[ch]):self.postexp.append(opor.pop())opor.push(ch)  # 当前运算符入栈# 处理数字字符else:d = ""  # 存储连续的数字字符while ch >= "0" and ch <= "9":  # 判断是否为数字d += ch  # 连续数字可能由多位组成，因此我们拼接所有连续的数字字符i += 1  # 移动到下一个字符if i < len(self.exp):ch = self.exp[i]  # 获取下一个字符else:breaki -= 1  # 回退索引，防止多读字符self.postexp.append(int(d))  # 将拼接的数字转为整数加入后缀表达式i += 1  # 处理下一个字符# 处理完表达式后，弹出栈中所有运算符while not opor.empty():e = opor.pop()self.postexp.append(e)  # 加入到后缀表达式中# 计算后缀表达式的值def getValue(self):'''后缀表达式的求值逻辑：使用栈存储操作数。遇到运算符时，从栈中弹出两个操作数进行计算，并将结果压回栈中。最终栈中只剩下一个元素，即为表达式的计算结果。'''opand = SqStack()  # 运算数栈i = 0  # 初始化索引 i# 遍历后缀表达式中的每个元素while i < len(self.postexp):opv = self.postexp[i]  # 获取当前元素# 如果是加号 +if opv == "+":a = opand.pop()  # 右操作数b = opand.pop()  # 左操作数c = b + a  # 计算 b + aopand.push(c)  # 将结果压入栈# 如果是减号 -elif opv == "-":a = opand.pop()  # 右操作数b = opand.pop()  # 左操作数c = b - a  # 计算 b - aopand.push(c)  # 将结果压入栈# 如果是乘号 *elif opv == "*":a = opand.pop()  # 右操作数b = opand.pop()  # 左操作数c = b * a  # 计算 b * aopand.push(c)  # 将结果压入栈# 如果是除号 /elif opv == "/":a = opand.pop()  # 右操作数b = opand.pop()  # 左操作数c = int(b / a)  # 计算 b / a，向零取整opand.push(c)  # 将结果压入栈else:  # 如果是操作数，直接压入栈opand.push(int(opv))i += 1  # 处理下一个元素# 最后栈中只剩一个元素，即计算结果return opand.pop()#  主程序
str="(56-20)/(4*3+2)"
print("中缀表达式: "+str)
obj = ExpressClass(str)
obj.Trans()
print("后缀表达式:", obj.getpostexp())
print("求值结果: %d" % (obj.getValue()))

3.2 队列

3.2.1 队列的定义

队列的定义

队列（queue）是一种只能在不同端进行插入或删除操作的线性表。
进行插入的一端称做队尾（rear），进行删除的一端称做队头或队首（front）。
队列的插入操作通常称为进队或入队（push），队列的删除操作通常称为出队或离队（pop）。

队列的特点：

先进先出，即先进队的元素先出队。
每次进队的元素作为新队尾元素，每次出队的元素只能是队头的元素。

3.2.2 队列的顺序存储结构及其基本运算算法实现

1. 非循环队列

初始时置front和rear均为-1（front==rear）
元素进队，rear增加1
元素出队列，front增加1

# 全局变量，假设容量为100
MaxSize = 100
# 非循环队列类
class SqQueue:def __init__(self):# 存放队列中的元素self.data = [None] * MaxSize# 队头指针self.front = -1# 队尾指针self.rear = -1# 判断队列是否为空def empty(self):return self.front == self.rear# 进队def push(self, data):assert not self.rear == MaxSize - 1  # 检测队满self.rear += 1self.data[self.rear] = data# 出队def pop(self):assert not self.empty()  # 检测队空self.front += 1return self.data[self.front]# 取队头元素def gethead(self):assert not self.empty()  # 检测队空return self.data[self.front + 1]# 主程序
if __name__ =="__main__":# 创建队列对象queue = SqQueue()# 示例数据queue.push(10)queue.push(20)queue.push(30)print("队头元素:", queue.gethead())  # 应输出 10print("出队:", queue.pop())  # 应输出 10print("队头元素:", queue.gethead())  # 应输出 20print("出队:", queue.pop())  # 应输出 20queue.push(40)print("队头元素:", queue.gethead())  # 应输出 30print("出队:", queue.pop())  # 应输出 30print("队头元素:", queue.gethead())  # 应输出 40

2. 循环队列

定义:
把data数组的前端和后端连接起来，形成一个循环数组，即把存储队列元素的表从逻辑上看成一个环，称为循环队列（也称为环形队列）。

特点:
循环队列允许元素在队尾插入，在队头删除，同时遵循先进先出原则。
由于循环队列是基于数组实现的，所以它的访问速度很快，特别是在移动元素时。
如果需要大量添加和删除元素，循环队列比链表更有效率，因为它不需要频繁地移动指针来访问元素。
不支持随机访问元素，因此不能像数组那样直接访问特定位置的元素。

判断队空队满的方法：
保留一个空位法：即始终保持队列中至少有一个空位，以区分队列满和队列空。例如，当 rear 的下一个位置是 front 时，表示队列已满，而当 front == rear 时，表示队列为空。可以用rear=(rear+1)％MaxSize表示。
增加一个计数器：使用一个计数器来记录当前队列中的元素个数，而不依赖于 front 和 rear 指针的位置关系来判断队列是否已满或为空。
队列的大小是固定的，一旦创建后不能改变。

# 全局变量，假设容量为100
MaxSize = 100# 循环队列类
class CSqQueue:def __init__(self):self.data = [None] * MaxSize  # 存放队列中元素# 队头指针self.front = 0# 队尾指针self.rear = 0# 判断队列是否为空def empty(self):return self.front == self.rear# 进队def push(self, data):assert (self.rear + 1) % MaxSize != self.front  # 检测队满self.rear = (self.rear + 1) % MaxSize     # 更新队尾self.data[self.rear] = data   # 插入元素到队尾# 出队def pop(self):assert not self.empty()   # 检测队空self.front = (self.front + 1) % MaxSize    # 更新队头return self.data[self.front]    # 返回队头元素# 取队头元素def gethead(self):assert not self.empty()   # 检测队空return self.data[(self.front + 1) % MaxSize]   # 返回队头元素# 计算队列元素个数def size(self):return ((self.rear - self.front + MaxSize) % MaxSize)# 主程序
if __name__ =="__main__":# 创建循环队列对象queue = CSqQueue()# 示例数据插入queue.push(10)queue.push(20)queue.push(30)# 队列操作print("队头元素:", queue.gethead())  # 应输出 10print("出队:", queue.pop())  # 应输出 10print("队头元素:", queue.gethead())  # 应输出 20print("出队:", queue.pop())  # 应输出 20queue.push(40)  # 插入 40print("队头元素:", queue.gethead())  # 应输出 30print("出队:", queue.pop())  # 应输出 30print("队头元素:", queue.gethead())  # 应输出 40print("出队:", queue.pop())  # 应输出 40

3.2.3 队列的链式存储结构及其基本运算算法实现

# 链队
# 定义结点类
class LinkNode:def __init__(self, data = None):self.data = data    # data属性self.next = None    # next属性# 链队类
class LinkQueue:def __init__(self):# 队头指针self.front = None# 队尾指针self.rear = None# 判断链队是否为空def empty(self):return self.front == None# 进队def push(self, data):s = LinkNode(data)   # 创建新结点# 原链队为空if self.empty():self.front = self.rear = s# 原链队不为空else:self.rear.next = s   # 将 s 结点链接到 rear 结点后面self.rear = s        # 更新尾结点# 出队def pop(self):assert not self.empty()  # 检测队空# 原链队只有一个结点,取首结点值,原链队置空if self.front == self.rear:data = self.front.dataself.front = self.rear = None# 原链队有多个结点,取首结点值, front 指向下一个结点else:data = self.front.dataself.front = self.front.next# 返回首结点值return data# 取队头元素def gethead(self):assert not self.empty()   # 检测队空data = self.front.data    # 取首结点的值return data               # 返回首结点# 主程序
if __name__  == "__main__":# 示例数据插入print("进队操作:")queue.push(10)print("进队 10")queue.push(20)print("进队 20")queue.push(30)print("进队 30")queue.push(40)print("进队 40")# 获取队头元素print("\n队头元素:", queue.gethead())  # 应输出: 10# 出队操作print("\n出队操作:")print("出队:", queue.pop())  # 应输出: 10print("出队:", queue.pop())  # 应输出: 20# 查看队头元素print("\n队头元素:", queue.gethead())  # 应输出: 30# 插入新元素queue.push(50)print("\n进队 50")# 出队操作print("\n出队操作:")print("出队:", queue.pop())  # 应输出: 30print("出队:", queue.pop())  # 应输出: 40print("出队:", queue.pop())  # 应输出: 50# 检查队列是否为空print("\n队列是否为空:", queue.empty())  # 应输出: True

3.2.4 双端队列

双端队列是在队列基础上扩展而来的，其示意图如下图所示。

双端队列与队列一样，元素的逻辑关系也是线性关系，但队列只能在一端进队，另外一端出队，而双端队列可以在两端进行进队和出队操作，具有队列和栈的特性，因此使用更加灵活。

Python提供了一个集合模块collections，里面封装了多个集合类，其中包括 deque 即双端队列（double-ended queue）。

1. 创建双端队列

qu=deque() # 创建一个空的双端队列qu
qu=deque(maxlen=N) # 创建一个固定长度为N的双端队列qu
qu=deque(L) # 创建的双端队列qu中包含列表L中的元素

2. 双端队列的方法

deque.clear()：清除双端队列中的所有元素。
deque.append(x)：在双端队列的右端添加元素x。时间复杂度为O(1)。
deque.appendleft(x)：在双端队列的左端添加元素x。时间复杂度为O(1)。
deque.pop()：在双端队列的右端出队一个元素。时间复杂度为O(1)。
deque.popleft()：在双端队列的左端出队一个元素。时间复杂度为O(1)。
deque.remove(x)：在双端队列中删除首个和x匹配的元素（从左端开始匹配的），如果没有找到抛出异常。时间复杂度为O(n)。
deque.count(x)：计算双端队列中元素为x的个数。时间复杂度为O(n)。
deque.extend(L)：在双端队列的右端添加列表L的元素。例如，qu为空，L=[1，2，3]，执行后qu从左向右为[1，2，3]。
deque.extendleft(L)：在双端队列的左端添加列表L的元素。例如，qu为空，L=[1，2，3]，执行后qu从左向右为[3，2，1]。
deque.reverse()：把双端队列里的所有元素的逆置。
deque.rotate(n)：双端队列的移位操作，如果n是正数，则队列所有元素向右移动n个位置，如果是负数，则队列所有元素向左移动n个位置。

3. 用双端队列实现栈

以左端作为栈底（左端保持不动），右端作为栈顶（右端动态变化，st[-1]为栈顶元素），栈操作在右端进行，则用append()作为进栈方法，pop()作为出栈方法。
以右端作为栈底（右端保持不动），左端作为栈顶（左端动态变化，st[0]为栈顶元素），栈操作在左端进行，则用appendleft()作为进栈方法，popleft()作为出栈方法。

from collections import deque	#引用deque
st=deque()
st.append(1)
st.append(2)
st.append(3)
while len(st)>0:print(st.pop(),end=' ')     #输出：3 2 1
print()

4. 用双端队列实现普通队列

以左端作为队头（出队端，），右端作为队尾（进队端），则用popleft()作为出队方法，append()作为进队方法。在队列非空时qu[0]为队头元素，qu[-1]为队尾元素。
以右端作为队头（出队端），左端作为队尾（进队端），则用pop()作为出队方法，appendleft()作为进队方法。在队列非空时qu[-1]为队头元素，qu[0]为队尾元素。

from collections import deque
qu=deque()
qu.append(1)
qu.append(2)
qu.append(3)
while len(qu)>0:print(qu.popleft(),end=' ')     	#输出：1 2 3
print()

3.2.5 优先队列

优先队列就是指定队列中元素的优先级，按优先级越大越优先出队，而普通队列中按进队的先后顺序出队，可以看成进队越早越优先。
优先队列的删除和读取与传统队列一样，但其插入类似于有序数组。删除数据和读取数据依然只能从优先队列的开头进行，但是插入需要确保数据总是按特定顺序排列。
优先队列的一个经典应用情景是管理医院急诊的分诊系统。

在急诊室，我们不会按患者来院顺序而是需要按患者症状的严重程度进行治疗。如果突然来了一个生命垂危的病患，那么即便有一个流感患者早来了几小时，也必须排在后面。假设分诊系统用1和10之间的数表示病人症状的严重程度，其中10表示最严重。这个优先队列可能会如下图所示。

因为优先队列的开头的病人症状最严重，所以我们总是会优先选择该病人进行治疗。在上面的例子中，会优先治疗病人C。
如果一个新病人E的症状严重程度是3，那么我们会把他放到优先队列中下图所示的合适位置。

优先队列也是一种抽象数据结构。它可以使用其他更基础的数据结构来实现。最直接的一种实现是使用有序数组。我们需要给数组加上以下限制。

• 插入数据时，需要确保数组顺序。
• 数据只能从数组末尾移除。​（数组末尾表示优先队列的开头。​）

优先队列有两种主要操作：删除和插入。

从数组开头删除的效率是O(N)。这是因为需要把其他所有数据左移来填补索引0处的空缺。
这里我们使用数组的末尾来表示优先队列的开头。这样就能一直从数组末尾删除元素，即需要O(1)步。

插入时最多要检查N个元素才能知道插入新数据的位置，所以有序数组的插入需要O(N)步。​（即便很快就找到了插入位置，也需要把剩余数据右移。​）

因此，基于数组的优先队列有着O(1)时间的删除和O(N)时间的插入。

例题

例3.11 在CSqQueue循环队列类中增加一个求元素个数的算法size()。

# 全局变量，假设容量为100
MaxSize = 100# 循环队列类
class CSqQueue:def __init__(self):self.data = [None] * MaxSize  # 存放队列中元素# 队头指针self.front = 0# 队尾指针self.rear = 0# 计算队列元素个数def size(self):return ((self.rear - self.front + MaxSize) % MaxSize)

例3.11 对于一个整数循环队列qu，利用队列基本运算和size()算法设计进队和出队第k（k≥1，队头元素的序号为1）个元素的算法。

# 元素 data 进队第 k 个位置
from Data_S_ch3_Queue import CSqQueue
def pushk(qu, k, data):# 合法性检查：首先检查 k 是否为合法的位置（范围 1 到 n + 1）。n = qu.size()if k < 1 or k > n + 1:return False# 插入到第 k 个位置：如果 k 在 1 到 n 之间，遍历队列，将第 k 个位置的元素插入，其他元素通过出队再进队的方式保持顺序。if k <= n:for i in range(1, n+1):if i == k:      # 查找 k 的位置qu.push(data)   # 插入 data 到 k 的位置x = qu.pop()    # x 元素出队qu.push(x)      # x 元素进队# 插入到队尾：如果 k == n + 1，直接插入元素到队尾。else:qu.push(data)# 返回值：插入成功则返回 True，非法参数时返回 False。return True# 第 k 个元素 data 出队
def popk(qu, k):# 获取队列当前大小，并检测 k 是否有效n = qu.size()assert k >= 1 and k <= n# 遍历队列：逐一遍历队列中的所有元素，通过pop()操作将元素从队头取出。for i in range(1, n+1):x = qu.pop()				# 出队元素xif i != k:qu.push(x)		        # 将非第k个元素进队else:data = x				# 取第k个出队的元素# 返回被删除的元素return data# 主程序
# 创建一个队列实例
queue = CSqQueue()# 插入一些初始数据
queue.push(10)
queue.push(20)
queue.push(30)
queue.push(40)print("初始队列状态:")
original_elements = []  # 保存原始元素
for i in range(queue.size()):element = queue.pop()print(element, end=' ')original_elements.append(element)  # 保存弹出的元素queue.push(element)  # 恢复队列原样
print("\n")# 插入元素15到队列的第2个位置
print("将15插入到第2个位置:")
pushk(queue, 2, 15)# 输出插入后的队列
print("插入后的队列状态:")
for i in range(queue.size()):element = queue.pop()print(element, end=' ')queue.push(element)  # 恢复队列原样
print("\n")# 删除第 3 个元素
k = 3
removed_element = popk(queue, k)
print(f"\n删除第 {k} 个元素: {removed_element}")# 输出删除后的队列
print("删除后的队列状态:")
for i in range(queue.size()):element = queue.pop()print(element, end=' ')queue.push(element)  # 恢复队列原样
print("\n")

例3.12 对于循环队列来说，如果知道队头指针和队列中元素个数，则可以计算出队尾指针。
也就是说，可以用队列中元素个数代替队尾指针。设计出这种循环队列的判队空、进队、出队和取队头元素的算法。

算法思路:
判队空：如果队列中元素个数为 0，则队列为空。
进队：在队列中插入一个新元素时，队尾指针可以根据队头指针和当前元素个数计算出来，将新元素插入相应位置，并增加队列元素个数。
出队：从队列中移除队头的元素，调整队头指针，元素个数减少。
取队头元素：根据队头指针直接获取队头的元素。

# 全局变量，假设容量为100
MaxSize = 100
class CSqQueue1:def __init__(self):self.data = [None] * MaxSize  # 存放队列中元素self.front = 0  # 队头指针self.size = 0   # 队列中元素的个数，初始化为 0# 判队空def empty(self):return self.size == 0# 进队def push(self, data):assert self.size != MaxSize  # 检测队列满# 计算队尾指针位置rear = (self.front + self.size) % MaxSizeself.data[rear] = data  # 在队尾插入元素self.size += 1  # 队列元素个数加1# 出队def pop(self):assert not self.empty()  # 检测队列空# 更新队头指针，指向下一个元素self.front = (self.front + 1) % MaxSizeself.size -= 1  # 队列元素个数减1# 返回队头元素return self.data[self.front]# 取队头元素def gethead(self):assert not self.empty()  # 检测队列空return self.data[(self.front + 1) % MaxSize]  # 返回队头指针指向的元素# 创建循环队列对象
queue = CSqQueue1()# 示例数据插入
queue.push(10)
queue.push(20)
queue.push(30)# 队列操作
print("队头元素:", queue.gethead())
print("出队:", queue.pop())
print("队头元素:", queue.gethead())
print("出队:", queue.pop())queue.push(40)print("队头元素:", queue.gethead())
print("出队:", queue.pop())
print("队头元素:", queue.gethead())
print("出队:", queue.pop())

例3.13 编写一个程序求解约瑟夫（Joseph）问题。
有n个小孩围成一圈，给他们从1开始依次编号，从编号为1的小孩开始报数，
数到第m个小孩出列，然后从出列的下一个小孩重新开始报数，数到第m个小孩又出列，…，
如此反复直到所有的小孩全部出列为止，求整个出列序列。
如当n=6，m=5时的出列序列是5，4，6，2，3，1。

from Data_S_ch3_Queue import LinkQueuedef Jsequence(n, m):  # 求约瑟夫序列,n：小孩的总人数,m：报数的数字# 初始化队列,小孩按照编号进队qu = LinkQueue()  # 定义一个链队for i in range(1, n + 1):  # 进队编号为1到n的n个小孩qu.push(i)# 模拟小孩出列的过程for i in range(1, n + 1):  # 共出列n个小孩# 循环报数，找到要出列的小孩j = 1while j <= m - 1:  # 出队m-1个小孩，并将他们进队到队尾qu.push(qu.pop())j += 1x = qu.pop()  # 出队第m个小孩print(x, end=' ')print()#主程序
print()
print("测试1: n = 6, m = 3")
print("出列顺序:", end = ' ')
Jsequence(6, 3)
print("测试2: n = 8, m = 4")
print("出列顺序:", end = ' ')
Jsequence(8, 4)

时间复杂度：由于外层循环执行了 n 次，内层循环每次执行 m - 1 次，因此总的时间复杂度为 O(n×m)。
空间复杂度：队列中最多存储 n 个元素，空间复杂度为 O(n)。

习题

逆波兰表达式求值
根据逆波兰表示法，求表达式的值。有效的运算符包括 +， -， ， / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
假设给定逆波兰表达式总是有效的，换句话说，表达式总会得出有效数值且不存在除数为0的情况。
其中整数除法只保留整数部分。例如，输入[“2”， “1”， “+”， “3”， ""]，输出结果为9。
输入[“4”， “13”， “5”， “/”， “+”]，输出结果为6。

算法思想：
使用栈存储操作数。
遇到运算符时，从栈中弹出两个操作数进行计算，并将结果压回栈中。
最终栈中只剩下一个元素，即为表达式的计算结果。

import sys
from collections import deque
def evalRPN(tokens):st = deque()  # 定义一个运算数栈i = 0while i < len(tokens):  # 遍历postexpopv = tokens[i]  # 从逆波兰表达式（后缀表达式）中取一个元素opvif opv == "+":  # 判定为"+"号a = st.pop()  # 退栈取数值ab = st.pop()  # 退栈取数值bc = b + a  # 计算cst.append(c)  # 将计算结果进栈elif opv == "-":  # 判定为"-"号a = st.pop()  # 退栈取数值ab = st.pop()  # 退栈取数值bc = b - a  # 计算cst.append(c)  # 将计算结果进栈elif opv == "*":  # 判定为"*"号a = st.pop()  # 退栈取数值ab = st.pop()  # 退栈取数值bc = b * a  # 计算cst.append(c)  # 将计算结果进栈elif opv == "/":  # 判定为"/"号a = st.pop()  # 退栈取数值ab = st.pop()  # 退栈取数值bc = int(b / a)  # 计算cst.append(c)  # 将计算结果进栈else:  # 处理整数st.append(int(opv))  # 将数值opv进栈i += 1  # 继续处理postexp的其他元素return st[-1]  # 栈顶元素即为求值结果if __name__ == '__main__':tokens = sys.stdin.readline().strip().split(' ')print(evalRPN(tokens))

设计循环队列
设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。
它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。
在一个普通队列里，一旦一个队列满了就不能插入下一个元素，即使在队列前面仍有空间。
但是使用循环队列时可以使用这些空间去存储新的值。你的实现应该支持如下操作：
（1）MyCircularQueue(k)：构造器，设置队列长度为k。
（2）Front：从队首获取元素。如果队列为空，返回-1。
（3）Rear：获取队尾元素。如果队列为空，返回-1。
（4）enQueue(value)：向循环队列插入一个元素。如果成功插入则返回真。
（5）deQueue()：从循环队列中删除一个元素。如果成功删除则返回真。
（6）isEmpty()：检查循环队列是否为空。
（7）isFull()：检查循环队列是否已满。
例如：
MyCircularQueue circularQueue = new MycircularQueue(3) #设置长度为 3
circularQueue.enQueue(1) #返回True
circularQueue.enQueue(2) #返回True
circularQueue.enQueue(3) #返回True
circularQueue.enQueue(4)#返回False，队列已满
circularQueue.Rear() #返回3
circularQueue.isFull() #返回True
circularQueue.deQueue() #返回True
circularQueue.enQueue(4) #返回True
circularQueue.Rear() #返回4
提示：所有的值都在0至1000的范围内，操作数将在1至1000的范围内，请不要使用内置的队列库。

class MyCircularQueue():def __init__(self, k):"""这里初始化你的数据结构，设置队列的大小为k"""self.data = [None] * k  # 初始化队列列表self.MaxSize = k  # 队中最多元素个数self.front = 0  # 队头指针self.rear = 0  # 队尾指针self.tag = 0  # 队列可能空或者满的标志def enQueue(self, value):"""插入元素value的队列中，如果操作成功返回True"""if self.isFull():return False  # 队满返回Falseself.rear = (self.rear + 1) % self.MaxSizeself.data[self.rear] = valueself.tag = 1return True  # 成功插入则返回Truedef deQueue(self):"""出队一个元素，如果操作成功返回True"""if self.isEmpty():return False  # 队空返回Falseself.front = (self.front + 1) % self.MaxSizeself.tag = 0return True  # 成功删除则返回Truedef Front(self):"""获取队头元素"""if self.isEmpty():  # 队空返回-1return -1head = (self.front + 1) % self.MaxSizereturn self.data[head]def Rear(self):"""获取队尾元素"""if self.isEmpty():  # 队空返回-1return -1return self.data[self.rear]def isFull(self):"""判断队列是否满"""if self.tag == 1 and self.rear == self.front:return Trueelse:return Falsedef isEmpty(self):"""判断队列是否空"""if self.tag == 0 and self.rear == self.front:return Trueelse:return Falseif __name__ == '__main__':q = MyCircularQueue(3)res = []res.append(q.enQueue(1))res.append(q.enQueue(2))res.append(q.enQueue(3))res.append(q.enQueue(4))res.append(q.Rear())res.append(q.isFull())res.append(q.deQueue())res.append(q.enQueue(4))res.append(q.Rear())print(res)

第五章 递归

例5.2 采用递归算法求整数数组a[0…n-1]中的最小值。

假设f (a，i ) 求数组元素a[0…i]（共i+1个元素）中的最小值。

• 当i=0时，有f(a，i)=a[0]。
• 假设f(a，i-1)已求出，显然有f(a，i)=MIN(f(a，i-1)，a[i])，其中MIN()为求两个值较小值函数。

从而得到递归模型：

# 定义递归函数，用于求数组 a[0..i] 中的最小值
def Min(a, i):# 当只剩一个元素时，直接返回它作为最小值if i == 0:return a[0]else:# 递归调用，找出前 i 个元素中的最小值min_val = Min(a, i - 1)# 比较前面的最小值和当前元素 a[i]return a[i] if min_val > a[i] else min_val# 含递归过程的主程序
# 辅助函数，用于递归调用过程的外部打印
def find_min(a):n = len(a) - 1  # 数组的最后一个索引print("数组:", a)for i in range(n, 0, -1):print(f"寻找 a[0..{i}] 中的最小值")min_value = Min(a, n)print("数组中的最小值是:", min_value)return min_value# 测试数据
a = [3, 5, 2, 8, 1]
find_min(a)# 不含递归过程的主程序
a = [3, 5, 2, 8, 1]
n = len(a) - 1
min_value = Min(a, n)
print(min_value)

递归会从 i = n-1 一直递归到 i = 0，也就是数组的第一个元素，总共会有 𝑛次递归调用。每次递归调用只执行常数时间的比较操作，所以每次调用的时间复杂度是 𝑂(1)，因此时间复杂度为 𝑂(𝑛)。
每层栈只需要常数空间 𝑂(1)来存储参数和返回地址，但由于递归深度为 𝑛，因此空间复杂度是 𝑂(𝑛)。

例5.3 假设有一个不带头结点的单链表p，完成以下两个算法设计：
（1）设计一个算法正向输出所有结点值。
（2）设计一个算法反向输出所有结点值。

正向输出：
递归出口：当 p == None（即链表遍历结束，没有下一个节点时），什么都不做，直接返回。这是递归的停止条件。
递归体：对于每一个节点 p，先输出当前节点的数据 p.data，然后递归调用 Positive(p.next) 来处理下一个节点。这会依次输出从头节点到链表尾部的数据。

反向输出：
递归出口：和 Positive 函数一样，当 p == None 时，直接返回。
递归体：对于每一个节点 p，先递归调用 Reverse(p.next) 处理下一个节点，然后再输出当前节点的数据 p.data。这样会等到链表末端节点的递归调用完成后，依次返回并输出数据，最终实现反向输出。

# 定义链表节点类
class Node:def __init__(self, data):self.data = data  # 节点的数据self.next = None  # 指向下一个节点的指针# 正向输出所有节点的值
def Positive(p):if p is None:returnelse:print("%d" % (p.data), end=' ')Positive(p.next)# 反向输出所有节点的值
def Reverse(p):if p is None:returnelse:Reverse(p.next)print("%d" % (p.data), end=' ')# 构建示例链表：1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)# 正向输出
print("正向输出：", end='')
Positive(head)  # 输出：1 2 3 4 5
print()# 反向输出
print("反向输出：", end='')
Reverse(head)  # 输出：5 4 3 2 1
print()

时间复杂度
正向输出和反向输出的时间复杂度都是 𝑂(𝑛)，其中 𝑛是链表的节点数。
每个函数需要遍历整个链表中的每个节点一次，无论是正向还是反向输出，都会递归访问所有节点一次，因此时间复杂度是线性的。

空间复杂度
空间复杂度为 𝑂(𝑛)，因为递归的调用栈会占用额外的内存。
每次递归调用都会在栈上保存一个新的函数调用状态，因此对于长度为 𝑛的链表，递归深度会达到 𝑛。
这意味着我们需要 𝑛层的栈空间来存储递归调用状态，导致空间复杂度为 𝑂(𝑛)。

思考：如何将带头结点转换为不带头结点的单链表？
从头节点的下一个节点开始处理即可。假设带头节点的链表用变量 head 表示，链表第一个实际数据节点是 head.next。要转换为不带头节点的链表，只需将 head.next 作为递归函数的参数传入。

# 带头节点的链表
head = Node()  # 假设这是头节点
head.next = Node(data=1)
head.next.next = Node(data=2)
# ...# 调用递归函数时从 head.next 开始
Positive(head.next)  # 正向输出，不包含头节点
Reverse(head.next)   # 反向输出，不包含头节点

若算法pow(x，n)用于计算xⁿ（n为大于1的整数）。完成以下任务：
（1）采用递归方法设计pow(x，n)算法。
（2）问执行pow(x，10)发生几次递归调用？求pow(x，n)对应的算法复杂度是多少？

分解问题的递归思想：

# 递归实现幂次计算函数
def pow(x, n):if n == 1:return xp = pow(x, n // 2)if n % 2 == 1:return x * p * pelse:return p * p# 辅助函数，用于跟踪递归调用过程
def trace_pow(x, n):print(f"Calculating {x}^{n}:")result = _trace_pow_helper(x, n, depth=0)print(f"Result: {x}^{n} = {result}")# 实际调用递归函数并打印每次调用过程
def _trace_pow_helper(x, n, depth):print(" " * depth * 2 + f"pow({x}, {n}) called")# 使用实际的递归计算if n == 1:print(" " * depth * 2 + f"Returning: {x}")return x# 递归调用p = _trace_pow_helper(x, n // 2, depth + 1)# 计算当前层的结果并打印if n % 2 == 1:result = x * p * pelse:result = p * pprint(" " * depth * 2 + f"Returning: {result} from pow({x}, {n})")return result# 示例数据
x = 2
n = 10# 调用跟踪函数，打印递归过程并输出最终结果
trace_pow(x, n)

由于每次递归将问题规模减半，递归的深度是 log2(𝑛)。因此，时间复杂度为 𝑂(log𝑛)。
空间复杂度也为 𝑂(log𝑛)，因为递归调用栈的深度是 log𝑛。

习题

求楼梯走法数问题。一个楼梯有 n 个台阶，上楼可以一步上一个台阶，也可以一步上两个台阶。编写一个实验程序，求上楼梯共有多少种不同的走法，并用相关的数据进行测试。

算法设计思路：

定义基础情况(递归出口)：

• 如果楼梯有 0 个台阶，那么只有 1 种方法（即什么都不做）。
• 如果楼梯有 1 个台阶，则只有 1 种走法（直接走 1 个台阶）。

递推公式(递归体)：

• 对于 n 个台阶，到达第 n 个台阶的方法数等于到达第 n−1 个台阶的方法数加上到达第 n−2 个台阶的方法数。
• 因为要到达第 n 个台阶，可以从第 n−1 个台阶走 1 步上来，也可以从第 n−2 个台阶走 2 步上来。
  递推公式为： ways(n)=ways(n−1)+ways(n−2)

def climb_stairs(n):# 递归出口if n <= 1:return 1# 递归体return climb_stairs(n - 1) + climb_stairs(n - 2)# 测试例子
n = 5  # 假设有5个台阶
print(f"共有 {climb_stairs(n)} 种不同的走法到达顶端。")

该递归算法的时间复杂度是 O(2ⁿ)，空间复杂度为 O(n)。

第六章 树和二叉树

6.1 树

6.1.1 树的定义

树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构、等等。
树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树具有以下特点：

1. 每个结点有零个或多个子结点；
2. 没有父结点的结点为根结点；
3. 每一个非根结点只有一个父结点；
4. 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树。

6.1.2 树的基本术语

结点的度：一个结点含有的子树的个数称为该结点的度。
叶结点：度为0的结点称为叶结点，也可以叫做终端结点。
分支结点：度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推。
孩子结点：一个结点的直接后继结点称为该结点的孩子结点。
双亲结点(父结点)：一个结点的直接前驱称为该结点的双亲结点。
兄弟结点：同一双亲结点的孩子结点间互称兄弟结点。
结点层次：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推结点的层序编号。
树的度：树中所有结点的度的最大值。
树的高度(深度)：树中结点的最大层次。
森林： m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树。

6.1.3 树的性质

性质1：树中的结点数等于所有结点的度数加1。

1. 引入树结构的节点和边
   首先，介绍树结构的基本组成：树是由节点和边（分支）组成的。每个节点通过边与其他节点相连，而树的节点总数为 n。
2. 度之和与分支数的关系
   解释度之和和分支数的概念：
   • 度之和：树中所有节点的度数加起来的总和。
   o 度数是每个节点连接的分支数。例如，度为 3 的节点有 3 条边与其他节点相连。
   • 分支数：整个树中的总边数，即有多少条边将节点连接在一起。
   在树结构中，每一条边都连接着两个节点，因此树的分支数就是节点的度之和。
3. 解释性质：树的节点数等于度之和加 1
   根据树的性质，树中的节点总数 n 等于度之和加 1。我们可以用以下逻辑来解释这一点：
   • 一棵树有 n 个节点，且整个树中只有 n-1 条分支可以连接这些节点，因为树是一个无环的连接图。
   • 如果我们将树看成一棵家谱树，从“根节点”开始，根节点通过若干条分支连接到其他节点。
   • 每增加一个节点，实际上是增加了一条分支，因此如果有 n-1 条分支，就会有 n 个节点。
4. 示例讲解
   
   用图片中的示例树来说明这个性质：
   • 树的节点数为 8（节点 A、B、C、D、E、F、G、H）。
   • 计算树的度之和：
   o A 的度为 3，C 的度为 2，B、D、E、F、G、H 的度都为 0。
   o 度之和为 3 + 2 + 1 + 1 + 1 + 0 + 0 + 0 = 7。
   • 根据性质，我们知道树的分支数为 n - 1 = 7，这与度之和相等。

总结
性质1的直观理解是，每个节点通过分支连接其他节点，而树中总的节点数始终比分支数多 1。因此，树的节点总数 n 等于度之和加 1。

性质2：度为 m 的树中第 i 层上至多有 m^i-1 个结点，这里应有 i ≥ 1。

1. 什么是“度为 m 的树”
   • 首先，解释什么是“度为 m 的树”。度为 m 的树表示每个节点最多可以有 m 个子节点。
   • 比如，度为 2 的树就是一个二叉树，每个节点最多有 2 个子节点；度为 3 的树表示每个节点最多有 3 个子节点，依此类推。
2. 分析第 i 层最多有多少节点
   • 我们可以用一个简单的逻辑来理解：假设树的根节点在第 1 层，它有 m 个子节点；这些子节点又可以有它们自己的子节点。
   • 每往下一层，每个节点会“分裂”出最多 m 个子节点。
   用具体的数字例子来说，假设度 m=2（即二叉树），我们来看看每层最多会有多少节点：
   • 第 1 层：只有 1 个根节点，即 2¹⁻¹=1。
   • 第 2 层：根节点的子节点数最多为 2 个，即 2²⁻¹=2。
   • 第 3 层：每个子节点又可以有 2 个子节点，最多有 2³⁻¹=2²=4个节点。
   由此可见，第 i 层最多有 mi−1 个节点。
3. 用数学归纳法解释为什么是 mⁱ⁻¹
   • 基础情况：在第 1 层，根节点只有 1 个，符合 m1−1=m⁰=1。
   • 归纳假设：假设第 k 层最多有 m^k−1 个节点。
   • 归纳步骤：在第 k+1 层，每个第 k 层的节点最多可以扩展出 m 个子节点，因此第 k+1 层最多有 m×m^k−1=m^k 个节点。
   这样就可以证明，对于第 i 层，最多有 mⁱ⁻¹ 个节点。
4. 为什么是“最多”而不是“确切”数量
   强调一下，这个性质中的“最多”意味着这是一个上限，实际情况可能少于这个数量：
   • 如果某些节点没有分出子节点，那么这一层的节点数就会少于最大值。
   • 满足这个上限的是一种特殊的树，称为“满 m 次树”，即每层都被完全填满。
5. 应用场景
   最后，举例说明这个性质的应用场景：
   • 满树的概念：当我们构造一棵每层都填满的树时，这棵树在相同高度下节点数最多。
   • 高度最小的树：如果有固定数量的节点，要构造度为 m 的树，满树或接近满树的结构可以使树的高度最小。

总结

1. 度为 m 的树的第 i 层最多有 mⁱ⁻¹ 个节点，因为每一层的节点数是上一层的m 倍。
2. 这个性质描述的是一个上限，真正达到这个上限的是一种“满 m 次树”。

性质3： 高度为 h 的 m 次树至多有 $\frac{m^h-1}{m-1}$ 个结点。

1. 回顾性质2
   • 性质2 告诉我们，度为 m 的树在第 i 层最多有 mⁱ⁻¹ 个节点。
   • 例如，如果树的度为 2（二叉树），第 1 层最多有 2⁰=1 个节点，第 2 层最多有 2¹=2 个节点，第 3 层最多有 2²=4个节点，依此类推。
2. 累加每一层的节点数
   现在，我们要计算一棵高度为 h 的 m 次树的最大节点数，也就是将每一层的最大节点数加起来：
   • 第 1 层：最多有 m⁰=1 个节点。
   • 第 2 层：最多有 m¹=m 个节点。
   • 第 3 层：最多有 m² 个节点。
   • ……
   • 第 h 层：最多有 m^h−1 个节点。
   因此，树的总节点数 N 为每层节点数的总和：
   N=1+m+m²+m³+⋯+m^h−1
3. 使用等比数列求和公式
   这个总和实际上是一个等比数列的求和问题，其中首项为 1，公比为 m，项数为 h。等比数列的求和公式为： $$s=\frac{a(r^n-1)}{r-1}$$
   在这里，a=1（首项），r=m（公比），项数是 h，因此我们可以得到：
   $$N=\frac{m^k-1}{m-1}$$
4. 解释公式含义
   通过这个公式，我们可以得到以下结论：
   • 高度为 h 的 m 次树，即每个节点最多有 m 个子节点的树，在节点数最多的情况下，它会有$\frac{m^h-1}{m-1}$个节点。
   • 这是一个上限，因为它假设树中的每一层都被填满（满 m 次树），实际情况中节点数可能会少于这个上限。
5. 例子帮助理解
   假设我们有一个高度为 3 的二叉树（度为 2，m=2）：
   • 使用公式，最大节点数为$\frac{2^3-1}{2-1}=7$ 。

总结
• 性质3 提供了一棵高度为 h 的 m 次树在最满情况下的节点上限。
• 这个上限由等比数列求和公式推导而来，公式为$\frac{m^h-1}{m-1}$。
• 它表示的是一个“满树”的情况，也就是每一层都填满的情况下的最大节点数。

性质4：具有 n 个结点的 m 次树的最小高度为 logm(n(m-1)+1)。

1. 问题背景
   树的高度是从根节点到叶子节点的最长路径上的层数。我们现在关注的是，在给定节点数 n的情况下，构造一棵度为 m 的树，使得这棵树的高度尽可能小。
2. 什么是“最小高度”？
   要使树的高度最小，我们希望尽可能地“填满”每一层，这样可以在较小的高度下容纳更多的节点。换句话说，最小高度的树是“尽量紧凑”的树，每一层几乎都达到满的状态。
3. 通过满树理解高度和节点数的关系
   根据性质3的结论，当一棵 m 次树的高度为 h 时，它的最大节点数是$\frac{m^h-1}{m-1}$：
   这意味着，如果我们希望一棵高度为 h 的树尽量紧凑，那么在最理想的情况下，树可以容纳的节点数就是这个公式的值。
4. 倒推出最小高度公式
   我们知道一棵度为 m 的树，如果高度为 h，那么它可以容纳的最大节点数是$\frac{m^h-1}{m-1}$：
   但是，在计算最小高度时，必须考虑树在高度 h 下节点数的最小情况。对于高度为 h 的树，最少节点的情况是前 h−1 层完全填满，第 h 层只包含 1 个节点，这种情况会让树的高度达到 h 的同时节点数最少。

6.2 二叉树

6.2.1 二叉树的定义

• 二叉树
  也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。即度不超过2的树(每个结点最多有两个子结点)。
  在含n个结点的二叉树中，所有结点的度小于等于2，通常用$n_0$表示叶子结点个数，$n_1$表示单分支结点个数，$n_2$表示双分支结点个数。

度为2的树至少有3个结点，而二叉树的结点数可以为0。

1. 度为2的树：在树论中，“度”指的是节点的分支数，即每个节点有多少个子节点。度为2的树意味着每个非叶子节点有2个子节点。这种树的最小结构是一个根节点带有两个子节点，所以至少需要三个节点才能构成度为2的树。因此，度为2的树至少有3个节点。
2. 二叉树：二叉树是树结构的一种，每个节点最多有两个子节点。二叉树的节点数没有最低限制，理论上可以是0个节点（即空树）。这意味着二叉树可以不存在任何节点，这与度为2的树不同，后者至少需要3个节点。

• 满二叉树
  一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。
  满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h且有2^h- 1个结点的二叉树称为满二叉树。
  

满二叉树特点：

1. 叶子结点都在最下一层。
2. 只有度为0和度为2的结点。
3. 含n个结点的满二叉树的高度为$lo{g}_2(n+1)$，叶子结点个数为$\lfloor \frac{n}{2}\rfloor +1$，度为2的结点个数为$\lfloor \frac{n}{2}\rfloor$。

• 完全二叉树
  在完全二叉树中，除了最后一层外，每一层的节点都达到了最大值，最后一层的节点则从左到右依次排列，且没有空缺。
  

完全二叉树特点：

1. 叶子结点只可能出现在最下面两层中。
2. 对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
3. 按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。
4. 如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子。

6.2.2 二叉树性质

性质1：非空二叉树上叶结点数等于双分支结点数加1。即 $n_0=n_2+1$。

证明：总结点数 $n=n_0+n_1+n_2$。
一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以，$总的度数=n_1+2n_2$。
因为，树中的结点数等于所有结点的度数加1。
所以，$总的度数=总分支数=n-1$。
则 $n_1+2n_2=n_0+n_1+n_2-1$，求出$n_0=n_2+1$。

在二叉树中计算结点时常用的关系式有：
①$所有结点的度之和=n-1$
②$所有结点的度之和＝n_1＋2n_2$
③$n=n_0+n_1+n_2$

性质2：非空二叉树上第 i 层上至多有 2^i-1 个结点，这里应有 i ≥ 1 。
性质3：高度为 h 的二叉树至多有 2^h-1 个结点（h ≥ 1）。
性质5：具有 n 个（n＞0）结点的完全二叉树的高度为$\lceil {\log }_2(n+1)\rceil \text{或}\lfloor {\log }_{2}n\rfloor +1$。

一棵完全二叉树中，由结点总数n 可以确定其树形。
$n_1$只能是0或1，当n为偶数时，$n_1=1$，当n为奇数时，$n_1=0$。
层序编号为 i 的结点层次恰好为$\lceil {\log }_2(i+1)\rceil \text{或}\lfloor {\log }_{2}i\rfloor +1$。

6.2.3 二叉树的存储结构

# 树的结点类
class TreeNode:def __init__(self, data=None, left=None, right=None):self.data = dataself.lchild = leftself.rchild = right# 二叉树类
class BTree:def __init__(self):self.root = None# 设置二叉树的根结点def SetRoot(self, root):self.root = root# 查找值为 x 的结点def FindNode(self, x):# 调用私有方法 _FindNode(self, t, x) 来实现实际的递归查找return self._FindNode(self.root, x)def _FindNode(self, t, x):# 空树或已遍历完毕的情况if t == None:return None# 找到目标值的情况elif t.data == x:return telse:# 在左子树中查找p = self._FindNode(t.lchild, x)if p != None:return p# 在右子树中查找else:return self._FindNode(t.rchild, x)# 计算树的高度Heightdef Height(self):return self._Height(self.root)def _Height(self, t):if t == None:return 0else:lh = self._Height(t.lchild)  # 左子树高度rh = self._Height(t.rchild)  # 右子树高度return max(lh, rh) + 1# 创建示例二叉树
#       10
#      /   \
#     5     15
#    / \      \
#   2   7      20
node2 = TreeNode(2)
node7 = TreeNode(7)
node5 = TreeNode(5, node2, node7)
node20 = TreeNode(20)
node15 = TreeNode(15, None, node20)
root = TreeNode(10, node5, node15)# 初始化二叉树
bt = BTree()
bt.SetRoot(root)# 查找并打印结果
def print_find_result(value):result = bt.FindNode(value)if result:print(f"找到节点，值为: {result.data}")else:print(f"未找到值为 {value} 的节点")# 测试查找节点
print_find_result(7)   # 应该找到节点，值为7
print_find_result(15)  # 应该找到节点，值为15
print_find_result(100) # 应该找不到节点# 计算并打印二叉树的高度
print("二叉树的高度:", bt.Height())  # 应该输出 3

6.3 二叉树先序、中序和后序遍历

6.3.1 二叉树遍历的概念

二叉树遍历是指按照一定次序访问二叉树中所有结点，并且每个结点仅被访问一次的过程。

1. 先序遍历
   ① 访问根结点。
   ② 先序遍历左子树。
   ③ 先序遍历右子树。

2. 中序遍历
   ① 中序遍历左子树。
   ② 访问根结点。
   ③ 中序遍历右子树。

3. 后序遍历
   ① 后序遍历左子树。
   ② 后序遍历右子树。
   ③ 访问根结点。

代码实现：

# 树的结点类
class TreeNode:def __init__(self, data=None, left=None, right=None):self.data = dataself.lchild = leftself.rchild = right# 二叉树类
class BTree:def __init__(self):self.root = None# 设置二叉树的根结点def SetRoot(self, root):self.root = root# 先序遍历接口def PreOrder(self):self._PreOrder(self.root)print()  # 换行# 先序遍历的递归方法def _PreOrder(self, t):# 如果 t 是 None，说明当前子树为空，不执行任何操作。if t != None:# 访问当前节点,打印当前节点的值# 先序遍历要求在递归访问子树之前先访问节点本身print(t.data, end=' ')# 先序遍历左子树self._PreOrder(t.lchild)# 先序遍历右子树self._PreOrder(t.rchild)# 中序遍历接口def InOrder(self):self._InOrder(self.root)print()  # 换行# 中序遍历的递归方法def _InOrder(self, t):if t != None:# 先遍历左子树self._InOrder(t.lchild)# 然后访问根节点，中序遍历要求在访问子树之前先访问左子树，再访问节点本身print(t.data, end=' ')# 最后遍历右子树self._InOrder(t.rchild)# 后序遍历接口def PostOrder(self):self._PostOrder(self.root)print()  # 换行# 后序遍历的递归方法def _PostOrder(self, t):if t != None:# 先遍历左子树self._PostOrder(t.lchild)# 然后遍历右子树self._PostOrder(t.rchild)# 最后访问根节点，后序遍历要求在递归访问左右子树之后再访问节点本身print(t.data, end=' ')# 创建示例二叉树
#       10
#      /   \
#     5     15
#    / \      \
#   2   7      20
node2 = TreeNode(2)
node7 = TreeNode(7)
node5 = TreeNode(5, node2, node7)
node20 = TreeNode(20)
node15 = TreeNode(15, None, node20)
root = TreeNode(10, node5, node15)# 初始化二叉树
bt = BTree()
bt.SetRoot(root)# 执行先序遍历
print("先序遍历结果:")
bt.PreOrder()# 执行中序遍历
print("中序遍历结果:")
bt.InOrder()# 执行后序遍历
print("后序遍历结果:")
bt.PostOrder()

例题

# 树的结点类
class TreeNode:def __init__(self, data=None, left=None, right=None):self.data = dataself.lchild = leftself.rchild = right# 二叉树类
class BTree:def __init__(self):self.root = Nonedef SetRoot(self, root):self.root = root# 创建示例二叉树
#       10
#      /   \
#     5     15
#    / \      \
#   2   7      20node2 = TreeNode(2)
node7 = TreeNode(7)
node5 = TreeNode(5, node2, node7)
node20 = TreeNode(20)
node15 = TreeNode(15, None, node20)
root = TreeNode(10, node5, node15)# 初始化二叉树
bt = BTree()
bt.SetRoot(root)

例6.9 假设二叉树采用二叉链存储结构存储，设计一个算法求一棵给定二叉树中的结点个数。

对于一个节点 t，我们可以通过递归的方式，按以下步骤计算整个二叉树的节点个数：
1.如果 t 为 None（空节点），返回 0，表示当前子树为空。
2.否则，当前节点 t 的个数为：
左子树的节点个数 + 右子树的节点个数 + 1（当前节点本身）。
3.递归计算左子树和右子树的节点个数，最终将它们加和。

# 前序遍历统计节点数
def NodeCount1(bt):return _NodeCount1(bt.root)def _NodeCount1(t):if t == None:return 0k = 1  # 当前节点m = _NodeCount1(t.lchild)  # 左子树n = _NodeCount1(t.rchild)  # 右子树return k + m + n# 中序遍历统计节点数
def NodeCount2(bt):return _NodeCount2(bt.root)def _NodeCount2(t):if t == None:return 0m = _NodeCount2(t.lchild)  # 左子树k = 1  # 当前节点n = _NodeCount2(t.rchild)  # 右子树return k + m + n# 后序遍历统计节点数
def NodeCount3(bt):return _NodeCount3(bt.root)def _NodeCount3(t):if t == None:return 0m = _NodeCount3(t.lchild)  # 左子树n = _NodeCount3(t.rchild)  # 右子树k = 1  # 当前节点return k + m + n# 直接递归统计节点数
# 当b=None：f(b)=0
# 其他情况：f(b)=f(b.lchild)+f(b.rchild)+1
def NodeCount4(bt):return _NodeCount4(bt.root)def _NodeCount4(t):if t == None:return 0else:return _NodeCount4(t.lchild) + _NodeCount4(t.rchild) + 1# 例6.9输出结果
print("基于前序遍历的节点数:", NodeCount1(bt))  # 应该输出 6
print("基于中序遍历的节点数:", NodeCount2(bt))  # 应该输出 6
print("基于后序遍历的节点数:", NodeCount3(bt))  # 应该输出 6
print("基于直接递归的节点数:", NodeCount4(bt))  # 应该输出 6

例6.10 假设二叉树采用二叉链存储结构存储，设计一个算法按从左到右输出一棵二叉树中所有叶子结点值。

由于先序、中序和后序递归遍历算法都是按从左到右的顺序访问叶子结点的，所以本题可以基于这三种递归遍历算法求解。
对于一个二叉树中的节点 t，可以通过递归遍历的方法来输出所有叶子节点：
1.判断当前节点是否为空：如果当前节点为 None，直接返回，表示当前子树为空。
2.判断当前节点是否为叶子节点：如果当前节点的左右子节点均为 None，那么当前节点就是叶子节点，直接输出它的值。
3.递归遍历子树：如果当前节点不是叶子节点，继续递归遍历左子树和右子树。

# 前序遍历输出叶子节点
def Displeaf1(bt):_Displeaf1(bt.root)print()  # 换行def _Displeaf1(t):if t != None:if t.lchild == None and t.rchild == None:print(t.data, end=' ')_Displeaf1(t.lchild)_Displeaf1(t.rchild)# 中序遍历输出叶子节点
def Displeaf2(bt):_Displeaf2(bt.root)print()  # 换行def _Displeaf2(t):if t != None:_Displeaf2(t.lchild)if t.lchild == None and t.rchild == None:print(t.data, end=' ')_Displeaf2(t.rchild)# 后序遍历输出叶子节点
def Displeaf3(bt):_Displeaf3(bt.root)print()  # 换行def _Displeaf3(t):if t != None:_Displeaf3(t.lchild)_Displeaf3(t.rchild)if t.lchild == None and t.rchild == None:print(t.data, end=' ')# 直接递归输出叶子节点
def Displeaf4(bt):_Displeaf4(bt.root)print()  # 换行def _Displeaf4(t):if t != None:if t.lchild == None and t.rchild == None:print(t.data, end=' ')else:_Displeaf4(t.lchild)_Displeaf4(t.rchild)# 例6.10输出结果
print("前序遍历输出叶子节点:")
Displeaf1(bt)  # 输出应为: 2 7 20print("中序遍历输出叶子节点:")
Displeaf2(bt)  # 输出应为: 2 7 20print("后序遍历输出叶子节点:")
Displeaf3(bt)  # 输出应为: 2 7 20print("直接递归输出叶子节点:")
Displeaf4(bt)  # 输出应为: 2 7 20

例6.11 假设二叉树采用二叉链存储结构存储，设计一个算法将二叉树bt1复制到二叉树bt2。

要复制二叉树 bt1 到 bt2，我们可以递归地遍历 bt1 的每一个节点，并在 bt2 中创建对应的节点。
每一个节点的复制需要包括它的值、左子树和右子树。我们可以选择前序遍历或后序遍历来实现这个复制过程：
1.前序遍历复制：先复制当前节点的值，再递归复制左子树和右子树。
2.后序遍历复制：先递归复制左子树和右子树，再复制当前节点的值。

# 前序遍历复制二叉树
def CopyBTree1(bt1):bt2 = BTree()bt2.SetRoot(_CopyBTree1(bt1.root))return bt2def _CopyBTree1(t1):if t1 is None:return Noneelse:t2 = TreeNode(t1.data)  # 复制当前节点t2.lchild = _CopyBTree1(t1.lchild)  # 递归复制左子树t2.rchild = _CopyBTree1(t1.rchild)  # 递归复制右子树return t2# 后序遍历复制二叉树
def CopyBTree2(bt1):bt2 = BTree()bt2.SetRoot(_CopyBTree2(bt1.root))return bt2def _CopyBTree2(t1):if t1 is None:return Noneelse:l = _CopyBTree2(t1.lchild)  # 递归复制左子树r = _CopyBTree2(t1.rchild)  # 递归复制右子树t2 = TreeNode(t1.data)  # 复制当前节点t2.lchild = lt2.rchild = rreturn t2# 例6.11输出结果
# 初始化原始二叉树
bt1 = BTree()
bt1.SetRoot(root)
# 使用前序遍历复制
bt2 = CopyBTree1(bt1)
print("前序遍历复制完成")# 使用后序遍历复制
bt3 = CopyBTree2(bt1)
print("后序遍历复制完成")# 前序遍历打印树，用于验证
def PreOrderPrint(t):if t is not None:print(t.data, end=' ')PreOrderPrint(t.lchild)PreOrderPrint(t.rchild)# 验证复制的二叉树
print("原始树前序遍历:")
PreOrderPrint(bt1.root)print("\n前序复制的树前序遍历:")
PreOrderPrint(bt2.root)print("\n后序复制的树前序遍历:")
PreOrderPrint(bt3.root)
print()

不建议采用中序遍历思路求解？

1. 前序和后序复制可以一步一步构建出和原树一样的结构
   在复制二叉树的时候，我们希望能够一步一步地构建出一个和原树结构完全相同的新树。前序和后序遍历的特点非常适合这个任务。
   前序遍历是“根节点 -> 左子树 -> 右子树”。这个顺序让我们：
   先创建根节点，
   然后递归地去创建左子树，
   最后递归地去创建右子树。
   每次我们递归一个节点，就可以立刻把它的左子树和右子树加到新树的对应位置上，所以整个树的结构可以按顺序完全复制。
   后序遍历是“左子树 -> 右子树 -> 根节点”。这个顺序让我们：
   先递归地创建左子树，
   再递归地创建右子树，
   最后再创建当前的根节点并把子树加到它上面。
   这种方法也可以保证每一步我们都能准确地复制出原树的结构。

2. 中序遍历的顺序在复制过程中会打乱树的结构
   中序遍历的顺序是“左子树 -> 根节点 -> 右子树”。这个顺序在复制过程中不太好用，因为：
   在处理左子树时，我们还没有访问根节点，因此无法把左子树连接到新的根节点上。
   我们必须等到左子树复制完，访问根节点，再开始右子树的复制。这会让我们很难保持复制过程中树的结构。

简单来说：中序遍历没有“从上到下”或“从下到上”地一步步处理完整棵树，而是“左中右”分开来访问，导致在复制过程中很难确定哪里是根节点，哪里是左右子树，最终可能导致复制出来的树结构和原来的不一样。

例6.12 假设一棵二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法求二叉树中指定结点值的结点所在的层次（根结点的层次计为1）。

1.定义递归函数 _Level(t, x, h)：
- t：当前节点
- x：要查找的目标值
- h：当前节点的层次（初始值为 1，表示根节点的层次）
2.递归遍历整个树：
- 如果当前节点 t 是 None，返回 0，表示该路径未找到目标节点。
- 如果当前节点的值 t.data 等于 x，表示找到目标节点，返回当前层次 h。
- 如果当前节点不是目标节点，先递归在左子树中查找。
- 如果在左子树中找到了（即返回值不为 0），则直接返回找到的层次。
- 如果左子树中未找到，再递归在右子树中查找。
3.主函数 Level(bt, x)：
- 调用 _Level 函数，传入树的根节点 bt.root、目标值 x 和初始层次 1，得到目标节点的层次。

# 查找指定节点值所在的层次
def Level(bt, x):return _Level(bt.root, x, 1)def _Level(t, x, h):if t is None:return 0  # 空节点未找到，返回 0elif t.data == x:return h  # 找到目标节点，返回其层次else:l = _Level(t.lchild, x, h + 1)  # 递归在左子树中查找if l != 0:return l  # 左子树中找到，返回层次else:return _Level(t.rchild, x, h + 1)  # 左子树未找到，在右子树中查找# 例6.12输出结果
print("节点 10 的层次:", Level(bt, 10))  # 应输出 1
print("节点 5 的层次:", Level(bt, 5))    # 应输出 2
print("节点 7 的层次:", Level(bt, 7))    # 应输出 3
print("节点 20 的层次:", Level(bt, 20))  # 应输出 3
print("节点 100 的层次:", Level(bt, 100))  # 不存在，应输出 0

例6.15 假设二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法输出值为x的结点的所有祖先。

使用递归函数遍历二叉树。
每次递归时检查当前节点的左子树和右子树，看其中是否存在目标节点。
如果在左子树或右子树中找到了目标节点，则说明当前节点是目标节点的祖先，将当前节点值添加到结果列表 res 中。
在递归返回前，最终将 res 逆序，以从根到叶节点的顺序输出祖先链。

# 查找节点 x 的所有祖先节点
def Ancestor1(bt, x):res = []_Ancestor1(bt.root, x, res)res.reverse()  # 逆序排列，使祖先节点从根到叶子顺序return resdef _Ancestor1(t, x, res):if t is None:return False# 如果当前节点是 x 的父节点，即当前节点的左子节点是否存在且等于目标值 xif (t.lchild and t.lchild.data == x) or (t.rchild and t.rchild.data == x):res.append(t.data)return True# 如果目标在左子树中找到，当前节点是其祖先if _Ancestor1(t.lchild, x, res) or _Ancestor1(t.rchild, x, res):res.append(t.data)return Truereturn False# 例6.15输出结果
print("节点 7 的祖先:", Ancestor1(bt, 7))  # 应输出: [10, 5]
print("节点 20 的祖先:", Ancestor1(bt, 20))  # 应输出: [10, 15]
print("节点 5 的祖先:", Ancestor1(bt, 5))  # 应输出: [10]
print("节点 10 的祖先:", Ancestor1(bt, 10))  # 根节点应输出空列表 []