数据结构二叉树实验

课程实验报告课程名称：数据结构实验专业班级：学号：姓名：指导教师：报告日期：计算机科学与技术学院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<stdio.h>#include<stdlib.h>#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 10typedef 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;elsereturn FALSE;}/******************************************************************** **************************************************************函数名称：Push(SqStack *L,BiTreeNode e)初始条件：栈已存在操作结果：插入一个元素作为新的栈顶(新的栈顶元素入栈）********************************************************************* *************************************************************/int Push(SqStack *L,BiTreeNode *e){if(L->stack_top<INIT_STACK_LENTH){L->stack_top+=1;L->stack[L->stack_top]=e;}elseprintf("\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;}elseprintf("\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;elsereturn 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);p=p->rChild;}}}/******************************************************************** ********************函数名称：RecursionIndOrderTraverse(BiTreeNode *T)函数功能：使用递归的方法对二叉树进行后序遍历初始条件：二叉树已经存在且不为空函数参数：树根指针********************************************************************* ********************/void RecursionPostOrderTraverse(BiTreeNode *T){if(T){RecursionPostOrderTraverse(T->lChild);RecursionPostOrderTraverse(T->rChild);Visit(T->data);}}/******************************************************************** ********************函数名称：UnRecursionPostdOrderTraverse(BiTreeNode *T)函数功能：使用非递归的方法对二叉树进行后序遍历初始条件：二叉树已经存在且不为空函数参数：树根指针********************************************************************* ********************/void UnRecursionPostOrderTraverse(BiTreeNode *T){}/******************************************************************** ********************函数名称：LevelOrderTraverse(BiTreeNode *T)函数功能：对二叉树进行层序遍历初始条件：二叉树已经存在且不为空函数参数：树根指针********************************************************************* ********************/int LevelOrderTraverse(BiTreeNode *T){BiTreeNode *p;LinkQueue Q;InitQueue(&Q);EnQueue(&Q,T);while(!QueueEmpty(&Q)){p=DeQueue(&Q);Visit(p->data);if(p->lChild!=NULL)EnQueue(&Q,p->lChild);if(p->rChild!=NULL)EnQueue(&Q,p->rChild);}return OK;}/******************************************************************** ********************函数名称：Destory(BiTreeNode *T)函数功能：将二叉树所占的空间释放掉初始条件：二叉树已经存在函数参数：树根指针********************************************************************* ********************/int DestoryBiTree(BiTreeNode *T){BiTreeNode *p=T,*q=NULL;SqStack s;InitStack(&s);while(p||!StackEmpty(&s)){if(p){q=p;p=p->lChild;free(q);}else{p=Pop(&s);q=p;p=p->rChild;free(q);}}}/******************************************************************** ********************函数名称：Root(BiTreeNode *T)函数功能：返回二叉树的根初始条件：二叉树已经存在函数参数：树根指针********************************************************************* ********************/BiTreeNode* Root(BiTreeNode *T){if(BiTreeEmpty(T)){printf("\n\t\t二叉树为空，无根！");return NULL;}return (T->lChild);}/******************************************************************** ********************函数名称：SaveBiTree(BiTreeNode *T)函数功能：将二叉树写入磁盘初始条件：二叉树已经存在且不为空函数参数：树根指针********************************************************************* ********************/int SaveBiTree(BiTreeNode *T){FILE *out;BiTreeNode *p=T;SqStack s;if((out=fopen("f:\\BiTree.txt","wb"))==NULL){printf("\n\t\t文件打开失败！");return ERROR;}InitStack(&s);while(p||!StackEmpty(&s)){if(p){fwrite(p,sizeof(BiTreeNode),1,out);p=p->lChild;}else{p=Pop(&s);fwrite(p,sizeof(BiTreeNode),1,out);p=p->rChild;}}fclose(out);return OK;}/******************************************************************** ********************函数名称：BiTreeDepth(BiTreeNode *T)函数功能：返回树的深度初始条件：二叉树已经存在且不为空函数参数：树根指针********************************************************************* ********************/int BiTreeDepth(BiTreeNode *T){int depth,ldepth,rdepth;if(BiTreeEmpty(T)){return 0;}ldepth=BiTreeDepth(T->lChild);rdepth=BiTreeDepth(T->rChild);depth=ldepth>rdepth?ldepth:rdepth;depth+=1;return depth;}/******************************************************************** ********************函数名称：Value(BiTreeNode *T,int i)函数功能：返回e的值初始条件：二叉树已经存在且不为空函数参数：树根指针，某结点编号********************************************************************* ********************/Elemtype Value(BiTreeNode *T,int i){BiTreeNode *p=T;SqStack s;InitStack(&s);while(p||!StackEmpty(&s)){if(p){if(p->Node_Num==i)return p->data;else{Push(&s,p);p=p->lChild;}}else{p=Pop(&s);p=p->rChild;}}}/******************************************************************** ********************函数名称：Assign(BiTreeNode *T,int i,Elemtype value)函数功能：将e赋值为value初始条件：二叉树已经存在且不为空函数参数：树根指针，某结点编号，要被赋的值********************************************************************* ********************/int Assign(BiTreeNode *T,int i,Elemtype data){BiTreeNode *p=T;SqStack s;InitStack(&s);while(p||!StackEmpty(&s)){if(p){if(p->Node_Num==i){p->data=data;return OK;}else{Push(&s,p);p=p->lChild;}}else{p=Pop(&s);p=p->rChild;}}}/******************************************************************** ********************函数名称：DeleteChild(BiTreeNode *T,int i,int RL)函数功能：删除结点的孩子结点初始条件：二叉树已经存在且不为空函数参数：树根指针，要被删除孩子的节点的编号，删除标记符********************************************************************* ********************/int DeleteChild(BiTreeNode *T,int i){BiTreeNode *p,*q,*o,*r;SqStack s1,s2,s3;if(BiTreeEmpty(T)){printf("\n\t\t二叉树为空！");return ERROR;}p=T;InitStack(&s1);while(p||!StackEmpty(&s1)){if(p){if(p->Node_Num==i){if(p->lChild){q=p->lChild;InitStack(&s2);while(q||!StackEmpty(&s2)){if(q){Push(&s2,q);q=q->lChild;}else{q=Pop(&s2);printf("\n\t\t%c",q->data);o=q;q=q->rChild;free(o);}}}if(p->rChild){q=p->rChild;InitStack(&s3);while(q||!StackEmpty(&s3)){if(q){Push(&s3,q);q=q->lChild;}else{q=Pop(&s3);printf("\n\t\t%c",q->data);r=q;q=q->rChild;free(r);}}}else{printf("\n\t\t该结点没有孩子结点！\n");}p->lChild=NULL;p->rChild=NULL;return OK;}else{Push(&s1,p);p=p->lChild;}}else{p=Pop(&s1);p=p->rChild;}}return OK;}/******************************************************************** *******************************函数名称：InsertChlid(BiTreeNode *T,int i,int RL,BiTreeNode c)初始条件：二叉树T存在,n为某个结点的编号,LR为0或1,非空二叉树c与T不相交且右子树为空函数功能：根据LR为0或者1,插入c为T中编号为n的结点的左或右子树,编号为n的结点的原有左子树或右子树则为c的右子树初始条件：二叉树已经存在且不为空#函数参数：树根指针，要被插入右子树的节点指针，删除标记符********************************************************************* ******************************/int InsertChlid(BiTreeNode *T,int i,BiTreeNode *c){BiTreeNode *p,*q;SqStack s;if(BiTreeEmpty(T)){printf("\n\t\t二叉树为空！");return NULL;}p=T;InitStack(&s);while(p||!StackEmpty(&s)){if(p){if(p->Node_Num==i){if(!p->rChild)p->rChild=c;else if(!p->lChild)p->lChild=c;else{q=p->lChild;p->lChild=c;c->rChild=q;}}else{Push(&s,p);p=p->lChild;}return OK;}else{p=Pop(&s);p=p->rChild;}}return OK;}/******************************************************************** *******************************函数名称：Parent(BiTreeNode *T,int i)初始条件：二叉树T存在，e是T中某个结点的值函数功能：若e指向的是非根结点，则返回他的父母结点，则返回NULL。