《数据结构》试验提醒

本文格式为Word版，下载可任意编辑——《数据结构》试验提醒

《数据结构》试验提醒

试验五、二叉树的基本操作和应用

（1）先定义宏，再定义元素、二叉树的顺序表等的类型，并声明顺序表的基本操作。例如如下：

#include\#include\#include\#defineTRUE1#defineFALSE0#defineOK1#defineERROR0

typedefintStatus;

typedefcharElemType[6];//元素类型typedefstructNode{

ElemTypedata;structNode*lchild;structNode*rchild;

}BiTNode,*BiTree;//二叉树的二叉链表结构

StatusCreateBiTree(BiTree//二叉树的建立算法voidPreOrder(BiTreeroot);//先根遍历算法voidInOrder(BiTreeroot);//中根遍历算法voidPostOrder(BiTreeT);//后根遍历算法

StatusPostOrder1(BiTreeT,Status(*Visit)(ElemTypee));//后根遍历算法StatusVisit(ElemTypee);//访问结点数据

（2）二叉树的基本操作例如如下：

StatusCreateBiTree(BiTreescanf(\

if(ch[0]=='.')T=NULL;else{

T=(BiTree)malloc(sizeof(BiTNode));//建立根结点strcpy(T->data,ch);

CreateBiTree(T->lchild);//建立左子树CreateBiTree(T->rchild);//建立右子树}

returnOK;

1

《数据结构》试验提醒

}//CreateBiTree

StatusVisit(ElemTypee)

{//访问结点数据，输出元素e的值

printf(\returnOK;}

voidInOrder(BiTreeroot){//中根遍历算法if(root!=NULL){

InOrder(root->lchild);Visit(root->data);InOrder(root->rchild);}}

voidPreOrder(BiTreeroot){//先根遍历算法

//不完整，要自己完善

}

StatusPostOrder1(BiTreeT,Status(*Visit)(ElemTypee)){//后根遍历算法

//不完整，要自己完善

}//PostOrder1

（3）按层遍历，需要使用队列，队列元素、顺序队列的等的类型定义及其基本操作等

的声明例如如下：

typedefBiTreeQElemType;//队列的元素类型QElemType，为二叉树结点类型的指针

typedefstruct{

QElemType*base;//动态分派的存储空间intfront;intrear;}Sueue;//顺序队列

StatusInitQueue(Sueue//循环队列初始化

StatusEnQueue(Sueue//进队算法

2

《数据结构》试验提醒

StatusDeQueue(Sueue//出队算法StatusEmptyQueue(SueueQ);//循环队列判空

（4）顺序队列的基本操作例如如下：

StatusEmptyQueue(SueueQ)……

StatusInitQueue(Sueue//否则返回ERROR。

if(Q.front==Q.rear)returnERROR;//队列空……

}//DeQueue

（5）按层次遍历二叉树的算法如下：

StatusLevelTraverTree(BiTreeT){//按层次遍历二叉树

SueueQ;//循环队列QElemTypee;

InitQueue(Q);//循环队列初始化EnQueue(Q,T);//进队while(!EmptyQueue(Q)){

DeQueue(Q,e);//出队