买了个网站源码后要怎么用_青岛疫情最新动态_百度账号个人中心_手机访问另一部手机访问文件

11、后序非递归遍历二叉树

后序非递归遍历二叉树

第一步：定义全局变量和结构体

根据题目中的“后序非递归遍历二叉树”，我们需要定义一个二叉树节点结构体 BTNode 和一个栈 St 用于存储节点。

// 定义二叉树节点结构体
typedef struct BTNode {int data;struct BTNode *lchild, *rchild;
} BTNode;// 函数用于后序非递归遍历二叉树
void Nonpost(BTNode *bt) {// （1）设定变量BTNode *St[MAXSIZE]; // 定义栈BTNode *tag = NULL; // tag用于标记是否访问了右孩子int top = -1; // 栈顶指针初始化为-1

第二步：实现后序遍历逻辑

根据题目要求，我们需要实现后序遍历的逻辑，即先访问左子树，再访问右子树，最后访问根节点。

    // （2）实现后序遍历逻辑while (bt != NULL || top != -1) {// 遍历左子树，直到当前节点为空或者没有左孩子if (bt != NULL) {St[++top] = bt; // 将当前节点压入栈bt = bt->lchild; // 移动到左孩子} else {BTNode *peekNode = St[top]; // 查看栈顶节点// 如果栈顶节点的右孩子存在且未被访问过，则移动到右孩子if (peekNode->rchild && peekNode->rchild != tag) {bt = peekNode->rchild; // 移动到右孩子} else {// 访问根节点printf("%d ", peekNode->data);tag = peekNode; // 标记右孩子已被访问top--; // 弹出栈顶元素bt = NULL; // 重置bt为NULL，继续循环}}}
}