二叉树实验报告.docx

二叉树实验报告.docx

《二叉树实验报告.docx》由会员分享，可在线阅读，更多相关《二叉树实验报告.docx（13页珍藏版）》请在冰点文库上搜索。

二叉树实验报告

实验四二叉树实验报告

一、实验要求

实现二叉树的中序递归遍历、中序非递归遍历、层次遍历等

二、程序功能说明

实现二叉树的中序递归遍历、中序非递归遍历、层次遍历等

三、概要设计

typedefstructBiNode

{

charData;

structBiNode*lChild;

structBiNode*rChild;

}BiNode,*pBiNode;

typedefstructSNode

{

pBiNodeelem;

structSNode*next;

}SNode;

structlink

{

structBiNode*p;

structlink*next;

};

四、详细设计

#include

#include

#defineOK1

#defineERROR0

#defineOVERFLOW-2

typedefintstatus;

typedefstructBiNode//二叉链表

{

charData;

structBiNode*lChild;

structBiNode*rChild;

}BiNode,*pBiNode;

typedefstructSNode/*链栈的结点类型*/

{

pBiNodeelem;/*栈中的元素是指向二叉链表结点的指针*/

structSNode*next;

}SNode;

structlink//队列链表

{

structBiNode*p;

structlink*next;

};

statusCreateTree（BiNode**pTree）;

statusInOrderTraval（BiNode*pTree）;//中序递归

statusst_InOrderTraverse（BiNode*pTree）;//中序非递归遍历

voidTreeLink（BiNode*pTree）;//队列实现层次遍历

statusVisit（charData）;

voidDisplay（BiNode*pTree,intLevel）;

BiNode*pRoot=NULL;

statusCreateTree（BiNode**pTree）/*InputExample:

abd##e##cf##g##*/

{

charch;

scanf（"%c",&ch）;

if（ch=='#'）

{

（*pTree）=NULL;

}

else

{

if（!

（（*pTree）=（BiNode*）malloc（sizeof（BiNode））））

{

exit（OVERFLOW）;

}

（*pTree）->Data=ch;

CreateTree（&（（*pTree）->lChild））;

CreateTree（&（（*pTree）->rChild））;

}

returnOK;

}

statusInOrderTraval（BiNode*pTree）//中序递归

{

if（pTree）

{

if（InOrderTraval（pTree->lChild））

{

if（Visit（pTree->Data））

{

if（InOrderTraval（pTree->rChild））

{

returnOK;

}

}

returnERROR;

}

returnERROR;

}

else

{

returnOK;

}

}

statusst_InOrderTraverse（BiNode*pTree）//中序非递归遍历

{

BiNode*p;

SNode*q,*Stop=NULL;/*用不带头结点的单链表作为栈的存储结构*/

p=pTree;

while（p!

=NULL||Stop!

=NULL）/*不是空树*/

{

if（p!

=NULL）

{

q=（SNode*）malloc（sizeof（SNode））;

if（q==NULL）returnERROR;

q->next=Stop;

q->elem=p;

Stop=q;/*根结点指针入栈*/

p=p->lChild;/*进入根的左子树*/

}

else

{

q=Stop;Stop=Stop->next;/*栈顶元素出栈*/

printf（"%c",q->elem->Data）;/*访问根结点*/

p=q->elem->rChild;/*进入根的右子树*/

free（q）;/*释放原栈顶元素的结点空间*/

}

}

returnOK;

}

voidTreeLink（BiNode*pTree）//队列实现层次遍历

{

structlink*head,*rear,*temp;

head=（structlink*）malloc（sizeof（structlink））;

head->p=pTree;

head->next=NULL;

rear=head;

do{

if（head->p->lChild!

=NULL）

{

temp=（structlink*）malloc（sizeof（structlink））;

temp->p=head->p->lChild;

temp->next=NULL;

rear->next=temp;

rear=temp;

}

if（head->p->rChild!

=NULL）

{

temp=（structlink*）malloc（sizeof（structlink））;

temp->p=head->p->rChild;

temp->next=NULL;

rear->next=temp;

rear=temp;

}

temp=head;

printf（"%c",head->p->Data）;

head=head->next;

free（temp）;

}

while（head!

=NULL）;

}

statusVisit（charData）

{

printf（"%c",Data）;

returnOK;

}

voidDisplay（BiNode*pTree,intLevel）//显示整个树

{

inti;

if（pTree==NULL）return;

Display（pTree->rChild,Level+1）;

for（i=0;i

{

printf（""）;

}

if（Level>=1）

{

printf（"--"）;

}

printf（"%c\n",pTree->Data）;

Display（pTree->lChild,Level+1）;

}

voidCmdList（）//显示命令列表

{

printf（"\n_____________________________________________\n"）;

printf（"请选择操作:

\n"）;

printf（"1.中序递归遍历\n"）;//中序递归遍历

printf（"2.中序非递归遍历\n"）;//中序非递归遍历

printf（"3.层次遍历\n"）;//层次遍历

printf（"0.退出程序\n"）;//退出

printf（"\n______________________________________________\n"）;

}

voidinit（）

{

printf（"请输入二叉树各元素:

（例如abd##e##cf##g##）\n"）;//例如abd##e##cf##g##

CreateTree（&pRoot）;

Display（pRoot,0）;

CmdList（）;

}

voidReadCommand（char&c）

{

do{c=getchar（）;}

while（c!

='0'&&c!

='1'&&c!

='2'&&c!

='3'&&c!

='4'&&c!

='5'&&c!

='6'&&c!

='7'&&c!

='8'&&c!

='9'）;

}

voidInterpret（char&c）

{

switch（c）

{

case'1':

{

printf（"\n中序递归遍历:

\n"）;

InOrderTraval（pRoot）;

CmdList（）;

break;

}

case'2':

{

printf（"\n中序非递归遍历:

\n"）;

st_InOrderTraverse（pRoot）;

CmdList（）;

break;

}

case'3':

{

printf（"\n层次遍历:

\n"）;

TreeLink（pRoot）;

CmdList（）;

break;

}

case'0':

printf（"程序结束，按任意键退出!

\n"）;

}

}

voidmain（）//主函数

{

charcmd;

init（）;

do

{

ReadCommand（cmd）;

Interpret（cmd）;

}

while（cmd!

='0'&&cmd!

='0'）;

}

五、调试说明和测试结果

1、输入二叉树元数

2、执行中序递归遍历

3、中序非递归遍历

4、层次遍历

5、退出程序