山东大学数据结构第三次实验实验报告.docx

实验3 二叉树的编程与实现实验目的：掌握指针变量、动态变量的含义，掌握二叉树的结构特征，以及各种存储结构的特点及适用范围，掌握指针类型描述、访问和处理二叉树的运算；实验原理：参照课本p.95-107， Figure4.13-4.25；实验内容：已知以二叉树表作为存储结构，写出按层次顺序遍历二叉树的算法算法思想：本算法采用一个队列q，先将二叉树根节点入队列，然后退队列，输出该节点，若它有左子树，便将左子树根节点入队列；若有右子树，便将右子树根节点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。实验要求：实现二叉树表的层次遍历算法，并给出应用。实验步骤：一、实验源程序：1、源文件Tree.c程序：//Tree.c#include stdafx.h#include tree.hint createbitree(bitree T,int sum){ char ch; scanf(%c,ch); if(ch== ) T=NULL; else { if(!(T=(bitree)malloc(sizeof(binode)))) return 0; T-data=ch; sum++; createbitree(T-lchild,sum); createbitree(T-rchild,sum); } return 1;}//初始化一个带头结点的队列void initqueue(linkqueue q){ q.front=q.rear=(queueptr)malloc(sizeof(queuenode)); q.front-next=NULL;}//入队列void enqueue(linkqueue q,bitree p){ queueptr s; int first=1; s=(queueptr)malloc(sizeof(queuenode)); s-ch=p; s-next=NULL; q.rear-next=s; q.rear=s;}//出队列void dequeue(linkqueue q,bitree p){ char data; queueptr s; s=q.front-next; p=s-ch; data=p-data; q.front-next=s-next; if(q.rear==s) q.rear=q.front; free(s); printf(%c ,data);}//判断队列是否为空int queueempty(linkqueue q){ if(q.front-next==NULL) return 1; return 0;}//按层次遍历树中结点void traverse(bitree bt){ int ceng=1,jiedian=0; linkqueue q; bitree p; initqueue(q); p=bt; enqueue(q,p); while(queueempty(q)!=1) { dequeue(q,p); jiedian++; if(jiedian%ceng == 0) {printf(\n);jiedian = 0;ceng = ceng*2; } if(p-lchild!=NULL) enqueue(q,p-lchild); if(p-rchild!=NULL) enqueue(q,p-rchild); } printf(\n);}2、源文件SearchTree.c程序：//SearchTree.c#include stdafx.h#include searchtree.h//创建空的二叉查找树SearchTreeMakeEmpty( SearchTree T ){if( T != NULL ){MakeEmpty( T-Left );MakeEmpty( T-Right );free( T );}return NULL;}//寻找二叉查找树中的某个元素PositionFind( ElementType X, SearchTree T ){if(T == NULL)return NULL;if( X T-Element )return Find( X, T-Left );elseif(X T-Element)return Find( X, T -Right );else return T;}//寻找二叉查找树中的最小元素PositionFindMin( SearchTree T ){if( T== NULL)return NULL;elseif( T-Left == NULL )return T;elsereturn FindMin( T-Left );}//寻找二叉查找树中的最大元素PositionF