|
《数据结构与算法》 上 机 实 验 报 告 （请双面打印） 实验内容 二叉树的基本操作 题 目 BinarySearch Tree的建立与遍历 指导教师 上机日期 学 院 信息与通信工程学院 学生姓名 班 级 学 号 成 绩 指导老师签字
《数据结构与算法》上机实验二 | 题目 | | | 1. 熟悉VC6.0编程环境； 2. 掌握Binary Search Tree的基本特性，掌握二叉树的遍历方法； 3. 加深对二叉树的理解，逐步培养解决问题的编程能力。 | | 参考给定的程序，实现Binary Search Tree的建立与遍历。要求如下： 1. 数据结点不少于10； 2. 数据中不要包括重复的数据； 3. 请数据结点保存在数组中，依次插入数据； 4. 二叉树的存储结构为二叉链表； 5. 对二叉树进行先序遍历并在屏幕上输出该序列； 6. 对二叉树进行中序遍历并在屏幕上输出该序列； 7. 对二叉树进行后序遍历并在屏幕上输出该序列； 提示： 1. 参考课本P10； 2. 先序、中序、后序遍历可参考PPT6.3 章第8页。 提高选做: 1. 实现查找函数。 | | 装有Visual C＋＋6.0或Visual Studio 2010的计算机一台。 | | [1] 严蔚敏, 吴伟民. 数据结构 (C语言版) [M]. 北京: 清华大学出版社, 2015. [2] 谭浩强. 《C语言程序设计》(第二版)[M].北京: 清华大学出版社, 2005. | | | | | | | | | |
一、请简单手写出二叉树的条性质 请预留足够多的空白，打印之后再手写。 1. 二叉树的第k层最多有___________个结点； 2. 深度为k的二叉树最多有_________个结点； 3. 请简要证明二叉树的第3条性质； 二、上机程序与问题 请将原程序、各个问题的答案写在程序中，并直接拷在此处。 #include<stdlib.h> #include<stdio.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElementType; //? typedef int Status; //? typedef struct TreeNode* Position; //? 用Position代替TreeNode*，实现结构体指针 typedef struct TreeNode* BSTree; //? 用BSTree代替TreeNode*，实现结构体指针 // 下面几句话的作用是什么？ struct TreeNode{ ElementType Element;//? 定义一个整形变量Element struct TreeNode* Left;//? 创建一个指向左支路的指针 struct TreeNode* Right; }; // 问题: 简述下述函数的功能,并指出输入和输出分别是什么？ BSTree Insert(ElementType X, BSTree T){ if (T==NULL){ // 问题：本部分的作用？ 判断T指针是否有指向的内存空间，若没有则分配 T=(BSTree)malloc(sizeof(structTreeNode)); //? 给指针T分配空间 if (T==NULL) exit(OVERFLOW);//? 异常中止 else{ T->Element=X; T->Left=NULL; T->Right=NULL; } } else{ // 问题：本部分的作用？ 根据传进来的参数，决定左支路或者右支路 if(X<T->Element) T->Left=Insert(X,T->Left);//? 给T加一个左支路 else if(X>T->Element) T->Right=Insert(X,T->Right); } return T; // 请问：返回的T代表什么意思？ 树的节点 } void Traverse (BSTree T)//先序遍历 { if(T) { printf("%d ",T->Element); Traverse(T->Left); Traverse(T->Right); } } void zhong (BSTree T)//中序遍历 { if(T) { zhong(T->Left); printf("%d ",T->Element); zhong(T->Right); } } void hou(BSTree T)//后序遍历 { if(T) { hou(T->Left); hou(T->Right); printf("%d ",T->Element); } } void main() { int seq[10]={35, 27,19, 0, 32, 12, 87, 26, 5, 41}; // 输入序列数据 BSTree T=NULL; //? 创建一个结构体指针T // 下面这3句话产生的效果是什么？ 按照Insert函数分配支路 for (int i=0; i<10;i++){ T=Insert(seq, T); } printf("\n先序遍历输出序列为:\n"); // 先编子程序，然后在这里调用子程序，实现二叉树的先序遍历 Traverse(T); printf("\n中序遍历输出序列为:\n"); // 先编子程序，然后在这里调用子程序，实现二叉树的中序遍历 zhong(T); printf("\n后序遍历输出序列为:\n"); // 先编子程序，然后在这里调用子程序，实现二叉树的后序遍历 hou(T); // 提高题（不要求同学必须完成）： // 如果以上程序均已完成,尝试写出Find函数 // Find函数实现的功能是：在上述二叉树T中查找某个数X,如果查找成功，则返回X的地址；否则，返回NULL； //先编子程序，然后在这里调用子程序，输出返回的地址 } if(T==NULL) printf(0): else if(T->Element==X) printf(sd,D); else if (X< T->Element) find(Xx,T->Left); else find(X,T->Right): return 0; void main() { int seq[10]={ 35,27,19,0,32,12,87,26,5,41}; BSTree T=NULL; for(int i=0;i< 10;i++){ T=Insert(seq,T);//将数字填入二叉树 printf("\n先序遍历输出序列为:\n"); Traverse(T);//调用子程序,实现叉树的先序遍历 printf("\n中序遍历输出序列为:\n"); zhong(T);//调用子程序,实现叉树的中序遍历 printf("\n后序遍历输出序列为:\n"); hou(T);//调用子程序,实现二叉树的后序遍历 int X; printf("n输入要查找的数:"); scanf("%d",&X); find(x,T); } 三、结果 1. 画出你的二叉树，写出你的先序、中序、后序遍历结果。 2. 贴出你的实验结果。注意：图片要有图标和图题，图片处理一下，避免大片的黑色。 3. 从程序上看，如果数据中有重复的数据，程序是怎么处理的？
四、遇到的问题、解决方法与个人心得。
| 
