二叉树的遍历

分为按照递归和非递归两种方法

#include
#include

typedef struct treenode//创建树
{
    char data;
    struct treenode* Lchild;
    struct treenode* Rchild;
}tree,*lptree;

lptree createnode(char data) //创建新结点
{
    lptree newnode = (lptree)malloc(sizeof(tree));
    newnode->data = data;
    newnode->Lchild = NULL;
    newnode->Rchild = NULL;
    return newnode;
}

void insertnode(lptree parentnode, lptree Lchild, lptree Rchild)
{
    parentnode->Lchild = Lchild;
    parentnode->Rchild = Rchild;
}

//打印当前结点中的数据
void printnownode(lptree nowdata)
{
    printf("%ct",nowdata->data);
}

//递归方法
void prenode(lptree root)               //前序/先序
{
    if (root != NULL)
    {
        printnownode(root);     //根
        prenode(root->Lchild);//左
        prenode(root->Rchild);//右
    }
}

void midnode(lptree root)               //中序
{
    if (root != NULL)
    {
        midnode(root->Lchild);//左
        printnownode(root);     //根
        midnode(root->Rchild);//右
    }
}

void lastnode(lptree root)              //后序
{
    if (root != NULL)
    {
        lastnode(root->Lchild);//左
        lastnode(root->Rchild);//右
        printnownode(root);     //根
    }
}


//非递归
void prestack(lptree root)              //前序
{
    if (root == NULL)
        return;
    lptree stack[10];                       //准备栈
    int stackTop = -1;
    lptree pmove = root;
    while (stackTop != -1 || pmove)
    {
        while (pmove)                               //找最左边结点
        {                                                   //入栈+打印走过的结点
            printf("%ct", pmove->data);
            stack[++stackTop] = pmove;          //入栈
            pmove = pmove->Lchild;
        }
        //无路可走
        if (stackTop != -1)
        {
            pmove = stack[stackTop];            //获取栈顶元素
            stackTop--;                                  //出栈
            pmove = pmove->Rchild;
        }
    }
}

void midstack(lptree root)              //中序.左中右
{
    if (root == NULL)
        return;
    lptree stack[10];                       //准备栈
    int stackTop = -1;
    lptree pmove = root;
    while (stackTop != -1 || pmove)
    {
        while (pmove)                           //走过的结点入栈，找到最左边结点
        {
            stack[++stackTop] = pmove;
            pmove = pmove->Lchild;
        }
        //出栈
        if (stackTop != -1)
        {
            pmove = stack[stackTop--];            //获取栈顶元素   出栈
            printf("%ct", pmove->data);
            pmove = pmove->Rchild;
        }
    }
}
void laststack(lptree root)              //后序，左右中
{
    if (root == NULL)
        return;
    lptree stack[10];                       //准备栈
    int stackTop = -1;
    struct treenode* pmove = root;
    lptree pLastVisit = NULL;
    
    while (pmove)
    {
        stack[++stackTop] = pmove;
        pmove = pmove->Lchild;
    }
    while (stackTop != -1)
    {
        pmove = stack[stackTop--];
        if (pmove->Rchild == NULL || pmove->Rchild == pLastVisit)
        {
            printf("%ct", pmove->data);
            pLastVisit = pmove;
        }
        else
        {
            stack[++stackTop] = pmove;
            pmove = pmove->Rchild;
            while (pmove)
            {
                stack[++stackTop] = pmove;
                pmove = pmove->Lchild;
            }
        }
    }

}

int main()
{

    lptree a = createnode('a');
    lptree b = createnode('b');
    lptree c = createnode('c');
    lptree d = createnode('d');
    lptree e = createnode('e');
    lptree f  = createnode('f');
    lptree g = createnode('g');

    insertnode(a, b, c);
    insertnode(b, d, NULL);
    insertnode(d, NULL, g);
    insertnode(c, e, f);

    printf("先序:n");
    prenode(a);
    printf("n");
    prestack(a);
    printf("n");

    printf("中序:n");
    midnode(a);
    printf("n");
    midstack(a);
    printf("n");

    printf("后序:n");
    lastnode(a);
    printf("n");
    laststack(a);
    printf("n");

    system("pause");
    return 0;
}