用递归、非递归两种方法遍历二叉树
数据结构（双语）
项目文档报告
用递归、非递归两种方法遍历二叉树
专业：计算机科学与技术班级：指导教师：姓名：学号：
1
f用递归、非递归两种方法遍历二叉树
目录
一、设计思想………………………………………………………03二、算法流程图……………………………………………………04三、源代码…………………………………………………………06四、运行结果………………………………………………………12五、遇到的问题及解决……………………………………………14六、心得体会………………………………………………………15
2
f用递归、非递归两种方法遍历二叉树
一、设计思想
1．递归：（1）主函数mai
（）主程序要包括：定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。（2）建树函数定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。（3）先序遍历函数根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。4中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。5）后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。2非递归：（1）跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。（2）然后是中序，先序，后序非递归遍历二叉树。（3）中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。4先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。5）后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左r