递归算法实现二叉树遍历.doc

《递归算法实现二叉树遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、输入一个二叉链表表示的二叉树，分别用递归实现先序、中序、后序3种遍历方法下面给出的是用递归算法实现的程序的源代码：#defineLEN200#defineNULL0#include#includestructtree{/*定义存放二叉树的栈*/chardata;/*结点数据*/structtree*lchild,*rchild;/*定义树的左右子树*/};/*创建二叉树*/structtree*creat(){charc;/*定义存放结点的变量*/structtree*t;/*定义树指针t*/c

2、=getchar();/*输入一个字符型数据付给树结点*/if(c=='')/*判断输入是否为空格*/t=NULL;/*遍历结束*/else{t=(structtree*)malloc(LEN);/*对树进行操作，树的结点数为LEN*/t->data=c;/*将输入放入结点处*/t->lchild=creat();/*创建左子树*/t->rchild=creat();/*创建右子树*/}/*递归创建树*/returnt;}/*前序遍历*/voidPreprint(structtree*t){/*定义函数preprint*/if(t!

3、=NULL){/*判断树是否为空树*/printf("%c",t->data);/*打印结点数据*/Preprint(t->lchild);/*递归遍历左子树*/Preprint(t->rchild);/*递归遍历右子树*/}}/*中序遍历*/voidInprint(structtree*t){/*定义函数*/if(t!=NULL){/*判断树是否为空树*/Inprint(t->lchild);/*递归遍历左子树*/printf("%c",t->data);/*打印结点数据*/Inprint(t->rchild);/*递归遍历右子树

4、*/}}/*后序遍历*/voidPostprint(structtree*t){/*定义函数*/if(t!=NULL){/*判断树是否为空树*/Postprint(t->lchild);/*递归遍历左子树*/Postprint(t->rchild);/*递归遍历右子树*/printf("%c",t->data);/*打印结点数据*/}}main(){structtree*t;/*定义指向树的指针*/printf("Pleaseinputtreeinorder:");/*输入一个树*/t=creat();/*将指针指向树*/pri

5、ntf("TheresultofPreordertraversalis");/*输出先序遍历结果*/Preprint(t);printf("TheresultofInordertraversalis");/*输出中序遍历结果*/Inprint(t);printf("TheresultofPostordertraversalis");/*输出后序遍历结果*/Postprint(t);printf("");/*换行*/getch();/*任意键退出*/}图8递归运行结果图