数据结构课程设计-二叉树的基本操作.docx

数据结构课程设计报告 设计题目：二叉树的基本操作专业：计算机科技院系：计算机学院姓名： xx xx学号： xxxxxxxx时间：2013年9月22日目录一、 设计要求-31. 问题描述-32. 需求分析-3二、 详细设计-31. 概要设计-32. 各模块源代码-3三、 用户手册-9四、 总结-10一、 设计要求1. 问题描述设计一个与二叉树基本操作相关的演示程序。2. 需求分析（1） 创建二叉树。按照用户需要构建二叉树（2） 分别以先序、中序、后序遍历二叉树（3） 查找子节点元素二、 详细设计（附源代码）1. 概要设计/定义二叉树数据结构typedef struct TNodeint num;struct TNode *lchild, *rchild;TNode;2各模块源代码（包含main( )函数）#include#include#define MaxLength 100/定义二叉树数据结构typedef struct TNodeint num;struct TNode *lchild, *rchild;TNode;/声明全局变量rootstatic TNode *root=NULL;/声明插入新结点的函数(根非空)int myInsert_Node(TNode *p, int n);/定义插入新节点的初始函数，拆开写的目的是递归时避免不必要的判断void Insert_Node(int n)if(root=NULL) /如果根结点不存在则创建root=(TNode *)malloc(sizeof(TNode);root-num=n;root-lchild=NULL;root-rchild=NULL;elsemyInsert_Node(root, n);/非根结点的插入操作int myInsert_Node(TNode *p, int n)TNode *temp;if(nnum) /比当前结点小，则访问左子树if(p-lchild=NULL) /左子树为空，则插入该结点temp=(TNode *)malloc(sizeof(TNode);temp-num=n;temp-lchild=NULL;temp-rchild=NULL;p-lchild=temp;return 0;else /左子树不为空，则与左子树进行比较myInsert_Node(p-lchild,n);else /右子树同理if(p-rchild=NULL)temp=(TNode *)malloc(sizeof(TNode);temp-num=n;temp-lchild=NULL;temp-rchild=NULL;p-rchild=temp;return 0;elsemyInsert_Node(p-rchild,n);/前序递归遍历二叉树void Pre_travel(TNode *p)if(p)printf(%d ,p-num);Pre_travel(p-lchild);Pre_travel(p-rchild);/中序递归遍历二叉树void Mid_travel(TNode *p)if(p)Mid_travel(p-lchild);printf(%d ,p-num);Mid_travel(p-rchild);/后序递归遍历二叉树void Suf_travel(TNode *p)if(p)Suf_travel(p-lchild);Suf_travel(p-rchild);printf(%d , p-num);/中序非递归遍历二叉树/*从根节点开始，沿左子树一直走到没有左孩子的节点为止，并将所经过的节点的地址进栈； 当找到没有左孩子的节点时，从栈顶退出该节点并访问它，此时，此节点的左子树已访问完毕； 在用上述方法遍历该节点的右子树，如此重复到栈空为止。*/void NRMid_travel(TNode *bitree)TNode *stackMaxLength;TNode *p;int top=-1;p=bitree;dowhile(p!=NULL)stack+top=p;p=p-lchild;if(top!=-1)p=stacktop-;printf(%d , p-num);p=p-rchild;while(top!=-1|p!=NULL);/释放分配的空间，防止内存泄露。/此处的root为静态区root的拷贝，root需要单独赋空值。void Free_node(TNode *p)if(p)Free_node(p-lchild);Free_node(p-rchild);free(p);p=NULL;/层次遍历二叉树void Level_travel(TNode *bitree)int i,j;TNode *arrayMaxLength, *temp;/建立一个先入先出的队列array,j标识队列增长,i控制输出temp=bitree;if(temp!=NULL)/初始化变量i=0;arrayi=temp;j=1;while(i!=j)temp=arrayi;/控制层次遍历顺序printf(%d , temp-num);if(temp-lchild!=NULL)arrayj=temp-lchild;/左子树存在，入队列j+;if(temp-rchild!=NULL)arrayj=temp-rchild;/右子树存在，入队列j+;i+;/声明核心查找函数int myNode_search(TNode *p, int key);/二叉树的查找，拆开写的目的是递归时避免不必要的判断int Node_search(int key)if(root=NULL)return 0;elseif(key=root-num)return 1;elsereturn myNode_search(root, key);int myNode_search(TNode *p, int key) /printf(p.num:%d key:%dn,p-num,key);if(key=p-num)return 1;elseif(keynum)if(p-lchild!=NULL)return myNode_search(p-lchild, key);elsereturn 0;elseif(p-rchild!=NULL)return myNode_search(p-rchild, key);elsereturn 0;int main()system(cls);system(color 1f);system(mode con: cols=78 lines=35);printf(n);printf( 必做题6：树结构的应用 n);printf( 姓名：xxxxx n);printf( 学号：xxxxxxxxxxx n);printf(n);int sum, i, key;int dataMaxLength;printf( 请输入二叉树结点总数: );scanf(%d,&sum);printf( 请依次输入结点数值大小(以空格或者回车隔开):n);for(i=0;isum;i+)scanf(%d, &datai);for(i=0;isum;i+)Insert_Node(datai);printf( 先序递归遍历后的结果为:n);Pre_travel(root);printf(n 中序递归遍历后的结果为:n);Mid_travel(root);printf(n 后序递归遍历后的结果为:n);Suf_travel(root);printf(n 中序非递归遍历后的结果为:n);NRMid_travel(root);printf(n 层次遍历后的结果为:n);Level_travel(root);/为便于测试，多次查找一下printf(n 请输入要查找的关键字(数字,非数字时终止):n);while(scanf(%d, &key)/scanf(%d, &key);if(Node_search(key)printf( 该关键字存在！n);elseprintf( 该关键字不存在！n);/释放内存Free_node(root);root = NULL;return 0;三、 用户手册（调试演示）包含主界面显示，当我们输入结点总数为12，各结点元素分别为1 2 3 4 5 6 7