《数据结构-二叉树的实现》由会员分享，可在线阅读，更多相关《数据结构-二叉树的实现（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程实验数据结构实验报告题目:_学号:_姓名:_东南大学成贤学院计算机系实验题目一、 实验目的1. 掌握二叉树的基本操作，理解递归算法。二、 实验内容1 将下图所示二叉树采用二叉链表进行存储，然后进行各种操作测试。三、 实验步骤1.启动VC6.0：开始菜单程序Microsoft Visual Studio 6.0 Microsoft Visual C+ 6.02.建立工程：文件（File）新建（new）在弹出的对话框中选择工程标签（Project）选中选项：Win32 Console Application（不能选别的）输入工程名（Project Name）选择工程的存放位置（Loca
2、tion）单击“确定”按钮（OK）在弹出的对话框中选中选项：An Empty Project单击“完成”按钮（Finish）在弹出的对话框中单击“确定”按钮（ OK ）。3.创建头文件：文件（File）新建（new）在弹出的对话框中选择文件标签（Files） 选中选项：C/C+ Header File输入头文件名（此处定义为“bin_tree_node.h”）单击“确定”按钮（OK）。bin_tree_node.h内容如下：/ 二叉树结点类模板 template struct BinTreeNode/ 数据成员:ElemType data; / 数据域BinTreeNode *leftChil
3、d;/ 左孩子BinTreeNode *rightChild;/ 右孩子;4.创建头文件：文件（File）新建（new）在弹出的对话框中选择文件标签（Files） 选中选项：C/C+ Header File输入头文件名（此处定义为“binary_tree.h”）单击“确定”按钮（OK）。binary_tree.h 定义了链队的类模板，代码如下：#ifndef _BINNARY_TREE_H_#define _BINNARY_TREE_H_/ 二叉树类模板template class BinaryTreeprivate:/ 二叉树的数据成员:BinTreeNode *root;/ 二叉树的私有函
4、数: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的结点,返回指针.BinTreeN
5、ode* 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(BinTr
6、eeNode *r, int level);/ 按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1public:/ 二叉树公共方法声明:BinaryTree();/ 无参数的构造函数模板void CreateBiTree();/ 构造二叉树BinTreeNode *GetRoot();/ 返回二叉树的根void InOrder();/ 二叉树的中序遍历void PreOrder();/ 二叉树的先序遍历void PostOrder();/ 二叉树的后序遍历void LevelOrder(); /按层遍历int Locate(ElemType e); /查找元素值为e的结
7、点。int GetLeft(ElemType e, ElemType &c); /读取指定元素的左孩子int GetParent(ElemType e, ElemType &f); /读取指定元素的父元素int GetLeftSibling(ElemType e, ElemType &s); /读取指定元素的左兄弟int InsertChild(ElemType e,ElemType x,ElemType y);/为指定元素 e 插入左、右孩子int SetElem(ElemType e, ElemType x);/更新指定元素int Size( ); int Depth( ); int Le
8、af( ); /统计并返回叶子结点个数virtual BinaryTree();/ 销毁二叉树void DisplayTree();函数实现由学生自己完成#endif5. 创建源程序文件main.cpp：文件（File）新建（new）在弹出的对话框中选择文件标签（Files） 选中选项：C+ Source File输入源程序文件名（main）单击“确定”按钮（OK）。main.cpp文件内容如下：#include binary_tree.h/ 二叉树类int main(void)利用swtich构造菜单，对二叉树操作进行测试。（初始化，构造二叉树，图形显示，前序，中序，后序遍历结果，求结点个数
9、，二叉树深度，叶子结点树，查找结点，找指定结点的左孩子，双亲，左兄弟，插入新的左、右孩子。注意：1.在编程过程中注意及时保存编写内容。四、 实验结果1. binary_tree.h的代码2. main.cpp的代码3. 运行结果截图（可以有多张）1、binary_tree.h#pragma once#include ”stdafx.h”using namespace std;/ 二叉树类模板template class BinaryTreeprivate:/ 二叉树的数据成员:BinTreeNode *root;/ 二叉树的私有函数:void PreOrderHelp(BinTreeNode
10、*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);/定位指定元
11、素的左孩子，返回其指针。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为根的二叉
12、树，level为层次数，可设根结点的层次数为1int size;public:/ 二叉树公共方法声明:BinaryTree();/ 无参数的构造函数模板void CreateBiTree();/ 构造二叉树/BinTreeNode *GetRoot();/ 返回二叉树的根void InOrder();/ 二叉树的中序遍历void PreOrder();/ 二叉树的先序遍历void PostOrder();/ 二叉树的后序遍历void LevelOrder(); /按层遍历int Locate(ElemType e); /查找元素值为e的结点。int GetLeft(ElemType e, El
13、emType &c);/读取指定元素的左孩子int GetParent(ElemType e, ElemType &f);/读取指定元素的父元素int GetLeftSibling(ElemType e, ElemType &s);/读取指定元素的左兄弟int InsertChild(ElemType e, ElemType x, ElemType y);/为指定元素 e 插入左、右孩子int SetElem(ElemType e, ElemType x);/更新指定元素int Size();int Depth();int Leaf(); /统计并返回叶子结点个数virtual BinaryTree();/
