数据结构课程设计二叉树的遍历

左右的方式进行访问 p 是要遍历树的根指针,若 p != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空。方法 1: 访问 p ->data 后,将p 入栈, 遍历左子树; 遍历完左子树返回时,栈顶元素应为 T ,出栈,再先序遍历 p 的右子树。方法 2: 访问 p ->data 后,将p ->rchild 入栈, 遍历左子树; 遍历完左子树返回时,栈顶元素应为 p ->rchild ,出栈,遍历以该指针为根中序:是按照左根右的方式进行访问 p 是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。先将 p 入栈,遍历左子树;遍历完左子树返回时,栈顶元素应数据结构课程设计第 5页共 19页为 p ,出栈,访问 p ->data ,再中序遍历 p 的右子树。后序:是按照左右根的方式进行访问 p 是要遍历树的根指针,后序遍历要求在遍历完左右子树后, 再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法, 结点入栈时, 配一个标志 t op 一同入栈(0: 遍历左子树前的现场保护, 1 :遍历右子树前的现场保护)。首先将 p和 t op(为 0) 入栈, 遍历左子树; 返回后, 修改栈顶 top 为 1 ,遍历右子树;最后访问根结点。层次: 用一个队列保存被访问的当前节点的左右孩子以实现层遍历。从队列取出一个元素并访问; 如果该元素有右子树就将它放入队列; 如果该元素有左子树就将它放入队列; 数据结构课程设计第 6页共 19页三.测试数据输入第一组数据 12345 ABCDE 输出输入第二组数据 123456789 ASDFGHJKL 数据结构课程设计第 7页共 19页输出输入第三组数据 123456 QWERTY 输出输入第四组数据数据结构课程设计第 8页共 19页 1234 ZXCV 输出输入第五组数据 123456 MNBPOI 输出