课程实验报告课程名称：数据结构实验
专业班级：
学号：
姓名：
指导教师：
报告日期：
计算机科学与技术学院
5 基于二叉存储结构实二叉树的基本操作 (3)
1.1 问题描述 (3)
1.2二叉树的操作系统设计 (3)
1.2.1 系统总体设计 (3)
1.2.2 有关常量和类型定义 (4)
1.2.3 算法设计&算法分析 (5)
1.3二叉树系统实现与测试 (9)
1.3.1 系统实现 (9)
1.3.2 系统测试 (47)
1.4 实验小结 (55)
5 基于二叉存储结构实二叉树的基本操作
1.1 问题描述
数据结构描述：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆，是一种非常重要的数据结构。其结构如图：
树根
左孩子右孩子
图-3.1 二叉树结构示意图
本次试验要完成的顺序表和链式栈的相关操作。算法有：1.构造二叉树数组2.创建二叉树3.清空二叉树4.判断二叉树是否为空5.返回指定元素的数据6.在指定位置插入和删除子树7.给指定元素结点赋值8.前序遍历二叉树9.中序遍历二叉树遍历10.后序便利二叉树11.层序遍历二叉树12.返回指定结点的左兄弟、右兄弟、双亲、左孩子和右孩子13.计算二叉树深度。
1.2二叉树的操作系统设计
1.2.1 系统总体设计
本系统包括22个模块的功能，包括栈的创建，销毁，清空，判断，计算长度，对指定元素操作，访问二叉树中元素等。系统总体结构如图：
图-3.2 函数调用关系
1.2.2 有关常量和类型定义
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define INIT_TREELINK_LENTH 20 #define INCREASE_LENTH 10
#define INIT_STACK_LENTH 10
初始化树根数组
创建二叉树
清空二叉树
取根地址
指定左孩子地址指定右孩子地址指定双亲地址
主函数
指定左兄弟地址
指定右兄弟地址
指定插入子树
指定删除子树
指定元素赋值
指定元素取值
typedef char Elemtype;
typedef struct BiTreeNode //树结点定义
{
struct BiTreeNode *lChild;
Elemtype data;
int Node_Num;
struct BiTreeNode *rChild;
int flag;
}BiTreeNode;
typedef struct TreeLink //根数组
{
BiTreeNode *root;
}TreeLink;
typedef struct //定义顺序栈结构
{
BiTreeNode* stack[INIT_STACK_LENTH];
int stack_top;
}SqStack;
typedef struct Qnode //定义队列结构
{
BiTreeNode* data;
struct Qnode *next;
}Qnode;
typedef struct LinkQueue
{
Qnode *front;
Qnode *rear;
}LinkQueue;
1.2.3 算法设计&算法分析
1.构造树根数组
创建一个树根数组，长度为INIT_ETRRLINK_LENTH，每一个元素的值为NULL 输入：数组首元素的地址
输出：一个树根数组
时间复杂度为常量阶，O(1);
空间复杂度为常量阶，O(20)
2.清空二叉树
直接将root置为NULL
输入：树根的地址
输出：销毁成功OK或失败False
时间复杂度：常量阶，O(1)；空间复杂度：常量阶O(0)
3.判空二叉树
判断root是否指向，是的即为空，否则不为空
输入：树根的地址
输出：是否为空OK或者FALSE
时间复杂度：常量阶O(1)；空间复杂度：O(0)
4.创建二叉树
递归创建结点，没有孩子则输入#；返回树的指针并赋值个树根指针并赋给对应的树根指针；
输入：无
输出：一个二叉树的树根地址
时间复杂度：线性阶O(n);空间复杂度：指数阶O(n2);
6.计算二叉树深度
输入：树根的地址
输出：树的深度
如果为空二叉树，则返回FALSE
否则，对左右子树递归调用自身函数，最后比较左右子树的深度，取大加一
时间复杂度：常量阶，O(n)；空间复杂度：指数阶，O(n2)
7.前序遍历二叉树
用递归和非递归两种方式进行遍历；
输入：树根地址
输出：打印遍历结果
如果为空，返回FALSE
时间复杂度：线性阶，O(n)；空间复杂度：线性阶，O(n)
8.中遍历二叉树
用递归和非递归两种方式进行遍历；
输入：树根地址
输出：打印遍历结果
如果为空，返回FALSE
时间复杂度：线性阶，O(n)；空间复杂度：线性阶，O(n)
9.后序遍历二叉树
用递归和非递归两种方式进行遍历；
输入：树根地址
输出：打印遍历结果
如果为空，返回FALSE
时间复杂度：线性阶，O(n)；空间复杂度：线性阶，O(n)
10.层序遍历二叉树
用一个队列保存结点地址，层序遍历
输入：树根地址
输出：屏幕打印遍历结果
如果为空返回FALSE；
时间复杂度：线性阶，O(n);空间复杂度：线性阶，O(n);
11.返回根地址
输入：树根地址
数度：树根地址
如果为空则返回FALSE；
时间复杂度：常数阶，O(0);空间复杂度：常熟阶，O(0);
12.返回指定结点左右孩子地址
输入：树根地址，结点编号
输出：对应结点的左（右）孩子地址
如果为空则返回FALSE，如果没有左（右）孩子则返回NULL，如果没有输入的元素则打印提示；
时间复杂度：线性阶，O(N),空间复杂度：线性阶O(n);
13.返回指定结点左右兄弟地址
输入：树根地址，结点编号
输出：对应结点的左（右）兄弟地址
如果为空则返回FALSE，如果没有左（右）兄弟则返回NULL，如果没有输入的元素则打印提示；
时间复杂度：线性阶，O(N),空间复杂度：线性阶O(n);
14.返回指定结点双亲地址
输入：树根地址，结点编号
输出：对应结点的双亲地址
如果为空则返回FALSE，如果没有双亲则返回NULL，如果没有输入的元素则打印提示；
时间复杂度：线性阶，O(N),空间复杂度：线性阶O(n);
15.对指定结点赋值（取值）
输入：树根指针，要赋的值
输出：对应元素的值
如果为空则返回FALSE
时间复杂度：线性阶，O(N),空间复杂度：线性阶O(n);
16.在指定位置插入（删除）子树
输入：树根指针，要插入的指针
输出：插入（删除）后的树根地址
如果为空返回FALSE
时间复杂度：线性阶，O(N),空间复杂度：线性阶O(n);
1.3二叉树系统实现与测试
1.3.1 系统实现
1.编程环境的设置
本次实验用的visual stdio 2012，语言使用C语言。
2.函数调用关系
主程序，调用各个功能函数，在与栈有关的功能函数中调用对栈的相关操作函数，在与队列有关的功能函数中调用对队列的相关操作函数。
3.程序清单
int InitQueue(LinkQueue *Q);
int QueueEmpty(LinkQueue *Q);
BiTreeNode* DeQueue(LinkQueue *Q);
int EnQueue(LinkQueue *Q,BiTreeNode *e);
int InitStack(SqStack *L);
int StackEmpty(SqStack *L);
int Push(SqStack *L,BiTreeNode *e);
BiTreeNode* Pop(SqStack *L);
TreeLink* InitBiTree();
BiTreeNode* CreatBiTree(void);
int Visit(Elemtype p);
void RecursionPreOrderTraverse(BiTreeNode *T);
void UnRecursionPreOrderTraverse(BiTreeNode *T) ;
int BiTreeEmpty(BiTreeNode *T);
int BiTreeDepth(BiTreeNode *T);
void RecursionInOrderTraverse(BiTreeNode *T) ;
void UnRecursionInOrderTraverse(BiTreeNode *T);
void RecursionPostOrderTraverse(BiTreeNode *T);
void UnRecursionPostOrderTraverse(BiTreeNode *T);
BiTreeNode* RightSibling(BiTreeNode *T,int i); BiTreeNode* LeftSibling(BiTreeNode *T,int i); BiTreeNode* Parent(BiTreeNode *T,int i); BiTreeNode* LeftChlid(BiTreeNode *T,int i); BiTreeNode* RightChlid(BiTreeNode *T,int i);
int InsertChlid(BiTreeNode *T,int i,BiTreeNode *c); int DeleteChild(BiTreeNode *T,int i);
int Assign(BiTreeNode *T,int i,Elemtype data); Elemtype Value(BiTreeNode *T,int i);
源代码：
#include
#include
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define INIT_TREELINK_LENTH 20
#define INCREASE_LENTH 10
#define INIT_STACK_LENTH 10
typedef char Elemtype;
typedef struct BiTreeNode //树结点定义{
struct BiTreeNode *lChild;
Elemtype data;
int Node_Num;
struct BiTreeNode *rChild;
int flag;
}BiTreeNode;
typedef struct TreeLink //根数组
{
BiTreeNode *root;
}TreeLink;
typedef struct //定义顺序栈结构{
BiTreeNode* stack[INIT_STACK_LENTH];
int stack_top;
}SqStack;
typedef struct Qnode //定义队列结构{
BiTreeNode* data;
struct Qnode *next;
}Qnode;
typedef struct LinkQueue
{
Qnode *front;
Qnode *rear;
}LinkQueue;
int InitQueue(LinkQueue *Q);
int QueueEmpty(LinkQueue *Q);
BiTreeNode* DeQueue(LinkQueue *Q);
int EnQueue(LinkQueue *Q,BiTreeNode *e);
int InitStack(SqStack *L);
int StackEmpty(SqStack *L);
int Push(SqStack *L,BiTreeNode *e);
BiTreeNode* Pop(SqStack *L);
TreeLink* InitBiTree();
BiTreeNode* CreatBiTree(void);
int Visit(Elemtype p);
void RecursionPreOrderTraverse(BiTreeNode *T); void UnRecursionPreOrderTraverse(BiTreeNode *T) ; int BiTreeEmpty(BiTreeNode *T);
int BiTreeDepth(BiTreeNode *T);
void RecursionInOrderTraverse(BiTreeNode *T) ; void UnRecursionInOrderTraverse(BiTreeNode *T); void RecursionPostOrderTraverse(BiTreeNode *T); void UnRecursionPostOrderTraverse(BiTreeNode *T); BiTreeNode* RightSibling(BiTreeNode *T,int i); BiTreeNode* LeftSibling(BiTreeNode *T,int i); BiTreeNode* Parent(BiTreeNode *T,int i);
BiTreeNode* LeftChlid(BiTreeNode *T,int i);
BiTreeNode* RightChlid(BiTreeNode *T,int i);
int InsertChlid(BiTreeNode *T,int i,BiTreeNode *c);
int DeleteChild(BiTreeNode *T,int i);
int Assign(BiTreeNode *T,int i,Elemtype data);
Elemtype Value(BiTreeNode *T,int i);
/******************************************************************** *************
函数名称：InitQueue(LinkQueue *Q)
函数功能：初始化一个空的队列
函数参数：队列基址
********************************************************************* *************/
int InitQueue(LinkQueue *Q)
{
Q->rear=(Qnode*)malloc(sizeof(Qnode));
Q->front=Q->rear;
Q->front->next=NULL;
Q->rear->data=NULL;
return OK;
}
/******************************************************************** *************
函数名称：EnQueue(LinkQueue *Q,Elemtype e)
初始条件：队列已经存在
函数功能：插入一个新的元素结点到队尾
函数参数：队列基址和插入的数据
********************************************************************* *************/
int EnQueue(LinkQueue *Q,BiTreeNode *e)
{
Qnode *p;
p=(Qnode *)malloc(sizeof(Qnode));
if(!p)
{
printf("\n\t\t生成结点失败！");
return ERROR;
}
p->data=e;
p->next=Q->front;
Q->rear->next=p;
Q->rear=p;
return OK;
}
/******************************************************************** *************
函数名称：QueueEmpty(LinkQueue *Q)
初始条件：队列已经存在
函数功能：判断队列是否为空队列，是则返回TRUE，否则返回FALSE
函数参数：队列基址
********************************************************************* *************/
int QueueEmpty(LinkQueue *Q)
{
if(Q->front==Q->rear)
{
return TRUE;
}
else
{
return FALSE;
}
}
/******************************************************************** *************
函数名称：DeQueue(LinkQueue *Q)
初始条件：队列已经存在
函数功能：删除队列首结点
函数参数：队列基址
*********************************************************************
*************/
BiTreeNode* DeQueue(LinkQueue *Q)
{
Qnode *p;
BiTreeNode *e;
if(QueueEmpty(Q))
{
printf("\n\t\t空队列，不能出队列！");
return ERROR;
}
p=Q->front;
Q->front=p->next;
e=p->next->data;
free(p);
return e;
}
/******************************************************************** ***************************************************************
函数名称：InitStack(SqStack *L)
操作结果：构造一个空栈
********************************************************************* **************************************************************/
int InitStack(SqStack *L)
{
L->stack_top=-1;
return OK;
}
/******************************************************************** **************************************************************
函数名称：StackEmpty(SqStack *L)
初始条件：栈已存在
操作结果：如果栈为空返回TRUE,不为空返回FALSE
********************************************************************* *************************************************************/
int StackEmpty(SqStack *L)
{
if(L->stack_top<0)
return TRUE;
else
return FALSE;
}
/******************************************************************** **************************************************************
函数名称：Push(SqStack *L,BiTreeNode e)
初始条件：栈已存在
操作结果：插入一个元素作为新的栈顶(新的栈顶元素入栈）
********************************************************************* *************************************************************/
int Push(SqStack *L,BiTreeNode *e)
{
if(L->stack_top { L->stack_top+=1; L->stack[L->stack_top]=e; } else printf("\n\t\t数据溢出\n"); return OK; } /******************************************************************** ************************************************************** 函数名称：Pop(SqStack *L,BiTreeNode e) 初始条件：栈已存在且不为空 操作结果：用e保存当前栈顶元素(栈顶元素出栈） ********************************************************************* *************************************************************/ BiTreeNode* Pop(SqStack *L) { BiTreeNode *e; if(L->stack_top!=-1) { e=L->stack[L->stack_top]; L->stack_top-=1; } else printf("\n\t\t栈已经为空\n"); return e; } /******************************************************************** ************************** 函数名称：InitBiTree() 函数功能：生成数目为初始长度棵树的根节点，并用一个根数组存储 函数参数：无 函数返回：存储根结点的数组基址 ********************************************************************* *************************/ TreeLink* InitBiTree() { TreeLink *T; T=(TreeLink*)malloc(sizeof(TreeLink)*INIT_TREELINK_LENTH); return T; } /******************************************************************** *********************** 函数名称：CreatBiTree(BiTreeNode *T) 函数功能：用递归的方式建立二叉树 函数参数：树根的左子树指针 ********************************************************************* ***********************/ BiTreeNode * CreatBiTree(void) { Elemtype c; BiTreeNode *T; int i; T=NULL; printf("\n\t\t输入结点数据，没有则输入#：\n\t\tc="); scanf("%1s",&c); if(c!='#') { printf("\n\t\t输入结点编号\n\t\ti="); scanf("%d",&i); T=(BiTreeNode*)malloc(sizeof(BiTreeNode)); T->data=c; T->Node_Num=i; printf("\n\t\t对左孩子："); T->lChild=CreatBiTree(); printf("\n\t\t对右孩子："); T->rChild=CreatBiTree(); } return T; } /******************************************************************** ********************* 函数名称：ClearBiTree(BiTreeNode *T) 函数功能：将二叉树置为空 函数参数：树根指针 ********************************************************************* *********************/ int ClearBiTree(BiTreeNode *T) { T=NULL; return OK; } /******************************************************************** ******************** 函数名称：BiTreeEmpty(BiTreeNode *T) 函数功能：判断一棵树是否为空,是则返回TRUE，否则返回FALSE 函数参数：树根指针 ********************************************************************* ********************/ int BiTreeEmpty(BiTreeNode *T) { if(T==NULL) return TRUE; else return FALSE; } /******************************************************************** ******************** 函数名称：Visit(Elemtype p) 函数功能：访问结点数据 函数参数：数据域标识符 ********************************************************************* ********************/ int Visit(Elemtype p) { printf("%4c",p); return OK; } /******************************************************************** ******************** 函数名称：RecursionPreOrderTraverse(BiTreeNode *T) 函数功能：使用递归的方法对二叉树进行前序遍历 初始条件：二叉树已经存在且不为空 函数参数：树根指针 ********************************************************************* ********************/ void RecursionPreOrderTraverse(BiTreeNode *T) { if(T) { printf("%4c",T->data); RecursionPreOrderTraverse(T->lChild); RecursionPreOrderTraverse(T->rChild); } } /******************************************************************** ******************** 函数名称：UnRecursionPreOrder(BiTreeNode *T) 函数功能：使用非递归的方法对二叉树进行前序遍历 初始条件：二叉树已经存在且不为空 函数参数：树根指针 ********************************************************************* ********************/ void UnRecursionPreOrderTraverse(BiTreeNode *T) { BiTreeNode *p=T; SqStack s; InitStack(&s); while(p||!StackEmpty(&s)) { if(p) { Visit(p->data); Push(&s,p); p=p->lChild; } else { p=Pop(&s); p=p->rChild; } } } /******************************************************************** ******************** 函数名称：RecursionIndOrderTraverse(BiTreeNode *T) 函数功能：使用递归的方法对二叉树进行中序遍历 初始条件：二叉树已经存在且不为空 函数参数：树根指针 ********************************************************************* ********************/ void RecursionInOrderTraverse(BiTreeNode *T) { if(T) { RecursionInOrderTraverse(T->lChild); Visit(T->data); RecursionInOrderTraverse(T->rChild); } } /******************************************************************** ******************** 函数名称：UnRecursionIndOrderTraverse(BiTreeNode *T) 函数功能：使用非递归的方法对二叉树进行中序遍历 初始条件：二叉树已经存在且不为空 函数参数：树根指针 ********************************************************************* ********************/ void UnRecursionInOrderTraverse(BiTreeNode *T) { BiTreeNode *p=T; SqStack s; InitStack(&s); while(p||!StackEmpty(&s)) { if(p) { Push(&s,p); p=p->lChild; } else { p=Pop(&s); Visit(p->data);
相关主题
文本预览