求一个二叉树的后序遍历非递归算法

[数据结构课程设计二叉排序树的实现用顺序和二叉链表作存储结构]/*以下是用c++ 实现的二叉排序树的源代码*/ #includetypedef struct TreeNode { int key; struct TreeNode *left; struct TreeNode *right; }treeNode; class BiSortTree {...+阅读

求一个二叉树的后序遍历非递归算法

// 中序遍历伪代码：非递归版本，用栈实现，版本2 void InOrder2(TNode* root) { Stack S; if( root != NULL ) { S.push(root); } while ( !S.empty() ) { TNode* node = S.pop(); if ( node->bPushed ) { // 如果标识位为true，则表示其左右子树都已经入栈，那么现在就需要访问该节点了 Visit(node); } else { // 左右子树尚未入栈，则依次将右节点，根节点，左节点入栈 if ( node->right != NULL ) { node->right->bPushed = false； // 左右子树均设置为false S.push(node->right); } node->bPushed = true； // 根节点标志位为true S.push(node); if ( node->left != NULL ) { node->left->bPushed = false; S.push(node->left)； } } } } 对比先序遍历，这个算法需要额外的增加O(n)的标志位空间。

另外，栈空间也扩大，因为每次压栈的时候都压入根节点与左右节点，因此栈空间为O(n)。时间复杂度方面，每个节点压栈两次，作为子节点压栈一次，作为根节点压栈一次，弹栈也是两次。因此无论从哪个方面讲，这个方法效率都不及InOrder1。后序 void postOrder(TreeNode*root) { stack*>st; TreeNode*p = root; TreeNode*pre = NULL;//pre表示最近一次访问的结点 while(p || st.size()!=0） { //沿着左孩子方向走到最左下。

while(p) { st.push(p); p = p->left; } //get the top element of the stack p = st.top（)； //如果p没有右孩子或者其右孩子刚刚被访问过 if(p->right == NULL || p->right == pre) { / isit this element and then pop it cout

后序遍历用递归和非递归的方法一起都要

我们的数据结构实验也是这题，需要我把我的实验报告给你参考下么！我这里就只发这部分的代码。Status PreOrderTraverse(BiTree T){ //先序遍历二叉树T的递归算法 if (T) { printf(＂%d ＂,T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->rchild) PreOrderTraverse(T->rchild); return FALSE; } else return OK;}Status PreOrder(BiTree T){ //先序遍历二叉树T的非递归算法 while(!(T==NULL&top==NULL)) { if(T) { printf(＂%d ＂,T->data); push(T); T=T->lchild; } else { T=(BiTree)pop(); T=T->rchild; } } }Status InOrderTraverse(BiTree T){ //中序遍历二叉树T的递归算法 if (T) { if (T->lchild) InOrderTraverse(T->lchild); printf(＂%d ＂,T->data); if (T->rchild) InOrderTraverse(T->rchild); return FALSE; } else return OK;}Status InOrder(BiTree T){ //中序遍历二叉树T的非递归算法 while(!(T==NULL&top==NULL)) { while(T) { push(T); T=T->lchild; } T=(BiTree)pop(); printf(＂%d ＂,T->data); T=T->rchild; }}Status PostOrderTraverse(BiTree T){ //后序遍历二叉树T的递归算法 if (T) { if (T->lchild) PostOrderTraverse(T->lchild); if (T->rchild) PostOrderTraverse(T->rchild); printf(＂%d ＂,T->data); return FALSE; } else return OK;}Status PostOrder(BiTree T){ //后序遍历二叉树T的递归算法 unsigned sign；//记录结点从栈中62616964757a686964616fe78988e69d8331333264643732弹出的次数 while(!(T==NULL&top==NULL)) { if(T) { push(T)；//第一次遇到结点T时压入其指针 push

(1)；//置标志为1 T=T->lchild; } else { while(top) { sign=pop(); T=(BiTree)pop(); if(1==sign)//表示走过T的左子树 { push(T); push

(2); T=T->rchild; break; } else { if(2==sign)//表示T的左右子树都已走过 { printf(＂%d ＂,T->data); T=NULL； } } } } }}另外，团IDC网上有许多产品团购，便宜有口碑

数据结构课程设计报告：后序遍历用递归和非递归的方法一起都

我们的数据结构实验也是这题，需要我把我的实验报告给你参考下么！我这里就只发这部分的代码。Status PreOrderTraverse(BiTree T) { //先序遍历二叉树T的递归算法 if (T) { printf(＂%d ＂,T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->rchild) PreOrderTraverse(T->rchild); return FALSE; } else return OK; } Status PreOrder(BiTree T) { //先序遍历二叉树T的非递归算法 while(!(T==NULL&top==NULL)) { if(T) { printf(＂%d ＂,T->data); push(T); T=T->lchild; } else { T=(BiTree)pop(); T=T->rchild; } } } Status InOrderTraverse(BiTree T) { //中序遍历二叉树T的递归算法 if (T) { if (T->lchild) InOrderTraverse(T->lchild); printf(＂%d ＂,T->data); if (T->rchild) InOrderTraverse(T->rchild); return FALSE; } else return OK; } Status InOrder(BiTree T) { //中序遍历二叉树T的非递归算法 while(!(T==NULL&top==NULL)) { while(T) { push(T); T=T->lchild; } T=(BiTree)pop(); printf(＂%d ＂,T->data); T=T->rchild; } } Status PostOrderTraverse(BiTree T) { //后序遍历二叉树T的递归算法 if (T) { if (T->lchild) PostOrderTraverse(T->lchild); if (T->rchild) PostOrderTraverse(T->rchild); printf(＂%d ＂,T->data); return FALSE; } else return OK; } Status PostOrder(BiTree T) { //后序遍历二叉树T的递归算法 unsigned sign；//记录结点从栈中弹出的次数 while(!(T==NULL&top==NULL)) { if(T) { push(T)；//第一次遇到结点T时压入其指针 push

(1)；//置标志为1 T=T->lchild; } else { while(top) { sign=pop(); T=(BiTree)pop(); if(1==sign)//表示走过T的左子树 { push(T); push

(2); T=T->rchild; break; } else { if(2==sign)//表示T的左右子树都已走过 { printf(＂%d ＂,T->data); T=NULL; } } } } } }

求二叉树后序遍历的非递归并行算法

#define maxsize 100typedef enum{L,R} tagtype;typedef struct { Bitree ptr; tagtype tag;}stacknode;typedef struct{ stacknode Elem[maxsize]; int top;}SqStack;void PostOrderUnrec(Bitree t){ SqStack s; stacknode x; StackInit(s); p=t; do { while (p!=null) //遍历左子树 { x.ptr = p; x.tag = L； //标记为左子树 push(s,x); p=p->lchild; } while (!StackEmpty(s) && s.Elem[s.top].tag==R) { x = pop(s); p = x.ptr; visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点 } if (!StackEmpty(s)) { s.Elem[s.top].tag =R； //遍历右子树 p=s.Elem[s.top].ptr->rchild; } }while (!StackEmpty(s));}//PostOrderUnrec 你参考一下，这应该是标准的答案