实验三(00001).doc

;;。重点与难点二叉树的四种遍历方法的程序实现教学手段与方法上机编程、调试并进行验证教学过程:(包括授课思路、过程设计、讲解要点及各部分具体内容、时间分配等)实验内容:,用#代表虚结点(空指针),如ABD###CE##F###建立二叉树,实现先序、中序和后序以及按层次遍历序列。。编程思路:首先建立二叉树的二叉链表存储结构,然后设计函数完成二叉树的各种操作。要求:对二叉树的先序遍历、中序遍历和后序遍历要给出递归和非递归算法。需要编写的函数有:栈的相关操作函数:InitStack(S)(初始化栈)、GetTop(S,e)(取栈顶元素)、Push(S,e)(入栈操作)、Pop(S,e)(出栈操作)以及StackEmpty(S)(判断栈空)队列的相关操作函数:InitQueue(Q)(初始化队列)、EnQueue(Q,e)(入队列操作)、DeQueue(Q,e)(出队列操作)、GetHead(Q,e)(取队头元素)以及QueueEmpty(Q)(判断队列空)二叉树操作的相关函数:PreOrderTraverse(bt)(先序遍历)、InOrderTraverse(bt)(中序遍历)、PostOrderTraverse(bt)(后序遍历)、LevelOrderTraverse(bt)(层次遍历)以及Leaves(bt)(求二叉树的叶子结点数)程序描述如下:#include<>#include<>typedefstructBiTNode{//建立二叉树的二叉链表chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;#defineMAXSTACK15typedefstruct{//定义栈的存储结构BiTree*base;inttop;}SqStack;#defineMAXQUEUE20typedefstruct{//定义队列的存储结构BiTree*base;intfront,rear;}SqQueue;//栈操作的相关函数voidInitStack(SqStack&S){=(BiTree*)malloc(sizeof(BiTNode));if(!)exit(0);=0;}voidPush(SqStack&S,BiTreee){if(==MAXSTACK)exit(0);[]=e;++;}voidPop(SqStack&S,BiTree&e){if(==0)exit(0);--;e=[];}intGetTop(SqStackS,BiTree&e){if(==0)return0;e=[-1];return1;}intStackEmpty(SqStackS){if(==0)return1;elsereturn0;}//队列操作的相关函数voidInitQueue(SqQueue&Q){=(BiTree*)m