二叉树遍历-非递归方式

初始化代码

#include <iostream>
#include <string>
using namespace std;
// 二叉树
typedef struct BiTNode
{
    string data;
    BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 初始化二叉树
BiTree tree;
tree = new BiTNode;
tree->data = "1";

BiTNode *p;

p = new BiTNode;
p->data="2";
p->lchild=NULL;
p->rchild=NULL;
tree->lchild=p;

p = new BiTNode;
p->data="3";
p->lchild=NULL;
p->rchild=NULL;
tree->rchild=p;


p = new BiTNode;
p->data="4";
p->lchild=NULL;
p->rchild=NULL;
tree->lchild->rchild=p;

p = new BiTNode;
p->data="6";
p->lchild=NULL;
p->rchild=NULL;
tree->lchild->rchild->lchild=p;

p = new BiTNode;
p->data="5";
p->lchild=NULL;
p->rchild=NULL;
tree->rchild->rchild=p;

用链式线性表做栈

typedef struct StackNode{
    BiTree data;
    StackNode *next;
}*Stack;

void InitStack(Stack &S)
{
    S = new StackNode;
    S->next=NULL;
}
void InitStack(Stack &S)
{
    S = new StackNode;
    S->next=NULL;
}
BiTree PopStack(Stack &S)
{
    BiTree x=S->next->data;
    StackNode *q = S->next;
    S->next=S->next->next;
    free(q);
    return x;
}
BiTree TopStack(Stack &S)
{
    return S->next->data;
}

1. 先序遍历

/*
先序遍历非递归方案；
顺序：中、左、右
先访问中
有右子树先push到stack
再访问左子树
没有再pop出stack
*/

void PreOrder(BiTree &T)
{
    Stack s;
    InitStack(s);
    BiTree p=T;
    while(p||!StackIsEmpty(s))
    {
        if(p)
        {
            cout<<p->data;
            if(p->rchild)
                PushStack(s,p->rchild);
            p=p->lchild;
        }
        else
        {
            p=PopStack(s);
        }
    }
    
}

2. 中序遍历

/*
中序遍历非递归方案；
顺序：左，中，右
优先访问左，有左子树则push到stack
没有左子树则进行访问节点内容，然后访问右子树--》重复开始内容
*/

void InOrder(BiTree &T)
{
    Stack s;
    InitStack(s);
    BiTree p=T;
    while(p||!StackIsEmpty(s))
    {
        if(p)
        {
            PushStack(s, p);
            p=p->lchild;
        }
        else
        {
            p=PopStack(s);
            cout<<p->data;
            p=p->rchild;
        }
    }
    
}

3. 后序遍历

/*
后序遍历非递归方案；
顺序：左，右，中
- 遍历规则：将不为空的右子树、左子树压入栈
- 访问数据的条件：左右子树为空或者左右子树都被访问过；
*/
void PostOrder(BiTree &T)
{
    Stack s;
    InitStack(s);
    BiTree p=T;
    BiTree pre=p;
    PushStack(s, p);
    while(!StackIsEmpty(s))//p最后指向跟节点，不可能为空
    {     
        p=TopStack(s); 
        if((p->lchild==NULL&&p->rchild==NULL)||(pre!=NULL&&(pre==p->lchild||pre==p->rchild)))
        // 输出节点条件：子树都为空，或者子树都被访问过
        {
            cout<<p->data;
            pre=p;
            PopStack(s);
        }
        else
        {
        if(p->rchild)
            PushStack(s,p->rchild);
        if(p->lchild)
            PushStack(s,p->lchild);
        }
    }
}

输出结果

PreOrder(tree)
InOrder(tree)
PostOrder(tree)
/*
124635
264135
642531
*/