143-4

二叉树自下而上，从右到左的层次遍历算法

相较于普通的层次遍历，该算法，只是利用栈的特点，将一系列元素反转。

层次遍历的每一个结点依次进栈，最后再将依次出栈

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

typedef TreeNode* Elem;

typedef struct{
    Elem data[MaxSize];
    int front,rear;
}Queue; 

void InitQueue(Queue &Q)
{
    Q.front=Q.rear=0;
}

bool isEmpty(Queue Q)
{
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

bool isFull(Queue Q)
{
    if((Q.rear+1)%MaxSize==Q.front)
        return true;
    else
        return false;
}

bool EnQueue(Queue &Q,Elem p)
{
    if(isFull(Q))
        return false;
    Q.data[Q.rear]=p;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

bool DeQueue(Queue &Q,Elem &p)
{
    if(isEmpty(Q))
        return false;
    p=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

typedef struct{
    Elem data[MaxSize];
    int top;
}Stack;

void InitStack(Stack &S)
{
    S.top=-1;
}

bool isEmpty(Stack S)
{
    if(S.top==-1)
        return true;
    else
        return false;
}

bool isFull(Stack S)
{
    if(S.top==MaxSize-1)
        return true;
    else
        return false;
}

bool Push(Stack &S,Elem x)
{
    if(isFull(S))
        return false;
    S.data[++S.top]=x;
    return true;    
}

bool Pop(Stack &S,Elem &x)
{
    if(isEmpty(S))
        return false;
    x=S.data[S.top--];
    return true;
}

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;    
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

void ReverseLeverOrder(Tree T)
{
    Queue Q;
    InitQueue(Q);
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    EnQueue(Q,p);
    while(!isEmpty(Q))
    {
        DeQueue(Q,p);
        Push(S,p);
        printf("%d  ",p->data);
        if(p->lchild)
            EnQueue(Q,p->lchild);
        if(p->rchild)
            EnQueue(Q,p->rchild);
    }
    printf("\n");
    while(!isEmpty(S))
    {
        Pop(S,p);
        printf("%d  ",p->data);
    }
}

int main()
{
    Tree T;
    CreateTree(T);
    ReverseLeverOrder(T);
    return 0;    
}