二叉树递归非递归遍历.docx
西安邮电大学（计算机学院）课内试验报告试验名称:二乂神历专业名称一通信工程班.然j¾T1309,学生姓名，张/学号（8位为指导老师：李树滨试验日期：.2014年11月17日-.试验目的及试验环境1,试验目的：二叉树的遍历.2,试验环境:二.试验内容从键盘接受输入先序序列，一二叉链表作为存储结构，建立二叉树（以先序来建立），并对其进行遍历，然后将遍历结果打印输出.三.方案设计（二叉树结点结构；结点数据*；左孩子*；右孩子,*；，栈结构定义）；（*S）;构造一个空栈S(*S);销毁栈S,S不再存在(*S);把栈S置为空栈(三);若栈S为空栈，则返回，否则返回(三);返回S元素的个数，即栈的长度(*e)：若栈不为空，则用e返回S的栈顶元素，并返回：否则返回(*e):插入元素e为新的栈顶元素(*e);若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回，否则返回(*S)：从栈底到栈顶依次对每个元素进行访问(T);按先后次序输入二叉树中结点的值(一个字符)，空格表示空树构造二叉链表表示的二叉树T(*)(e);采纳二叉链表存储结结构，是对数据元素操作的应用函数先序遍历二叉树T的递归算法，对每个数据元素调用函数采纳二叉锥表存储结结构，是对数据元素操作的应用函数中序遍历二叉树T的递归算法，对每个数据元素调用函数(*)(e);采纳二叉链表存储结结构，是对数据元素操作的应用函数后序遍历二叉树T的递归算法，对每个数据元素调用函数(*)(e):采纳二叉锥表存储结结构，是对数据元素操作的应用函数先序遍历二叉树T的非递归尊法，对每个数据元素调用函数(*)(e);采纳二叉链表存储结结构，是对数据元素操作的应用函数中序遍历二叉树T的非递归算法，对每个数据元素调用函数(*)(e)：采纳二叉锥表存储结结构，是对数据元素操作的应用函数后序遍历二叉树T的非递归算法，对每个数据元素调用函数(e);对二叉树中的数据元素访问四,测试数据及运行结果I.正常测试数据(3组)及运行结果;IW1<X,，曲,人二X，M1IAA>TtFJSMAX'>五.总结1 .试验过程中遇到的问题及解决方法；起初代码总是出错，不过细致检查之后，便找到了错误所在，更加加深了对程序算法的理解。2 .对设计及调试过程的心得体会。更加深刻体会r编程的乐趣，对于c语言也有了更多的r解。六.附录，（电子版）1O-110010;二叉树结点元素类型（二叉树结点结构;结点数据*:左孩子*;右孩子t，栈结构定义(*S);构造一个空栈S(*S);销毁栈S,S不再存在(*S);把栈S置为空栈(三);若栈S为空栈，则返回，否则返回(三);返回S元素的个数，即栈的长度(*e)：若栈不为空，则用e返回S的栈顶元素，并返回：否则返回(*e)：插入元素e为新的栈顶元素(*e)；若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回，否则返回(*S);从栈底到栈顶依次对每个元素进行访问(T);按先后次序输入二叉树中结点的值(一个字符)，空格表示空树构造二叉链表表示的二叉树T(*)(e);采纳二叉链表存储结结构，是对数据元素操作的应用函数先序遍历二叉树T的递归算法，对每个数据元素调用函数(*)(e)：采纳二叉锥表存储结结构，是对数据元素操作的应用函数中序遍历二叉树T的递归算法，对每个数据元素调用函数(*)(e):采纳二叉链表存储结结构，是对数据元素操作的应用函数后序遍历二叉树T的递归算法，对每个数据元素调用函数(*)(e);采纳二叉跳表存储结结构，是对数据元素操作的应用函数先序遍历二叉树T的非递归律法，对每个数据元素调用函数(*)(e);采纳二叉链表存储结结构，是对数据元素操作的应用函数中序遍历二叉树T的非递归算法，对每个数据元素调用函数(*)(e);采纳二叉处表存储结结构，是对数据元素操作的应用函数后序遍历二叉树T的非递归算法，对每个数据元素调用函数(e);对二叉树中的数据元素访问O(*)(e);("请按先序遍历输入二叉树元素(每个结点一个字符，空结点为''):n");(T);("n递归先序遍历：n");0；Cn递归中序遍历：n");0；CAn递归后序遍历：n");0；("n非递归先序遍历：n");0；("n非递归中序遍历：n*);0；CAn非递归后序遍历:n*);0；r.11；0：(T)(按先后次序输入二叉树中结点的值(一个字符)，空格表示空树构造二叉链表表示的二叉树T(!(*)()0；>：生成根节点>(»：构造左子树>(»；构造右子树(*)(e)先序遍历递归算法(»)(»；(»；(*)(e)中序遍历递归算法(T)(»：(»);(»：(*)(e)后序遍历递归算法(T)(»；(»：(»)(*)(e)先序遍历二叉树T的依递归算法0;0:根指针入栈(三)0;访问根节点(»);(»(»:(»(»:)0;(*)(e)中序遍历二叉树T的非递归算法S:O;：(三)(p)()>:根指针进栈，遍历左子树(根指针退栈，访问根节点，遍历右子树0；(»)；>)0;(*)(e)后序遍历二叉树T的非递归算法S;O;0;根指针入栈(三)(0)(»向左走到终点0;空指针出栈0;(»(»(三)(访问结点，向右i步0;(W)Z(O)若当前为右子树，则接着出栈0;(W)Z0;(»O):(O;(»);)O;(e)对二叉树中的数据元素访问C0,)依次栈操作(*S)(构造个空栈SX*)(*()；()安排失败(安排内存失败n");(O);)»；销毁栈S,S不再存在()为空("指针为空,释放失败.n");(»：(*S)把栈S置为空栈()不存在»干脆将栈顶指针指向栈底(三)若栈S为空栈，则返回，否则返回(三)返回S元素的个数，即栈的长度(*e)若栈不为空，则用e返回S的栈顶元素，并返回；否则返回O插入元素e为新的栈顶元素(»»)(栈已满，追加存储空间X*)0,(»*();(»("重新申请空间失败.n");(0)：)更改栈顶指针；)*；(*e)若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回，否则返回(»)(栈为空)*(»:9)
