华北理工大学二叉树遍历报告.doc

数据结构（双语） ——项目文档报告 用递归、非递归两种方法遍历二叉树 专 业： 计算机科学与技术 班 级： 15计算机1班 指导教师： 苏亚光 姓 名： 学 号： 目 录 一、设计思想……………………………………………………….3 二、算法流程图…………………………………………………….4 三、源代码………………………………………………………….7 四、运行结果……………………………………………………….12 五、遇到的问题及解决…………………………………………….13 六、心得体会……………………………………………………….14 设计思想 程序代码是用两种算法实现二叉树的遍历，并输出遍历后的值。 第一种算法是递归实现二叉树的遍历 首先对于先序遍历，若二叉树为空，则空操作；否则，先访问根结点，然后先序遍历左子树，再先序遍历右子树。对于中序遍历，若二叉树为空，则空操作；否则，先中序遍历左子树，然后访问根节点，在中序遍历右子树。对于后续遍历，若二叉树为空，则空操作；否则，先后续遍历左子树，然后后续遍历右子树，在访问跟结点。 第二种算法是非递归实现二叉树的遍历 首先对于先序非递归遍历， 先序遍历是借用栈来实现的。 先声明并初始化一个栈。 首先站在根节点上， 对于根节点直接访问它， 即打印它的 data，再将其压入栈中， 再判断栈 stack是否为空，如果 stack 为空，则循环结束，遍历结束；如果不为空，则访问该根结点。对于其它结点上如果它有左子，则访问它的左子，即打印其左子中成员 data 的值，然后再将该左子压入栈中； 如果该结点没有左子，则弹出栈顶元素， 站在其右子所在的结点上，再对当前所在的结点是否有左子进行判断，此时进入了一个循环。循环结束的条件是栈 stack 和最后所在结点也为空。此时，所输出的结果即为先序遍历的结果。 对于中序非递归遍历，也是借用一个栈来实现的，先声明并初始化一个栈，站到一个结 点 a 上，如果当前结点 a 有左子 b，则将其左子 b 入栈，如果其左子 b 还有左子 c 也将当前所站的结点 b 入栈，循环此过程直到遇到没有左子的结点 p，此时弹出栈顶元素 p，并访问它，即打印 p 结点的 data，然后判断 p 结点的成员指针变量 right ，把 right 当成第一个开始的结点进行处理， 直到最后栈为空且当前所站得结点为 NULL ，则中序遍历结束。 所输出的结果即为中序遍历的结果。 对于后续非递归遍历， 它与前面两个不同， 要使用两个栈来实现。 先分别声明并初始化两个栈 stack 和 output，首先站在根结点上， 对于根结点是直接将根节点压入栈 stack 中。如果是其它的结点则首先要判断栈 stack 是否为空，然后才往下执行。如果当前栈 stack 不为空，则将 stack 中得栈顶元素 A 弹出并压入到栈 output 中，现在站在结点 A 上，先依次判断它是否有左右子， 如果它有左子， 则将其左子压入栈 stack 中，如果它有右子也将它压入栈 stack中，然后再判断栈 stack 是否为空， 如果不为空， 则弹出栈顶元素， 并将其压入栈 output 中，再对该元素进行左子、右子的判断。 到最后， stack 为空时，则此循环结束， 而此时栈 output中存储的则是已经按后续遍历排好的各个结点。 依次访问栈顶元素并弹出栈顶元素， 直到此栈为空，则所输出的结果即为后序遍历的结果。 算法流程图 图 1 为使用递归实现的先序遍历二叉树的流程图。 图 2 为使用递归实现的中序遍历二叉树的流程图 图 3 为使用递归实现的中序遍历二叉树的流程图 图 4 为使用非递归实现的先序遍历二叉树的流程图 图 5 为使用非递归实现的中序遍历二叉树的流程图 图 6 为使用非递归实现的后序遍历二叉树的流程图 图1先序遍历二叉树流程图 图2中序遍历二叉树流程图 图3后序遍历二叉树流程图 图4非递归先序遍历二叉树流程图 图5非递归中序遍历二叉树流程图 图6非递归后序遍历二叉树流程图 源代码 下面给出的是二叉树遍历实现的关键源代码： //前序递归遍历 void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf(%c,T-data);/* 显示结点数据，可以更改为其它对结点操作 */ PreOrderTraverse(T-lchild); /* 再先序遍历左子树 */ PreOrderTraverse(T-rchild); /* 最