二叉树的遍历非递归算法中应注意哪些问题

二叉树中序遍历非递归算法(c语言实现）~

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0

struct node
{
char data;
struct node *lchild;
struct node *rchild;
};

//先序，中序 建树
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;

head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}


//中序递归遍历
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}



//中序非递归遍历

void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;

p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}


//主函数
int main()
{
struct node * head;
char pre[30],ord[30];
int n;

gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("
");
inorder1(head);
printf("
");
}

//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/

几个月前自己编写，原版
vc++ 6.0实验通过

怎么样，老板，第一次上百度知道，好激动
给点面子
给分！给分啊

// 中序遍历伪代码：非递归版本，用栈实现，版本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 data << endl;
st.pop();
pre = p;
p = NULL;

}
else
{
p = p->right;

}
}//end of while(p || st.size()!=0)

}

先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法一，流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}

if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法二，流程图如右，当型循环
InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右，当型循环
InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】

T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}

while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 设置栈顶标记
T = GetTopPointer(S); // 取栈顶保存的指针
T = T->rchild;
}else break;
}
}

---

吴兴区13312552883： 二叉树的非递归遍历?要有讲解 不要纯程序~!! - ？
海庙盐酸： 我尽量写得详细一点,你再回去自己举个例子应该就容易明白了,这个遍历采用的是中序遍历. struct node{int data;struct node *lchild;struct node *rchild;}/*定义结点,lchild和rchild分别为左右孩子*/ void inorder(struct node *T) {struct node ...

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

吴兴区13312552883： 如何不用递归遍历二叉树 - ？
海庙盐酸： 非递归的方法是用存储代替计算,就是在建立树时,实现了存储展开,相当于存储了未来需要遍历的路径,所以就快了.递归是送快递,一层层往下递,非递归是先建好区域仓库,由各地仓库储存发货,所以速度更快,但需要仓库储存(内存占...

吴兴区13312552883： 先序遍历二叉树非递归算法如何理解?? - ？
海庙盐酸： 先序遍历是中->左->右 进行遍历,每次 读入中后,下一步是读入左,读入左的下一步是读入右,但是左可能也是一颗树,那么 右就应该被压栈,保存.等左读完了,取出右再读入.对子树进行同样的操作.也就是 除了叶子节点,所有的右子节点都要压一次栈. 递归的是调用的系统栈,非递归的是用 堆中的数组来模拟系统栈.最直观的概念是 如果你有一个大任务,可以分成几个小任务,为了知道做完一个小任务后怎么办,你应当把其他小任务记下来,记到本子上.

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

吴兴区13312552883： 二叉树的中序非递归遍历问题 - ？
海庙盐酸： case 6: {printf(＂中序非递归遍历 : ＂); in_order(T); //先序遍历 你这里为什么要写T而不是root呢?你的T指针要不是没有初始化的值,要不是就是空值,写在这里没有任何意义.如果是空值还好,你的in_order函数会退出,如果是未初始化的值,那么程序就会崩溃了 还有在定义指针类型变量的时候最好初始化 BinTree T = NULL,root = NULL; //初始化变量是个好习惯 int i,depth; printf(＂\n＂);

吴兴区13312552883： 请教关于非递归的二叉树遍历算法 - ？
海庙盐酸： 中序非递归:1、根节点入栈 2、栈非空循环{循环I{if(栈顶元素有左孩子)左孩子入栈;else 跳出循环;}循环II{if(栈顶元素有右孩子){出栈访问栈顶元素;右孩子入栈;跳出循环;}else 出栈访问栈顶元素;}}3、结束

吴兴区13312552883： 二叉树非递归遍历的问题 - ？
海庙盐酸： 注意写算法和写程序是两码事 函数参数怎么能用 void InitStack(SqStack &S) 这里S表示一个什么东西?指针是SqStack *S,不是指针SqStack S,&S表示什么变量啊?估计你是想调进S的地址,那么函数void InitStack(SqStack *S); 调用时取地址InitStack(&S);

吴兴区13312552883： 二叉树中序遍历的非递归算法 - ？
海庙盐酸： #define MAXNODE 100 //二叉树最大节点数//定义二叉树链式结构 typedef struct BitNode { char data; //数据域 struct BitNode *lchild,*rchild;//左右指针域 }BitNode,*BiTree;//二叉树进行中序非递归遍历 void NRInorder(BiTree t) { BiTree s; //s-指向...

吴兴区13312552883： 二叉树的非递归遍历 - ？
海庙盐酸： 哈,我们数据结构的实验: typedef int Status; typedef int TElemType; typedef struct BiTNode {TElemType data;struct BiTNode *lchild, * rchild;//左右孩子指针 }BiTNode, *BiTree; typedef struct SqQueue {TElemType front ,rear ;BiTree data[...