二叉树前序、中序和后序非递归遍历的方法 转载

/***********************************************************
Author: vison
Email : [email protected]
Date  : 2010-03-19
***********************************************************/
#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef int btData;

typedef struct btNode
{
    btData data;
    btNode *lchild, *rchild;
}BinTree;

void DeleteBinTree(BinTree* bt)
{
    if (bt)
    {
        DeleteBinTree(bt->lchild);
        DeleteBinTree(bt->rchild);
        free(bt);
    }
}

bool _isdigit(int d)
{
    return (d >= 0 && d <= 9);
}

BinTree* CreateBinTree(btData** ds)
{
    if (!_isdigit(**ds))
    {
        (*ds)++;
        return 0;
    }

    BinTree* pNode = (BinTree*)malloc(sizeof(BinTree));

    if (pNode)
    {
        pNode->data   = *(*ds)++;
        pNode->lchild = 0;
        pNode->rchild = 0;
        
        pNode->lchild = CreateBinTree(ds);
        pNode->rchild = CreateBinTree(ds);
    }

    return pNode;
}

//Stack------------------------------------------------------------------------
typedef btNode* stNode;

struct Stack
{
    stNode* buf;
    int     top;
    int     size;
};

void InitStack(Stack& s, int sz)
{
    int i  = sizeof(stNode) * sz;
    s.buf  = (stNode*)malloc(i);
    s.top  = 0;
    s.size = sz;
   
    char* p = (char*)s.buf;

    while (i > 0)
    {
        p[--i] = 0;
    }
}

bool Push(Stack& s, stNode n)
{
    if (s.top >= s.size)
    {
        return false;
    }

    s.buf[s.top++] = n;

    return true;
}

bool Pop(Stack& s, stNode& n)
{
    if (s.top == 0)
    {
        return false;
    }

    n = s.buf[--s.top];

    return true;
};

stNode StackTop(Stack& s)
{
    if (s.top <= 0)return s.buf[0];
    return s.buf[s.top - 1];
}

bool StackEmpty(Stack& s)
{
    return (s.top == 0);
}

void DeleteStack(Stack& s)
{
    free(s.buf);
}

//////////////////////////////////////////////////////////
//中序遍历
void InOrderTraverse(BinTree* bt)
{
    Stack s;
    InitStack(s, 10);

    stNode p = bt;

    while (p || !StackEmpty(s))
    {
        if (p)
        {
            Push(s, p);
            p = p->lchild;
        }
        else
        {
            Pop(s, p);
            printf("%d,", p->data);
            p = p->rchild;
        }
    }

    DeleteStack(s);
};


//前序遍历
void PreOrderTraverse(BinTree* bt)
{
    Stack s;
    InitStack(s, 10);

    stNode p = bt;

    while (p || !StackEmpty(s))
    {
        if (p)
        {
            printf("%d,", p->data);
            Push(s, p);
            p = p->lchild;
        }
        else
        {
            Pop(s, p);
            p = p->rchild;
        }
    }

    DeleteStack(s);
};

//后序遍历
void PostOrderTraverse(BinTree* bt)
{
    Stack s, t;
    InitStack(s, 10);
    InitStack(t, 10);

    stNode r = 0;
    stNode p = bt;

    while (p || !StackEmpty(s))
    {
        if (p)
        {
            Push(s, p);
            if (p->rchild)Push(t, p->rchild);
            p = p->lchild;
        }
        else
        {
            p = StackTop(s);
            r = StackTop(t);
   
            if (p->rchild == r)
            {
                Pop(t, r);
                Push(t, p);//临时堆栈保存非叶子节点
                p = r;
                continue;
            }   

            Pop(s, p);
            printf("%d,", p->data);
           
            if (p == r)
            {
                p = 0;
                Pop(t, r);
            }
            else
            {
                p = p->rchild;
            }
        }
    }

    DeleteStack(s);
}

int main(int argc, char* argv[])
{
    btData ds[] = {0,1,3,'x','x',4,'x','x',2,5,'x','x',6,'x','x'};
    btData* p = ds;

    BinTree* root = CreateBinTree(&p);

    printf("InOrderTraverse: ");
    InOrderTraverse(root);

    printf("\r\nPreOrderTraverse: ");
    PreOrderTraverse(root);

    printf("\r\nPostOrderTraverse: ");
    PostOrderTraverse(root);
   
    while (getchar() != 'q');

    return (0);
}