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

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

1、用递归、非递归两种方法遍历二叉树一、设计思想1. 用递归算法遍历 设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 中序遍历： 先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树

2、不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。 后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 2. 用非递归算法遍历 设计思想：主要是通过栈的存取，判空，从而实现树的遍历 前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断

3、左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。 后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值

4、为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。-12-用递归、非递归两种方法遍历二叉树开始Root=nullYN输出数据Root.getLTree=nullRoot=TreetRoot.getRTree=nullNYYN结束开始Root=TreetRoot=nullRoot.getLTree=nullNN输出数据YRoot.getRTre

5、e=null结束YN开始Root=TreetRoot=nullRoot.getLTree=nullRoot.getRTree=nullY输出数据结束YYYNNN二、算法流程图图1递归算法-先序遍历图2递归算法-后序遍历图3递归算法-中序遍历-12-用递归、非递归两种方法遍历二叉树开始t.getRtree=nullTreet=rootoutputt=nullNYPusht.getLtree=nullPushNYN栈为空t=stack.pop()YN结束Y开始Treet=root压栈t=nullNYt=current.getLtree

6、()t=stack.Pop()outputt=current.getRltree()栈为空N结束Y图4非递归算法-先序遍历图5非递归算法-中序遍历-12-用递归、非递归两种方法遍历二叉树开始Treet=rootPusht=nullNYt=t.getLtree()标签栈压栈t=stack.pop()标签栈出栈赋值给标志位判断栈是否已经入栈过NYt=t.getRTree()标签栈压栈出栈并赋值tOutputCurrent=null树栈为空且当前节点为空N结束Y图6非递归算法-后序遍历-12-用递归、非递归两种方法遍历二叉树三、源代码#

7、include#includetypedefcharElemType;//定义树结构typedefstructtree{ElemTypedata;structtree*lchild;structtree*rchild;unsignedintisOut;//专为后序遍历设置的，0为不需要被输出，1为需要被输出}TreeNode,*Tree;//定义栈结构typedefstructstack{Tree*base;Tree*top;intstacksize;}SqStack;voidInitStac

8、k(SqStack&s);voidPush(SqStack&s,Treee);voidGetTop(SqStacks,Tree&e);voidPop(SqStack&s,Tree&e);intStackEmpty(SqStacks);voidCre