搜索
《数据结构》课程实验1《数据结构》实验报告题目:_学号:_________姓名:___________东南大学成贤学院计算机系《数据结构》课程实验2实验题目一、实验目的1.掌握二叉树的基本操作，理解递归算法。二、实验内容1．将下图所示二叉树采用二叉链表进行存储，然后进行各种操作测试。三、实验步骤1.启动VC6.0：开始菜单→程序→MicrosoftVisualStudio6.0→MicrosoftVisualC++6.02.建立工程：文件（File）→新建（new）→在弹出的对话框中选择工程标签（Project）→选中选项：Win32ConsoleApplication（不能选别的）→输入工程名（ProjectName）→选择工程的存放位置（Location）→单击“确定”按钮（OK）→在弹出的对话框中选中选项：AnEmptyProject→单击“完成”按钮（Finish）→在弹出的对话框中单击“确定”按钮（OK）。3.创建头文件：文件（File）→新建（new）→在弹出的对话框中选择文件标签（Files）→选中选项：C/C++HeaderFile→输入头文件名（此处定义为“bin_tree_node.h”）→单击“确定”按钮（OK）。bin_tree_node.h内容如下：//二叉树结点类模板templateclassElemTypestructBinTreeNode{//数据成员:ElemTypedata;//数据域BinTreeNodeElemType*leftChild;//左孩子BinTreeNodeElemType*rightChild;//右孩子《数据结构》课程实验3};4.创建头文件：文件（File）→新建（new）→在弹出的对话框中选择文件标签（Files）→选中选项：C/C++HeaderFile→输入头文件名（此处定义为“binary_tree.h”）→单击“确定”按钮（OK）。binary_tree.h定义了链队的类模板，代码如下：#ifndef__BINNARY_TREE_H__#define__BINNARY_TREE_H__//二叉树类模板templateclassElemTypeclassBinaryTree{private://二叉树的数据成员:BinTreeNodeElemType*root;//二叉树的私有函数:voidPreOrderHelp(BinTreeNodeElemType*r);//先序遍历voidInOrderHelp(BinTreeNodeElemType*r);//中序遍历voidPostOrderHelp(BinTreeNodeElemType*r);//后序遍历voidCreat(BinTreeNodeElemType*r,intflag,ElemTypeempty,ElemTypeend);//递归创建子树BinTreeNodeElemType*GetRoot();//返回根指针BinTreeNodeElemType*Locate(BinTreeNodeElemType*r,ElemTypee);//查找元素值为e的结点,返回指针.BinTreeNodeElemType*LeftChild(ElemTypee);//定位指定元素的左孩子，返回其指针。BinTreeNodeElemType*Parent(BinTreeNodeElemType*r,ElemTypee);//定位指定元素的父结点BinTreeNodeElemType*LeftSibling(ElemTypee);//定位指定元素的左兄弟intSize(BinTreeNodeElemType*r);intDepth(BinTreeNodeElemType*r);intLeaf(BinTreeNodeElemType*r);//统计并返回叶子结点个数voidClear(BinTreeNodeElemType*r);voidDisplayTreeeHelp(BinTreeNodeElemType*r,intlevel);//按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1public://二叉树公共方法声明:BinaryTree();//无参数的构造函数模板voidCreateBiTree();//构造二叉树BinTreeNodeElemType*GetRoot();//返回二叉树的根voidInOrder();//二叉树的中序遍历《数据结构》课程实验4voidPreOrder();//二叉树的先序遍历voidPostOrder();//二叉树的后序遍历voidLevelOrder();//按层遍历intLocate(ElemTypee);//查找元素值为e的结点。intGetLeft(ElemTypee,ElemType&c);//读取指定元素的左孩子intGetParent(ElemTypee,ElemType&f);//读取指定元素的父元素intGetLeftSibling(ElemTypee,ElemType&s);//读取指定元素的左兄弟intInsertChild(ElemTypee,ElemTypex,ElemTypey);//为指定元素e插入左、右孩子intSetElem(ElemTypee,ElemTypex);//更新指定元素intSize();intDepth();intLeaf();//统计并返回叶子结点个数virtual~BinaryTree();//销毁二叉树voidDisplayTree();};函数实现由学生自己完成#endif5.创建源程序文件main.cpp：文件（File）→新建（new）→在弹出的对话框中选择文件标签（Files）→选中选项：C++SourceFile→输入源程序文件名（main）→单击“确定”按钮（OK）。main.cpp文件内容如下：#includebinary_tree.h//二叉树类intmain(void){利用swtich构造菜单，对二叉树操作进行测试。（初始化，构造二叉树，图形显示，前序，中序，后序遍历结果，求结点个数，二叉树深度，叶子结点树，查找结点，找指定结点的左孩子，双亲，左兄弟，插入新的左、右孩子。}注意：1.在编程过程中注意及时保存编写内容。四、实验结果1.binary_tree.h的代码2.main.cpp的代码3.运行结果截图（可以有多张）《数据结构》课程实验51、binary_tree.h#pragmaonce#include”stdafx.h”usingnamespacestd;//二叉树类模板templateclassElemTypeclassBinaryTree{private://二叉树的数据成员:BinTreeNodeElemType*root;//二叉树的私有函数:voidPreOrderHelp(BinTreeNodeElemType*r);//先序遍历voidInOrderHelp(BinTreeNodeElemType*r);//中序遍历voidPostOrderHelp(BinTreeNodeElemType*r);//后序遍历voidCreat(BinTreeNodeElemType*r,intflag,ElemTypeempty,ElemTypeend);//递归创建子树BinTreeNodeElemType*GetRoot();//返回根指针BinTreeNodeElemType*Locate(BinTreeNodeElemType*r,ElemTypee);//查找元素值为e的结点,返回指针.BinTreeNodeElemType*LeftChild(ElemTypee);//定位指定元素的左孩子，返回其指针。BinTreeNodeElemType*Parent(BinTreeNodeElemType*r,ElemTypee);//定位指定元素的父结点BinTreeNodeElemType*LeftSibling(ElemTypee);//定位指定元素的左兄弟intSize(BinTreeNodeElemType*r);intDepth(BinTreeNodeElemType*r);intLeaf(BinTreeNodeElemType*r);//统计并返回叶子结点个数voidClear(BinTreeNodeElemType*r);voidDisplayTreeeHelp(BinTreeNodeElemType*r,intlevel);//按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1intsize;public://二叉树公共方法声明:BinaryTree();//无参数的构造函数模板voidCreateBiTree();//构造二叉树//BinTreeNodeElemType*GetRoot();//返回二叉树的根voidInOrder();//二叉树的中序遍历voidPreOrder();//二叉树的先序遍历《数据结构》课程实验6voidPostOrder();//二叉树的后序遍历voidLevelOrder();//按层遍历intLocate(ElemTypee);//查找元素值为e的结点。intGetLeft(ElemTypee,ElemType&c);//读取指定元素的左孩子intGetParent(ElemTypee,ElemType&f);//读取指定元素的父元素intGetLeftSibling(ElemTypee,ElemType&s);//读取指定元素的左兄弟intInsertChild(ElemTypee,ElemTypex,ElemTypey);//为指定元素e插入左、右孩子intSetElem(ElemTypee,ElemTypex);//更新指定元素intSize();intDepth();intLeaf();//统计并返回叶子结点个数virtual~BinaryTree();//销毁二叉树voidDisplayTree();};templateclassElemTypevoidBinaryTreeElemType::PreOrderHelp(BinTreeNodeElemType*r)//private{if(r!=NULL){coutr-data;//访问根结点PreOrderHelp(r-leftChild);//遍历左子树PreOrderHelp(r-rightChild);//遍历右子树}}templateclassElemTypevoidBinaryTreeElemType::PreOrder()//public{PreOrderHelp(root);}templateclassElemTypevoidBinaryTreeElemType::InOrderHelp(BinTreeNodeElemType*r)//private{if(r!=NULL){InOrderHelp(r-leftChild);//遍历左子树coutr-data;//访问根结点InOrderHelp(r-rightChild);//遍历右子树《数据结构》课程实验7}}templateclassElemTypevoidBinaryTreeElemType::InOrder()//public{InOrderHelp(root);}templateclassElemTypevoidBinaryTreeElemType::PostOrderHelp(BinTreeNodeElemType*r)//private{if(r!=NULL){PostOrderHelp(r-left