数据结构-二叉树的实现.doc

《数据结构-二叉树的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》实验报告题目:_学号:_________姓名:___________东南大学成贤学院计算机系实验题目一、实验目的1.掌握二叉树的基本操作，理解递归算法。二、实验内容1．将下图所示二叉树采用二叉链表进行存储，然后进行各种操作测试。三、实验步骤1.启动VC6.0：开始菜单→程序→MicrosoftVisualStudio6.0→MicrosoftVisualC++6.02.建立工程：文件（File）→新建（new）→在弹出的对话框中选择工程标签（Project）→选中选项：Win32ConsoleApplication（不能选别的）→输入工程名（ProjectName）→选择工

2、程的存放位置（Location）→单击“确定”按钮（OK）→在弹出的对话框中选中选项：AnEmptyProject→单击“完成”按钮（Finish）→在弹出的对话框中单击“确定”按钮（OK）。3.创建头文件：文件（File）→新建（new）→在弹出的对话框中选择文件标签（Files）→选中选项：C/C++HeaderFile→输入头文件名（此处定义为“bin_tree_node.h”）→单击“确定”按钮（OK）。bin_tree_node.h内容如下：//二叉树结点类模板templatestructBinTreeNode{//数据成员:ElemTypeda

3、ta;//数据域BinTreeNode*leftChild;//左孩子BinTreeNode*rightChild;//右孩子};4.创建头文件：文件（File）→新建（new）→在弹出的对话框中选择文件标签（Files）→选中选项：C/C++HeaderFile→输入头文件名（此处定义为“binary_tree.h”）→单击“确定”按钮（OK）。binary_tree.h定义了链队的类模板，代码如下：#ifndef__BINNARY_TREE_H__#define__BINNARY_TREE_H__//二叉树类模板template

4、lemType>classBinaryTree{private://二叉树的数据成员:BinTreeNode*root;//二叉树的私有函数:voidPreOrderHelp(BinTreeNode*r);//先序遍历voidInOrderHelp(BinTreeNode*r);//中序遍历voidPostOrderHelp(BinTreeNode*r);//后序遍历voidCreat(BinTreeNode*r,intflag,ElemTypeempty,ElemTypeend);//

5、递归创建子树BinTreeNode*GetRoot();//返回根指针BinTreeNode*Locate(BinTreeNode*r,ElemTypee);//查找元素值为e的结点,返回指针.BinTreeNode*LeftChild(ElemTypee);//定位指定元素的左孩子，返回其指针。BinTreeNode*Parent(BinTreeNode*r,ElemTypee);//定位指定元素的父结点BinTreeNode*LeftSibli

6、ng(ElemTypee);//定位指定元素的左兄弟intSize(BinTreeNode*r);intDepth(BinTreeNode*r);intLeaf(BinTreeNode*r);//统计并返回叶子结点个数voidClear(BinTreeNode*r);voidDisplayTreeeHelp(BinTreeNode*r,intlevel);//按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1public://二叉树公共方法声明:BinaryTre

7、e(　);//无参数的构造函数模板voidCreateBiTree();//构造二叉树BinTreeNode*GetRoot();//返回二叉树的根voidInOrder();//二叉树的中序遍历voidPreOrder();//二叉树的先序遍历voidPostOrder();//二叉树的后序遍历voidLevelOrder();//按层遍历intLocate(ElemTypee);//查找元素值为e的结点。intGetLe