实验八_二叉树建立与遍历(昆工版本).docVIP

昆明理工大学信息工程与自动化学院学生实验报告 （ 2013 — 2014 学年第三学期 ） 课程名称：数据结构 开课实验室：信自楼444 2013年11月26日 年级、专业、班 计科122班 学号 201210405204 姓名 邹华宇 成绩 实验项目名称 二叉树的建立与遍历及二叉树中序线索化及线索化遍历 指导教师 胡守成 教师评语 教师签名： 年 月 日 注：报告内容按实验须知中七点要求进行。 一、实验目的和要求 二叉树二叉链表非线性存储结构上实现的各种算法。 二、实验原理及基本技术路线图（方框原理图） 线索二叉树的主要函数设置如下： 1.树的存储的类型为：typedef struct bithrnode { char data; struct bithrnode *lchild,*rchild; int ltag,rtag; }bithrnode,*bithrtree; 2.主程序： bithrtree T, p,T1; int k; Do { switch(k) { case 1: creat(T); --------建立二叉树 T1=copy(T); ---------复制建立后的二叉树 case 2: T=copy(T1); ---------复制建立后的二叉树 PreOrderThreading(p,T); ---------先序线索化 first(p); --------------先序遍历 case 3: T=copy(T1); ---------复制建立后的二叉树 InOrderThreading(p,T); ----------中序线索化 mid(p); ---------------中序遍历 case 4: T=copy(T1); ---------复制建立后的二叉树 backorderThreading(p,T); -------------后序线索化 last(p); --------------后序遍历 } }while(k!=0); 3.子程序： bithrtree creat(bithrtree T) --------建立二叉树 Status PreOrderThreading(bithrtree thrt,bithrtree T) ---------先序线索化 {void PreThreading(bithrtree p)} ---------先序线索化子函数 Status InOrderThreading(bithrtree thrt,bithrtree T) ----------中序线索化 {void inthreading(bithrtree p)} ----------中序线索化子函数 Status backorderThreading(bithrtree thrt,bithrtree T) -------------后序线索化 {void backthreading(bithrtree p)} -----------后序线索化子函数 void first(bithrtree thrt) ------------先序遍历 void mid(bithrtree thrt) ------------中序遍历 void last(bithrtree t) ------------后序遍历 bithrtree copy(bithrtree r) ------复制建立后的二叉树 bithrtree creat(bithrtree T) #includestdio.h #include string.h #includemalloc.h #includestdlib.h #define OVE