实验六二叉树遍历算法的设计与实现实验人 :杨嘉雯学号 : Xb10680230 时间： 2012
27一、实验目的1
掌握二叉树的建立与存储2
掌握二叉树的遍历方法二、实验内容1
编写程序实现根据用户输入二叉树的先序序列建立一棵二叉树，并实现对此二叉树的先序、中序、和后序遍历
用非递归方法实现中序遍历
（选做）三、实验步骤：1．接收用户输入的先序序列建立以二叉链表为存储结构的二叉树
2． 对建立好的二叉树实现先序、中序、和后序遍历，将遍历后的序列输出
四、算法说明对于三种遍历的过程， 要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了
至于非递归的三种遍历， 中序最为简单， 用一个栈就可以完成了，思路是边进栈边收索左孩子， 直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作
采用非递归中序遍历算法， 先逐步扫描二叉树的左子树，并压入堆栈， 如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出
然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都扫描完成
此时输出的序列便是该二叉树的中序遍历序列
五、测试结果中序线索化二叉树:六、分析与探讨实验中经常会出现前后字符不一致的情况，主要原因是自己比较马虎，平时编程比较少，遇到比较长的程序，就容易出错
七、附录：源代码#include #include typedef struct BiTNode /* 定义二叉链表结点结构*/ { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void CreateBiTree(BiTree *T)/* 输入二叉树的先序遍历序列，创建二叉链表*/ { char ch; ch=getchar(); if (ch=='#') *T=NULL; else { *T
