文档介绍：用递归、非递归两种方法遍历二叉树一、:主要是通过不同程序顺序,从而实现递归的顺序遍历前序遍历:先判断节点是否为空,如果不为空,则输出。再判断左节点是否为空,如果不为空,则递归调用,直到遍历到最左边。接着再遍历最左边的右子树,如果此时右子树不为空,则递归遍历左子树的操作,直到遍历到叶子节点。如果右子树为空,则回溯上次的递归调用,重复输出和遍历右子树的操作。中序遍历:先遍历左节点是否为空,如果不为空,则递归调用,直到遍历到最左边或者叶子节点,然后输出,接着再遍历最左边的右子树,如果此时右子树不为空,则递归重复遍历左子树的操作,直到遍历到叶子节点。如果右子树为空,则回溯到上次递归调用,重复输出和遍历右子树的操作。后序遍历:先判断左节点是否为空,如果不为空则一直递归直到遍历到最左边,然后遍历右节点,再接着遍历到左子树的最右边,直到遍历到叶子节点。此时输出,回溯到上次递归,继续执行后面的操作,重复,直到将整个树遍历完毕。:主要是通过栈的存取,判空,从而实现树的遍历前序遍历:通过一个循环实现。先输出节点的数值,因为栈的特性,则需要先判断右子树是否为空,如果不为空,则将右子树压栈。然后判断左子树是否为空,如果不为空,则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量,重复上述操作,直到栈为空后退出循环。中序遍历:通过循环实现。将树一直遍历到最左端,并将中间所经过的节点保存在栈中,当遍历到最左边的时候,则弹出栈里面的子树。输出数值,将当前节点赋值为当前节点的右子树,遍历右子树,即重复上述操作,直到当前节点为空,并且栈内元素为0。后序遍历:通过循环和标记栈实现。将数一直遍历到最左端,并将中间的节点保存在树栈中,同时同步的添加一个标记栈。当遍历到最左边的时候,弹栈并赋值给当前栈,然后判断标记栈的数值,如果数值为0的话则代表当前树没有遍历过,遍历右子树。然后重复上面的操作,如果数值为1的话则代表此时数已经遍历过了,可以开始输出了,为了避免重复输出,将当前栈赋为空。重复循环操作,直到栈内没有元素,且当前节点为空(因为一直左的操作并没有将右子树压栈)。-1-用递归、非递归两种方法遍历二叉树二、算法流程图开开开Root=TreetRoot=TreetRoot=TreetYYYRoot=nullRoot=nullRoot==nullNTree====nullTree=null输出数YY结束结束结束图2递归算法-后序遍历先序遍历-递归算法图1图3递归算法-中序遍历-2-用递归、非递归两种方法遍历二叉树开始开Treet=rootTreet=rootNNt=null压t=nulloutpuYYt=()=t=()=Pusnullt=()YNt=()栈为YY结束结束-5-4图非递归算法先序遍历图非递归算法中序遍历-3-