C语言实现二叉树的前序、中序、后续遍历(递归法).doc

二叉树的前序遍历、中序遍历、后续遍历（递归法）1、前序遍历（递归）：算法实现一：#include #include typedef struct BiTNode/定义结构体 char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void CreateBiTree(BiTree &T) /前序创建树char ch;scanf(%c,&ch);if(ch= ) T=NULL;elseT=(struct BiTNode *)malloc(sizeof(struct BiTNode);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);int print(BiTree T)/前序遍历（输出二叉树）if(T=NULL)return 0;else if(T-lchild=NULL & T-rchild=NULL)return 1;else return print(T-lchild)+print(T-rchild);void main()/主函数BiTree T;CreateBiTree(T);printf(%dn,print(T);算法实现二：#include#includestruct BiTNode/定义结构体 char data; struct BiTNode *lchild,*rchild;int num=0;void CreatBiTree(struct BiTNode *&p) /前序创建树char ch;scanf(%c,&ch);if(ch= ) p=NULL;elsep=(struct BiTNode *)malloc(sizeof(struct BiTNode);p-data=ch;CreatBiTree(p-lchild);CreatBiTree(p-rchild);void print(struct BiTNode *p) /前序遍历（输出二叉树）if(p!=NULL)if(p-lchild=NULL&p-rchild=NULL)elseprint(p-lchild);print(p-rchild);void main()/主函数struct BiTNode *p;CreatBiTree(p);print(p);printf(%dn,num);2、中序遍历（递归）：#include#includestruct BiTNode/定义结构体 char data; struct BiTNode *lchild,*rchild;void later(struct BiTNode *&p) /前序创建树char ch;scanf(%c,&ch);if(ch= )p=NULL;elsep=(struct BiTNode *)malloc(sizeof(struct BiTNode);p-data=ch;later(p-lchild);later(p-rchild);void print(struct BiTNode *p) /中序遍历（输出二叉树）if(p!=NULL)print(p-lchild);printf(%c,p-data);print(p-rchild);elseprintf( );void main()/主函数struct BiTNode *p;later(p);print(p);3、后序遍历（递归）：#include#includestruct BiTNode/定义结构体 char data; struct BiTNode *lchild,*rchild;void later(struct BiTNode *&p) /前序创建树char ch;scanf(%c,&ch);if(ch= )p=NULL;elsep=(struct BiTNode *)malloc(sizeof(struct BiTNode);p-data=ch;later(p-lchild);later(p-rchild);void print(struct BiTNode *p) /后序遍历（输出二叉树）if(p!=NULL)print(p-lchild);print(p-rchild);printf(%c,p-data);elseprintf( );void main()/主函数/*检测：printf(到了吗);*/struct