用递归非递归两种方法遍历二叉树.doc

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

1、.专业整理.数据结构（双语）——项目文档报告用递归、非递归两种方法遍历二叉树专业：计算机科学与技术班级：指导教师：姓名：学号：.学习帮手..专业整理.目录一、设计思想……………………………………………………….03二、算法流程图…………………………………………………….04三、源代码………………………………………………………….06四、运行结果……………………………………………………….12五、遇到的问题及解决…………………………………………….14六、心得体会……………………………………………………….15.学习帮手..专业整理.一、设计思想1．递归：（

2、1）主函数main（）主程序要包括：定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。（2）建树函数定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。（3）先序遍历函数根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。(4)中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次

3、进行下去。(5）后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。2.非递归：（1）跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。 （2）然后是中序，先序，后序非递归遍历二叉树。 （3）.学习帮手..专业整理.中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不

4、再进栈。重复上面的操作，直到栈空的时候。 (4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。 (5）后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。二、算法流程图1.递

5、归.学习帮手..专业整理.2.非递归.学习帮手..专业整理.三、源代码1.递归.学习帮手..专业整理.#include"stdio.h"#include"conio.h"#include#includetypedefstructnode{chardata;structnode*lchild,*rchild;}BinTnode;typedefBinTnode*BinTree;//定义二叉树类型的指针/*先序创建二叉树*/intCreateBinTree(BinTree*T){charch;*T=(BinTree)malloc

6、(sizeof(BinTnode));if(!*T)printf("overflow");do{ch=getchar();if(ch==''){*T=NULL;return0;}else{(*T)->data=ch;CreateBinTree(&((*T)->lchild));CreateBinTree(&((*T)->rchild));return1;}}while(ch!='');}/*中序递归遍历*/voidInorderTransverse(BinTrees){if(s){InorderTransverse(s->lchild);printf(

7、"%c",s->data);InorderTransverse(s->rchild);}}//先序递归遍历二叉树voidPreOrderTranverseTree(BinTrees){if(s){.学习帮手..专业整理.printf("%c",s->data);PreOrderTranverseTree(s->lchild);PreOrderTranverseTree(s->rchild);}}//后序递归遍历二叉树voidPostOrderTranverseTree(BinTrees){if(s){PreOrderTranverseTree(s->lch

8、ild);PreOrderTranverseTree(s->rch