C语言如何实现非递归方式的后序遍历二叉树？

本文共计919个文字，预计阅读时间需要4分钟。

C语言实现二叉树的非递归后序遍历算法及前序、中序的遍历方法：- 后序遍历：根、右、左- 前序遍历：根、左、右- 中序遍历：左、根、右在遍历中，要注意后序遍历中后序的顺序，确保最后一个访问的是根节点。如果仅在栈中保留指向节点的指针，可能不足以完成遍历，需要额外保存一些信息。

C语言数据结构之二叉树的非递归后序遍历算法

前言：

前序、中序、后序的非递归遍历中，要数后序最为麻烦，如果只在栈中保留指向结点的指针，那是不够的，必须有一些额外的信息存放在栈中。

方法有很多，这里只举一种，先定义栈结点的数据结构

typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构，rvisited==1代表p所指向的结点的右结点已被访问过。 lastOrderTraverse(BiTree bt){ 　　//首先，从根节点开始，往左下方走，一直走到头，将路径上的每一个结点入栈。