B11050624靳康康实验五.doc

洛阳理工学院实验报告系部计算机系班级B110506学号B11050624姓名靳康康课程名称数据结构实验日期2013/5/12实验名称二叉树的建立及遍历成绩实验目的：掌握二叉树的结构特征，掌握用指针类型描述、建立、遍历二叉树的运算。实验条件： VC+6.0，计算机一台实验内容与算法思想：内容：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历(先序，中序和后序)，打印输出遍历结果算法思想： 本程序主要是利用二叉链表方式建立一颗二叉树，并对其进行遍历，分别输出先序、中序、后序的遍历结果。程序中主要包含五大功能函数，二叉树的创建函数CreateBiTree，先序遍历二叉树函数PreOrder，中序遍历二叉树函数InOrder，后序遍历二叉树函数LastOrder及主函数。函数CreateBiTree的主要功能是利用先序遍历序列创建二叉链表，该程序是采用递归的方法实现遍历的，各子函数依次被主函数调用。运行结果：输入二叉链表元素：ABC DE G F 输出先序遍历结果：ABCDEGF输出中序遍历结果：CBEGDFA输出后序遍历结果：CGEFDBA实验总结： 通过本次程序的编写，我基本掌握了二叉树的结构特征，掌握了如何用指针类型描述、建立、遍历二叉树的运算。二叉树的三种遍历的主要区别就是对根结点访问的先后顺序不同，其原理是相同的，都是利用了递归运算的原理。从键盘输入字符串时，输入的结点数必须是一棵完全二叉树，如果某个子树为空，则必须输入空格键来代替该空子树，否则无法正确输出遍历结果。通过上机操作，更加有助于查找问题的所在，能更好的理解程序的原理。附：源程序：#include #include typedef struct Node char data;struct Node *Lchild;struct Node *Rchild;BiTNode,*BiTree;void CreateBiTree(BiTree *bt)/先序遍历创建二叉链表 char ch;ch=getchar();if(ch= )*bt=NULL;else *bt=(BiTree)malloc(sizeof(BiTNode);(*bt)-data=ch; CreateBiTree(&(*bt)-Lchild);CreateBiTree(&(*bt)-Rchild);void Visit(char x)/访问根结点函数 printf(%c ,x);void PreOrder(BiTree root)/先序遍历二叉树函数if(root!=NULL) Visit(root-data); PreOrder(root-Lchild); PreOrder(root-Rchild);void InOrder(BiTree root)/中序遍历二叉树函数if(root!=NULL) InOrder(root-Lchild); Visit(root-data); InOrder(root-Rchild);void LastOrder(BiTree root)/后序遍历二叉树函数if(root!=NULL) LastOrder(root-Lchild); LastOrder(root-Rchild); Visit(root-data);void main() BiTree bt;printf(输入二叉链表元素：);CreateBiTree(&bt); printf(n); printf(输出先序遍历结果：); PreOrder(bt);printf(n);print