算法与数据结构》课程实验报告
一、实验目的
1、实现二叉树的存储结构
2、熟悉二叉树基本术语的含义
3、掌握二叉树相关操作的具体实现方法
二、实验内容及要求
1. 建立二叉树
2. 计算结点所在的层次
3. 统计结点数量和叶结点数量
4. 计算二叉树的高度
5. 计算结点的度
6. 找结点的双亲和子女
7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历
8. 二叉树的复制
9. 二叉树的输出等
三、系统分析
（1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。
（2）功能方面：能够实现二叉树的一些基本操作，主要包括：
1. 采用广义表建立二叉树。
2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。
3. 判断结点是否存在二叉树中。
4. 寻找结点父结点、子女结点。
5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。
6. 进行二叉树的复制。
四、系统设计
（1）设计的主要思路
二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。
（2）数据结构的设计
二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉
树的每一个结点可以有两个分支，分别指向结点的左、右子树。因此，二叉树的结点至少应
包括三个域，分别存放结点的数据，左子女结点指针，右子女结点指针。这将有利于查找到某个结点的左子女与右子女，但要找到它的父结点较为困难。该实验采取二叉链表存储二叉树中元素，具体二叉树链表表示如下图所示。
图1 二叉树的链表表示
（3）基本操作的设计二叉树关键主要算法：利用广义表进行二叉树的建立。该算法首先通过重载输入符号，在重载函数中调用CreatBinTree 函数，该函数有两个参数，第一个参数为输入流，用于传递用户输入的二叉树字符串，第二个参数则是二叉树的根结点root。再通过栈操作是实现二叉树。
递归与非递归两种方式实现前序、中序、后序的遍历。递归实现三种遍历的函数均只有一个参数即二叉树根节点root，递归结束条件则是结点为空。当结点不为空时，根据三种遍历的方式不同而代码顺序不同。其中前序遍历访问结点顺序是：根结点、左子树、右子树；中序遍历访问结点顺序是：左子树、根结点、右子树；后序遍历访问结点顺序是：左子树、右子树、根结点。具体算法以及流程图见报告实验分析部分。
涉及二叉树性质的一些计算例如树的高度，结点所处层次，结点的度等。在进行二
叉树相关性质计算函数中参数为二叉树根节点root，再通过需要计算不同
性质实现不同递归代码。需要注意的是不同计算的递归结束条件不同
对于结点父节点与子女结点的寻找。对于结点父结点与子女结点的查找函数均有2 个参数，一个是二叉树根结点root 以及需要查找结点的数据域data。具体实现方式是通过递归遍历每一个二叉树结点，当匹配到需要查找结点数据域时再进行对于该结点父结点或子女结点的输出，若未匹配成功则输出二叉树中不存在该结点。
五、编程环境与实验步骤
（1）编程环境
操作系统：Windows 操作系统；编程工具软件：Visual Studio 2017
（2）实验步骤
程序相关文件有：BinTreeNode.h、BinaryTree.h、Queue.h、SeqStack.h四个头文件以及主函数调试文件main.cpp
（3）编译参数无编译参数，在Vs2017 或其他版本中新建项目然后将程序相关文件添加到解决方案中对应位置中调试即可。
六、实现代码
#include "BinTreeNode.h"
#include "SeqStack.h"
#include "Queue.h"
enum tag { L, R };
extern int number;
extern bool flag;
extern bool flag1;
extern bool flag2;
template
class BinaryTree {
public :
BinTreeNode
T RefValue; // 数据输入停止标志
public :
BinaryTree（） {
root = NULL;
}
BinaryTree（ T value ） {
root = NULL;
RefValue = value ;
BinaryTree( BinaryTree
} // 复制构造函数
BinTreeNode
~BinaryTree(){ destroy(root); }
void destroy( BinTreeNode
void Find_Father( BinTreeNode
void Find_Children( BinTreeNode
void Find( BinTreeNode
int Height( BinTreeNode
int Size( BinTreeNode
void level( BinTreeNode
void Dujisuan( BinTreeNode
个数
BinTreeNode
bool Isempty() { return (root == NULL) ? true : false ; } // 判二叉树是否为空void
dgpreOrder( BinTreeNode
void dgpostOrder( BinTreeNode
void PrintBTree( BinTreeNode
void preOrder( BinTreeNode
void inOrder( BinTreeNode
void postOrder( BinTreeNode
void CreateBinTree( istream & in , BinTreeNode
template
friend istream & operator>>( istream &in , BinaryTree
template
friend ostream & operator<<( ostream &out , BinaryTree
template
if ( subTree != NULL) {
destroy( subTree ->leftChild); destroy( subTree ->rightChild); delete subTree;
} }
template
BT = NULL; // 置空二叉树
BinTreeNode
in >> ch;
while (ch != RefValue) {
switch (ch) {
case '(' :s.Push(p); k = 1; break ;
case ')' :s.Pop(t); break ;
case ',' :k = 2; break ; default :p = new BinTreeNode
if ( BT == NULL ) BT = p; else if (k == 1) { s.getTop(t); t->leftChild = p;
} if (k==2) { s.getTop(t); t->rightChild = p;
} } in >> ch;
}
} template
out << subTree->data << " " ; Traverse( subTree ->leftChild, o ut );
Traverse( subTree->rightChild, out);
}
}
template
void BinaryTree
dginOrder( subTree ->leftChild); cout << subTree ->data << " " ; dginOrder( subTree ->rightChild);
} } template
if ( subTree != NULL) { dgpostOrder( subTree ->leftChild); dgpostOrder( subTree ->rightChild); cout << subTree ->data << " " ;
}
template
void BinaryTree
cout << subTree ->data << " " ; dgpreOrder( subTree ->leftChild); dgpreOrder( subTree ->rightChild);
}
}
template
int BinaryTree
return 0;
else {
int i = Height( subTree ->leftChild);
int j = Height( subTree ->rightChild); return (i < j) ? j + 1 : i + 1;
}
}
template
int BinaryTree
return 0;
else
return 1 + Size( subTree ->leftChild) + Size( subTree ->rightChild);
}
template
void BinaryTree
cout << BT->data;
if ( BT->leftChild != NULL || BT->rightChild != NULL) {
cout << "(" ;
PrintBTree( BT->leftChild);
cout << "," ;
if ( BT->rightChild != NULL) PrintBTree( BT->rightChild);
cout << " ) ";
}
}
}
template
void BinaryTree
BinTreeNode
S.Push(n); while (p != NULL) { cout << p->data << " " ;
if (p->rightChild != NULL) S.Push(p->rightChild); if (p->leftChild != NULL) p = p->leftChild; else
S.Pop(p);
}
} template
SeqStack
BinTreeNode
BinTreeNode
do { while (p != NULL) {
S.Push(p); p = p->leftChild;
}
if (!S.IsEmpty()) { S.Pop(p); if (p != n) { cout << p->data << " " ; p = p->rightChild;
}
}
} while (p != NULL || !S.IsEmpty());
} template
BinTreeNode
tag ta;
stkNode( BinTreeNode
template
void BinaryTree
BinTreeNode
do {
while (p != NULL) {
w.ptr = p; w.ta = L; S.Push(w);
p = p->leftChild;
} int continuel = 1; while (continuel && !S.IsEmpty()) { S.Pop(w); p = w.ptr; switch (w.ta) { case L:w.ta
= R; S.Push(w);
continuel = 0; p = p->rightChild; break ;
case R:cout << p->data << " " ; break ;
} }
} while (!S.IsEmpty());
cout << endl;
} template
Tree .CreateBinTree( in , Tree .root); return in ;
}
template
Tree .Traverse( Tree.root, out);
out << endl; return
out;
} template
BinTreeNode
BinTreeNode
temp->leftChild = Copy( orignode ->leftChild); temp->rightChild = Copy( orignode ->rightChild); return temp;
} template
if ( subTree == NULL) return ;
else {
Queue
Q.EnQueue(subTree );
Q.EnQueue(n);
int level = 1;
while (!Q.IsEmpty()) { BinTreeNode
(Q.IsEmpty()) break ;
level++; Q.EnQueue(n); continue ;
}
cout << "第" << level << "层结点:" << node->data << endl; if ( NULL != node->leftChild) Q.EnQueue(node->leftChild);
if ( NULL != node->rightChild) Q.EnQueue(node->rightChild);
}
}
}
template
void BinaryTree
if ( subTree == NULL) return ;
else {
Queue
Q.EnQueue(subTree );
while (!Q.IsEmpty()) { BinTreeNode
count = 2;
else if (node->leftChild == NULL && node->rightChild == NULL)
{
count = 0; number++;
}
else
count = 1;
cout << node->data<< " 的度为：" <
Dujisuan(node->leftChild);
if ( NULL != node->rightChild) Dujisuan(node->rightChild);
}
}
}
template
void BinaryTree
{
if ( subTree == NULL)
return ;
if ( subTree->leftChild != NULL) // 当左孩子存在的时候才进行判断，否则程序出错
{
if ( subTree ->leftChild->data == data)
{
cout << " 该节点的父结点是:" << subTree ->data< flag = true ;// 全局变量设置了一个标志flag=false ，如果找到父结点，则flag 赋值为true } } if ( subTree ->rightChild != NULL) // 如左子树所示 { if ( subTree ->rightChild->data == data) { cout << " 该节点的父结点是:" << subTree ->data< } } Find_Father( subTree ->leftChild, data ); Find_Father( subTree ->rightChild, data ); } template void BinaryTree { if ( subTree == NULL) return ; else { if ( subTree ->data == data) { flag2 = true ; // 全局变量设置了一个标志flag2=false ，如果找到父结点，则flag2 赋值为 true } template subTree ), T data) { if ( subTree == NULL) return ; else { if ( subTree ->data == data) flag1 = true ; else { Find( subTree ->leftChild, data ); Find( subTree ->rightChild, data ); } } 七、测试结果与说明 菜单界面： if ( subTree ->leftChild != NULL) { cout << " 该节点的左子女结点是 : } if ( subTree ->rightChild != NULL) { cout << " 该节点的右子女结点是 : } if ( subTree ->leftChild == NULL) { cout << " 该节点的左子女结点为空 } if ( subTree ->rightChild == NULL) { cout << " 该节点的右子女结点为空 } } else { Find_Children( subTree ->leftChild, Find_Children( subTree ->rightChild, << subTree ->leftChild->data << endl; << subTree->rightChild->data << endl; << endl; << endl; data ); data ); 二叉树建立： 二叉树高度计算：统计结点数量： 结点度计算以及叶节点数量： 结点所在层次计算： 查找结点是否在树中： 查找结点父结点：查找结点子女结点； 二叉树输出结果（前序） 三种方式（前序、中序、后序）输出二叉树（递归） 三种方式（前序、中序、后序）输出二叉树（非递归）二叉树复制： 八、实验分析 （1）算法的性能分析 二叉树涉及主要算法有利用广义表进行二叉树的建立、递归与非递归两种方式实现前序、中序、后序的遍历、二叉树性质的一些计算例如树的高度，结点所处层次，结点的度等。下面对主要的算法进行分析。 在二叉树的建立采用广义表进行建立。该算法的基本思路是：依次保存广义表的字符串中输入字符。 1. 若是字母（假设以字母作为结点的值），则表示是结点的值，为它建立一个新的结点，并把该结点作为左子女（当k=1）或有子女（k=2）链接到其父结点上。 2. 若是左括号“（”，则表明子表的开始，将k置为1；若遇到的是右括号“）”，则表明子表结束。 3. 若遇到的是逗号“，”，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将k 置为2。以此种方式处理每一个字符，直到读入结束符 “ #”为止。在此算法中使用了一个栈，在进入子表之前将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。 下面分析前序、中序、后序遍历，由于方法大致类似，故在此只对非递归实现中序遍历进行分析。该算法需要使用一个栈，以记录遍历过程中回退的路径。在一棵子树中首先访问的是中序下的第一个结点，它位于从根开始沿leftChild 链走到最左下角的结点，该结点的leftChild 指针为NULL 。访问它的数据后，再遍历该结点的右子树。此右子树又是二叉树，重复执行上面的过程，直到该子树 图2 非递归实现二叉树中序遍历 下面分析二叉树中利用性质进行相关计算。在此只对计算结点所在层次算法进行详细分析，其余计算与该算法有所类似。具体算法是：利用队列实现二叉树层次顺序访 问。在访问二叉树某一层结点时，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。因此，每当访问一个结点时，将它的子女依次加到队列的队尾，然后再访问已在队列队头的结点。由于还需要知道在访问一个结点时它所处层次，故在一层结束的时候，把一个特殊标记入队，用于标记一层已经结束，当这个特殊标记出队时，就知道即将开始遍历新一层的结点了。在该实验中选取NULL 作为特殊标记，具体实现过程如下图所示（部分过程）。 图３计算结点所在层次流程图部分 2）数据结构的分析 由二叉树的存储结构以及相关操作可得出以下优缺点： 1. 优点： 对于形态 剧烈变化 的二叉树 存储利用 较为理 想。 2. 缺点：链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指 定节点的时候效率偏低O（nlogn） 适用场景： 在实际使用时会根据链表和有序数组等数据结构的不同优势进行选择。有序数组的优势在于二分查找，链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢，同样在链表中查找数据项效率就很低。综合以上情况，二叉树可以利用链表和有序数组的优势，同时可以合并有序数组和链表的优势，二叉树是一种常用的数据结构。 九、实验总结 经过一个多星期的努力，完成了数据结构中二叉树实验内容，通过这次试验，对于二叉树的存储方式、二叉树的性质、二叉树的基本应用有了更为深入的理解。同时对递归相关操作复习了一遍，对递归结束条件以及相关代码分析更加透彻。并且，在整个实验程序编写的各个阶段也都有所收获。 首先，在理论课上学习了二叉树的性质以及存储方式等，在了解了实验原理之后在后面对于书中的代码分析阶段也更为轻松，但是还是遇到了一些问题，例如在利用广义表进行二叉树创建时，由于是在重载输入函数中调用二叉树创建函数，故在传参数过程 中有点绕，好在最后通过自己慢慢理解分析知道了参数是如何传递以及具体算法流程。另外就是在二叉树模板类实例化也遇到了一些问题，由于构造函数有重载，并且参数也有些复杂，在这个阶段也花费了一些时间，最后通过理解函数中属性代表含义才成功进行实例化，并约定“ #”作为二叉树输入结束标识符。 其次，在程序的设计阶段也让我有很大收获，由于此次实验需要完成内容较多，在通过对于书上代码仔细理解之后发现大部分功能的实现都需要利用递归，于是再程序设计之前将递归重新复习了一次，对于如何编写递归结束条件，以及何时进行递归有了更深的理解。在重新熟悉递归之后，在进行二叉树的设计明显显得简单不少，只需确定递归结束条件，递归代码即可。这个过程让我收获最大的就是对于递归的理解更加深入，同时也对于二叉树的理解更为透彻。 另外，在编写查找结点父结点以及子女结点过程中也遇到不少问题，第一次进行设计的是考虑使用二叉树结点数据类型作为函数参数进行传递，但后面发现这样编写会增加一些难度，因为必须得重载双等号函数才行，于是最后决定先确定二叉树结点得数据类型，在通过结点的数据域进行查找，在查找到结点之后，在将该结点的父结点或子女结点输出。 在程序的是实现阶段也遇到了一些麻烦，由于使用VS2017环境下编写，可能是因为环境不同的原因，一些代码中存在问题，但都通过百度进行解决了。并且在程序实现阶段遇到输出内容与理论不一致时，采用逐步调试分析变量值的变换来确定问题所在，并将其解决。这个过程通过这么多次的实验已经很熟练了。 最后完成上述实验过程之后就是代码的测试阶段，由于对于二叉树已经有了足够的了解，并且对代码有所分析，所以这个过程中基本没有遇到大问题，只是在不断的去完善输出内容，能够让用户更易理解。 当然，二叉树还有其他存储方式进行存储，此次实验采用二叉链表存储方式进行存储结点，还有三叉存储方式等。为了能够更深入地去理解二叉树以及它的功能，也应该在课后进行其他存储方式代码的分析。相信之后在面对需要使用二叉树进行实现的场景时能够更加熟练操作，并且对于二叉树性质、功能等掌握更加透彻。
相关主题
文本预览