非递归遍历二叉树：前中后序代码详解

本文档主要介绍了如何使用非递归方法遍历二叉树，重点讲解了前序、中序和后序遍历。首先，我们定义了一个名为`lnode`的结构体，用于表示二叉树节点，以及与之相关的栈结构`linkstack`。接下来，文中给出了初始化栈、获取栈顶元素、压入元素、弹出元素以及判断栈是否为空等基本操作的函数实现。 1. **栈结构与操作**: - 初始化一个空栈：`init(linkstack *s)`创建一个指向`lnode`的指针`s`并将其下一个节点设置为`NULL`。 - 获取栈顶元素：`int gettop(linkstack s, Bitree *e)`检查栈是否为空，然后将栈顶元素数据赋值给`e`。 - 压入元素：`void push(linkstack *s, Bitree e)`动态分配一个新的`lnode`并将给定的`e`节点数据放入栈顶，然后更新链表链接。 - 弹出元素：`void pop(linkstack *s, Bitree *e)`取出栈顶元素并将其赋值给`e`，同时释放栈顶节点，保持栈的结构。 - 判断栈是否为空：`int stackempty(linkstack head)`检查栈头的下一个节点是否为`NULL`，以确定栈是否为空。 2. **前序非递归遍历**: - `void inodertra(Bitree T)`函数实现了前序遍历（根-左-右），它通过栈来模拟递归过程。首先，初始化栈`s`，然后进入一个循环，当当前节点`p`不为空或栈不为空时，进行以下操作： - 打印当前节点（根节点）的数据。 - 将当前节点压入栈。 - 更新当前节点为当前节点的左子节点（直到左子节点为空）。 3. **中序非递归遍历**: - 类似于前序遍历，中序遍历（左-根-右）的过程也需要栈来辅助，但访问节点的顺序不同。在中序遍历中，需要先处理左子树，再访问根节点。 4. **后序非递归遍历**: - 后序遍历（左-右-根）则需要对栈的操作更复杂，需要记录遍历过的节点以便在访问完所有子节点后再访问它们。具体实现方式可能涉及两个栈，一个用于存储待访问的节点，另一个用于存储已经访问过的节点。 总结，这段代码展示了如何使用非递归的方式遍历二叉树，通过利用栈数据结构，可以避免传统递归算法的调用栈开销，提高效率。理解这些核心函数的实现原理是深入掌握二叉树遍历的关键。