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

文档介绍：数据结构(双语)——项目文档报告用递归、非递归两种方法遍历二叉树专业:计算机科学与技术班级:指导教师:姓名:学号:目录一、设计思想……………………………………………………….03二、算法流程图…………………………………………………….04三、源代码………………………………………………………….06四、运行结果……………………………………………………….12五、遇到的问题及解决…………………………………………….14六、心得体会……………………………………………………….15一、:(1)主函数main()主程序要包括:定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。(2)建树函数定义一个输入的数是字符型的,当ch为空时,T就为空值,否则的话就分配空间给T,T就指向它的结点,然后左指针域指向左孩子,右指针指向右孩子,若还有,继续调用,依次循环下去,直到ch遇到空时,结束。最后要返回建立的二叉树T。(3)先序遍历函数根据先序遍历规则,当T为非空时,先输出结点处的数据,指针指向左、右孩子,依次进行下去。(4)中序遍历函数根据中序遍历规则,当T为非空时,先左指针指向左孩子数据,然后输出结点处的数据,再右指针指向右孩子,依次进行下去。(5)后序遍历函数根据后序遍历规则,当T为非空时,先右指针指向右孩子,然后左指针指向左孩子,最后输出结点处的数据,依次进行下去。:(1)跟递归遍历二叉树的前提一样,首先应该创建一个二叉树,同样使用先序递归的方式创建二叉树。 (2)然后是中序,先序,后序非递归遍历二叉树。 (3)中序非递归遍历二叉树的思想是:首先是根节点压栈,当根节点的左子树不是空的时候,左子树压栈。直到左子树为空的时候,不再压栈。将栈顶元素出栈,访问栈顶元素,并将栈顶的右子树进栈。当右子树的左子树不是空的时候,左子树一直进栈,直到左子树为空,则不再进栈。重复上面的操作,直到栈空的时候。 (4)先序非递归遍历二叉树的思想是:首先是根节点进栈,然后当栈不为空的时候,将栈顶元素出栈,然后访问。同时将出栈元素的右子树进栈,左子树进栈。重复上面的操作,直到栈为空。 (5)后序非递归遍历二叉树的思想:首先是根节点进栈,当根节点的左子树不为空的时候,左子树进栈,直到左为空的时候,左子树不再进栈。指针指向的是右子树,当右子树为空的时候,直接访问根节点。当右子树不为空的时候,则右子树的指针进栈,当右子树的左子树不为空的时候,则左也进栈,直到左为空。重复上面的操作,直到栈为空的时候,则遍历树完成。二、、#include""#include""#include<>#include<stack>typedefstructnode{chardata;structnode*lchild,*rchild;}BinTnode;typedefBinTnode*BinTree;//定义二叉树类型的指针/*先序创建二叉树*/intCreateBinTree(BinTree*T){charch; *T=(BinTree)malloc(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!='\0');}/*中序递归遍历*/voidInorderTransverse(BinTrees){ if(s) { InorderTransverse(s->lchild); printf("%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->lchild); PreOrderTranverseTree(s->rchild); printf("%c",s->data); }