数据结构-二叉树的实现

数据结构 课程实验 1 数据结构 实验报告 题目 学号 姓名 东南大学成贤学院计算机系 数据结构 课程实验 2 实验题目实验题目 一 一 实验目的实验目的 1 掌握二叉树的基本操作 理解递归算法 二 二 实验内容实验内容 1 将下图所示二叉树采用二叉链表进行存储 然后进行各种操作测试 三 三 实验步骤实验步骤 1 启动 VC6 0 开始菜单 程序 Microsoft Visual Studio 6 0 Microsoft Visual C 6 0 2 建立工程 文件 File 新建 new 在弹出的对话框中选择工程标签 Project 选中选项 Win32 Console Application 不能选别的 输入 工程名 Project Name 选择工程的存放位置 Location 单击 确定 按钮 OK 在弹出的对话框中选中选项 An Empty Project 单击 完成 按钮 Finish 在弹出的对话框中单击 确定 按钮 OK 3 创建头文件 文件 File 新建 new 在弹出的对话框中选择文件标签 Files 选中选项 C C Header File 输入头文件名 此处定义为 bin tree node h 单击 确定 按钮 OK bin tree node h 内容如下 二叉树结点类模板二叉树结点类模板 templatetemplate classElemType structstruct BinTreeNodeBinTreeNode 数据成员数据成员 ElemTypeElemType data data 数据域数据域 BinTreeNodeBinTreeNode leftChild leftChild 左孩子左孩子 BinTreeNodeBinTreeNode rightChild rightChild 右孩子右孩子 数据结构 课程实验 3 4 创建头文件 文件 File 新建 new 在弹出的对话框中选择文件标签 Files 选中选项 C C Header File 输入头文件名 此处定义为 binary tree h 单击 确定 按钮 OK binary tree h 定义了链队的类模板 代码如下 ifndef ifndef BINNARY TREE H BINNARY TREE H define define BINNARY TREE H BINNARY TREE H 二叉树类模板二叉树类模板 templatetemplate classElemType classclass BinaryTreeBinaryTree private private 二叉树的数据成员二叉树的数据成员 BinTreeNodeBinTreeNode root root 二叉树的私有函数二叉树的私有函数 voidvoid PreOrderHelp BinTreeNodePreOrderHelp BinTreeNode r r 先序遍历先序遍历 voidvoid InOrderHelp BinTreeNodeInOrderHelp BinTreeNode r r 中序遍历中序遍历 voidvoid PostOrderHelp BinTreeNodePostOrderHelp BinTreeNode r r 后序遍历后序遍历 voidvoid Creat BinTreeNodeCreat BinTreeNode r r intint flag flag ElemTypeElemType empty empty ElemTypeElemType end end 递归创建子树递归创建子树 BinTreeNodeBinTreeNode GetRoot GetRoot 返回根指针返回根指针 BinTreeNodeBinTreeNode Locate Locate BinTreeNodeBinTreeNode r r ElemTypeElemType e e 查找元素值为查找元素值为 e e 的结点的结点 返回指针返回指针 BinTreeNodeBinTreeNode LeftChild ElemTypeLeftChild ElemType e e 定位指定元素的左孩子 返回其指针 定位指定元素的左孩子 返回其指针 BinTreeNodeBinTreeNode Parent Parent BinTreeNodeBinTreeNode r r ElemTypeElemType e e 定位指定元素的父结点定位指定元素的父结点 BinTreeNodeBinTreeNode LeftSibling ElemTypeLeftSibling ElemType e e 定位指定元素的左兄弟定位指定元素的左兄弟 intint Size BinTreeNodeSize BinTreeNode r r intint Depth BinTreeNodeDepth BinTreeNode r r intint Leaf BinTreeNodeLeaf BinTreeNode r r 统计并返回叶子结点个数统计并返回叶子结点个数 voidvoid Clear BinTreeNodeClear BinTreeNode r r voidvoid DisplayTreeeHelp BinTreeNodeDisplayTreeeHelp BinTreeNode r r intint level level 按树状形式显示以按树状形式显示以 r r 为根的二叉树 为根的二叉树 levellevel 为层次数 可设根结点为层次数 可设根结点 的层次数为的层次数为 1 1 public public 二叉树公共方法声明二叉树公共方法声明 BinaryTree BinaryTree 无参数的构造函数模板无参数的构造函数模板 voidvoid CreateBiTree CreateBiTree 构造二叉树构造二叉树 BinTreeNodeBinTreeNode GetRoot GetRoot 返回二叉树的根返回二叉树的根 voidvoid InOrder InOrder 二叉树的中序遍历二叉树的中序遍历 数据结构 课程实验 4 voidvoid PreOrder PreOrder 二叉树的先序遍历二叉树的先序遍历 voidvoid PostOrder PostOrder 二叉树的后序遍历二叉树的后序遍历 voidvoid LevelOrder LevelOrder 按层遍历按层遍历 intint Locate ElemTypeLocate ElemType e e 查找元素值为查找元素值为 e e 的结点 的结点 intint GetLeft ElemTypeGetLeft ElemType e e ElemTypeElemType 读取指定元素的左孩子读取指定元素的左孩子 intint GetParent ElemTypeGetParent ElemType e e ElemTypeElemType 读取指定元素的父元素读取指定元素的父元素 intint GetLeftSibling ElemTypeGetLeftSibling ElemType e e ElemTypeElemType 读取指定元素的左兄弟读取指定元素的左兄弟 intint InsertChild ElemTypeInsertChild ElemType e ElemTypee ElemType x ElemTypex ElemType y y 为指定元素为指定元素 e e 插入左 右孩子插入左 右孩子 intint SetElem ElemTypeSetElem ElemType e e ElemTypeElemType x x 更新指定元素更新指定元素 intint Size Size intint Depth Depth intint Leaf Leaf 统计并返回叶子结点个数统计并返回叶子结点个数 virtualvirtual BinaryTree BinaryTree 销毁二叉树销毁二叉树 voidvoid DisplayTree DisplayTree 函数实现由学生自己完成函数实现由学生自己完成 endif endif 5 创建源程序文件 main cpp 文件 File 新建 new 在弹出的对话框 中选择文件标签 Files 选中选项 C Source File 输入源程序文件名 main 单击 确定 按钮 OK main cpp 文件内容如下 include binary tree h 二叉树类 int main void 利用 swtich 构造菜单 对二叉树操作进行测试 初始化 构造二叉树 图形显示 前序 中序 后序遍历结果 求结点个数 二叉树深度 叶子结点 树 查找结点 找指定结点的左孩子 双亲 左兄弟 插入新的左 右孩子 注意 1 在编程过程中注意及时保存编写内容 四 四 实验结果实验结果 1 binary tree h的代码 2 main cpp的代码 3 运行结果截图 可以有多张 数据结构 课程实验 5 1 binary tree h pragma once include stdafx h using namespace std 二叉树类模板 template class BinaryTree private 二叉树的数据成员 BinTreeNode root 二叉树的私有函数 void PreOrderHelp BinTreeNode r 先序遍历 void InOrderHelp BinTreeNode r 中序遍历 void PostOrderHelp BinTreeNode r 后序遍历 void Creat BinTreeNode r int flag ElemType empty ElemType end 递归创建子树 BinTreeNode GetRoot 返回根指针 BinTreeNode Locate BinTreeNode r ElemType e 查找元素值 为e的结点 返回指针 BinTreeNode LeftChild ElemType e 定位指定元素的左孩子 返回其指针 BinTreeNode Parent BinTreeNode r ElemType e 定位指定元素 的父结点 BinTreeNode LeftSibling ElemType e 定位指定元素的左兄弟 int Size BinTreeNode r int Depth BinTreeNode r int Leaf BinTreeNode r 统计并返回叶子结点个数 void Clear BinTreeNode r void DisplayTreeeHelp BinTreeNode r int level 按树状形式显示以r为根的二叉树 level为层次数 可设根结点的层次数为1 int size public 二叉树公共方法声明 BinaryTree 无参数的构造函数模板 void CreateBiTree 构造二叉树 BinTreeNode GetRoot 返回二叉树的根 void InOrder 二叉树的中序遍历 void PreOrder 二叉树的先序遍历 数据结构 课程实验 6 void PostOrder 二叉树的后序遍历 void LevelOrder 按层遍历 int Locate ElemType e 查找元素值为e的结点 int GetLeft ElemType e ElemType 读取指定元素的左孩子 int GetParent ElemType e ElemType 读取指定元素的父元素 int GetLeftSibling ElemType e ElemType 读取指定元素的左兄弟 int InsertChild ElemType e ElemType x ElemType y 为指定元素 e 插入左 右孩子 int SetElem ElemType e ElemType x 更新指定元素 int Size int Depth int Leaf 统计并返回叶子结点个数 virtual BinaryTree 销毁二叉树 void DisplayTree template void BinaryTree PreOrderHelp BinTreeNode r private if r NULL cout data leftChild 遍历左子树 PreOrderHelp r rightChild 遍历右子树 template void BinaryTree PreOrder public PreOrderHelp root template void BinaryTree InOrderHelp BinTreeNode r private if r NULL InOrderHelp r leftChild 遍历左子树 cout data rightChild 遍历右子树 数据结构 课程实验 7 template void BinaryTree InOrder public InOrderHelp root template void BinaryTree PostOrderHelp BinTreeNode r private if r NULL PostOrderHelp r leftChild 遍历左子树 PostOrderHelp r rightChild 遍历右子树 cout data 访问根结点 template void BinaryTree PostOrder public PostOrderHelp root template void BinaryTree LevelOrder LinkQueue BinTreeNode q BinTreeNode t root if t NULL q InQueue t 如果根非空 则入队 while q Empty q OutQueue t cout data leftChild NULL 左孩子非空 q InQueue t leftChild 左孩子入队 if t rightChild NULL 右孩子非空 q InQueue t rightChild 右孩子入队 template BinaryTree BinaryTree root NULL 数据结构 课程实验 8 template void BinaryTree CreateBiTree BinTreeNode r ElemType end empty x cout 按先序序列的顺序输入一棵二叉树 endl cout end cout empty cout 请开始输入 x r new BinTreeNode r data x r leftChild r rightChild NULL root r Creat r 0 empty end 创建根结点的左子树 Creat r 1 empty end 创建根结点的右子树 template void BinaryTree Creat BinTreeNode r int flag ElemType empty ElemType end BinTreeNode p ElemType x cin x if x end p data x p leftChild p rightChild NULL if flag 0 r leftChild p p为左子树 else r rightChild p p为右子树 size Creat p 0 empty end 递归创建左子树 Creat p 1 empty end 递归创建右子树 template BinTreeNode BinaryTree GetRoot return root template BinTreeNode BinaryTree Locate BinTreeNode r ElemType e private 数据结构 课程实验 9 if r NULL return NULL if r data e return r BinTreeNode p Locate r leftChild e if p NULL p Locate r rightChild e return p template int BinaryTree Locate ElemType e public if Locate root e NULL return false else return true template BinTreeNode BinaryTree LeftChild ElemType e private BinTreeNode ep Locate root e if ep NULL return NULL 找不到结点e if ep leftChild NULL e无左孩子 return NULL return ep leftChild 返回e左孩子的指针 template int BinaryTree GetLeft ElemType e ElemType if p NULL return false e无左孩子 c p data return true template BinTreeNode BinaryTree Parent BinTreeNode r ElemType e private BinTreeNode p if r NULL return NULL if r leftChild NULL r是e的父结点 返回结点r的指针 p Parent r leftChild e 递归调用r的左子树 if p NULL p Parent r rightChild e 数据结构 课程实验 10 return p template int BinaryTree GetParent ElemType e ElemType BinTreeNode p Parent root e if p NULL return false 树中无元素e f p data return true template BinTreeNode BinaryTree LeftSibling ElemType e private if root data e return NULL BinTreeNode p Parent root e if p NULL return NULL 无e结点 if p leftChild data e e是其父亲的左孩子 return NULL return p leftChild 返回e的左兄弟指针 template int BinaryTree GetLeftSibling ElemType e ElemType 根结点无兄弟 BinTreeNode p LeftSibling e if p NULL return false e无左兄弟 s p data return true template int BinaryTree InsertChild ElemType e ElemType x ElemType y BinTreeNode ep xp yp ep Locate root e 定位元素e if ep NULL return false 找不到元素e xp new BinTreeNode xp data x xp rightChild NULL yp new BinTreeNode 数据结构 课程实验 11 yp data y yp leftChild NULL xp leftChild ep leftChild ep leftChild xp 结点x置为结点e的左孩子 yp rightChild ep rightChild ep rightChild yp 结点y置为结点e的右孩子 size size 2 return true template int BinaryTree SetElem ElemType e ElemType x BinTreeNode p Locate root e if p NULL return false p data x return true template int BinaryTree Size public return Size root template int BinaryTree Size BinTreeNode r private if r NULL return 0 else return Size r leftChild Size r rightChild 1 二叉树的结点总数为左右子树的结点数之和加1 template int BinaryTree Depth public return Depth root template int BinaryTree Depth BinTreeNode r private if r NULL return 0 else int leftD rightD 数据结构 课程实验 12 leftD Depth r leftChild rightD Depth r rightChild return 1 leftD rightD leftD rightD 二叉树的深度为左右子树的深度的 最大值加1 template int BinaryTree Leaf public return Leaf root template int BinaryTree Leaf BinTreeNode r private if r NULL return 0 if r leftChild NULL return Leaf r leftChild Leaf r rightChild 递归遍历左子树和右子树 template void BinaryTree Clear BinTreeNode r private if r NULL Clear r leftChild 后序递归 Clear r rightChild delete r size template BinaryTree BinaryTree Clear root root NULL template void BinaryTree DisplayTreeeHelp BinTreeNode r int level if r NULL DisplayTreeeHelp r rightChild level 1 显示右子树 数据结构 课程实验 13 cout endl 显示新行 for int i 0 i level 1 i cout 确保在第level列显示结点 cout data 显示结点 DisplayTreeeHelp r leftChild level 1 template void BinaryTree DisplayTree DisplayTreeeHelp root 1 cout endl endif 2 stdafx h pragma once include targetver h include bin tree node h include lk queue h include include 3 main cpp include stdafx h using namespace std int main BinaryTree bt int c 0 int tmp1 tmp