二叉树的四种遍历方法.doc

#include #include #define MAX 100#define OVERFLOW -2typedef struct BiTree /定义二叉树节点类型char data; struct BiTree *lchild,*rchild;/定义左右孩子BitNode;BitNode *CreatBiTree()/创建二叉树char c; BitNode *T; c=getchar();if(c=0)T=NULL; elseif(!(T=(BitNode*)malloc(sizeof(BitNode)exit(OVERFLOW); T-data=c;T-lchild=CreatBiTree();T-rchild=CreatBiTree();return T;void PreOrder(BitNode *T)/非递归先序遍历BitNode *stackMAX,*p; /定义栈的容量和指针变量int top=-1;/定义栈顶指针if(T!=NULL)top+;stacktop=T;while(top-1) /栈不空时循环p=stacktop;top-;printf(%3c,p-data);if(p-rchild!=NULL)top+;stacktop=p-rchild;if(p-lchild!=NULL)top+;stacktop=p-lchild;printf(n);void InOrder(BitNode *T) /非递归中序遍历BitNode *stackMAX,*p;/定义栈的容量和指针变量int top = -1; /定义栈顶指针if (T!=NULL)p=T;while (top-1|p!=NULL)while(p!=NULL)top+;stacktop=p;p=p-lchild;if(top-1)p=stacktop;top-;printf(%3c,p-data);p=p-rchild;printf(n);void PostOrder(BitNode *T) /非递归后序遍历BitNode *stackMAX,*p; /定义栈的容量和指针变量int sign,top=-1; if(T!=NULL) dowhile(T!=NULL) top+; stacktop=T;T=T-lchild;p=NULL; sign=1; while(top!=-1&sign) T=stacktop; if(T-rchild=p) printf(%3c,T-data);top-; p=T;elseT=T-rchild;sign=0;while (top!=-1);printf(n);void LevelOrder(BitNode *T)BitNode *queueMAX,*p;int front=-1, rear=-1;queuefront+=T;/ 树根结点先进队while(front-rear+MAX)%MAX!=0)/ 当队列不为空时，出队一个结点的同时将其左右孩子进队p=queuerear+;printf(%3c, p-data);if(p-lchild!=NULL)queuefront+=p-lchild;if(p-rchild!=NULL)queuefront+=p-rchild;int main() BitNode *T; printf(please input the preorder number:n); /提示按照先序递归建立二叉树T=CreatBiTree(); printf(the nonrecursive preorder traversal result is:n); PreOrder(T); /输出非递归先序遍历printf(the nonrecursive inorder traversal result is:n);InOrder(T); /输出非递归中序遍历printf(the nonrecursive postorder traversal result is:n);PostOrder(T); /输