后序非递归遍历二叉树

要实现一个后序非递归遍历二叉树的算法。后序遍历的顺序是先遍历左子树，然后遍历右子树，最后访问根节点。

第一步：定义遍历函数

根据题目中的“后序非递归遍历二叉树”，我们需要：

1. 定义一个遍历函数 Nonpost，它接受一个二叉树节点的指针作为参数。

这部分的代码为：

void Nonpost(BTNode* bt) {BTNode *St[maxsize], *tag = NULL;int top = -1;

第二步：遍历二叉树

根据题目中的“后序非递归遍历”，我们需要：

1. 使用一个栈 St 来存储节点，top 用于指示栈顶。
2. 使用一个 while 循环来遍历树，直到栈为空且当前节点为 NULL。
3. 如果当前节点不为空，将其压入栈并移动到其左子节点。
4. 如果当前节点为空，从栈中弹出一个节点，并检查其右子节点。
5. 如果右子节点存在且未被访问过，移动到右子节点。
6. 否则，访问弹出的节点，并将其标记为已访问，然后将当前节点设置为 NULL。

这部分的代码为：

    while (bt || top != -1) {if (bt != NULL) {St[++top] = bt; // 将当前节点压入栈bt = bt->lchild; // 移动到左子节点} else {bt = St[top]; // 从栈中弹出节点if (bt->rchild && bt->rchild != tag) {bt = bt->rchild; // 移动到右子节点} else {bt = St[top--]; // 弹出节点cout << bt->data << " "; // 访问节点tag = bt; // 标记节点为已访问bt = NULL; // 将当前节点设置为NULL}}}
}

完整代码

#include <iostream>
using namespace std;// 定义二叉树节点结构
struct BTNode {int data;BTNode *lchild, *rchild;
};// 后序非递归遍历二叉树
void Nonpost(BTNode* bt) {BTNode *St[maxsize], *tag = NULL;int top = -1;while (bt || top != -1) {if (bt != NULL) {St[++top] = bt; // 将当前节点压入栈bt = bt->lchild; // 移动到左子节点} else {bt = St[top]; // 从栈中弹出节点if (bt->rchild && bt->rchild != tag) {bt = bt->rchild; // 移动到右子节点} else {bt = St[top--]; // 弹出节点cout << bt->data << " "; // 访问节点tag = bt; // 标记节点为已访问bt = NULL; // 将当前节点设置为NULL}}}
}

代码过程表格

描述变量在每一步的变化：

步骤	bt	top	St	tag	输出
初始	根节点	-1	空	NULL
1	左子节点	0	根节点	NULL
2	左子节点的左子节点	1	根节点, 左子节点	NULL
3	NULL	1	根节点, 左子节点	NULL
4	右子节点	1	根节点, 左子节点	左子节点
5	右子节点的右子节点	2	根节点, 左子节点, 右子节点	左子节点
6	NULL	2	根节点, 左子节点, 右子节点	左子节点	右子节点的数据
7	左子节点	2	根节点, 左子节点, 右子节点	右子节点
…	…	…	…	…	…

注意：
这个表格假设二叉树至少有两个节点，并且树的结构是已知的。在实际应用中，树的结构会根据具体情况而有所不同。