二叉树数据结构实训报告

1、山东科技大学泰山科技学院课程实训说明书课程： 数据结构实训题目链表的应用与二叉树院 系： 专业班级：学 号：学生姓名：指导教师：年月日目录1、设计题目课程设计题一：链表操作一、设计目的二、设计内容和要求三、数据结构及算法设计四、源代码五、运行结果分析课程设计题二：二叉树的基本操作一、设计目的二、设计内容和要求三、数据结构及算法设计四、源代码五、运行结果分析2、实习总结（收获及体会）3、参考资料；附录（核心代码）1、设计题目课程设计题一：链表操作一、设计目的1掌握线性链表的建立。 2掌握线性链表的基本操作。二、设计内容和要求 利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、

2、输出、 排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数)， 并能在屏幕上输出操作前后的结果。三、数据结构及算法设计链表的各种功能，例如创建，输出，查找，插入，删除，计数，排序； 以上这些功能都是先建立子函数，然后再主函数 main 中进行调用，而不是直接在主函数 中生成，调用过程中主要的就是实参，形参之间的传递，同时运用case语句构造主菜单，使 可以对各种方法进行选择。四、源代码#include #include #include #define OK 1#define ERROR 0typedef int ElemType;typedef int statu

3、s;typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkList;void CreateList_L(LinkList &L)LinkList p,s;int n,i;printf(输入创建元素的个数:n);scanf(%d,&n);L=(LinkList)malloc(sizeof(LNode);L-next=NULL;s=L;printf(输入 %d 元素:n,n);for(i=1;idata);p-next=s-next;s-next=p;s=p;status GetElem_L(LinkList L)int

4、j,i,e;LinkList p;p=L-next;j=1;printf(输入査找的位序i:n ”)； scanf(%d,&i);while(p&jnext；j+；if(!p|ji)return ERROR； e=p-data；return e；status InsertList_L(LinkList &L)int i,j；LinkList p,s； printf(输入插入的位序i:n ); scanf(%d,&i)；p=L;j=0;while(p&jnext;j+; if(!p|ji-1)return(ERROR); s=(LinkList)malloc(sizeof(LNode);prin

5、tf(”输入插入的数值:n); scanf(%d,&s-data); s-next=p-next;p-next=s;return OK;status DeletetList_L(LinkList &L)int i,j;LinkList p,s;p=L;j=0;prinf(输入删除的位序i:n ”)；scanf(%d,&i);while(p&jnext；j+； if(!p|ji-1)return ERROR； s=p-next；p-next=s-next；free(s)； return OK；int CountList_L(LinkList &L)LinkList p；int j；p=L；j=0

6、；while(p-next)p=p-next；+j；if(!p) return ERROR；return j；status GetLocationElem_L(LinkList L) int i,j,e；LinkList p； p=L-next；j=1；i=CountList_L(L)；printf(输入査找的数e:n );scanf(%d,&e)； while(p)if(p-data!=e)p=p-next;j+;else break;if(jnext;printf(链表L的元素为:”)；while(p)printf( %d ,p-data)； p=p-next；printf(n)；void

7、 ArrnyList_L(LinkList L)LinkList p,q；int s； p=L-next； while(p)for(q=p-next；q!=NULL；q=q-next) if(p-data=q-data) s=p-data； p-data=q-data； q-data=s；p=p-next；void PostList_L(LinkList L)LinkList p,q,t； t=L-next； p=t-next； while(p)q=p-next；p-next=t；t=p；p=q；L-next-next=p；L-next=t；void Emue()printf(*n);prin

8、tf(|n);printf( * 1 查找 2 插入3 删除4查找 5 计数 6 输出 7 排序 8 逆置 9 退出 *n);printf(|n);printf(*n);void main()/* 欢迎进入链表操作系统 /* 欢迎进入链表操作系统 */printf(/* 欢迎进入链表操作系统 */n);printf(|n);!请先建表!请先建表!n);printf(n);printf(CreateList_L(L);Emue();do prinf(其输入操作数:);ntf(n); etche();ntf(n);switch(c)case 1:PrintList_L(L); d=GetElem_

9、L(L);printf(査找的数为：”); printf( %d ,d); printf(n);break;case 2:PrintList_L(L); InsertList_L(L); tList_L(L); break;case 3:PrintList_L(L);DeletetList_L(L);PrintList_L(L);break;case 4:PrintList_L(L); d=GetLocationElem_L(L);printf(査找的数的位序为：)；printf( %d ,d);printf(n)；PrintList_L(L)；break；case 5:PrintList_L

10、(L)；s=CountList_L(L)；printf(链表兀素的个数为：”)； printf( %d ,s)； printf(n)；break；case 6:PrintList_L(L)；break；case 7:PrintList_L(L)； ArrnyList_L(L)； PrintList_L(L)；break；case 8:PrintList_L(L)；PostList_L(L)；PrintList_L(L)；break；case 9:exit(0)；default :printf(操作数错误”)；printf(n);break;Emue();while(1);五、运行结果分析(1)

11、.链表的创建链表操作程序实现了链表的九个基本功能：当运行程序时，屏幕会出现一个选择菜单让你先创建一个链表，输入需要创建的元素个数 如图：输入数据，用空格分开，如图：然后随机输入一串数据，例如 3 7 5 1，回车然后便会出现生成的链表 3 7 5 1 。如图(2).链表的查找选择 1 便会出现：输入要查找数据的位置。输入位置，例如 3，回车便会处在第三个位置的 数据 5。(3).排序选择 7 选择 7 便会出现数据按正序排列，如图：.链表的删除选择 3 便会出现：删除数据的位置，例如输入 4，回车便会出现删除后的链表3 7 5 。如图：* 1查找2插入3删除4查找5计数6输岀7排序&逆置9退岀

12、*【输入操作数:3i：3【输入操作数:3i：3.链表的插入选择 2 便会出现：输入数据的位置，例如输入 2，回车便会出现：输入的数据为，例如输入 9 回车便会出现 3 9 7 5 。如图：.链表的计数选择 5 便会出现：计数为：4。如图.查找选择 2 便会出现：输入数据，例如输入 9，回车便会出现：输入的数据位置为：2，如图* 1查找2插入 珊|除4查找5计数&输岀7排序8逆萱9退岀*玄输入操作数:為入查找的数冲善找敢麹的位序为：2链衰L苗元裹为：397 5KHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHK

13、HKHKHKHKHK.逆置选择 8，回车便会出现数据逆置为：5 7 9 3，如图.输出选择 6，回车便会出现数据输出为：5 7 9 3，如图(10).退出选择 9 之后按任意键便会退出运行界面。至此整个链表的各种功能运算完成课程设计题二：二叉树的基本操作一、设计目的1掌握二叉树的概念和性质2. 掌握任意二叉树存储结构。3掌握任意二叉树的基本操作。二、设计内容和要求1.对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构，并实现二叉树的先序、 中序、后序三种遍历，输出三种遍历的结果。2 求二叉树高度、结点数、度为 1 的结点数和叶子结点数。三、数据结构及算法设计二叉树的各种功能，例如创建，先

14、序，中序，后序三种遍历，高度，节点数，叶子节点 数等.对于二叉树的遍历，是运用的递归的思想，求高度，节点数，叶子数等方法和链表一样 都是先建立子函数，再进行调用。四、源代码#include #include #define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;typedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;Status CreateBiTree(BiTr

15、ee &T)char c;scanf(%c,&c);if(c= )T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW); T-data=c;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;Status Visit(TElemType e)printf(%c,e);return OK;Status PreOrder(BiTree T,Status(*Visit)(TElemType e)if(T)if(Visit(T-data)if(PreOrder(T-

16、lchild,Visit) if(PreOrder(T-rchild,Visit) return OK; return OK;elsereturn OK;Status InOrder(BiTree T,Status(*Visit)(TElemType e)if(T)if(InOrder(T-lchild,Visit) if(Visit(T-data) if(InOrder(T-rchild,Visit) return OK; return OK; elsereturn OK;Status PostOrder(BiTree T,Status(*Visit)(TElemType e) if(T)

17、if(PostOrder(T-lchild,Visit) if(PostOrder(T-rchild,Visit) if(Visit(T-data) return OK;return OK;else return OK;int CountLeaf(BiTree T,int &count)if(T)if(!T-lchild)&(!T-rchild)count+; CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);return count;int BiTreeDepth(BiTree T,int level,int &depth)if(T)if

18、(leveldepth)depth=level; BiTreeDepth(T-lchild,level+1,depth);BiTreeDepth(T-rchild,level+1,depth);return depthlevel?depth+1:level+1;int Node1(BiTree T)int n1,n2,n=0;if(T=NULL) return 0;else if(T-lchild&T-rchild=NULL|T-lchild=NULL&T-rchild) n=1;n1=Node1(T-lchild); n2=Node1(T-rchild);return n1+n2+n;int

19、 Nodes(BiTree T)int n1,n2,n;if(T=NULL) return 0;else if(T-lchild=NULL&T-rchild=NULL)return 1;else n1=Nodes(T-lchild); n2=Nodes(T-rchild);n=n1+n2+1;return n;void main()BiTree T;int count=0,depth=0,level=0,n1,N;printf(n请按先序顺序输入各结点的值(空树用空格表示)：);printf(n);CreateBiTree(T);printf(先序遍历结果为：”)；PreOrder(T,Visit);printf(nn)；printf(中序遍历结果为：”)；InOrder(T,Visit)；printf(nn)；printf(后序遍历结果为：)；PostOrder(T,Visit)；printf(nn)；count=CountLeaf(T,count)；printf(叶子结点数为:%dnn,count);depth=BiTreeDepth(T,level,depth)；printf(二叉树深度为:dnn,depth);n1=Node1(T)；printf(二叉树中度为1的结点数为：%dnn,n1);N=Nodes(T)；printf(二叉树的总结点数为：d