华科数据结构二叉树实验报告

1、课 程 实 验 报 告课程名称： 数据结构 专业班级：计算机科学与技术130*班学 号： * 姓 名： * 指导教师： * 报告日期： 2015.5.13 计算机科学与技术学院目 录实验三 基于二叉链表的二叉树实现4.1 问题描述14.2 系统设计14.3 系统实现14.4 效率分析14实验总结与评价16 实验三 基于二叉链表的二叉树实现4.1 问题描述基于二叉链表，实现常见的，基本的运算。4.2 系统设计4.2.1实现如下功能：1.InitBitree 2.DestroyBitree 3.CreatBiTree 4.ClearBitree 5.BiTreeEmpty 6.BiTreeDept

2、h 7.Value 8.Root 9.Assign 10.Parent 11.Leftchild 12.RightChild 13.LeftSibling 14.RightSibling 15.InsertChild 16.DeleteChild 17.PreOrderTraverse 18.InOrderTraverse 19.PostOrderTraverse20.LevelOrderTraverse4.4.2.系统采用二叉链表存储结构： typedef struct TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针BiTNod

3、e, *BiTree;4.4.3.存储数据类型如下： typedef struct int num; char c;TElemType;4.3 系统实现4.3.1. InitBiTree(BiTree *T)初始条件：二叉树根结点不存在操作结果：为根结点分配一个空间，将根结点数据值置为空字符，代表该树为空树int InitBiTree(BiTree *T) if(*T = (BiTNode*)malloc(sizeof(BiTNode) /分配节点空间 (*T)->data.c = ' '/节点置空 (*T)->lchild = NULL; (*T)->rch

4、ild = NULL; return 1; else return 0;4.3.2. DestroyBiTree(BiTree T)初始条件：二叉树存在操作步骤：递归释放左右子树，最后释放双亲节点操作结果：释放所有二叉树节点int DestroyBiTree(BiTree T) if(!T) return 0; else if(!T->lchild) DestroyBiTree(T->lchild);/递归销毁左子树 if(!T->rchild) DestroyBiTree(T->rchild);/递归销毁右子树 free(T); return 1;4.3.3. Cre

5、ateBiTree(BiTree *T)初始条件：二叉树已被初始化操作步骤：采用递归先序创建二叉树，其中，空节点用操作结果：成功创建二叉树int CreateBiTree(BiTree *T) char ch; getchar(); scanf("%c",&ch); if(ch = '#') *T = NULL; return 0; else if(!(*T = (BiTNode *)malloc(sizeof(BiTNode)exit(0); (*T)->data.c = ch; CreateBiTree(&(*T)->lchi

6、ld);/递归创建左子树 CreateBiTree(&(*T)->rchild);/递归创建右子树 return 1;4.3.4. ClearBiTree(BiTree T)初始条件：二叉树存在操作步骤：使用DestroyBitree函数释放所有节点，然后重新初始化操作结果：二叉树置空int ClearBiTree(BiTree T) DestroyBiTree(T); InitBiTree(&T); /不同于Destroy的是之后又给头结点分配空间置空4.3.5BiTreeEmpty(BiTree T)初始条件：二叉树T存在操作步骤：判断二叉树是否为空操作结果：二叉树为

7、空则返回1，不为空则返回0int BiTreeEmpty(BiTree T) if(T->data.c=' ') return 1; else return 0;4.3.6. BiTreeDepth(BiTree T)初始条件：二叉树存在操作步骤：递归返回树的深度，递归出口为树根结点为空操作结果：返回树的深度int BiTreeDepth(BiTree T) int deep=0; if(T) int lchilddeep=BiTreeDepth(T->lchild); /递归计算左子树深度 int rchilddeep=BiTreeDepth(T->rchi

8、ld); /递归计算右子树深度 deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1; return deep;4.3.7. Root(BiTree T)初始条件：二叉树存在操作步骤：返回根结点BiTNode* Root(BiTree T) if(BiTreeEmpty(T) return NULL; else return T;4.3.8Value(BiTree T,TElemType e) 初始条件：二叉树存在操作步骤：递归查找与传入节点值相等的节点操作结果：若该节点存在，则返回1，若不存在，则返回0int Value(BiTre

9、e T,TElemType e)/返回e的值 if(!T)return 0; if(T->data.c = e.c)return 1; if(Value(T->lchild,e) return 1; /递归查找左子树 if(Value(T->rchild,e) return 1; /递归查找右子树 return 0;4.3.9. Assign(BiTree T, BiTNode *e, TElemType value) 初始条件：二叉树存在，传入一个节点值value ，将其中节点e的值修改为value操作步骤： 判断节点是否在树T中，若在，则修改其数据，为value操作结果：

10、若成功，e值被修改为value，并返回1，否则，修改失败，返回0int Assign(BiTree T, BiTNode *e, TElemType value) if(Value(T,value) (*e).data = value; return 1; else return 0;4.3.10. Parent(BiTree T,TElemType e) 初始条件：二叉树存在，e是其中一个节点 操作步骤： 利用队列，先将根结点入队，在队列不为空的时候，出队，再将判断其左子树和右子树是否有与之相同的，若有，返回节点值，否则，将其左右孩子入队，返回循环，直到查找到该节点，返回该节点值，或者是未查

11、找到返回空。操作结果：返回e的双亲，或者不存在双亲时，返回空字符TElemType Parent(BiTree T,TElemType e) LinkQueue q; QElemType a; if(T) InitQueue(&q); / 初始化队列 EnQueue(&q,T); / 树根入队 BiTNode *p,*r; while(!QueueEmpty(q) /队不空 DeQueue(&q,&a); /出队元素赋值给a p = a->lchild; r = a->rchild; if(a->lchild&&p->da

12、ta.c=e.c|a->rchild&&r->data.c=e.c) /找到e(是其左或右孩子) return a->data; / 返回e的双亲的值 else /没找到e,则入队其左右孩子指针(如果非空) if(a->lchild) EnQueue(&q,a->lchild); if(a->rchild) EnQueue(&q,a->rchild); TElemType s; s.c = ' ' return s; / 树空或没找到e 4.3.12. LeftChild(BiTree T,TElemTy

13、pe e) 初始条件：二叉树存在，e是其中一个节点 操作步骤： 递归调用函数查找左孩子，若存在，返回左孩子数值，若不存在，则返回空字符操作结果：返回e的左孩子，或者返回空字符TElemType LeftChild(BiTree T,TElemType e) TElemType s; s.c = ' ' BiTNode *p; if(T=NULL) return s; if(T->data.c = e.c) p = T->lchild; if(p) return p->data; else return s; else LeftChild(T->lchil

14、d,e); /递归查找左子树 LeftChild(T->rchild,e);/递归查找右子树 return s;4.3.13. RightChild(BiTree T,TElemType e) 初始条件：二叉树存在，e是其中一个节点 操作步骤： 递归调用函数查找右孩子，若存在，返回右孩子数值，若不存在，则返回空字符操作结果：返回e的右孩子，或者返回空字符TElemType RightChild(BiTree T,TElemType e) TElemType s; s.c = ' ' BiTNode *p; if(T=NULL) return s; if(T->dat

15、a.c = e.c) p = T->rchild; if(p) return p->data; else return s; RightChild(T->lchild,e); /递归查找左子树 RightChild(T->rchild,e); /递归查找右子树4.3.14. LeftSibling(BiTree T, TElemType e) 初始条件：二叉树存在，e是其中一个节点 操作步骤： 先查找e的双亲，然后根据双亲判断，其左孩子是否存在，若存在，则返回左孩子，不存在则返回空操作结果：返回e的左兄弟，不存在左兄弟时返回空TElemType LeftSibling(

16、BiTree T, TElemType e) TElemType a; BiTree p; BiTree q,r; TElemType s; s.c = ' ' if(T) a=Parent(T,e); p=Point(T,a); /找到双亲节点 if(p=NULL) return s; q = p->lchild; r = p->rchild; if(p->lchild&&p->rchild&&r->data.c=e.c) / p存在左右孩子且右孩子是e return q->data; /返回p的左孩子(e的

17、左兄弟) return s; / 树空或没找到e的左兄弟 4.3.15. RightSibling(BiTree T, TElemType e) 初始条件：二叉树存在，e是其中一个节点 操作步骤： 先查找e的双亲，然后根据双亲判断，其右孩子是否存在，若存在，则返回右孩子，不存在则返回空操作结果：返回e的左右兄弟，不存在右兄弟时返回空TElemType RightSibling(BiTree T, TElemType e) TElemType a; BiTree p; BiTree q,r; TElemType s; s.c = ' ' if(T) /非空树 a=Parent(T

18、,e); / a为e的双亲 p=Point(T,a); / p为指向结点a的指针 if(p=NULL) return s; q = p->lchild; r = p->rchild; if(p->lchild&&p->rchild&&q->data.c=e.c) /p存在左孩子且右孩子是e return r->data; / 返回p的左孩子(e的左兄弟) return s; /树空或没找到e的左兄弟 4.3.16. InsertChild(BiTree T,TElemType p,int LR,BiTree C)初始条件：二叉

19、树存在，p指向某个节点，LR为0或1，非空二叉树c与T不相交且右子树为空 操作步骤：当树C右子树为空时，根据LR，其值为0，将C插为左子树，当LR为1时，将C插为右子树，将断开部分连接为C的右子树。 操作结果：将C根据LR的值连接为T的子树int InsertChild(BiTree T,TElemType p,int LR,BiTree C) BiTNode *t,*c,*m,*n; t = T; c = C; if(t = NULL|c = NULL)return 0; if(c->rchild != NULL) printf("二叉树C含有右子树！n"); /判

20、断C是否含有右子树 return 0; m = Point(t,p); /找到p所在节点 if(LR) n = m->rchild; m->rchild = c; c->rchild = n; /插入为右子树 else n = m->lchild; m->lchild = c; c->rchild = n; /插入为左子树 return 1;4.3.17. DeleteChild(BiTree T,TElemType p,int LR) 初始条件：二叉树T存在 操作步骤：当p指向的节点存在时，根据LR的值删除其左子树，或右子树操作结果：根据LR的值，删除以p

21、为根节点的子树int DeleteChild(BiTree T,TElemType p,int LR) BiTNode *q; q = T; if(q = NULL)return 0; q = Point(q,p); /找到p指向的节点 if(LR) q->rchild = NULL; /删除右子树 else q->lchild = NULL; /删除左子树 return 1;4.3.18. PreOrderTraverse(BiTree T, int (*visit)(TElemType e) 初始条件：二叉树存在 操作步骤： 利用传入的visit函数进行显示递归进行遍历，先遍历

22、根节点，然后遍历左子树，然后遍历右子树操作结果：先序遍历整个二叉树int PreOrderTraverse(BiTree T, int (*visit)(TElemType e)if(T) visit(T->data); PreOrderTraverse(T->lchild,visit); PreOrderTraverse(T->rchild,visit); 4.3.19. InOrderTraverse(BiTree T,int (*visit)(TElemType e) 初始条件：二叉树T存在 操作步骤：利用传入的visit函数进行显示递归进行遍历，先遍历左子树，然后遍历

23、根节点，然后遍历右子树操作结果：中序遍历整个二叉树int InOrderTraverse(BiTree T,int (*visit)(TElemType e)if(T)InOrderTraverse(T->lchild,visit);/遍历左子树visit(T->data);/输出根节点值InOrderTraverse(T->rchild,visit);/遍历右子树4.3.20. PostOrderTraverse(BiTree T,int (*visit)(TElemType e) 初始条件：二叉树T存在操作步骤：利用传入的visit函数进行显示，递归进行遍历，先遍历左子树

24、，然后遍历右子树，然后遍历根节点操作结果：后序遍历二叉树int PostOrderTraverse(BiTree T,int (*visit)(TElemType e) if(T)PostOrderTraverse(T->lchild,visit);/遍历左子树PostOrderTraverse(T->rchild,visit);/遍历右子树visit(T->data);/输出根节点值4.3.21. LevelTraverse(BiTree T,int (*visit)(TElemType e) 初始条件： 二叉树存在操作步骤： 利用队列，先将根节点入队，然后队列顺序出队，出

25、队元素的左右子树存在时，将他们入队，之后对该元素调用visit函数，直到队列为空操作结果：按层遍历整个二叉树int LevelTraverse(BiTree T,int (*visit)(TElemType e) BiTNode *p; LinkQueue Q; InitQueue(&Q); p = T; if(p) EnQueue(&Q,p); while(!QueueEmpty(Q) DeQueue(&Q,&p); if(p->lchild)EnQueue(&Q,p->lchild); if(p->rchild)EnQueue(&a

26、mp;Q,p->rchild); if(!visit(p->data) return 0; return 1;4.3.22. Save(BiTree T,FILE *pf) 初始条件： 二叉树存在操作步骤： 递归进行保存，先序保存，节点为空时，保存节点值为“#”操作结果：保存整个二叉树到指定文件int Save(BiTree T,FILE *pf) char c = '#' if(T = NULL) fwrite(&c, sizeof(char), 1, pf); else fwrite(&(T->data.c), sizeof(char),

27、1, pf); Save(T->lchild, pf); Save(T->rchild, pf); return 1;4.3.23. Load(BiTree *T, FILE *pf) 初始条件： 初始化过二叉树操作步骤： 递归进行读取，先序创建二叉树，过程类似与CreatBitree操作结果：将文件中的二叉树恢复到系统中int Load(BiTree *T, FILE *pf) char c; fread(&c, sizeof(char), 1, pf); if(c = '#') *T = NULL; else *T = (BiTree )malloc(s

28、izeof(BiTNode); (*T)->data.c = c; Load(&(*T)->lchild), pf); Load(&(*T)->rchild), pf); return 1;4.4 效率分析4.4.1. InitBiTree(BiTree *T) 效率分析：执行常数运算，时间复杂度为O(1)4.4.2. DestroyBiTree(BiTree T)效率分析：递归释放二叉树节点，对每一个节点操作一次，时间复杂度为O(n)4.4.3. CreateBiTree(BiTree *T)效率分析：递归建立二叉树，对每一个节点操作一次，时间复杂度为O(n

29、)4.4.4. ClearBiTree(BiTree T)效率分析：算法与Destroy相同，为O(n)4.4.5BiTreeEmpty(BiTree T)效率分析：执行常数运算，时间复杂度为O(1)4.4.6. BiTreeDepth(BiTree T)效率分析：执行常数运算，时间复杂度为O(1)4.4.7. Root(BiTree T)效率分析：执行常数运算，时间复杂度为O(1)4.4.8Value(BiTree T,TElemType e) 效率分析：递归查找二叉树，对每一个节点操作一次，时间复杂度为O(n)4.4.9. Assign(BiTree T, BiTNode *e, TElemType value) 效率分析：基础为Value，时间复杂度为O(n)4.4.10. Parent(BiTree T,T