二叉树-----非递归算法.doc

#include #include char pre50;static j;typedef struct Nodechar data;struct Node *LChild;struct Node *RChild;BiTNode,*BiTree;void CreateBiTree(BiTree &bt)char ch;ch=getchar();if (ch = ) bt=NULL; elsebt=(BiTNode *)malloc(sizeof(BiTNode);bt-data=ch;prej+=ch;CreateBiTree(bt-LChild);CreateBiTree(bt-RChild);void Visit(char data_value)printf(%c,data_value);void PreOrder( )prej =0;int i;for (i=0;prei != 0;i+)if (prei != )printf(%c,prei);printf(nnn);void InOrder(BiTree root)int top=0,m=20;BiTree s20;BiTree p;p=root;do while (p!=NULL)if (topm) return;top=top+1;stop=p;p=p-LChild;if (top!=0)p=stop;top=top-1;Visit(p-data);p=p-RChild; while (p!=NULL|top!=0);printf(nnn);void PostOrder(BiTree root)BiTNode *p,*q;BiTNode * *s;int NUM=20;int top=0;q=NULL;p=root;s=(BiTNode * *)malloc(sizeof(BiTNode)*NUM);while (p != NULL | top != 0)while (p != NULL)top+;stop=p;p=p-LChild;if (top 0)p=stop;if (p-RChild = NULL | p-RChild = q)Visit(p-data);q=p;top-;p=NULL; elsep=p-RChild; free(s);printf(nnn);void main()BiTree pnt;int choice;int flag=1;printf(请输入先序的二叉树序列，以空格表示空子树!n);CreateBiTree(pnt);while(flag)printf(请根据菜单选择：n);printf(1.先序遍历二叉树。n);printf(2.中序遍历二叉树。n);printf(3.后序遍历二叉树。n);scanf(%d,&choice);switch(choice)case 1:PreOrder();break;case 2:InOrder(pnt);break;case 3:Pos