《二叉树结点的左右子树交换课程设计报告.docx》由会员分享，可在线阅读，更多相关《二叉树结点的左右子树交换课程设计报告.docx（11页珍藏版）》请在三一办公上搜索。
1、二叉树结点的左右子树交换 课程设计报告目录 一 需求分析. 1 二 概要设计. 1 三 详细设计. 2 四 调试分析和测试结果. 4 五 总结. 6 六 参考文献. 7 七 致谢. 7 八 附录. 7 一 需求分析 问题描述：交换二叉树中所有结点的左、右子树，该二叉树以二叉链表作为存储结构。 基本思想：设二叉树的根指针为s，且以二叉链表表示，可利用一个类型为Q的指针队列来实现，且设队列单元包含两个域，一个为front，一个为rear，整个队列容量为maxsize，当树非空时，将当前的树根结点入队列，同时将当前队列顶元素出队列当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指
2、针进行交换；再将交换后的左指针或右指针入队列，这样反复进行，直到队列空为止。 图1-1是该课题的功能模块图： 二叉树结点的左、右子树的交换 重新建立二叉树 交换左右子数 先根遍历二叉树退出 图 1-1 二 概要设计 该课题主要分为三个功能模块：重新建立二叉树、交换左右子数、先根遍历二叉树。这里主要用到了队列及二叉树的知识，先对二叉树进行层次遍历，然后1 再进行左右子树交换操作，最后再进行先根遍历二叉树，这就实现了二叉树节点的左右子树交换。三个功能模块相互独立又相互关联，独立仅在于各自操作互不影响，而关联在于后两个功能可以对当前建立的二叉树进行操作，产生不同的结果。 该功能流程图如下： 开 始
3、输入二叉树的节点 enter 0 菜 单 1 重新建立二叉树 2 交换左右子数 3 先根遍历二叉树 结 束 图2-1 三 详细设计 本课题为二叉树结点的左、右子树的交换，主要分为三个模块：重新建立二叉树、交换左右子数、先根遍历二叉树。各模块的详细设计如下： 2 首先定义结构体类型及二叉树结点类型，如下所示： typedef char datatype; / 树的结点数据类型为字符型，可以根据需要修改 typedef struct node *pointer; / 定义二叉树结点类型 struct node datatype data; /结点数据 pointer lchild,rchild;
4、/左右孩子结点 ; 三个模块各写三个函数，分别如下所示： bitree level_creat /由层次序列建立二叉树，返回根指针 char ch; ch=cin.get; int front,rear; pointer root,s; root=NULL; /置空二叉树 front=rear=0; /置空队列 /while(cinch,ch!=!) while(cinch,ch!=!) if(ch!=) /非虚结点，建立新结点 s=new node; s-data=ch; s-lchild=s-rchild=NULL; else s=NULL; rear+; Qrear=s; /不管结点是否
5、为虚都要入队 if(rear=1) root=s; front=1; /第一个点是根，要修改头指针，他不是孩子 else if(s & Qfront) /孩子和双亲都不是虚结点 if(rear%2=0) Qfront-lchild=s; / rear是偶数，新结点是左孩子 else Qfront-rchild=s; /rear 是奇数，新结点是右孩子 front+; return root; void exchange(bitree t) /交换左右子数函数 pointer p; 3 if(t=NULL) return; /空树，直接返回 p=t-lchild; t-lchild=t-rchi
6、ld; t-rchild=p; /交换 exchange(t-rchild); /遍历原左子树 exchange(t-lchild); /遍历原右子树 void preorder(bitree t) /先根遍历函数 if(t=NULL) return; coutdatalchild); /先根遍历左子树 preorder(t-rchild); /先根遍历右子树 flag=1; 四 调试分析和测试结果 本人主要编写main函数及先根遍历函数，主函数还是比较简单，就是先根遍历函数有一个小问题：输入的的第一个树即根结点始终打印不出来，分析代码，也没发现什么错误，比较纠结。 下面是测试结果截图： 图4
7、-1为程序运行首页。 图4-1 图4-2为输入二叉树结点的界面。 4 图4-2 图4-3为操作菜单。 图4-3 图4-4为左右二叉树交换成功。 图4-4 图4-5为先根遍历输出结果。 5 图4-5 五 总结 在刚选到该课题的时候，感觉挺茫然的，不知从何处入手。毕竟一个寒假过来，上学期学的数据结构知识也忘的差不多了，并且学的也不是很扎实，所以感觉无从下手。在队友的相互帮助下，我们开始加紧的看书，去图书馆借资料以及上网进行搜索相关的资料，并慢慢的开始做起来。 我们这组三人，分工也比较明确，各自主要负责自己的模块。二本人负责先序遍历模块以及主函数的的编写。在编码过程中，我们遇到了很多小问题，以及一些
8、因粗心而造成的错误，我们都一一解决了。只是我这个环节还有一个问题没有得到解决，就是输出先根遍历的结果时根节点没输出来。这个问题困扰我两天，一直没有得到解决。这个需要以后再继续学习、探究。 总的来说，由于时间有限，本次课程设计“马马虎虎”地完成了。从理论到实践，在整整一个星期的日子里，我学到很多很多的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的内容。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才是真正的知识，才能提高自己的实际动手能力和独立思考的能力。 6 六 参考文献 1.严蔚
9、敏 吴伟明 数据结构-清华大学出版社 2. csdn论坛 网址： 七 致谢 完成该课题的设计，离不开队友的相互配合、同学的帮助及老师的指导，在此表示十分感谢！ 八 附录 /源代码 #include #include #include using namespace std; /* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; / 树的结点数据类型为字符型，可以根据需要修改 typedef struct node *pointer; / 定义二叉树结点类型 struct node datatype data; /结点数据 pointer lchild,
10、rchild; /左右孩子结点 ; typedef pointer bitree; /定义二叉树类型 /* 先根遍历交换左右子树 */ /* 层次遍历序列生成 */ 7 const int maxsize=100; int flag=0; pointer Qmaxsize+1; bitree level_creat /由层次序列建立二叉树，返回根指针 char ch; ch=cin.get; int front,rear; pointer root,s; root=NULL; /置空二叉树 front=rear=0; /置空队列 /while(cinch,ch!=!) while(cinch,
11、ch!=!) if(ch!=) /非虚结点，建立新结点 s=new node; s-data=ch; s-lchild=s-rchild=NULL; else s=NULL; rear+; Qrear=s; /不管结点是否为虚都要入队 if(rear=1) root=s; front=1; /第一个点是根，要修改头指针，他不是孩子 else if(s & Qfront) /孩子和双亲都不是虚结点 if(rear%2=0) Qfront-lchild=s; / rear是偶数，新结点是左孩子 else Qfront-rchild=s; /rear 是奇数，新结点是右孩子 front+; retu
12、rn root; /* 交换左右子数 */ void exchange(bitree t) pointer p; if(t=NULL) return; /空树，直接返回 p=t-lchild; t-lchild=t-rchild; t-rchild=p; /交换 exchange(t-rchild); /遍历原左子树 8 exchange(t-lchild); /遍历原右子树 /* 二叉树的先根遍历 */ void preorder(bitree t) /先根遍历 if(t=NULL) return; coutdatalchild); /先根遍历左子树 preorder(t-rchild);
13、/先根遍历右子树 flag=1; /*void stop / coutn按任意键继续：; getch; */ void main bitree T=NULL; int ch; cout首先层次遍历序列生成二叉树，请输入结点数据(输入为虚结点，输入!结束):n; T=level_creat; if(T=NULL) coutnntt二叉树生成失败!n; coutn按任意键返回菜单：; getch; else coutnntt二叉树生成成功!n; coutn按任意键返回菜单：; getch; AA: do system(cls); /调用清屏函数 coutn; cout; cout 二叉树左右子树交
14、 ; cout9 ; couttt1.重新建立二叉树 ; couttt2.交换左右子数 ; couttt3.先根遍历二叉树 ; couttt0.退出 ; cout; coutch; switch(ch) case 0: break; case 1: T=level_creat; system(cls); coutnntt二叉树生成成功!n; coutn按任意键返回菜单：; getch; break; case 2: exchange(T); coutnntt左右子树交换成功!n; coutn按任意键返回菜单：; getch; break; case 3: coutn先根遍历二叉树结果：n; preorder(T); if(flag) coutnn按任意键返回菜单：; getch; coutendl; break; default:coutnntt您输入错误!请重新输入:nn; getch; goto AA; while(ch!=0); 10
