数据结构实验树与叉树的操作实验指导.docVIP

实验六 树与二叉树 6.1实验目的： 掌握二叉树链表的结构和二叉树的建立过程； 掌握二叉树的基本操作，加深对二叉树的理解，逐步培养解决实际问题的编程能力。 6.2实验要求： 复习课本中有关树与二叉树的知识； 用C语言完成算法和程序设计并上机调试通过； 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。 6.3基础实验 [实验1] 二叉树的构造 实验内容与要求: 按先序序列构造一棵二叉链表表示的二叉树T； 分析: 二叉树是每个结点至多只有两棵子树，并有左、右之分，顺序不能任意颠倒的一种非线性结构。二叉树常用的存储结构是二叉链表形式，二叉链表由一个数据项data（用于存放结点的值）和两个指针项lchild、rchild（分别指向该结点的左、右子树）。结点及结构如图6-1所示： //- - - - - - 二叉树的二叉链表存储表示模型- - - - - - - typedef struct BiTNode{ ? TElemType??????? data; ? Struct BiTNode?? * lchild, * rchild;? //左右孩子指针 }BiTNode, * BiTree; 将此结构定义放在一个头文件.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出的及常量的定义。 Status CreateBiTree(BiTree T) //按先序次序输入二叉树中结点的值（一个字符），＃字符表示空树， //构造二叉链表表示的二叉树T。 scanf(ch); if (ch==＃) T=NULL; else { if (!(T=(BiTNode *) malloc(sizeof(BiTNode)))) exit (OVERFLOW); ??? T-data = ch;????????????? //生成根结点 ??? CreateBiTree(T-lchild);?? //生成左子树 ??? CreateBiTree(T-rchild);?? //生成右子树 } return OK; }//CreateBiTree 参考程序： //头文件BiTNode.h的内容如下： #include stdio.h #include stdlib.h #include malloc.h #define MAX 20 #define OK 1 #define ERROR 0 #define NULL 0 #define OVERFLOW 0 typedef char TElemType; typedef int Status; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree CreateBiTree(BiTree T) { char ch; scanf(%c,ch); if (ch==#) T=NULL; /* #代表空指针*/ else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); /*申请结点 */ T-data=ch; /*生成根结点 */ T-lchild=CreateBiTree(T-lchild); /*构造左子树 */ T-rchild=CreateBiTree(T-rchild); /*构造右子树 */ } //以下是主程序shiyan6_1_1.c #include BiTNode.h main() { BiTree T=NULL; printf(\n请读入构造二叉树的字符序列：); CreateBiTree(T); /*建立一棵二叉树T*/ } [实验2] 二叉树的遍历 实验内容与要求: 对一棵二叉链表表示的二叉树进行先序遍历、中序遍历、后序遍历和层序遍历并分别输出遍历的结点顺序。 分析： 二叉树的先序遍历是：若二叉树为空，则空操作；否则，访问根结点，先序遍历左子树，先序遍历右子树。 二叉树的中序遍历是：若二叉树为空，则空操作；否则，中序遍历左子树，访问根结点，中序遍历右子树。 二叉树的后序遍历是：若二叉树为空，则空操作；否则，后序遍历左子树，后序遍历右子树；访问