递归和非递归遍历二叉树.doc

数据结构(双语)——项目文档报告递归、非递归两种算法遍历二叉树专业:计算机科学与技术班级:指导教师:苏亚光姓名:学号:目录一、设计思想……………………………………………………………….3页二、算法流程图……………………………………………………………、源代码…………………………………………………………………10页四、运行结果……………………………………………………………..15页五、遇到的问题及解决……………………………………………………15页六、心得体会………………………………………………………………16页一、::首先判断根结点是否为空,为空则停止遍历,不为空则将左子作为新的根结点重新进行上述判断,左子遍历结束后,再将右子作为根结点判断,直至结束。到达每一个结点时,打印该结点数据,即得先序遍历结果。若二叉树非空,则依次进行如下操作:(1)访问跟结点;(2)前序遍历左子树;(3)前序遍历右子树。:首先判断该结点是否为空,为空则结束,不为空则将左子作为根结点再进行判断,打印左子,然后打印二叉树的根结点,最后再将右子作为参数进行判断,打印右子,直至结束。若二叉树非空,则依次进行如下操作:(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。:指针到达一个结点时,判断该结点是否为空,为空则停止遍历,不为空则将左子作为新的结点参数进行判断,打印左子。左子判断完成后,将右子作为结点参数传入判断,打印右子。左右子判断完成后打印根结点。若二叉树非空,则依次进行如下操作:(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。::建立一个栈,当指针到达根结点时,打印根结点,判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈,将左子作为新的根结点进行判断,方法同上。若当前结点没有左子,则直接将右子打印,同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子,同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子,则当前结点为叶子结点,此时将从栈中出栈一个元素,作为当前的根结点,打印结点元素,同时将当前结点同样按上述方法判断,依次进行。直至当前结点的左右子都为空,且栈为空时,遍历结束。:建立一个栈,当指针到达根结点时,把根结点压栈,判断根结点是否有左孩子。有左孩子的话将左孩子,将新结点入栈,然后再将指针指向当前结点的左子,直至左子为空,弹栈一个元素,作为当前结点,打印该栈顶元素,将指针指向当前结点右子,将右子作为新的结点,结点入栈,再次进行上面的判断,直至当前结点右子也为空,则再出栈一个元素作为当前结点,一直到结束,使得当前结点右子为空,且栈空,遍历结束。:建立一个栈,然后定义一个tag,取值为0,1,0代表右子没有去过,1代表去过。①初始时指针指向根结点,将根结点压栈,指针指向左子,则将左子作为当前结点,继续判断直至左孩子为null,设q=null,tag=1。然后取得栈顶元素,设为当前结点,判断当前结点的右孩子是否等于q,如果相等,则打印当前结点,然后弹出当前结点,并且令q=当前结点的值。然后继续判断,直至右孩子不等于q,则将指针指向右孩子,把右孩子设为当前结点,令tag=0,继续步骤①,直到全部元素弹栈,栈为空时,遍历结束。,压栈,指针指向它的左孩子判断结点是否空弹出栈顶元素,,指针指向它的左孩子判断结点是否空弹栈,设为当前结点,打印结点值,..,用一个bool变量tag标记右孩子已被访问把当前结点压栈,p=p->lchildtop++判断标志tag是否为1输出结点值p=()p=p->