Ardent迭代器家族源码全解：栈与队列实现4种树遍历的完整清单

Ardent迭代器家族源码全解：栈与队列实现4种树遍历的完整清单

【免费下载链接】ArdentA Collections library for PHP.项目地址: https://gitcode.com/gh_mirrors/ard/Ardent

Ardent 是一个面向 PHP 的集合（Collections）库，它的迭代器家族用栈和队列两种基础结构，优雅地实现了二叉树的 4 种经典遍历：前序、中序、后序和层序。本文将带你快速读懂这套源码的设计思路，帮你彻底搞懂"树遍历为什么离不开栈与队列"。

一、先认识 Ardent 迭代器家族 🌳

Ardent 的核心理念是：PHP 标准库（SPL）对常用数据结构的封装并不够丰富，而数组又被过度使用。Ardent 补上了这块空白，用面向对象的方式实现了链表、栈、队列、集合、映射、二叉树等结构。

其中，二叉树的遍历能力由一个专门的接口统一约束：

• 接口定义：src/Collection/BinaryTreeIterator.php（继承Enumerator，实现Countable）

所有树遍历迭代器都实现该接口，因此它们可以像数组一样被foreach遍历，也可以用count()获取节点总数。

二、为什么栈和队列是树遍历的"最佳拍档" 🔑

树是递归结构，但非递归遍历需要借助额外结构来"记住"访问路径：

一句话总结：深度优先靠栈"回头"，广度优先靠队列"排队"。

三、4 种遍历迭代器完整清单 📋

下面逐个拆解它们的关键实现。

1. 前序遍历：栈模拟"先访问根"

PreOrderIterator的思路非常直观：

• rewind()：新建一个LinkedStack，把根节点压栈（见src/Collection/PreOrderIterator.php第 42~47 行）
• next()：弹出栈顶节点，先压右子、再压左子（利用栈的后进先出，保证左子先被访问）

这个"右左颠倒压栈"的 trick 是前序遍历非递归实现的标准写法。

2. 中序遍历：栈保存"左链"

InOrderIterator（src/Collection/InOrderIterator.php）是四种实现中最简洁的：

• rewind()：调用私有方法pushLeft()，把从根节点开始的所有左子节点一路压栈（第 110~114 行）
• current()直接返回栈顶节点的值
• next()：弹出栈顶，如果它有右子树，就把右子树的左链再压栈

栈在这里扮演的是"回溯路径"的角色——随时能回到未完成的祖先节点。

3. 后序遍历：最复杂的栈实现

PostOrderIterator（src/Collection/PostOrderIterator.php）的难点在于"根最后访问"。源码用一组私有小方法拆解状态机：

• next_valueNotNull()：把当前节点的右子入栈，然后沿左子继续（第 115~121 行）
• next_right()：判断右子是否已处理，决定是否"回退"到栈中继续
• next_set()：把当前节点确定为输出值并移动 key

阅读建议：先弄清"栈中存的是父节点链"，再看每个分支如何修改value指针，状态机就清晰了。

4. 层序遍历：队列逐层出队

LevelOrderIterator（src/Collection/LevelOrderIterator.php）是唯一的"广度优先"实现：

• rewind()：初始化队列为[根节点]（第 43~47 行）
• next()：array_shift()取出队首节点，把它的左子、右子依次入队（第 81~94 行）
• 队列空时遍历结束

虽然这里内部用了数组模拟队列（而非LinkedQueue），但思想与队列完全一致：先进先出保证同层节点按顺序访问。

四、底层支撑：栈与队列是怎么实现的 💪

4 个遍历迭代器站在两个基础集合之上：

• LinkedStack（src/Collection/LinkedStack.php）：
  • 基于链表节点Pair实现，push()新节点直接指向旧top（第 45~48 行）
  • pop()返回top->first并前进指针，last()可在不弹出时偷看栈顶——树遍历迭代器正是靠last()拿到"当前节点"
• LinkedQueue（src/Collection/LinkedQueue.php）：
  • 维护head和tail双指针，enqueue()尾插（第 41~51 行）、dequeue()头删（第 57~64 行），两端操作都是 O(1)
  • first()支持不取出查看队首

两者都是 O(1) 的入/出操作，这正是它们适合作为遍历引擎的原因。相关接口定义见src/Collection/Stack.php与src/Collection/Queue.php。

五、动手验证：测试用例在哪里跑 🧪

每个迭代器都有对应的单元测试，直接看"输入树 → 期望输出序列"最容易建立直觉：

• test/Collection/BinarySearchTree/InOrderIteratorTest.php
• test/Collection/BinarySearchTree/PreOrderIteratorTest.php
• test/Collection/BinarySearchTree/PostOrderIteratorTest.php
• test/Collection/BinarySearchTree/LevelOrderIteratorTest.php
• 公共基类：test/Collection/BinarySearchTree/BinaryTreeIteratorTest.php

克隆仓库后（仓库地址：https://gitcode.com/gh_mirrors/ard/Ardent），用phpunit.xml配置即可运行全部测试，观察四种遍历在 BST 上输出的有序/有序变体序列。

六、小结：一张清单带走核心要点 ✨

1. 前序、中序、后序 = 栈：深度优先遍历靠栈保存回溯路径；
2. 层序 = 队列：广度优先靠队列保证逐层顺序；
3. 四种迭代器统一实现BinaryTreeIterator接口，支持foreach与count()；
4. 栈/队列本身基于Pair链表节点，入出操作均为 O(1)。

读懂这 4 个文件（约 400 行），你就掌握了非递归树遍历的全部套路——这也是 Ardent 迭代器家族最值得入门的一处源码。

【免费下载链接】ArdentA Collections library for PHP.项目地址: https://gitcode.com/gh_mirrors/ard/Ardent