二叉树自下而上，从右到左的层次遍历算法
相较于普通的层次遍历，该算法，只是利用栈的特点，将一系列元素反转。
层次遍历的每一个结点依次进栈，最后再将依次出栈
#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; }