Ardent迭代器家族源码全解栈与队列实现4种树遍历的完整清单【免费下载链接】ArdentA Collections library for PHP.项目地址: https://gitcode.com/gh_mirrors/ard/ArdentArdent 是一个面向 PHP 的集合Collections库它的迭代器家族用栈和队列两种基础结构优雅地实现了二叉树的 4 种经典遍历前序、中序、后序和层序。本文将带你快速读懂这套源码的设计思路帮你彻底搞懂树遍历为什么离不开栈与队列。一、先认识 Ardent 迭代器家族 Ardent 的核心理念是PHP 标准库SPL对常用数据结构的封装并不够丰富而数组又被过度使用。Ardent 补上了这块空白用面向对象的方式实现了链表、栈、队列、集合、映射、二叉树等结构。其中二叉树的遍历能力由一个专门的接口统一约束接口定义src/Collection/BinaryTreeIterator.php继承Enumerator实现Countable所有树遍历迭代器都实现该接口因此它们可以像数组一样被foreach遍历也可以用count()获取节点总数。二、为什么栈和队列是树遍历的最佳拍档 树是递归结构但非递归遍历需要借助额外结构来记住访问路径数据结构访问顺序适合场景栈LIFO 后进先出先压入的先被处理的是最近的节点深度优先前序、中序、后序队列FIFO 先进先出先入队的先被处理广度优先层序按层遍历一句话总结深度优先靠栈回头广度优先靠队列排队。三、4 种遍历迭代器完整清单 遍历方式迭代器类依赖结构源码位置前序根→左→右PreOrderIterator栈src/Collection/PreOrderIterator.php中序左→根→右InOrderIterator栈src/Collection/InOrderIterator.php后序左→右→根PostOrderIterator栈src/Collection/PostOrderIterator.php层序逐层LevelOrderIterator队列src/Collection/LevelOrderIterator.php下面逐个拆解它们的关键实现。1. 前序遍历栈模拟先访问根PreOrderIterator的思路非常直观rewind()新建一个LinkedStack把根节点压栈见src/Collection/PreOrderIterator.php第 42~47 行next()弹出栈顶节点先压右子、再压左子利用栈的后进先出保证左子先被访问这个右左颠倒压栈的 trick 是前序遍历非递归实现的标准写法。2. 中序遍历栈保存左链InOrderIteratorsrc/Collection/InOrderIterator.php是四种实现中最简洁的rewind()调用私有方法pushLeft()把从根节点开始的所有左子节点一路压栈第 110~114 行current()直接返回栈顶节点的值next()弹出栈顶如果它有右子树就把右子树的左链再压栈栈在这里扮演的是回溯路径的角色——随时能回到未完成的祖先节点。3. 后序遍历最复杂的栈实现PostOrderIteratorsrc/Collection/PostOrderIterator.php的难点在于根最后访问。源码用一组私有小方法拆解状态机next_valueNotNull()把当前节点的右子入栈然后沿左子继续第 115~121 行next_right()判断右子是否已处理决定是否回退到栈中继续next_set()把当前节点确定为输出值并移动 key阅读建议先弄清栈中存的是父节点链再看每个分支如何修改value指针状态机就清晰了。4. 层序遍历队列逐层出队LevelOrderIteratorsrc/Collection/LevelOrderIterator.php是唯一的广度优先实现rewind()初始化队列为[根节点]第 43~47 行next()array_shift()取出队首节点把它的左子、右子依次入队第 81~94 行队列空时遍历结束虽然这里内部用了数组模拟队列而非LinkedQueue但思想与队列完全一致先进先出保证同层节点按顺序访问。四、底层支撑栈与队列是怎么实现的 4 个遍历迭代器站在两个基础集合之上LinkedStacksrc/Collection/LinkedStack.php基于链表节点Pair实现push()新节点直接指向旧top第 45~48 行pop()返回top-first并前进指针last()可在不弹出时偷看栈顶——树遍历迭代器正是靠last()拿到当前节点LinkedQueuesrc/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.phptest/Collection/BinarySearchTree/PreOrderIteratorTest.phptest/Collection/BinarySearchTree/PostOrderIteratorTest.phptest/Collection/BinarySearchTree/LevelOrderIteratorTest.php公共基类test/Collection/BinarySearchTree/BinaryTreeIteratorTest.php克隆仓库后仓库地址https://gitcode.com/gh_mirrors/ard/Ardent用phpunit.xml配置即可运行全部测试观察四种遍历在 BST 上输出的有序/有序变体序列。六、小结一张清单带走核心要点 ✨前序、中序、后序 栈深度优先遍历靠栈保存回溯路径层序 队列广度优先靠队列保证逐层顺序四种迭代器统一实现BinaryTreeIterator接口支持foreach与count()栈/队列本身基于Pair链表节点入出操作均为 O(1)。读懂这 4 个文件约 400 行你就掌握了非递归树遍历的全部套路——这也是 Ardent 迭代器家族最值得入门的一处源码。【免费下载链接】ArdentA Collections library for PHP.项目地址: https://gitcode.com/gh_mirrors/ard/Ardent创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考