胡承欣

摘 要：自计算机出现以来，人们就开始尝试将生活中遇到的问题在计算机中抽象出来并解决，因此出现了数据结构的概念，而树是数据结构中十分重要的一种，目前应用十分广泛。本文从树的结构及概念入手，首先介绍了数据结构的概念，以及二叉树的基本知识，接着重点介绍了二叉树在计算机中的顺序存储和链式存储方式，并详细介绍了二叉树的先根遍历算法以及霍夫曼树的构建方法，最后对全文进行了总结。

关键词：数据结构;二叉树;存储方式;遍历算法;霍夫曼树

中图分类号：TP273 文献标识码：A 文章编号：1671-2064（2019）02-0056-02

1 树的结构及其概念

1.1 數据结构的主要分类

数据结构实质上是数据的存储形式，在数据结构中较重要的有数组，线性表，树等[1]。数组是数据结构中较为常见的一种，它是有序的元素序列，表示有限个相同类型元素的集合。在一个数据集合中，每一个数据元素对应于一个存储单元，也称之为数据结点，简称结点。而树就是由有限结点组成的一个具有层次关系的集合，结点则是树的层次性的体现者。在数据结构中出现的树并非我们生活中所提及的自然之树，只是因为其像一棵倒立的树，故称之为树。

1.2 二叉树简介

上文提到的树有很多分类，如二叉树、有序或无序树等。二叉树是指在整个树中每个结点最多只有两个子结点的树结构，是树结构中最重要也是最基础的结构。二叉树含有完全二叉树，满二叉树等。完全二叉树与满二叉树又有一些区别。完全二叉树是指除最后一层外，其余各层达到该层的最大结点数，若最后一层不满，则最后一层的所有结点都靠左排，而满二叉树是指所有结点都达到该层的最大结点数，在满二叉树中每层的最大结点数为2n-1。

完全二叉树与满二叉树是包含关系，即完全二叉树包含了满二叉树，但满二叉树无法包含完全二叉树。本文重点介绍的为二叉树相关的内容。

2 二叉树的主要存储方式

在计算机能够对树进行一系列的操作之前，我们需要知道二叉树的存储方式是什么。我们将需要存储的元素比作需要存取的衣物，将衣柜比作内存区域，而存衣物可以有不同的方法，不同的方法对找到不同的衣物的快慢不同，同样的数据的存储中存在不同的存储方式，我们需要根据实际情况来选择。在二叉树的存储中主要有两种存储方式，即顺序存储与链式存储[2]。

2.1 顺序存储

顺序存储的定义为：在计算机中用存储单元存储相应的元素，存储单元的在内存地址上是连续的，且被存储的元素在逻辑上也是连续的，如一维数组的从左至右的所有元素。例如：int arrary[ ]={3，4，5，6，7，8}，在该数组中有6个元素，对应了6个存储单元，该6个存储单元在位置上是连续的，则该存储方式为顺序存储。从例子我们可以知道array[0]=3，而与它相邻的则是array[1]=4。在顺序存储中，想访问其中的元素其实很容易，因为它们的物理位置是连续的。所以当我们按照顺序存储数据时，我们会根据自己的需求来存放数据。对二叉树而言，顺序存储用地址连续的存储单元按照从上至下，从左至右的顺序存储结点元素。在顺序存储中的存储规则为：将其每个结点与完全二叉树上的结点相对应，将结点元素存储在一维数组中。

2.2 链式存储

在数据存储中还有一种存储方式叫链式存储，其定义为：在计算机中用一组任意的存储单元存储线性表中的元素。链式存储结构的存储方式不要求每个数据元素物理位置相邻，也就是说它的物理地址位置关系是随机的，不像顺序存储那样有规律。但为了方便寻找与其中一个元素逻辑相邻的元素的物理位置，我们需要在定义链式存储结构时还需定义一个保存与其逻辑相邻元素的信息的指针域，在二叉树的链式存储中，给每个结点定义相同的链表结构，每个结点包含它本身的数据域和指向下一个结点的指针域。如二叉树的二叉链表，就包含数据域和指向左右孩子的指针域。（总而言之，若其中一个元素值称为数据域，则与它相邻逻辑关系相邻元素位置的信息称为指针域）。

2.3 二者的利弊分析

从上文对顺序存储和链式存储的分析可知，二者的特征几乎是不相同的，二者各有利弊。我们可以发现，在顺序存储中相邻元素的存储位置也是相邻的，是一块连续的内存，所以我们对数据进行插入或删除时，就会显得比较繁琐，对数据进行插入或删除时，需要进行对位置的填充，并且可能要移动一系列结点，比较浪费时间。而链式结构中位置可不连续，所以只要内存空间中有空位就可以存入。但链式存储结构失去了顺序表中的可直接访问的优点。所以在数据存储时，我们通常把握几个原则：（1）当我们需要对数据频繁查找，很少对数据进行改动时，选择顺序存储;（2）当线性表中我们不知道内存大小时，选择链式存储。对于二叉树来说，若该二叉树为完全二叉树，且对所存储的数据很少改动时，选用顺序存储，除此之外使用链式存储。

3 遍历算法

3.1 二叉树遍历算法简介

所谓遍历，是指按照一定的策略，依次访问树中的每个节点，且不重复访问;而遍历算法就是利用遍历的原理对树进行运算。在遍历算法中主要有三种遍历方式，即先根遍历，中根遍历，后根遍历，在进行运算时应根据实际问题选择遍历方式。将遍历算法区分成三种，是因为它们所遵循的遍历规则不同：主要根据访问根节点的先后来区分，先访问根节点再遍历左右子树为先根遍历，同理中间访问根节点为中根遍历，最后访问根节点为后跟遍历[3]。因此，遍历一个非空二叉树一般要进行以下几个操作：（1）访问结点（将节点当作根节点）;（2）遍历当前结点的左子树;（3）遍历当前结点的右子树。根据遍历算法的不同规则，以上三个操作的顺序也是不同的[4]。下文重点介绍先根遍历的原理与实现过程。

3.2 先根遍历的实现原理及过程

由于三种遍历算法仅仅执行顺序不同，本文仅详细介绍先根遍历的过程，根据上文介绍的先根遍历规则：先访问根节点，再遍历左子树，最后遍历右子树，我们以图1为例来分析：

在先根遍历中，我们首先要找到根结点，即A，记录A。根据先根遍历规则，所以再遍历A的左子树，A的左子树存在，找到C，记录C，把C当做根结点，遍历C的左子树;C的左子树存在，找到D，把D当做根结点，记录D，D的左子树不存在，根据规则，D的右子树存在找到B，把B当做根结点，记录B;返回D，D的右子树遍历完，返回C;C的左右子树遍历完，返回A;A的左子树遍历完，开始遍历A的右子树，找到E，记录E，把E当做根结点，开始遍历E的左子树，找到F，把F当做根结点，遍历F的左子树，左子树不存在，返回F并记录F，再遍历F的右子树，找到G，记录G，把G当做根结点，遍历G的左子树，找到I，把I当做根结点，遍历I的左子树，找到J;J为叶子结点，返回I，记录I;I无右子树，返回G;G无右子树，返回E并记录E;遍历E的右子树，找到H，记录H，返回E，A的右子树遍历完毕，所以整个二叉树先根遍历完毕。所以先根遍历的顺序为：ACDBEFGIJH。根据以上的遍历步骤，中根遍历的遍历顺序为：DBCAFJIGEH;后根遍历的遍历顺序：BDCJIGFHEA。

3.3 霍夫曼编码

二叉树在实际生活中的应用最普遍的额就是霍夫曼编码，因为霍夫曼树得到的编码长度不一，以发送电报为例，将经常出现的字符用较短长度的编码表示，不常出现的字符用较长编码表示，这就能够从整体上得到编码长度较短的电报。有利于提升电报发送的速度和效率。以下对霍夫曼编码进行详细说明：

首先我们将给定的4个根節点分别定义为a，b，c，d，需要选择两棵根节点权值最小的树，即c，d;将其组合为一个新的二叉树，其中c，d为该二叉树的左右结点，组成的二叉树的根节点权值为8;用e表示，将原有的c，d删除并将e放入集合中，比较权值大小，发现e和a为现集合权值最小的两棵树;将e和a组合成一个新的二叉树，权值为15;以此类推，直到F只有一棵树，见图2。

4 结语

在计算机中，树可以说是无处不在，并且在计算机的体系中，树的地位是无可替代的。因为计算机的核心是计算和储存，而树有效的解决了计算机的储存问题和计算时程序调用的问题。在数据结构方面，因为树的强大的储存查询功能，使查询数据时显得十分高效，树的空间复杂度利于数据储存;在计算机的算法方面，从前文所述中可以发现，没有树作为算法的模板，我们很难去描述一个算法，由此可见，树在计算机中的应用十分的广泛。

参考文献

[1] 朱战立，张选平.数据结构要点与解题——三一丛书[M].西安交通大学出版社，2006.

[2] 杨萌，李嵩嵩，苏姣.一种高效的二叉树存储结构[J].中国科技博览，2009（28）：228-228.

[3] 马靖善，秦玉平.顺序存储二叉树的遍历及其应用研究[J].渤海大学学报（自然科学版），2013（2）：172-176.

[4] 刘洋.一种统一的二叉树结构遍历算法及其实现[J].赣南师范学院学报，2004，25（3）：10-13.

[5] 王防修，刘春红.一种哈夫曼编码的改进算法[J].武汉轻工大学学报，2016，35（1）：88-91.