二叉树数据类型.doc

数据结构课程设计报告题目: 二叉树抽象数据结构 学 院 _计算机学院 专 业 _ _年级班别 _ _ _ 学 号 _ 学生姓名 _ _指导教师 _ _ _ 成 绩 _2009 年 6 月 一、题目采用字符类型为元素信息，用顺序存储结构和链式存储结构，实现二叉树抽象数据类型。ADT BiTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空二叉树；若D仅含一个数据元素，则R为空集，否则R = H, H是如下二元关系：（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2） 若D root ，则存在D root 的一个划分Dl Dr ，DlDr =;（3） 若Dl ,则Dl 中存在惟一的数据元素xl ， H，且存在Dl 上的关系Hl H；若Dr ,则Dr 中存在惟一的数据元素xr ， H，且存在Dr 上的关系Hr H；（4） （Dl， Hl、）是一棵符合本定义的二叉树，称为根root的左子树；（Dr， Hr、）是一棵符合本定义的二叉树，称为根root的右子树。基本操作P：InitBitree(&T);操作结果：构造空二叉树。CreateBitree(&T);初始条件：二叉树存在。操作结果：按输入格式构造二叉树。DestroyBitree(&T);初始条件：二叉树存在。操作结果：销毁二叉树T。ClearBitree(&T);初始条件：二叉树存在。操作结果：将二叉树T清为空树。BitreeEmpty(T);初始条件：二叉树存在。操作结果：若T为空二叉树，则返回TURE，否则FALSE。BitreeDepth(T);初始条件：二叉树存在。操作结果：返回T的深度。Root(T);初始条件：二叉树存在。操作结果：返回T的根。Value(T, e);初始条件：二叉树存在，e是T中某个结点。操作结果：返回结点e的值。Assign(&T, &e, value);初始条件：二叉树存在，e是T中某个结点。操作结果：结点e赋值为value 。Parent(T, e);初始条件：二叉树存在，e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。LeftChild(T, e);初始条件：二叉树存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild(T, e);初始条件：二叉树存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。PreOrder(T);初始条件：二叉树存在。操作结果：先序遍历T，按顺序输出每个结点。InOrder(T);初始条件：二叉树存在。操作结果：中序遍历T，按顺序输出每个结点。PostOrder(T);初始条件：二叉树存在。操作结果：后序遍历T，按顺序输出每个结点。LevelOrder(T);初始条件：二叉树存在。操作结果：按层遍历T，按顺序输出每个结点。 ADT BiTree二、存储结构定义公用头文件dso.h：#include #include #include /字符串操作#include /数学#include /内存操作文件#include /系统时间#include /队列using namespace std;#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define MAXLEN 30 #define ElemType char#define Status int(1)顺序存储结构 #define MAX_SIZE 100 typedef ElemType SqBitreeMAX_SIZE;(2)链式存储结构 typedef struct BiTNode ElemType data; struct BiTNode *lchild, * rchild;BiTNode, * Bitree;三、算法设计（1）顺序存储结构Status InitBitree(SqBitree &T)/构造空二叉树。 /置为空树 memset(T, 0, sizeof(T); T0 = ; T1 = #; return OK; Status CreateBitree(SqBitree &T)/按输入顺序构造二叉树。 /按照完全二叉树的层次先左后右顺序输入，#代表空树 / （例如 a,b,c,d,#,f ） int i; ElemType c; scanf(%*c); for(i = 1; i MAX_SIZE; i+) scanf(%c,&c); if(c = ,) i-; continue; if(c = n) break; Ti = c; if(c != #) T2*i = #; T2*i + 1 = #; return OK;Status DestroyBitree(SqBitree &T)/销毁二叉树T if(T) free(T); /释放T的存储空间 return OK; else return ERROR; /T不存在，返回ERROR Status ClearBitree(SqBitree &T)/将二叉树T清为空树。 if(T) InitBitree(T); else return ERROR; /T不存在，返回ERROR Status BitreeEmpty(SqBitree T)/若T为空二叉树，则返回TURE，否则FALSE。 return (T1 = # ? TURE: FALSE); int BitreeDepth(SqBitree T)/返回T的深度。 int i; int len = strlen(T) - 1; /求 log2(len) for(i = 0; ; i+) len = len/2; if(len = 0) break; return i;ElemType * Root(SqBitree T)/返回T的根。 if(T1 = #) return NULL; else return &T1; ElemType Value(SqBitree T, int e)/返回结点e的值。 return Te;Status Assign(SqBitree &T, int &e, ElemType value)/结点e赋值为value 。 if(Te = #) Te = value; T2*e = #; T2*e + 1 = #; else Te = value; return OK; ElemType * Parent(SqBitree T, int e)/若e是T的非根结点，则返回它的双亲，否则返回空。 if(e data = c; if(si = () i+; CreateBitree(T-lchild, s, i); i+; CreateBitree(T-rchild, s, i); i+; else T-lchild = NULL; T-rchild = NULL; return OK; Status DestroyBitree(Bitree &T)/销毁二叉树T if(T-lchild) DestroyBitree(T-lchild); if(T-rchild) DestroyBitree(T-rchild); if(T) free(T); /释放T的存储空间 return OK; else return ERROR; /T不存在，返回ERROR Status ClearBitree(Bitree &T)/将二叉树T清为空树。 if(T) DestroyBitree(T); /销毁T InitBitree(T); return OK; else return ERROR; /T不存在，返回ERROR Status BitreeEmpty(Bitree T)/若T为空二叉树，则返回TURE，否则FALSE。 return T = NULL; int BitreeDepth(Bitree T)/返回T的深度。 int hl, hr; if(!T) return 0; hl = BitreeDepth(T-lchild); hr = BitreeDepth(T-rchild); if(hl hr) return +hl; else return +hr;BiTNode * Root(Bitree T)/返回T的根。 return T;int c;BiTNode * PreOrder(Bitree T, int k)/返回先序遍历中第k个结点。 BiTNode * ans = NULL; if(T) c+; if(c = k) return T; else ans = PreOrder(T-lchild, k); if(ans != NULL) return ans; ans = PreOrder(T-rchild, k); if(ans != NULL) return ans; return NULL; ElemType Value(Bitree T, int e)/返回结点e的值。 BiTNode * p; c = 0; p = PreOrder(T,e); /返回先序遍历中第k个结点。 if(!p) return #; /如果为空，则返回# else return p-data;Status Assign(Bitree T, int e, ElemType value)/结点e赋值为value 。 BiTNode * p; c = 0; p = PreOrder(T,e); /返回先序遍历中第k个结点。 if(c e) return ERROR; if(!p) p = (BiTNode *)malloc(sizeof(BiTNode); p-data = value; p-lchild = NULL; p-rchild = NULL; else p-data = value; return OK; BiTNode * Par(Bitree T, BiTNode * k)/找结点k的双亲结点 BiTNode * p = NULL; if(T) if(T-lchild = k | T-rchild = k) return T; else p = Par(T-lchild, k); if(p) return p; p = Par(T-rchild, k); if(p) return p; return NULL; BiTNode * Parent(Bitree T, int e)/若e是T的非根结点，则返回它的双亲，否则返回空。 BiTNode * p, * parent; c = 0; p = PreOrder(T,e); parent = Par(T, p); return parent; /如果为空，则返回# BiTNode * LeftChild(Bitree T, int e)/返回e的左孩子。若e无左孩子，则返回空。 BiTNode * p; c = 0; p = PreOrder(T,e); if(!p) return NULL; else return p-lchild; BiTNode * RightChild(Bitree T, int e)/返回e的左孩子。若e无左孩子，则返回空。 BiTNode * p; c = 0; p = PreOrder(T,e); if(!p) return NULL; else return p-rchild; void PreOrder(Bitree T)/按先序遍历的顺序输出每个结点。 if(T) printf(%c,T-data); PreOrder(T-lchild); PreOrder(T-rchild); return ;void InOrder(Bitree T)/按中序遍历的顺序输出每个结点。 if(T) PreOrder(T-lchild); printf(%c,T-data); PreOrder(T-rchild); return ;void PostOrder(Bitree T)/按后序遍历的顺序输出每个结点。 if(T) PreOrder(T-lchild); PreOrder(T-rchild); printf(%c,T-data); return ;void LevelOrder(Bitree T)/按层遍历的顺序输出每个结点。 BiTNode * p; queue q ; /用stl库里面的队列 q.push(T); while(! q.empty() p = q.front(); q.pop(); printf(%c, p-data); if(p-lchild) q.push(p-lchild); if(p-rchild) q.push(p-rchild); return ;void Dprint(Bitree T)/输出二叉树 if(T) printf(%c, T-data); if(T-lchild != NULL | T-rchild != NULL) printf(); if(T-lchild = NULL) printf(#); else Dprint(T-lchild); printf(,); if(T-rchild = NULL) printf(#); else Dprint(T-rchild); printf(); return ;四、测试(1)顺序存储结构 int main() SqBitree t; ElemType *p, value; int cas, e; time_t timep; struct tm * ti; while(1) time(&timep); ti = localtime(&timep); system(cls); printf(-n); printf(| 1、构造空二叉树 |n); printf(| 2、按层输入构造二叉树 |n); printf(| 3、销毁二叉树 |n); printf(| 4、清空二叉树 |n); printf(| 5、二叉树是否为空 |n); printf(| 6、二叉树的深度 |n); printf(| 7、二叉树的根 |n); printf(| 8、(输入)e结点的值 |n); printf(| 9、结点e赋值为value |n); printf(| 10、结点e的双亲 |n); printf(| 11、结点e的左孩子 |n); printf(| 12、结点e的右孩子 |n); printf(| 0、退出 |n); printf(-n); printf( 当前系统时间：%d:%d:%dn,ti-tm_hour, ti-tm_min, ti-tm_sec); printf( 作者：蔡超凡 n); printf(-n); printf(请选择操作：); scanf(%d, &cas); switch(cas) case 1: system(cls); InitBitree(t); printf(构造成功，); system(pause); break; case 2: system(cls); printf(请按层(格式为：a,b,c,d,#,f)输入：n); CreateBitree(t); printf(构造成功，现在的二叉树为：%sn,t); system(pause); break; case 3: system(cls); DestroyBitree(t); printf(销毁成功,); system(pause); break; case 4: system(cls); ClearBitree(t); printf(清空成功，); system(pause); break; case 5: system(cls); if(BitreeEmpty(t) printf(现在二叉树为空n); else printf(现在二叉树不为空n); system(pause); break; case 6: system(cls); printf(二叉树为：%sn,t); printf(现在二叉树深度为：%dn,BitreeDepth(t); system(pause); break; case 7: system(cls); p = Root(t); printf(二叉树为：%sn,t); printf(现在二叉树的根为：%cn,*p); system(pause); break; case 8: system(cls); printf(二叉树为：%sn,t); printf(请输入结点e的序号:); scanf(%d, &e); printf(结点e的值为: %cn,Value(t, e); system(pause); break; case 9: system(cls); printf(二叉树为：%sn,t); printf(请输入结点e的序号:); scanf(%d, &e); printf(请输入要赋给结点e的值:); scanf(%*c%c, &value); Assign(t, e, value); printf(赋值成功，现在的二叉树为：%sn,t); system(pause); break; case 10: system(cls); printf(二叉树为：%sn,t); printf(请输入结点e的序号:); scanf(%d, &e); p = Parent(t, e); if(!p) printf(结点e没有双亲n); else printf(结点e的双亲为：%cn,*p); system(pause); break; case 11: system(cls); printf(二叉树为：%sn,t); printf(请输入结点e的序号:); scanf(%d, &e); p = LeftChild(t, e); if(!p) printf(结点e没有左孩子n); else printf(结点e的左孩子为：%cn,*p); system(pause); break; case 12: system(cls); printf(二叉树为：%sn,t); printf(请输入结点e的序号:); scanf(%d, &e); p = RightChild(t, e); if(!p) printf(结点e没有右孩子n); else printf(结点e的右孩子为：%cn,*p); system(pause); break; default: return 0; return 0;(2)链式存储结构 int main() Bitree t; ElemType value, s200; BiTNode * p; int cas, e, i; time_t timep; struct tm * ti; while(1) time(&timep); ti = localtime(&timep); system(cls); printf(-n); printf(| 1、构造空二叉树 |n); printf(| 2、按层输入构造二叉树 |n); printf(| 3、销毁二叉树 |n); printf(| 4、清空二叉树 |n); printf(| 5、二叉树是否为空 |n); printf(| 6、二叉树的深度 |n); printf(| 7、二叉树的根 |n); printf(| 8、e结点(先序)的值 |n); printf(| 9、结点e赋值为value |n); printf(| 10、结点e(先序)的双亲 |n); printf(| 11、结点e(先序)的左孩子 |n); printf(| 12、结点e(先序)的右孩子 |n); printf(| 13、先序遍历 |n); printf(| 14、中序遍历 |n); printf(| 15、后序遍历 |n); printf(| 16、按层遍历 |n); printf(| 0、退出 |n); printf(-n); printf( 当前系统时间：%d:%d:%dn,ti-tm_hour, ti-tm_min, ti-tm_sec); printf( 作者：蔡超凡 n); printf(-n); printf(请选择操作：); scanf(%d, &cas); switch(cas) case 1: system(cls); InitBitree(t); printf(构造成功，); system(pause); break; case 2: system(cls); printf(请用完全二叉树(格式为：a(b(d(h,i),#),c(f,#) )输入：n); scanf(%*c%s, s); i = 0; CreateBitree(t, s, i); printf(构造成功，现在的二叉树为：); Dprint(t); printf(n); system(pause); break; case 3: system(cls); DestroyBitree(t); printf(销毁成功,); system(pause); break; case 4: system(cls); ClearBitree(t); printf(清空成功，); system(pause); break; case 5: system(cls); if(BitreeEmpty(t) printf(现在二叉树为空n); else printf(现在二叉树不为空n); system(pause); break; case 6: system(cls); printf(二叉树为：); Dprint(t); printf(n); printf(现在二叉树深度为：%dn,BitreeDepth(t); system(pause