实验六 树与二叉树
6.1实验目的：
（1） 掌握二叉树链表的结构和二叉树的建立过程；
（2） 掌握二叉树的基本操作，加深对二叉树的理解，逐步培养解决实际问题的编程能力。
6.2实验要求：
（1） 复习课本中有关树与二叉树的知识；
（2） 用C语言完成算法和程序设计并上机调试通过；
（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括
时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
6.3基础实验
[实验1] 二叉树的构造
实验内容与要求:
按先序序列构造一棵二叉链表表示的二叉树T； 分析:
二叉树是每个结点至多只有两棵子树，并有左、右之分，顺序不能任意颠倒的一种非线性结构。二叉树常用的存储结构是二叉链表形式，二叉链表由一个数据项data（用于存放结点的值）和两个指针项lchild、rchild（分别指向该结点的左、右子树）。结点及结构如图6-1所示：
data lchild rchild data
rchild lchild 图6-1含有两个指针的二叉树的结点及结构
//- - - - - - 二叉树的二叉链表存储表示模型- - - - - - - typedef struct BiTNode{ TElemType data;
Struct BiTNode * lchild, * rchild; //左右孩子指针 }BiTNode, * BiTree;
将此结构定义放在一个头文件BiTNode.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出二叉链表的初始化及常量的定义。 实现提示
按先序序列建立一棵二叉树，先构造根结点，再构造根的左、右子树；每一棵子树又都是一颗二叉树，所以构造一棵子树的过程与构造整棵二叉树的过程完全相同， 按照先序序列，先构造根，再构造左子树，然后构造右子树；采用递归形式直到叶子结点为止。以下是算法描述：
Status CreateBiTree(BiTree &T)
//按先序次序输入二叉树中结点的值（一个字符），＃字符表示空树， //构造二叉链表表示的二叉树T。
1
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
#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(\
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 \main() {
BiTree T=NULL;
2
printf(\请读入构造二叉树的字符序列：\ CreateBiTree(T); /*建立一棵二叉树T*/
}
[实验2] 二叉树的遍历
实验内容与要求:
对一棵二叉链表表示的二叉树进行先序遍历、中序遍历、后序遍历和层序遍历并分别输出遍历的结点顺序。
分析：
二叉树的先序遍历是：若二叉树为空，则空操作；否则，访问根结点，先序遍历左子树，先序遍历右子树。
二叉树的中序遍历是：若二叉树为空，则空操作；否则，中序遍历左子树，访问根结点，中序遍历右子树。
二叉树的后序遍历是：若二叉树为空，则空操作；否则，后序遍历左子树，后序遍历右子树；访问个结点。
二叉树的层序遍历是：在访问二叉树的结点时按照自上而下，从左至右的顺序。根作为第一层，根的孩子作为第二层，以此类推。 先序遍历二叉树递归算法
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){ //采用二叉链表存储结构，Visit是对数据元素操作的应用函数， //先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。 //一旦visit()失败，则操作失败。 if (T){
if (Visit(T->data))
if (PreOrderTraverse(T->lchild,Visit))
if (PreOrderTraverse(T->rchild，Visit)) return OK;
return ERROR; }else return OK; }// PreOrderTraverse 中序遍历的递归算法
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){ if (T){
if (InOrderTraverse(T->rchild，Visit)) if (Visit(T->data))
3
if (InOrderTraverse(T->rchild，Visit)) return OK; return ERROR; }else return OK; }// InOrderTraverse 后序遍历递归算法
Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){
if (PostOrderTraverse(T->lchild,Visst) )
if (PostOrderTraverse(T->rchild，Visit)) if (Visit(T->data)) return OK; return ERROR; }else return OK; }// PreOrderTraverse
层次遍历二叉树的非递归算法 Status LevelOrder(BiTree T){ //按层次遍历二叉树T， Q为队列 InitQueue(Q);
If (T!=NULL){// 若树非空
EnQueue(Q,T);//根结点入队列 While (!QueueEmpty(Q)){
DeQueue(Q,b); //队首元素出队列 Visit(b->data); //访问结点
If (b->lchild!=NULL) EnQueue(Q,b->lchild);//左子树非空，则入队列 If (b->rchold!=Null) EnQueue(Q,b->rchild);//右子树非空，则入队列 }//while }//if }LevelOrder
参考程序：
//以下代码保存在文件shiyan6_1_2.c
#include
Status PrintElement(TElemType e) {
printf(\
4
return OK; }
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)) {
int i,j,k;
if(T==NULL) return OK; else {
i=Visit(T->data); if(i) {
j=PreOrderTraverse(T->lchild,Visit); /*先序遍历左子树*/ if(j) {
k=PreOrderTraverse(T->rchild,Visit);/*先序遍历右子树*/ if(k) return OK; } }
else return ERROR; } }
Status InOrderTraverse( BiTree T, Status(*Visit)(TElemType) ) {/*中序遍历*/ if (T) {
if (InOrderTraverse(T->lchild, Visit)) if (Visit(T->data))
if (InOrderTraverse(T->rchild, Visit)) return OK; return ERROR; }
else return OK; }
Status PostOrderTraverse( BiTree T, Status(*Visit)(TElemType) ) {/*后序遍历*/ if (T) {
if (PostOrderTraverse(T->lchild, Visit))
if (PostOrderTraverse(T->rchild, Visit)) if (Visit(T->data)) return OK; return ERROR; }
else return OK; }
5