非递归后序遍历二叉树算法详解及实例分析
5星
- 浏览量: 0
- 大小:None
- 文件类型：PDF
简介：
本文详细解析了非递归方式实现二叉树后序遍历的算法原理，并通过具体示例进行深入剖析和代码实现。
在前序、中序和后序遍历的非递归方法中，后序遍历是最复杂的。如果仅使用栈来存储指向节点的指针是不够的，还需要额外的信息存放在栈中以帮助完成正确的遍历顺序。
定义一个栈结点的数据结构如下：
```c
typedef struct {
Node *p;
int rvisited; // 当rvisited为1时，表示该结点的右子树已被访问。
} SNode;
```
其中`Node`是二叉树节点的结构体类型。
后序遍历函数可以这样实现：
```c
void lastOrderTraverse(BiTree bt) {
Node *p = bt; // 初始化指针，指向根结点
while (true) {
// 往左下方走，直到没有左子节点为止，并将路径上的每个结点入栈。
while (p != NULL) {
push(p, 0);
p = p->left;
}
if (stackEmpty()) break; // 如果栈为空，则遍历结束
SNode top = pop(); // 弹出当前栈顶元素
Node *current;
if (!top.rvisited && top.p->right != NULL) {
current = top.p->right;
push(top.p, 1); // 更新已访问右子树的信息，并将该结点重新入栈。
p = current; // 继续处理右子节点
} else {
visit(top.p); // 访问当前节点（即输出或记录）
}
}
}
```
这样就可以实现二叉树的非递归后序遍历。
全部评论 (0)
