树和二叉树的关键算法实现及性能分析_树和二叉树设计性实验

实验题目：树和二叉树的关键算法实现及性能分析（预习报告）

一、实验目的

1. 能够运用高级程序设计技术实现数和二叉树及其关键算法（实验1、2、3）

2. 能够通过对比分析的方法分析递归、遍历等操作对树和二叉树的关键算法性能的影响规律（实验3）

3. 具体任务参加各个实验的任务书

二、实验原理

1.树的基本原理

（1）树是一种数据结构，它是由n(n≥1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

（2）特性：每个结点有零个或多个后继结点；没有前驱结点的结点称为根结点，没有后继的结点称为叶子结点；每一个非根结点有且只有一个父节点；除了根节点外，每个子结点可以分为多个不相交的子树。

1. 抽象数据类型定义；

ADT Tree{ 

数据对象 D: D 是具有相同特性的数据元素的集合。

数据关系 R: 若 D 为空集，则称为空树；

若 D仅含一个数据元素，则 R 为空集，否则 R={H}, H 是如下二元关系：

①在D 中存在唯一的称为根的数据元素 root,它在关系 H 下无前驱；

②若D-{root} ≠空集，则存在D-{root}的一个划分D1 , D2, …，比(m>0), 对任意j≠k(1<=j, k<=m) 有DjnDk =空集, 且对任意的 i (1<=i<=m), 唯一存在数据元素 xi∈Di, 有 <root, xi>∈H; 对应于D-{root} 的划分，H-{ < root, x1 >, …， <root,xm> =有唯一的一个划分 H1 , H2 , …,Hm (m> 0), 对任意j≠k(l<=j<=m) 有HjnHk =空集, 且对任意 i(1<=i<=m), H1 是D1 上的二元关系，(D1, {Hi}) 是一棵符合本定义的树，称为根 root 的子树。

基本操作P:

InitTree(&T)      操作结果：构造空树T。

DestroyTree (&T)  初始条件：树T存在。    操作结果：销毁树T。

CreateTree(&T,definition) 初始条件：definition 给出树 T 的定义。

操作结果：按 definition 构造树 T。

ClearTree(&T)    初始条件：树T存在。    操作结果：将树T清为空树。TreeEmpty(T)      初始条件：树T存在。

操作结果：若 T 为空树，则返回 true, 否则 false。

TreeDepth(T)      初始条件：树T存在。   操作结果：返回T的深度。

Root(T)           初始条件：树T存在。   操作结果：返回T的根。

Value(T,cur_e)    初始条件：树 T 存在， cur_e是 T 中某个结点。

操作结果：返回 cur_e 的值。

Assign(T,cur_e,value) 初始条件：树 T 存在， cur_e是 T 中某个结点。

操作结果：结点 cur_e 赋值为 value。

Parent(T,cur_e); 初始条件：树 T 存在， cur_e是 T 中某个结点。

操作结果：若 cur_e是 T 的非根结点，则返回它的双亲，否则函数值为 “空”。

LeftChild(T,cur_e)   初始条件：树 T 存在， cur_e是 T 中某个结点。

操作结果：若 cur_e是T 的非叶子结点，则返回它的最左孩子，否则返回 “空”。

RightSibling(T,cur_e)    初始条件：树 T 存在， cur_e是 T 中某个结点。

操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则函数值为 “空”。

InsertChild(&T,p,i,c)

初始条件：树 T 存在， p 指向 T 中某个结点， 1<=i<=p 所指结点的度+ 1, 非空树 c 与 T 不相交。

操作结果：插入c为T中 p 指结点的第l.棵子树。

DeleteChild(&T,p,i)

初始条件：树 T 存在， p 指向 T 中某个结点， 1<=i<=p 指结点的度。

操作结果：删除T中 p 所指结点的第l.棵子树。

TraverseTree(T)     初始条件：树T存在。

操作结果：按某种次序对T的每个结点访问一次。

) ADT Tree

1. 二叉树的基本原理

1. .二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
2. 特性：二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。
3. 抽象数据类型定义；

 ADT BinaryTree{

数据对象D: D是具有相同特性的数据元素的集合。

数据关系R:若 D=<空集, 则 R=<空集, 称 BinaryTree 为空二叉树；

R={H}, H是如下二元关系：

①在 D 中存在唯一的称为根的数据元素 root, 它在关系 H 下无前驱；

②若 D-{root} -,6¢, 则存在 D-{root}={D1, Dr}, 且 D1 nDr=<空集;

③(D1, { H1}) 是一棵符合本定义的二叉树，称为根的左子树， (Dr, {Hr｝）是一棵符合本定义的二叉树，称为根的右子树。

基本操作 P:

InitBiTree(&T)

操作结果：构造空二叉树T。

DestroyBiTree(&T)

初始条件：二叉树T存在。

操作结果：销毁二叉树T。

Crea七eBiTree(&T,definition)

初始条件； definition 给出二叉树 T的定义 。

操作结果：按 definition 构造二叉树 T。

ClearBiTree(&T)

初始条件：二叉树T存在。

操作结果：将二叉树T清为空树。

BiTreeEmpty(T)

初始条件：二叉树T存在。

操作结果：若 T 为空二叉树，则返回 true, 否则 false。

BiTreeDepth (T)

初始条件：二叉树T存在。

操作结果：返回T的深度。

Root(T)

初始条件：二叉树T存在。

操作结果：返回T的根 。

Value(T,e)

初始条件：二叉树 T存在，e是 T中某个结点。

操作结果：返回e的值。

Assign(T,&e,value)

初始条件：二叉树T存在， e是T中某个结点。

操作结果：结点 e 赋值为 value。

Parent(T,e)

初始条件：二叉树 T存在，e是 T中某个结点。

操作结果：若 e是T的非根结点，则返回它的双亲，否则返回 “空”。

LeftChild(T,e)

初始条件：二叉树T存在， e是T中某个结点。

操作结果：返回e的左孩子。若e 无左孩子，则返回 “空”。

RightChild(T,e)

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回 e的右孩子。若 e 无右孩子，则返回 “空”。

LeftSibling (T, e)

初始条件：二叉树T存在， e是T中某个结点。

操作结果：返回 e的左兄弟。若 e是T的左孩子或无左兄弟，则返回 “空”。

RightSibling(T,e)

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回 e的右兄弟。若 e是T的右孩子或无右兄弟，则返回 “空”。

3.关键算法设计原理及性能影响因素分析

求二叉树的深度本质上就是二叉树的遍历过程。分别遍历左右子树，取大的即可二叉数树深度 = max(左子树深度，右子树深度) + 1。二叉树的非递归遍历即设计对二叉树的先序遍历、中序遍历和后序遍历。如果能够同时知道先、中序遍历或者同时知道后、中序遍历即可推出二叉树的结点分布。层次遍历利用队列先进后出的特征，先让根结点入队，接着开始循环一下操作，出队，出队的结点左孩子，右孩子入队。直到队列为空。

求二叉树的叶子结点数就是要利用递归解法：如果二叉树为空，返回0。如果二叉树不为空且左右子树为空，返回1。如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子结点个数。

三、实验方案设计

1.存储方案设计

分析：（1）顺序存储结构：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。

    

1. ）链式存储结构：用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含3个域：数据域data，左指针域lchild和右指针域rchild。
   二叉树的链式存储结构描述如下：
                typedef struct BiTNode{
                    ElemType data;         //数据域
                    struct BiTNode    *child, *rchild;  //左右孩子指针
                }BiTNode, *BiTree;

        

二叉树的顺序存储，寻找后代节点和祖先节点都非常方便，但对于普通的二叉树，顺序存储浪费大量的存储空间，同样也不利于节点的插入和删除。因此顺序存储一般用于存储完全二叉树。链式存储相对顺序存储节省存储空间，插入删除节点时只需修改指针，但寻找指定节点时很不方便。不过普通的二叉树一般是用链式存储结构。

2.算法的设计和实现

（1）先序遍历

void PreOrder (BiTree T) {
if (T!=NULL) {
visit (T):             //访问根结点
PreOrder (T-›lchild);  //递归遍历左子树
PreOrder (T-›rchild);  //递归遍历右子树

     }

     }

二叉树遍历所有的方法都可以通过栈结构实现，其中先序遍历是先把根节点押入栈内，然后pop()并记录，然后压入当前节点的右节点和左节点，循环这一过程。

（2）中序遍历

      void InOrder (BiTree T) {
if (T!=NULL) {
InOrder (T-›lchild) ;    //递归遍历左子树
visit (T):               //访问根结点
InOrder (T-›rchild) ;   //递归遍历右子树

}

}

中序遍历的非递归方法先把左节点压入栈中， 当左节点全部压入，记录当前节点，并从当前节点的右节点开始循环。

1. 后序遍历

      void PostOrder (BiTree T) {
if (T!=NULL) {
Post0rder (T-›lchild);    //递归遍历左子树
PostOrder(T-›rchild):      //递归遍历右子树
visit (T);                //访问根结点

            }

             }

先把根节点放入栈中，然后pop出插入可变数组的头部，再压入根节点的左节点和右节点即可。正好和先序遍历相反。

3.测试方案

①测试方式：输入一系列数据，用0代表空结点，返回二叉树的深度和叶子结点数

  输入测试数据：2 5 0 0 8 9 0 0 0

  测试结果：3 2

测试方式：输入一系列数据，用0代表空结点，进行二叉树的先序遍历

②输入测试数据：7 9 6 0 0 7 5 0 0 0 1 3 0 1 0 0 3 0 0

  测试结果：7 9 6 7 5 1 3 1 3

③输入测试数据：12 6 8 1 0 0 0 5 0 0 9 7 15 0 0 4 0 0 11 0 0

测试结果：12 6 8 1 5 9 7 15 4 11

测试方式：输入一系列数据，用0代表空结点，进行二叉树的中序遍历

④输入测试数据：2 6 4 0 0 9 7 0 0 0 1 5 0 4 0 0 2 0 0

  测试结果：4 6 7 9 2 5 4 1 2

⑤输入测试数据：12 6 8 1 0 0 0 5 0 0 9 7 15 0 0 4 0 0 11 0 0

测试结果：1 8 6 5 12 15 7 4 9 11

测试方式：输入一系列数据，用0代表空结点，进行二叉树的后序遍历

⑥输入测试数据：5 8 6 0 0 3 2 0 0 0 4 3 0 6 0 0 9 0 0

  测试结果：6 2 3 8 6 3 9 4 5

⑦输入测试数据：12 6 8 1 0 0 0 5 0 0 9 7 15 0 0 4 0 0 11 0 0

  测试结果：1 8 5 6 15 4 7 11 9 12

实验: 

• 概述

本次实验的内容是与树和二叉树相关。包括对二叉树的一系列操作、如求树的深度和叶子结点数、二叉树的遍历和二叉树的非递归遍历等内容。在本次实验中，首先采用递归的思想创建二叉树各结点，输入零代表创建空树。而创建非空树的过程可以归结为先创建根节点，输入其数据域值；再创建左子树；最后创建右子树；左右子树递归即可完成创建。然后键盘输入数据存入表中，通过不同的数字输入，实现对二叉树的遍历等操作。二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点N，左子树L，右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序(NIR)、中序(INR)和后序(LRN)三种遍历算法，其中“序”指的是根结点在何时被访问。

二、实验过程

1.调试分析

（1）在进行if语句的运用时，{}的使用不正确，导致程序无法运行。

        

（2）由于在输入代码时误将赋值操作符写成了等于操作符，导致运行错误（正确输出的数据应为3 2 但却错误输出2 2）。

（3）.对于指针内部的变量引用，要用箭头符号而不是点符号，因此产生了错误，于是在原来程序中的“->”改为了“.”操作符号，最后运行成功。

（5）返回的括号写错误，在c语言中，return返回的两个内容相加，不需要加括号。加了括号使其蕴含的意思也发生改变，所以会进行报错。

       

2.测试过程

对于不同的实验应该有不同的输入，所以将实验分为三个大部分，一个实验对应一个部分，并且每一部分应有不同的测试数据。

实验一：二叉树求深度和叶子数

该实验主要考察对二叉树的操作部分，因此要有大量的的测试数据才能够进行测量。这里只进行两个测试数据的结果展示。

第一组测试数据：输入一系列数据，用0代表空结点，返回二叉树的深度和叶子结点数。 2 5 0 0 8 9 0 0 0，构造这样一棵二叉树，求它的深度和叶子数。

它的二叉树表示为：

运行结果如下图：

     

分别遍历左右子树，取大的即可二叉数树深度 = max(左子树深度，右子树深度) + 1。如果二叉树为空，返回0。如果二叉树不为空且左右子树为空，返回1。如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子结点个数。

由以上两个图可以得到，运行结果和预期结果完全相符，所以该程序测试完毕且无误。

实验二：二叉树的非递归遍历 

二叉树的非递归遍历即设计对二叉树的先序遍历、中序遍历和后序遍历。如果能够同时知道先、中序遍历或者同时知道后、中序遍历即可推出二叉树的结点分布。

测试数据：12 6 8 1 0 0 0 5 0 0 9 7 15 0 0 4 0 0 11 0 0

构建的二叉树为：

运行结果如下图：

测试数据：1 3 5 7 0 0 0 0 8 0 5 2 0 0 0

构建的二叉树为：

运行结果如下图：

   

  

这两组数据所构建的二叉树进行的先序遍历、中序遍历和后序遍历均与输出的相符，表示实验的程序正确。

三、评价分析

1.实验结果分析

实验过程中，对程序的调试基本达到了预期的效果，对于二叉树叶子结点和深度的计算，先建立了一棵二叉树，然后在程序中运行，通过不断地调试改错，最终获得的结果和预期的一样。进行二叉树的遍历实验时，中序遍历的写法相对简单，而且用到了栈，三种遍历得到的结果，由中序遍历和另外任意一种遍历结果都能反推二叉树的形状，从而验证程序是否正确。所有的结点都可看作父结点（叶子结点可看作两个孩子为空的父结点）。实验结果显示出来了几种遍历的结果，但是也有可以改进的地方，比如，可否直接特殊地标出二叉树的根结点元素，这样可以方便地检验程序输出的结果的准确性。其中，先找出先序遍历的第一个元素，即为根结点元素，然后再在中序遍历中找到这个根结点元素，从而确定二叉树根结点的左右子树。整体上讲这次实验的结果无论是二叉树的叶子结点还是根结点的元素的求解以及二叉树的遍历都较为成功。

2.算法性能评价

遍历二叉树的算法中的基本操作是访问结点，则不论按哪一种次序进行遍历，对n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n, 则空间复杂度也为O(n)。递归遍历的优点是算法简单明了，缺点也十分明显：对于栈的消耗比较大。尤其是在嵌入式应用中，嵌入式处理器资源往往有限。每次递归调用，都会涉及到压栈。当树的深度比较大时，对于栈的消耗会变得非常严重，很有可能造成栈的溢出。因此，二叉树的非递归遍历方法就显得非常有实际应用价值。下面是非递归遍历的算法，这里使用了数据结构栈，利用其先进后出的特点，用结点入栈出栈过程手工模拟递归调用过程中的栈操作。相对于先序遍历，中序遍历要求只是将左子树和根结点的顺序对调了一下，这正符合栈的特点。后进先出本身就是一个顺序反转过程。入栈时遍历，就是前序，出栈时遍历就是中序遍历。后序遍历要求根结点在左右子树均遍历完成后才能遍历，更确切的条件就是，根结点要在其右子树遍历完成后紧接着遍历。这样就需要保存上一次遍历的结点信息。再者，栈中保存了未遍历的树的全部信息。后序遍历要求：先左子树，再右子树最后根结点，所以在右子树没有遍历完之前，根结点不能出栈。这一点其实也是递归后序遍历中所存在的过程。在具体代码中，相对于前序和中序又存在一个：右子树没有遍历时，结点需再次入栈的过程。出栈时如果满足为叶子节点，或者该结点的右孩子已经遍历，则遍历。

• 总结与体会

   二叉树是一类非常重要的非线性数据结构，也是以分支关系定义的层次结构。二叉树的应用非常广泛，比如源程序的语法结构等。二叉树的优点在于快速查找，可以在相对较少的步骤中搜索包含大量信息的树，可以提升排序和检索的效率。二叉树既有链表的好处，也有数组的好处，可以应用于处理大批量的动态数据。但是顺序存储可能会浪费空间(在非完全二叉树的时候)，但是读取某个指定的节点的时候效率比较高。链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低。经过这次实验，对于二叉树的遍历的相关代码已基本熟悉，算法知识得到了复习与巩固。在写代码的过程与调试中，在解决问题过程中，丰富了个人编程的经历和经验，提高了个人解决问题的能力。但是在编写程序的过程中关于一些语法还是不够熟悉，容易出现错误这也影响了对数据结构这门课的理解和掌握。所以应该把C语言的题和数据结构结合起来练习巩固。