实验六二叉树遍历算法的设计与实现实验人 :杨嘉雯学号 : Xb10680230 时间： 2012.11.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=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=ch; //printf(" 当前根结点 :%c\n",(*T)->data); CreateBiTree(&(*T)->lchild); /* 建左子树*/ CreateBiTree(&(*T)->rchild); /* 建右子树*/ } } void PreOrderTraverse(BiTree T)/* 对二叉树进行先序遍历*/ { if(T==NULL) return; printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } void InOrderTraverse(BiTree T)/* 对二叉树进行中序遍历*/ { if(T==NULL) return; InOrderTraverse(T->lchild); //中序遍历左子树printf("%c",T->data); //显示结点数据，可以更改为其它对结点操作InOrderTraverse(T->rchild); //最后中...
