数据结构课程设计报告-二叉树的遍历.docx

数据结构课程设计报告 课程名称：二叉树的遍历 学院：*学院 专业： 班级： 姓名： 学号： 指导教师： 实验时间：二叉树及其遍历方法【问题描述】用递归和非递归两种方法创建一棵二叉树，并对它们进行先序遍历、中序遍历、后序遍历及层次遍历，并求出该二叉树的深度和叶子结点数、输入一个结点查找该结点的双亲、祖先及左右孩子结点。【基本要求】（1） 用递归和非递归两种方法创建一棵二叉树。（2） 用递归和非递归两种方法，对二叉树进行先序遍历、中序遍历、后序遍历及层次遍历。（3） 求出该二叉树的深度和叶子结点数。（4） 输入一个结点查找该结点的双亲、祖先及左右孩子结点。（5） 写出课程设计报告【测试数据】选定两组测试数据进行测试，验证程序的正确性。程序的调试分析 主菜单 递归创建二叉树 遍历二叉树 查找功能 非递归创建非递归遍历心得体会：通过设计遍历二叉树，让我懂得了递归创建和非递归创建二叉树等有关二叉树的基本知识，通过这次编程实现二叉树的遍历等问题，让我的动手能力增加了，以及在变成的过程中让我懂得了学习数据结构需要动手，不能光看书就能知道各种存储结构。 在这次编程中，我通过查阅书本以及请教别人，让我受益匪浅，让我对数据结构有了新的认知。#include #include#includetypedef int data;typedef struct snodedata ndata;struct snode *lchild,*rchild;snode,*bitree,bitnode ;typedef structbitree link;int flag; stacktype;snode *ptree;int menu();int search_menu();int sub_recu_menu();int sub_unrecu_menu();void inittree(snode *p);int depth_tree(snode *p);int leaf_tree(snode *p);data parent_tree(snode* p,data data);data lchild_tree(snode* p,data data);data rchild_tree(snode* p,data data);bool ancest_tree(snode* p, int data);snode * recu_create(snode *&p);void preorder(snode *p);void inorder(snode *p);void laterorder(snode *p);bitnode * create(bitnode *t);void preorder(bitnode *t);void inorder(bitnode *t);void lateorder(bitnode *t);void levelorder(bitree t);int main(int argc, char* argv)inittree(ptree);while( menu() );return 0;void inittree(snode *p)p = null;int menu()data i;char c = 0;puts( );puts( );puts( );puts( );puts( *欢迎构造二叉树* );puts( );puts( );puts( );puts( );puts( 1、选择递归创建二叉树);puts( 2、选择非递归创建二叉树);puts( 0、退出);scanf(%d,&i);doswitch(i)case 1:recu_create(ptree);while( sub_recu_menu();break;case 2:ptree = create(ptree);while( sub_unrecu_menu();break;case 0:exit(0);default:return 0;printf( 请选择：n);puts( 1、选择递归创建二叉树);puts( 2、选择非递归创建二叉树);puts( 0、结束系统);fflush(stdin);if(i = 0)exit(0);scanf(%d,&i);switch(i)case 1:c = y;break;case 2:c = y;break;default:break;while(c != n & c != n);return 0;int sub_recu_menu()system(cls);data i;puts( );puts( );puts( );puts( );puts( 1、选择先序遍历二叉树);puts( 2、选择中序遍历二叉树);puts( 3、选择后序遍历二叉树);puts( 4、选择层次遍历二叉树);puts( 5、选择对比先序、中序、后序、层次遍历二叉树);puts( 6、输出该二叉树的深度);puts( 7、输出该二叉树的叶子结点数);puts( 8、进行查找);puts( 0、返回上一级);scanf(%d,&i);char c = 0;doswitch(i)case 0:return 0;case 1:preorder(ptree);puts();system(pause);break;case 2:inorder(ptree);puts();system(pause);break;case 3:laterorder(ptree);puts();system(pause);break;case 4:levelorder(ptree);puts();system(pause);break;case 5:preorder(ptree);puts();inorder(ptree);puts();laterorder(ptree);puts();levelorder(ptree);puts();system(pause);break;case 6:printf(%dn,depth_tree(ptree);system(pause);break;case 7:printf(%dn,leaf_tree(ptree);system(pause);break;case 8:while( search_menu() );puts();system(pause);break;default:break;system(cls);printf( 请选择：n);puts( 1、选择先序遍历二叉树);puts( 2、选择中序遍历二叉树);puts( 3、选择后序遍历二叉树);puts( 4、选择层次遍历二叉树);puts( 5、选择对比先序、中序、后序、层次遍历二叉树);puts( 6、输出该二叉树的深度);puts( 7、输出该二叉树的叶子结点数);puts( 8、进行查找);puts( 0、返回上一级);fflush(stdin);if(i = 0)exit(0);scanf(%d,&i);switch(i)case 1:c = y;break;case 2:c = y;break;case 3:c = y;break;case 4:c = y;break;case 5:c = y;break;case 6:c = y;break;case 7:c = y;break;case 8:c = y;break;default:break;while(c != n & c != n);return 0;int sub_unrecu_menu()system(cls);data i;puts( );puts( );puts( );puts( );puts( 1、选择先序遍历二叉树);puts( 2、选择中序遍历二叉树);puts( 3、选择后序遍历二叉树);puts( 4、选择层次遍历二叉树);puts( 5、选择对比先序、中序、后序、层次遍历二叉树);puts( 6、输出该二叉树的深度);puts( 7、输出该二叉树的叶子结点数);puts( 8、进行查找);puts( 0、直接退出);scanf(%d,&i);char c = 0;doswitch(i)case 0:exit(0);case 1:preorder(ptree);puts();system(pause);break;case 2:inorder(ptree);puts();system(pause);break;case 3:lateorder(ptree);puts();system(pause);break;case 4:levelorder(ptree);puts();system(pause);break;case 5:preorder(ptree);puts();inorder(ptree);puts();lateorder(ptree);puts();levelorder(ptree);puts();system(pause);break;case 6:printf(%dn,depth_tree(ptree);system(pause);break;case 7:printf(%dn,leaf_tree(ptree);system(pause);break;case 8:while( search_menu() );puts();system(pause);break;default:break;system(cls);printf( 请选择：n);puts( 1、选择先序遍历二叉树);puts( 2、选择中序遍历二叉树);puts( 3、选择后序遍历二叉树);puts( 4、选择层次遍历二叉树);puts( 5、选择对比先序、中序、后序、层次遍历二叉树);puts( 6、输出该二叉树的深度);puts( 7、输出该二叉树的叶子结点数);puts( 8、进行查找);puts( 0、返回上一级);fflush(stdin);scanf(%d,&i);switch(i)case 0:exit(0);case 1:c = y;break;case 2:c = y;break;case 3:c = y;break;case 4:c = y;break;case 5:c = y;break;case 6:c = y;break;case 7:c = y;break;case 8:c = y;break;default:break;while(c != n & c != n);return 0;/双亲或者左右孩子结点为空时显示为0int search_menu()system(cls);char c = 0;data i,data;doputs( );puts( );puts( );puts( );puts( 1、查找该结点的双亲);puts( 2、查找该结点的左孩子结点);puts( 3、查找该结点的右孩子结点);puts( 4、查找该结点的祖先各节点);scanf(%d,&i);puts(请输入一个结点:t);scanf(%d,&data);switch(i)case 1:printf(双亲是：t%dn,parent_tree(ptree,data);system(pause);break;case 2:printf(左孩子是：t%dn,lchild_tree(ptree,data) );system(pause);break;case 3:printf(右孩子是：t%dn,rchild_tree(ptree,data) );system(pause);break;case 4:ancest_tree(ptree,data);system(pause);default:break;puts(请选择是否继续查找【y/n】); puts( 选择0 直接退出系统);fflush(stdin);scanf(%c,&c);if(c = 0)exit(0);while(c != n & c != n);return 0;/*公共操作*int depth_tree(snode *p)int deep=0;if(p)int lchilddeep=depth_tree(p -lchild);int rchilddeep=depth_tree(p -rchild);deep=lchilddeep=rchilddeep?lchilddeep+1:rchilddeep+1;return deep;int leaf_tree(snode *p)if(!p) return 0;else if(p -lchild = null & p -rchild = null) return 1;else return leaf_tree(p -lchild ) + leaf_tree(p -rchild );data parent_tree(snode* p,data data)if(p)if( (p -lchild & (p -lchild -ndata = data) |(p -rchild & (p -rchild -ndata =data) )return p -ndata ;elseparent_tree(p -lchild ,data);parent_tree(p -rchild ,data);return 0;data lchild_tree(snode* p,data data)data m;if(p)if( (p -lchild) & (p -ndata = data) )m = p -lchild -ndata ;elselchild_tree(p -lchild ,data);lchild_tree(p -rchild ,data);return m;return 0;data rchild_tree(snode* p,data data)data m;if(p)if( (p -rchild ) & (p -ndata = data) )m = p -rchild -ndata ;elselchild_tree(p -lchild ,data);lchild_tree(p -rchild ,data);return m;return 0;bool ancest_tree(snode* p, int data) if(p = null) return false; if(p-ndata = data) return true; if( ancest_tree(p -lchild, data) | ancest_tree(p -rchild, data) ) printf(%dt,p -ndata); return true; return false; /*以下是有关递归的一些操作*snode* recu_create(snode* &p)data ndata = 0;printf(请输入一个数据: );scanf(%d,&ndata);if(ndata = 0)p = 0;elsep = (snode *)malloc(sizeof(snode);if(!p)exit(0);p -ndata = ndata;recu_create(p -lchild);recu_create(p -rchild);return p;void preorder(snode *p)if(!p)return ;elseprintf(%dt,p -ndata); preorder(p -lchild);preorder(p -rchild);void inorder(snode *p)if(!p)return ;elseinorder(p -lchild);printf(%dt,p -ndata);inorder(p -rchild);void laterorder(snode *p)if(!p)return ;elselaterorder(p -lchild);laterorder(p -rchild);printf(%dt,p -ndata); /*以下是非递归有关的操作*bitnode * create(bitnode *t)bitree s20;bitree q;int i,j,x; i=1;printf(i,x=);scanf(%d%d,&i,&x);while(i!=0)q=(bitnode *)malloc(sizeof(bitnode);q -ndata=x;q -lchild=null;q -rchild=null;si=q ;if(i=1) t=q;elsej=i/2;if(i%2=0) sj -lchild = q;elsesj -rchild = q;printf(i,x=);scanf(%d%d,&i,&x);return t;void preorder(bitnode *t)bitree stack20;bitree p;int top;top=0;p=t;while(!(p=null)&(top=0)while(p!=null)p