二叉树实验报告

1、*实践教学* *学院计算机信息与科学学院2010年春季学期算法与数据结构课程设计题 目： 二叉排序树的实现 专业班级： * 姓 名： * 学 号： * 指导教师： * 成 绩：_目 录摘 要2前 言2正 文31. 问题描述32. 任务与分析33. 整体程序设计34 程序编码45. 程序的测试和演示16设计总结17参考文献18附录程序代码18摘 要该设计要求学生设计程序，实现二叉排序树的相关操作。通过该题目的设计过程，可以加深理解二叉树、查找表的逻辑结构、存储结构，掌握二叉排序树上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能

2、力。使用二叉链表存储二叉排序树，生成一棵二叉排序树，并掌握二叉树正确查找，插入，删除一个给定值的方法。关键词：二叉排序树，二叉链表，查寻，删除，遍历，输出结果前 言 问题的背景二叉树是树型结构的一个重要类型，关于二叉树的存储结构及算法都较为简单，因此，二叉树在数据结构的研究领域中具有很重要的地位。问题的意义 掌握二叉树的概念，二叉树的性质，存储结构以及基本运算，并用二叉树解决一些综合应用问题。正 文1. 问题描述操作1 ：用顺序和二叉链表作存储结构设置一个字符作为输入结束标志,输入数列L，生成一棵二叉排序树T；对二叉排序树T作中序遍历，输出结果。操作2：输入元素x,查找二叉排序树T,若存在含x

3、的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；2.任务与分析1、查阅文献资料，一般在3篇以上；2、建立数据的逻辑结构和物理结构；3、完成相应算法的设计；4、完成测试工作；5、撰写设计说明书；6、做好答辩工作。任务是一个二叉排序树的实现问题，根据任一数列生成一棵二叉排序树；查询结点并删除结点且保证仍为二叉排序树。根据二叉排序树的概念，查找当前插入的元素的位置；删除结点如果不是叶子结点，要注意考虑如何使树仍为二叉排序树；当删除结点为根结点时，考虑如何保证二叉树照常输出。3.整体程序设计方案此课题是研究二叉排序树的实现，建立二叉树；查找一个数是否存在；插入一个给定的值；删除

4、一个给定的值并输出结果。为了直观和方便，画出流程图如下图1：主程序模块创建一个菜单建立一个二叉树查找字符是否存在删除查到的结点遍历输出结果 图-1 4.程序编码4.1主程序程序执行时需要的头文件及程序中运用到的结构体。#include<malloc.h>#include<stdio.h>#include<string.h>#include<iostream.h>#include<windows.h>#define maxsize 50typedef struct node2char data; /数据域struct node2 *lc

5、hild,*rchild,*parent; /左指针域，右指针域btnode;/二叉链接点类型typedef struct stack btnode* datamaxsize; int top;seqstack; /建立一个栈 以便非递归使用4.2 建立一个二叉排序树以先序形式构建一个二叉树，使产生的结点有3个指针域，左、右孩子及父结点，以空格结束（结点为空）。btnode *createbitree(btnode *&t) /先序产生二叉树 char ch; scanf("%c",&ch); if(ch=' ') t=NULL; else

6、t=(btnode*)malloc(sizeof(btnode); t->data=ch;t->parent=NULL; t->lchild=createbitree(t->lchild); if(t->lchild) t->lchild->parent=t;t->rchild=createbitree(t->rchild);if(t->rchild) t->rchild->parent=t; return t;4.3 在一个二叉排序树查找一个数是否存在对输入的字符x进行查找，当x存在时返回该结点，否则返回空。btnode

7、 *searchnode(btnode *b,char x) /查找结点btnode *p;if(b=NULL)return NULL; /空二叉树的查找失败出口else if(b->data=x)return b; /查找成功出口elsep=searchnode(b->lchild,x); /在左子树查找if(p!=NULL)return p;else return searchnode(b->rchild,x); /在右子树查找4.5 删除结点对结点进行删除，有以下5种情况：根结点、叶子结点、有右无左、有左无右、有左有右，当结点删除后不改变输出二叉树的顺序。btnode*

8、 deltree(btnode *t,char x) btnode *q; if(t->lchild=NULL&&t->rchild=NULL) /删除结点为叶子结点if(t->parent=NULL) /删除结点为根结点 q=t; q=NULL;else if(t->parent->lchild->data=x)q=t->parent->lchild;t->parent->lchild=NULL;elseq=t->parent->rchild;t->parent->rchild=NULL;fr

9、ee(t);else if(t->lchild=NULL&&t->rchild!=NULL) /删除结点无左孩子，将右孩子上提，代替该结点 if(t->parent=NULL) /删除结点为根结点 q=t->rchild; while(q->lchild!=NULL) / 以先序方式遍历到最后一个左孩子 q=q->lchild; q->parent->lchild=NULL; q->rchild=t->rchild; t->rchild->parent=q; q->parent=NULL;else i

10、f (t->parent->lchild->data=x)t->parent->lchild=t->rchild;t->rchild->parent=t->parent;else t->parent->rchild=t->rchild;t->rchild->parent=t->parent;free(t);else if(t->lchild!=NULL&&t->rchild=NULL) /删除结点无右孩子，将左孩子上提，代替该结点if(t->parent=NULL) /删

11、除结点为根结点 q=t->lchild; q->parent=NULL;else if(t->parent->lchild->data=x)t->parent->lchild=t->lchild;t->lchild->parent=t->parent;else t->parent->rchild=t->lchild;t->lchild->parent=t->parent;free(t);else /删除结点既有 左孩子又有右孩子 if(t->parent=NULL) /删除结点为根结点

12、q=t->rchild; while(q->lchild!=NULL) / 以先序方式遍历到最后一个左孩子 q=q->lchild; q->parent->lchild=NULL; q->lchild=t->lchild; q->rchild=t->rchild; t->rchild->parent=q; t->lchild->parent=q; q->parent=NULL;else if(t->parent->lchild->data=x|t->parent->rchild-&

13、gt;data=x)/ 直接指向 删除结点的右孩子q=t->rchild;while(q->lchild!=NULL) / 以先序方式遍历到最后一个左孩子 q=q->lchild; q->parent->lchild=NULL; /当将q结点提出时，则应该其原来的储存位置置空 / 用q代替要删除结点， 保证以中序输出的结点顺序不变 if(t->parent->lchild->data=x) q->lchild=t->lchild; q->rchild=t->rchild; t->lchild->parent=q

14、; t->rchild->parent=q; t->parent->lchild=q; q->parent=t->parent; else q->lchild=t->lchild; q->rchild=t->rchild; t->lchild->parent=q; t->rchild->parent=q; t->parent->rchild=q; q->parent=t->parent; free(t); return q;4.5 进行遍历void preorder(btnode *bt

15、) /递归 先序 遍历 if(bt!=NULL)printf("%c",bt->data);preorder(bt->lchild);preorder(bt->rchild);void preorder2(btnode* bt) /非递归 先序遍历 btnode* p;seqstack ps;ps.top=-1;if(bt=NULL)return;elseps.top+;ps.dataps.top=bt;while(ps.top!=-1)p=ps.dataps.top;ps.top-;printf("%c",p->data);if

16、(p->rchild!=NULL)ps.top+;ps.dataps.top=p->rchild;if(p->lchild!=NULL)ps.top+;ps.dataps.top=p->lchild;void inorder(btnode *p) / 递归中序遍历if(p!=NULL) inorder(p->lchild); printf("%c",p->data); inorder(p->rchild);void inorder2(btnode *bt) /非递归中序遍历btnode *p,*q;seqstack ps;ps.to

17、p=-1;if(bt=NULL)return;elsewhile(bt!=NULL)ps.top+;ps.dataps.top=bt;bt=bt->lchild;while(ps.top!=-1)p=ps.dataps.top;ps.top-;printf("%c",p->data);while(p->rchild!=NULL)ps.top+;ps.dataps.top=p->rchild;q=p->rchild;while(q->lchild!=NULL)ps.top+;ps.dataps.top=q->lchild;q=q-&g

18、t;lchild;break; void postorder(btnode *bt) /递归后序遍历if(bt!=NULL)postorder(bt->lchild);postorder(bt->rchild);printf("%c",bt->data);void postorder2(btnode* bt) /非递归后序遍历seqstack ps; ps.top=-1; btnode* t; int flag; dowhile (bt!=NULL)ps.top+;ps.dataps.top=bt;bt=bt->lchild; t=NULL;flag

19、=1;while (ps.top!=-1 && flag)bt=ps.dataps.top;if(bt->rchild=t) /t：表示为null，或者右子节点被访问过了。printf("%c ",bt->data);ps.top-;t=bt; /t记录下刚刚访问的节点elsebt=bt->rchild;flag=0; while (ps.top!=-1);4.6 创建菜单void output1() int i;for(i=0;i<23;i+)printf(" ");for(i=0;i<32;i+)prin

20、tf("*");printf("n");void mainpp()int i;output1();for(i=0;i<23;i+)printf(" ");printf("* "); printf("1.先 序 建 立 二 叉 树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");print

21、f("* "); printf("2.非递归先序遍历二叉树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* "); printf("3.非递归中序遍历二叉树");for(i=0;i<4;i+)printf(" ");printf("*");prin

22、tf("n");for(i=0;i<23;i+)printf(" ");printf("* "); printf("4.非递归后序遍历二叉树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* ");printf("5.递归先序 遍历 二叉树");fo

23、r(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* ");printf("6.递归中序 遍历 二叉树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" &qu

24、ot;);printf("* ");printf("7.递归后序 遍历 二叉树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* ");printf("8.查 找 并 删 除 结 点");for(i=0;i<4;i+)printf(" ");printf("*

25、");printf("n");for(i=0;i<23;i+)printf(" ");printf("* ");printf("9.输出删除结点的二叉树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* ");printf("10.以嵌套形式输出二叉

26、树");for(i=0;i<3;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* ");printf("0.退 出");for(i=0;i<5;i+)printf(" ");printf("*");printf("n");output1();4.7主函数void main() syste

27、m("color 0B"); mainpp(); btnode *root,*t; char x; int w,k=1; while(k) printf("请选择0-9："); scanf("%d",&w); getchar(); switch(w) case 0: return; case 1: printf("先 序 建 立 二 叉 树: "); createbitree(root); getchar(); break; case 2: printf("非递归先序遍历二叉树: ");

28、 preorder2(root); break; case 3: printf("非递归中序遍历二叉树: "); inorder2(root); break; case 4: printf("非递归后序遍历二叉树: "); postorder(root); break; case 5: printf("递归先序遍历二叉树: "); preorder(root); break; case 6: printf("递归中序遍历二叉树: "); inorder(root); break; case 7: printf(&q

29、uot;递归后序遍历二叉树: "); postorder(root); break; case 8: printf("输入字符x："); scanf("%c",&x); getchar(); t=searchnode(root,x); if(t) if(t=root) root=deltree(t,x); else deltree(t,x); printf("删除结点成功!n"); else printf("无x!n"); break; case 9: printf("中序输出删除后二叉

30、树的各结点:n"); inorder(root); break; case 10: printf("嵌套形式输出二叉树："); dispbitree(root); default: return; printf("n继续运行吗y(1)/n(0): "); scanf("%d",&k); getchar(); if(!k) return; 5 程序测试与演示： 测试数据：a + b * c - d -e/f。测试结果下如图： 设 计 总 结通过这次课程设计的程序实践，我实在获益匪浅！数据结构是这个学期开展的一门学科，学

31、习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。但是通过努力，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次课程设计的核心算法，并使其能够正常的运行。这次的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到

32、应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中的辛苦，很难用言语表达出来。今后，我会更加努力的学习专业知识，努力提高自我的能力。 参考文献1. 谭浩强.c语言程序设计. 清华大学出版社. 2. 陈建新、李志敏。数据结构（实验指导与课程设计教程）附录 程序代码#include<malloc.h>#include<stdio.h>#include<string.h>#include<iostream.h>#include<windows.h>#define ma

33、xsize 50typedef struct node2char data; /数据域struct node2 *lchild,*rchild,*parent; /左指针域，右指针域btnode;/二叉链接点类型typedef struct stack /建立一个栈 btnode* datamaxsize; int top;seqstack;btnode *createbitree(btnode *&t) /先序产生二叉树 char ch; scanf("%c",&ch); if(ch=' ') t=NULL; else t=(btnode*

34、)malloc(sizeof(btnode); t->data=ch; t->parent=NULL; t->lchild=createbitree(t->lchild); if(t->lchild) t->lchild->parent=t; t->rchild=createbitree(t->rchild); if(t->rchild) t->rchild->parent=t; return t;btnode *searchnode(btnode *b,char x) /查找结点btnode *p; if(b=NULL)

35、return NULL; /空二叉树的查找失败出口else if(b->data=x)return b; /查找成功出口elsep=searchnode(b->lchild,x); /在左子树查找if(p!=NULL)return p;else return searchnode(b->rchild,x); /在右子树查找btnode* deltree(btnode *t,char x) btnode *q; if(t->lchild=NULL&&t->rchild=NULL) /删除结点为叶子结点if(t->parent=NULL) /删除

36、结点为根结点 printf("删除结点为根结点n"); q=t; q=NULL;else if(t->parent->lchild->data=x)printf("删除结点为叶子结点n");q=t->parent->lchild;t->parent->lchild=NULL;elseprintf("删除结点为叶子结点n");q=t->parent->rchild;t->parent->rchild=NULL;free(t);else if(t->lchild=NU

37、LL&&t->rchild!=NULL) /删除结点无左孩子，将右孩子上提，代替该结点 if(t->parent=NULL) /删除结点为根结点 printf("删除结点为根结点n"); q=t->rchild; while(q->lchild!=NULL) / 以先序方式遍历到最后一个左孩子 q=q->lchild; q->parent->lchild=NULL; q->rchild=t->rchild; t->rchild->parent=q; q->parent=NULL;else

38、 if (t->parent->lchild->data=x) printf("删除结点叶结点n");t->parent->lchild=t->rchild;t->rchild->parent=t->parent;elseprintf("删除结点叶结点n"); t->parent->rchild=t->rchild;t->rchild->parent=t->parent;free(t);else if(t->lchild!=NULL&&t-&g

39、t;rchild=NULL) /删除结点无右孩子，将左孩子上提，代替该结点if(t->parent=NULL) /删除结点为根结点 printf("删除结点根结点n"); q=t->lchild; q->parent=NULL;else if(t->parent->lchild->data=x) printf("删除结点叶结点n");t->parent->lchild=t->lchild;t->lchild->parent=t->parent;else printf("删除

40、结点叶结点n"); t->parent->rchild=t->lchild;t->lchild->parent=t->parent;free(t);else /删除结点既有 左孩子又有右孩子 if(t->parent=NULL) /删除结点为根结点 printf("删除结点叶结点n"); q=t->rchild; while(q->lchild!=NULL) / 以先序方式遍历到最后一个左孩子 q=q->lchild; q->parent->lchild=NULL; q->lchild=

41、t->lchild; q->rchild=t->rchild; t->rchild->parent=q; t->lchild->parent=q; q->parent=NULL;else if(t->parent->lchild->data=x|t->parent->rchild->data=x)/ 直接指向 删除结点的右孩子 printf("删除结点叶结点n");q=t->rchild;while(q->lchild!=NULL) / 以先序方式遍历到最后一个左孩子 q=q-&

42、gt;lchild; q->parent->lchild=NULL; /当将q结点提出时，则应该其原来的储存位置置空 / 用q代替要删除结点， 保证以中序输出的结点顺序不变 if(t->parent->lchild->data=x) q->lchild=t->lchild; q->rchild=t->rchild; t->lchild->parent=q; t->rchild->parent=q; t->parent->lchild=q; q->parent=t->parent; else q

43、->lchild=t->lchild; q->rchild=t->rchild; t->lchild->parent=q; t->rchild->parent=q; t->parent->rchild=q; q->parent=t->parent; free(t); return q; void preorder(btnode *bt) /递归 先序 遍历 if(bt!=NULL)printf("%c",bt->data);preorder(bt->lchild);preorder(bt-&

44、gt;rchild);void preorder2(btnode* bt) /非递归 先序遍历 btnode* p;seqstack ps;ps.top=-1;if(bt=NULL)return;elseps.top+;ps.dataps.top=bt;while(ps.top!=-1)p=ps.dataps.top;ps.top-;printf("%c",p->data);if(p->rchild!=NULL)ps.top+;ps.dataps.top=p->rchild;if(p->lchild!=NULL)ps.top+;ps.dataps.t

45、op=p->lchild;void inorder(btnode *p) / 递归中序遍历 if(p!=NULL) inorder(p->lchild); printf("%c",p->data); inorder(p->rchild);void inorder2(btnode *bt) /非递归中序遍历btnode *p,*q;seqstack ps;ps.top=-1;if(bt=NULL)return;elsewhile(bt!=NULL)ps.top+;ps.dataps.top=bt;bt=bt->lchild;while(ps.to

46、p!=-1)p=ps.dataps.top;ps.top-;printf("%c",p->data);while(p->rchild!=NULL)ps.top+;ps.dataps.top=p->rchild;q=p->rchild;while(q->lchild!=NULL)ps.top+;ps.dataps.top=q->lchild;q=q->lchild;break; void postorder(btnode *bt) /递归后序遍历if(bt!=NULL)postorder(bt->lchild);postorde

47、r(bt->rchild);printf("%c",bt->data);void postorder2(btnode* bt) /非递归后序遍历seqstack ps; ps.top=-1; btnode* t; int flag; dowhile (bt!=NULL)ps.top+;ps.dataps.top=bt;bt=bt->lchild; t=NULL;flag=1;while (ps.top!=-1 && flag)bt=ps.dataps.top;if(bt->rchild=t) /t：表示为null，或者右子节点被访问过

48、了。printf("%c ",bt->data);ps.top-;t=bt; /t记录下刚刚访问的节点elsebt=bt->rchild;flag=0; while (ps.top!=-1);void dispbitree(btnode *b) /嵌套 输出二叉树if(b!=NULL) printf("%c",b->data);if(b->lchild!=NULL|b->rchild!=NULL)printf("(");dispbitree(b->lchild); /递归处理左子树if(b->

49、rchild!=NULL)printf(",");dispbitree(b->rchild); /递归处理右子树printf(")");void output1()int i;for(i=0;i<23;i+)printf(" ");for(i=0;i<32;i+)printf("*");printf("n");void mainpp()int i;output1();for(i=0;i<23;i+)printf(" ");printf("*

50、"); printf("1.先 序 建 立 二 叉 树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* "); printf("2.非递归先序遍历二叉树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* "); printf("3.非递归中序遍历二叉树");for(i=0;i<4;i+)printf(" ");printf("*");printf("n");for(i=0;i<23;i+)printf(" ");printf("* "); printf("4.非递归后序遍历二叉树&qu