二叉树后序遍历（非递归）

二叉树非递归后序遍历的思想是什么 越详细越好 急急！！！！~

按照二叉树后序遍历的定义，无论是访问整颗树还是其子树均应该遵循选访问根结点的左子树，然后访问根结点的右子树，最后访问根结点的规律。因此对于一棵树（子树）t ，如果 t 非空，首先应该进入t的左子树访问，此时由于t的右子树及根结点尚未访问，因此必须将t保存起来，放入栈中，以便访问完左子树后，从栈中取出t，进行其右子树及根结点的访问。这里值得注意的是，当一个元素位于栈顶即将处理时，其左子树的访问一定已经完成，如果其右子树尚未遍历，接下来应该进入其右子树的访问，而此时该栈顶元素是不能出栈的，因为其根结点还未被访问；只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输其根结点的值。因此，在二叉树后序遍历的过程中，必须使用seq.stack类型中的数组tag，其每个元素取值为0或1，用于标识栈中每个元素的状态。当一个元素刚进栈时，其对应的tag值置0；当它第一次位于栈顶即将被处理时，其tag值为0，意味着应该访问其右子树，于是将其右子树作为当前处理的对象，此时该栈顶元素仍应该保留在栈中，并将其对应的tag值改为1；当其右子树访问完成后，该元素又一次位于栈顶，而此时其tag值为1，意味着应该访问其根结点，并将其出栈。在整个二叉树后序遍历的过程中，程序要做的工作始终分成两个部分：当前正在处理的树（子树）和保存在栈中待处理的部分。只有这两部分的工作均完成后，程序方能结束。
（以上存手工输入）

后序遍历的非递归步骤类似于中序遍历，在遍历左子树前将根结点指针送入栈中
但是左子树遍历完成后，无法访问根结点，只有在右子树遍历完后，才能访问根结点

如果不使用标志位区分第几次到达根结点，可以利用如下的后序遍历特征来完成：
当栈顶元素(根)的右子树为空(即：无右孩子)，或者是右子树非空但是已遍历完，即右孩子恰好是刚才访问过的结点，此时应访问栈顶结点，并在访问后退栈
否则，如果栈顶元素的右孩子非空且未遍历，此时直接访问栈顶元素的右孩子而不退栈

算法要点只是需要记住最近访问过的结点即可，也就是每次访问一个结点后，就记住这个结点

一，大循环中的第一个循环，当前节点一直往左走一直走到头，并且把走过的节点压栈，这个循环遍历完成后，栈里面都是左边走过但是右边还没有走过的节点

二，从最左边那个没有更左的那个节点，它位于栈顶，因为这时栈顶不是一个右节点，第二个循环跳过，然后把栈顶结点的右节点标记为r并以此作为根节点重复之前的操作

回溯：
因为一直往下层走，总会遇到既没有左节点有没有右节点的节点，就是叶子节点，就开始往回退 取他的右节点，取之前会把该节点标记为r，但是他没有右节点，为null，就会跳过第一个循环，来到第二个，那么这个叶子就从栈中pop掉，新的栈顶结点是那个叶子的父节点，如果没有右节点，那他就成了叶子，更简单，如果有右节点，那么继续二

一步一步推就是这样子，需要考虑所有情况，会把问题想复杂，但是利用递归的思想就好想了
参考递归算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一个函数就是第一个小循环，只走左边，然后把新得到的节点作为根节点，继续调用第一个函数，得到左节点，然后再作为根节点，直到左节点为空；
第二个函数就是最后一个if，非递归算法中是从栈顶取，就是左边走过了的节点，相当于递归中，第一个函数执行完已经返回，然后取他的右节点作为根节点，继续递归
以上回答你满意么？

---

池州市19777567683： 求高手解答!!!!!!!!!!!!!!! 实验内容: 二叉树后序遍历的非递归算法 - ？
旗皇阿苯： /*后序非递归遍历二叉树函数*/ Status PostOrderTree(BiTLink T){struct {BiTLink nodeptr[STACK_INIT_SIZE]; /*存放树中结点的指针*/int subtreetag[STACK_INIT_SIZE]; /*存放左右子树标志*/int top;}stack;stack.top=-1;do{while(...

池州市19777567683： 求二叉树的非递归后序遍历的c语言代码? - ？
旗皇阿苯： #include<iostream> #include<stdio.h> #define N 10 using namespace std;char *a;typedef struct NODE{char data;struct NODE *lch, *rch,*parent; } *BINTREE,Node;void visit(char data){ printf(＂%5c＂,data); }void preorder(BINTREE T){ // 先...

池州市19777567683： 二叉树后序遍历非递归算法程序跪求解释 - ？
旗皇阿苯： 一,大循环中2113的第一个循环,当5261前节点一直往左走一直走到头,并且4102把走过的节点压栈,这个循1653环遍历完成后,栈里面都是左边走过但是右边还没有走过的节点 二,从最左边那个没有更左的那个节点,它位于栈顶,因为这时...

池州市19777567683： 二叉树非递归后序遍历的思想是什么 越详细越好 急急!!!! - ？
旗皇阿苯： 按照二叉树后序遍历的定义,无论是访问整颗树还是其子树均应该遵循选访问根结点的左子树,然后访问根结点的右子树,最后访问根结点的规律.因此对于一棵树(子树)t ,如果 t 非空,首先应该进入t的左子树访问,此时由于t的右子树及根...

池州市19777567683： 二叉树非递归后序遍历的思路是什么 - ？
旗皇阿苯： 前序:根-左-右;中序:左-根-右;后序:左-右-根.遍历的思路有3个重点:1)利用堆栈实现递归2)树中结点要有指向父结点的指针 //后序遍历用不上这一条3)树中结点要有标志记录是否已被访问过 上述3点其实就是自己来完成原来递归实现...

池州市19777567683： 二叉树的后序遍历非递归算法 - ？
旗皇阿苯： typedef struct node { //定义树的结点 int data; struct node *left; struct node *right;} *btree;void AfterTraverseNotRecursive(node *root) //非递归后序遍历{ b...

池州市19777567683： 求一个二叉树的后序遍历非递归算法 - ？
旗皇阿苯： // 中序遍历伪代码:非递归版本,用栈实现,版本2 void InOrder2(TNode* root) { Stack S; if( root != NULL ) { S.push(root); } while ( !S.empty() ) { TNode* node = S.pop(); if ( node->bPushed ) { // 如果标识位为true,则表示其左右子树都已经入栈,...

池州市19777567683： 一个二叉树的后序遍历的非递归算法代码是多少？
旗皇阿苯： #include <stdio.h> #include <stdlib.h> //#include <conio.h> struct TREE //二叉树结点结构 { char data; struct TREE *lsubtree; struct TREE *Rsubtree; }; struct TREE *tree; void createtree(struct TREE *&p) //先序创建二叉树 { char ch; ch = getchar(); if (...

池州市19777567683： c语言 数据结构 非递归遍历二叉树 - ？
旗皇阿苯： /* 非递归法遍历二叉树 C语言 VC 6.0 */#include ＂stdio.h＂#include ＂stdlib.h＂ typedef char Datatype; typedef struct BinTNode{ Datatype data; struct BinTNode *lchild, *rchild; }BinTree,*PBinTree; typedef struct stnode{ //栈的结构 Datatype data; ...

池州市19777567683： c++ 采用二叉链表作存储结构,实现二叉树非递归后序遍历算法 - ？
旗皇阿苯： 链接存储的二叉树类型和结构定义如下:typedef struct bnode { ElemType data; struct bnode *lchild, *rchild; } btree; 后序遍历 void postorder(btree *bt) { btree *p=bt, *stack[MAX];//p表示当前结点,栈stack[]用来存储结点int tag[MAX]; int ...