2014广工数据结构实验报告二叉树.doc

数据结构设计性实验报告 课程名称_数据结构实验 _ 题目名称 二叉树 学生学院_ 计算机学院_ 专业班级_ _学 号_ _学生姓名_ _指导教师_ 黄剑锋 _2015年 7月 7日1.题目 采用二叉链表存储结构实现二叉链表的基本接口。基本操作：创建一棵空二叉树：void InitBiTree(BiTree &T);创建一棵二叉树T，其中根结点的值为e，LR分别为左右子树：BiTree MakeBiTree(TElemType e,BiTree L,BiTree R);销毁二叉树：void DestroyBiTree(BiTree &T);二叉树判空。若为空返回TRUE，否则FALSE：Status BiTreeEmpty(BiTree T);将一棵二叉树T分解成根，左子树和右子树三个部分：Status BreakBiTree(BiTree &T,BiTree &L,BiTree &R);替换左子树。若T非空，则用LT替换T的左子树，并用LT返回T的原有子树：Status ReplaceLeft(BiTree &T,BiTree <);替换右子树。若T非空，则用RT替换T的右子树，并用RT返回T的原有子树：Status ReplaceRight(BiTree &T,BiTree &RT);剪除左子树。若T非空，则剪除T的左子树，并用LT返回：Status CutLeft(BiTree &T,BiTree <);剪除右子树。若T非空，则剪除T的右子树，并用RT返回：Status CutRight(BiTree &T,BiTree &RT);显示树T：Status Display(BiTree T);2.存储结构定义 #include#define ERROR 0#define OK 1#define TRUE 1#define FALSE 0 链式储存结构：typedef int Status;typedef char TElemType;typedef struct BiTNodeTElemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;3.算法设计void InitBiTree(BiTree &T) T=NULL;BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)BiTree t; t=(BiTree)malloc(sizeof(BiTNode); if(NULL=t)return NULL; t-data=e; t-lchild=L; t-rchild=R; return t;void DestroyBiTree(BiTree &T)if(T) DestroyBiTree(T-lchild); DestroyBiTree(T-rchild); free(T); Status BiTreeEmpty(BiTree T)if(T=NULL)return TRUE; else return FALSE;Status BreakBiTree(BiTree &T,BiTree &L,BiTree &R)if(T) L=T-lchild; R=T-rchild; T-lchild=NULL; T-rchild=NULL; return OK; else return ERROR;Status ReplaceLeft(BiTree &T,BiTree <)BiTree temp; if(NULL=T)return ERROR; temp=T-lchild; T-lchild=LT; LT=temp; return OK; Status ReplaceRight(BiTree &T,BiTree &RT)BiTree temp; if(NULL=T)return ERROR; temp=T-rchild; T-rchild=RT; RT=temp; return OK; Status CutLeft(BiTree &T,BiTree <)if(NULL=T)LT=NULL;return ERROR; LT=T-lchild; T-lchild=NULL; return OK;Status CutRight(BiTree &T,BiTree &RT)if(NULL=T)RT=NULL;return ERROR; RT=T-rchild; T-rchild=NULL; return OK;Status Display(BiTree T)if(T=NULL)printf(#);return ERROR; else printf(%c,T-data); printf(); Display(T-lchild); printf(,); Display(T-rchild); printf(); return OK; 4.测试 void main()int i; TElemType e; BiTree T,L,R,A,B,C,D,E,F,G; InitBiTree(T); e=D; D=MakeBiTree(e,NULL,NULL); e=E; E=MakeBiTree(e,NULL,NULL); e=B; B=MakeBiTree(e,D,E); e=F; F=MakeBiTree(e,NULL,NULL); e=G; G=MakeBiTree(e,NULL,NULL); e=C; C=MakeBiTree(e,F,G); e=A; A=MakeBiTree(e,B,C); T=A; printf(T的序列n); Display(T); printf(n判空n); i=BiTreeEmpty(T); if(i)printf(是n); else printf(否n); printf(n执行剪除T左右子树，用LR返回n); CutLeft(T,L); CutRight(T,R); printf(T的序列n); Display(T); printf(nL的序列n); Display(L); printf(nR的序列n); Display(R); printf(n执行替换，用LR替换T左右子树n); ReplaceLeft(T,L); ReplaceRight(T,R); printf(T的序列n); Display(T); printf(nL的序列n); Display(L); printf(nR的序列n); Display(R); printf(n分解操作，左右分到LRn); BreakBiTree(T,L,R); printf(T的序列n); Display(T); printf(nL的序列n); Display(L); printf(nR的序列n); Display(R); printf(n销毁Tn); DestroyBiTree(T); printf(T的序列n); Display(T); printf(n判空n); i=BiTree