先序遍历、中序遍历、后续遍历的非递归实现

作者: Temple_Li | 来源:发表于2017-09-18 20:53 被阅读0次

【数据结构】【C#】026-二叉树（BT）：🌱遍历介绍
二叉树的遍历算法
数据结构-树的遍历
二叉树遍历
树的遍历
树
二叉树遍历
java二叉树三种遍历实现
二叉树的遍历
手敲数据结构——二分搜索树

void PreOrderTraverse(BiTree T)//非递归先序遍历  
{  
      
    stack<BiTree> Stack;  
    if(!T)  
    {  
        printf("空树！\n"); 
        return;  
    }  
    while(T || !Stack.empty())  
    {  
        while(T)  
        {
            Stack.push(T);
            printf("%c",T->data); 
            T=T->lchild; 
        }
        T=Stack.top(); 
        Stack.pop(); 
         T=T->rchild;  
    }                                                                                                                                     
}

void InOrderTraverse(BiTree T)//非递归中序遍历  
{  
      
    stack<BiTree> Stack;  
    if(!T)  
    {  
        printf("空树！\n");  
        return;  
    }  
      
    while(T || !Stack.empty())  
    {  
        while(T)  
        {  
            Stack.push(T);  
            T=T->lchild;  
        }  
        T=Stack.top();  
        Stack.pop();  
        printf("%c",T->data);  
        T=T->rchild;  
    }                                                                                                                                     
}

void PostOrderTraverse(BiTree T)//非递归后序遍历,用一个标记标记右子树是否访问过  
{  
    int flag[20];  
    stack<BiTree> Stack;  
    if(!T)  
    {  
        printf("空树！\n");  
        return;  
    }  
    while(T)  
    {  
        Stack.push(T);  
        flag[Stack.size()]=0;  
        T=T->lchild;  
    }  
    while(!Stack.empty())  
    {  
        T=Stack.top();            
        while(T->rchild && flag[Stack.size()]==0)  
        {  
            flag[Stack.size()]=1;  
            T=T->rchild;  
            while(T)  
            {  
                Stack.push(T);  
                flag[Stack.size()]=0;  
                T=T->lchild;  
            }  
        }  
        T=Stack.top();  
        printf("%c",T->data);  
        Stack.pop();  
    }                                                                                                                                     
}