数据结构二叉树作业.doc

个人收集整理 勿做商业用途
1. 实验目的：
通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法.
2. 实验内容与要求：
基于二叉链表存储结构实现二叉树的基本运算,要求:
⑴能建立非空二叉树;
⑵实现二叉树的先、中、后序递归遍历算法；
⑶实现二叉树的非递归的先(或中、或后)序遍历算法及层序遍历算法;
⑷记录运行结果并对递归算法和非递归算法的效率加以分析。
3. 数据结构设计：
逻辑结构：树形结构
存储结构：链式存储结构
4. 算法设计:

＃include 〈stdio.h>
＃include
#define OK 1
＃define ERROR 0
//使用二叉链表存储形式
typedef struct BiTNode
{
char data；
struct BiTNode ＊lchild，＊rchild;
｝BiTNode，*BiTree;
//这里是将指向节点的指针放到栈里，而通过调试是
//可以看到指针指向的值的,所以不是将树放进去了
typedef struct
{
BiTree *base；
BiTree ＊top;
int stacksize；
｝SqStack;
typedef struct
{
BiTree ＊base；
int front；
int rear;
}SqQueue;

int InitStack（SqStack &S)
｛
S.base = （BiTree ＊)malloc(100＊sizeof(BiTree）);
if( ！S。base)
exit(2)；
S.top = S.base；
S.stacksize = 100；
return OK；
｝

int GetTop(SqStack S,BiTree ＆e)
{
if(S。top == S.base )
return ERROR；
e = *（S。top—1);
return OK;
}

int PUSH（SqStack &S ,BiTree e)
｛
if(S。top—S。base 〉= S.stacksize)
{
S.base = (BiTree *）realloc(S.base,(S。stacksize + 10)*sizeof(BiTree） )；
if（！S。base）
exit（2)；
S.top = S。base + S。stacksize；
S.stacksize = S.stacksize+10;
}
＊S.top++ = e;
return OK；
｝

int POP(SqStack ＆S,BiTree &e）
{
if(S.top == S.base)
return ERROR；
e = *—-S。top;
return OK;
｝

int StackEmpty(SqStack S）
{
if （S。base == NULL)
return ERROR；
if (S。base == S。top）
return OK；
return ERROR;
｝
//队列的东西伤不起啊
int InitQueue（SqQueue &Q）
{
Q.base = (BiTree *)malloc(100*sizeof（BiTree))；
if(！Q.base）
exit(2);
Q。front=Q。rear = 0；
return OK;
}

int EnQueue（SqQueue &Q，BiTree e)
{
if（ (Q。rear+1） ％ 100 == Q。front）
return ERROR；
Q。base［Q。rear] = e;
Q.rear = （ Q。rear+1 ) % 100；
return OK;
}

int DeQueue(SqQueue ＆Q,BiTree &e）
{
if(Q。front == Q.rear）
return ERROR；
e = Q.base［Q.front]；
Q。front = (Q.front+1） % 100；
return OK；
｝

int QueueEmpty（SqQueue Q)
｛
if (Q。base == NULL)
return ERROR；
if (Q.front == Q.rear）
return OK;
return ERROR;
｝

BiTree CreateBiTree(BiTree &T)
{ // 算法6。4
// 按先序次序输入二叉树中结点的值（一个字符）,空格字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch；
scanf(”％c",＆ch）; //这里表明了输入形式是ABCDE＃＃FG然后是回车
if (ch==’#’)
T = NULL；
else
{
if (！(T = (BiTNode ＊)malloc(sizeof(BiTNode)）)）
return ERROR；
T—>data = ch； // 生成根结点
CreateBiTree(T-〉lchild); // 构造左子树
CreateBiTree(T->rchild)； // 构造右子树
}
return T；
} // CreateBiTree

int PrintElement(char e）
｛ // 输出元素e的值
printf（"%c",e）；
return OK；
}

int PreOrderTraverse（ BiTree T， int（＊Visit）（char） )
{
// 算法6.1
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数,
// 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
// 调用实例：PreOrderTraverse（T, PrintElement);
if(T）
｛
if (Visit（T—〉data））
if (PreOrderTraverse（T—>lchild, Visit))
if （PreOrderTraverse(T-〉rchild, Visit））
return OK；
printf（"\n");
return ERROR;
}
else
return OK;
} // PreOrderTraverse
//和前面一样的，不解释
int InOrderTraverse2( BiTree T, int(*Visit)(char) )
{
if(T）
｛
if (InOrderTraverse2(T—〉lchild, Visit))
if （Visit(T—>data））
if （InOrderTraverse2（T—〉rchild， Visit))
return OK；
printf(”\n");
return ERROR;
}
else
return OK；
｝

int PostOrderTraverse BiTree T， int（*Visit）(char） )
｛
if（T)
{
if （PostOrderTraverse（T—>lchild， Visit)）
if （PostOrderTraverse(T—>rchild, Visit)）
if （Visit(T-〉data))
return OK;
printf(”\n”）；
return ERROR；
}
else
return OK；
}

int InOrderTraverse(BiTree T， int (*Visit)（char））
{
// 算法6.2
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
int InitStack(SqStack &S);
int GetTop（SqStack S，BiTree ＆e）；
int PUSH（SqStack &S ,BiTree e）；
int POP(SqStack ＆S，BiTree ＆e）;
int StackEmpty（SqStack S） ;

SqStack S;
BiTree p;
if（!T）
return ERROR;
InitStack（S）；
PUSH(S，T); // 根指针进栈
while (!StackEmpty（S))
｛
while （GetTop(S， p） &＆ p)
PUSH(S, p->lchild）; // 向左走到尽头
POP(S， p)； // 空指针退栈
if (！StackEmpty（S）)
｛ // 访问结点，向右一步
POP(S, p）;
if （!Visit(p—〉data））
return ERROR；
PUSH(S, p—〉rchild);
}
}
return OK；
} // InOrderTraverse

//层序遍历法
int LevelOrderTraverse（BiTree T, int （＊Visit）(char））
｛
int InitQueue(SqQueue ＆Q)；
int EnQueue(SqQueue ＆Q,BiTree e);
int DeQueue（SqQueue &Q,BiTree &e)；
int QueueEmpty（SqQueue Q);

SqQueue Q；
BiTree p;
if(！T)
return ERROR；
InitQueue(Q）;
EnQueue（Q,T）; //先入队
while(！QueueEmpty（Q)）//判空，如果是刚开始的话肯定不空直到遍历完
｛
DeQueue(Q，p);//先出队
if(！Visit（p—〉data)） //访问
return ERROR；
if（p-〉lchild） //左孩子入队（如果有）
EnQueue（Q,p-〉lchild）；
if（p—>rchild) //右孩子入队(如果有）
EnQueue（Q，p-〉rchild
}
return OK；
｝

int main（）
{
LARGE_INTEGER litmp；
LONGLONG QPart1,QPart2;
double dfMinus,dfFreq，dfTim；
BiTree CreateBiTree（BiTree &T);
int PrintElement（char e);

BiTNode *T；
printf("请输入二叉树，空节点为\”＃\”\n"）；
printf(”例如:a#bc#d##＃\n”）；
CreateBiTree(T）;

printf(”前序遍历二叉树的结果为:\n"）;
PreOrderTraverse（T，PrintElement）；
printf（"\n”）；

QueryPerformanceFrequency（＆litmp)；
dfFreq = （double)litmp.QuadPart;
QueryPerformanceCounter（&litmp）；
QPart1 = litmp。QuadPart;
printf(”中序遍历二叉树的结果为:\n"）;
InOrderTraverse2(T,PrintElement）；
printf(”\n");
QueryPerformanceCounter(&litmp);
QPart2 = litmp。QuadPart；
dfMinus = （double)(QPart2—QPart1）;
dfTim = dfMinus / dfFreq；
printf(”中序遍历（递归)使用时间为％lf毫秒\n”，dfTim)；

printf(”后序遍历二叉树的结果为:\n"）；
PostOrderTraverse(T,PrintElement);
printf（”\n");

printf("层序遍历二叉树的结果为:\n")；
LevelOrderTraverse(T，PrintElement);
printf("\n”)；

QueryPerformanceFrequency(＆litmp）；
dfFreq = （double）litmp。QuadPart；
QueryPerformanceCounter(＆litmp)；
QPart1 = litmp.QuadPart；
printf("中序遍历二叉树(非递归)的结果为:\n”)；
InOrderTraverse（T，PrintElement);
printf("\n”）；
QueryPerformanceCounter(&litmp）；
QPart2 = litmp.QuadPart;
dfMinus = (double）（QPart2-QPart1)；
dfTim = dfMinus / dfFreq；
printf（"中序遍历(非递归）使用时间为％lf毫秒\n”,dfTim）；

system("pause");
return OK；
}

5. 实验结果: