树与图的简单遍历算法

树与图的简单遍历算法

闵俊齐

重庆第二外国语学校重庆400065

摘要：树与图是两种重要的数据结构，而树可以说是一种特殊的图，它的两两结点之间存在唯一简单路径。利用其特殊性质，人们创造了许多算法来处理数据结构问题和程序调用问题。而树与图的遍历算法也是数据结构中重要的算法之一。本文从树与图的概念出发，简单的介绍了树与图的主要存储方式，并重点对二叉树的简单遍历算法、哈夫曼树的生成和图的深度优先遍历及广度优先遍历做出了介绍。

关键词：数据结构；二叉树；图；遍历算法

1.树与图的概念

树是一种数据结构，是由n（n≥0）个结点构成的具有明显层次关系的有限集合。一棵树一般由一个根节点和若干个子结点构成。结点与结点之间具有明显的并列或层次关系，这种层次关系称为父子关系。在一棵树中，没有父结点的结点被称为根结点。树有几个重要的概念，以下做出简单的介绍——树的度：某个结点拥有的子树的数量称为这个结点的度，度为零的结点也叫做叶结点，而度不为零的结点叫做分支结点。树的深度：一棵树的根结点的层次为1，其他结点的层次是其父结点的层次加1。一棵树里最大的层次的值被称为这棵树的深度。树有无序树，有序树，二叉树等。其中二叉树是每个结点最多有两个子结点的树，每个结点的子树通常被称为“左子树”和“右子树”，故二叉树中每个结点的度的最大值为2，而又有左右之分，二叉树中结点的次序不能任意颠倒。除最后一层的叶结点没有子结点外，其余每一层的每个结点都具有两个子结点的二叉树称为满二叉树。如果存在一个深度为h的二叉树，它的除h层外其余各层（1~h-1）的结点数都达到了最大值，并且它的第h层的结点全部集中在树的左边，这种二叉树就被称为完全二叉树。完全二叉树是由满二叉树引申出来的，它是一种效率很高的数据结构。本文后部分将会介绍二叉树的简单遍历算法。

图由若干个顶点组成的有限非空集合和各个顶点的边构成，通常表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。图数据结构主要研究形状和图形数据元素之间的关系。它必须反映数据所对应的元素之间的几何关系和拓扑关系。图依照边的方向可分为有向图和无向图。有向图由顶点和弧构成。弧有弧尾和弧头，带箭头的一边称为弧头。图结构与树结构相比较，图中的任意两个元素都有可能相关。而对某个结点而言，树下层可能有多个元素，上层只有能一个元素，复杂度比树大[1]。

2二叉树与图的储存方式

2.1二叉树的储存方式

二叉树有两种储存方式：顺序存储和链式存储。

顺序储存就是按照完全二叉树的结点层次顺序存储的一种只适用于完全二叉树的储存方式，且在最坏的情况下，k个结点的单支数却只需要长度的-1的一维数据。这种储存需要一个完全连续地址，所以会占用许多的储存空间。

在二叉树中，每个结点信息一般都由一下几个部分构成：该结点的数据元素（Data）、指向左子树的指针（Lchild）和指向右子树的指针（Rchild）。利用指针，我们可以很好的存储二叉树。若使用二叉链表，每个结点的结构如图1（a）所示。一般可以（L,D,R）来表示。在三叉链表中，可表示每个结点的父结点，结构如图1（b）所示。一般可以（L,D,P,R）来表示[5]。链式储存不需要完全连续地址，节约储存空间[2]。

图2

3.二叉树的遍历算法及哈夫曼树的生成

3.1二叉树的遍历算法

遍历，是指用某种方法沿着某条路对每一个元素做一且仅一次访问，它是二叉树的重要运算之一。二叉树的主要有三种访问方式：先序遍历、中序遍历、后序遍历。具体实现过程如下：

先序遍历：先序遍历是按照“根节点→左子树→右子树”的顺序来访问一个二叉树。以下图为例，先序遍历的结果为“ABDECFG”。获得该结果的思维过程是：先访问根节点A，A有左右两个子树，根据先左后右的顺序，所以访问B。因为B中也有左右两个子结点，递归调用，访问结点D。D没有子结点，所以接下来访问B的右结点E。此时，左子树以访问完毕，开始访问右子树。以相同的规则，接下来依次访问C,F,G。

中序遍历：中序遍历按照“左子树→根节点→右子树”的顺序来访问二叉树。依然以下图为例，中序遍历的结果是“DBEAFCG”。获得该结果的思维过程是：从根结点A开始，访问其左子树。将根结点A的左子树单独拿出来看，B作为根结点也具有左右子树，而其左子树只具有一个结点C，所以先访问C，再访问B，接着访问E。此时，A的左子树已全部访问，故接下来访问A和它的右子树。根据相同的规则，后面的访问顺序为F,C,G。

后序遍历：后序遍历按照“后序左子树→后序右子树→根节点”的顺序来访问二叉树。还是以下图为例，后序遍历的结果是“DEBFGCA”。获得该结果的思维过程是：从左到右，从叶结点到父结点，依次访问树中的结点，顺序为D,E,B,F,G,C。最后访问根结点A。

三种遍历方法的遍历过程中查找的节点及路线是一样的，只是访问的顺序不同[3]。

3.2哈夫曼树的生成

哈夫曼树又称最优二叉树。给定n个权值{W1,W2,……Wn}作为n个子结点来构建一棵二叉树，如果这棵二叉树的带权路径达到最小，就称这样的具有最小带权路径的二叉树为最优二叉树。

哈夫曼树的实现过程如下简述：

（1）根据给定的n个权值{W1,W2,……Wn}来构造出由n棵二叉树组成的集合N={C1,C2,……Cn}，在二叉树集合N中的每棵二叉树Ci中只有一个权值为Wi的根结点，它的左右子树皆为空。

（2）在集合N中选取两棵权值最小的二叉树，将这两棵二叉树分别作为左子树和右子树来重新构建一棵新的二叉树，这棵新的二叉树的权值为其左右子树的根结点的权值之和。

（3）于集合N中删除在步骤（2）中使用的两个二叉树，并将步骤（2）中新创建的一个二叉树加入集合N。

（4）重复步骤（2）和（3），直到集合N中只剩下一棵二叉树，这棵二叉树便是所求的最优二叉树[4]。

如图1所示。我们给定一组权值{9,5,3,7}，以其来构造一棵最优二叉树。根据以上提到的步骤沿（a）、（b）、（c）、（d）便可构造出一棵最优二叉树。

建立最优二叉树后便使用哈夫曼编码进行储存。这样可以节约内存，提高效率。

在最优二叉树建立后从根结点到所以叶结点的每个左分支为0，右分支为1，让后从上到下写出每个结点的哈夫曼编码。图1中每个结点的哈夫曼编码为：A-0B-110C-111D-10。值得注意的是，由于二叉树的左右子树交换对其父结点的权值大小没有影响，所以给定一组权值所创造的最优二叉树并不是唯一的。

最优二叉树的主要表现具有直观性，对其编码进行通讯可以极大的提高信息通道的利用率，降低信息传递时间，降低信息传递成本[2]。

4.图的遍历

图的遍历算法主要有深度优先遍历和广度优先遍历。

深度优先搜索是树的先根遍历的推广，从图中任意一点V开始，访问V，再依次从V的未被访问的邻接点出发深度优先遍历图，直到图中所以和V路径相通的点都被访问到，若还有顶点未被访问，则从另一未访问的点出发进行深度优先遍历。如在图二中，先从顶点1开始访问，与顶点1相邻的顶点为顶点2和顶点4，我们选取顶点2作为下一个访问点，这之后访问顶点5，最后访问顶点3。此时，本侧的访问结束，但顶点1还有与之相邻的未访问的顶点，于是接下来访问顶点4，到此为止，改图的所有结点都完成了访问，于是该图的遍历就结束了。该图深度优先遍历顺序总结为：1→2→5→3、4。

广度优先搜索是树的按层遍历的类似。从图中任意一点V开始，访问V，再依次从V的未被访问的邻接点出发依次访问它们的邻接点，并使先被访问到的邻接点先于后被访问顶点的邻接点被访问，直到图中所以的顶点被访问。如图2中广度优先遍历的顺序为：14253。

参考文献

[1]寇斌.图在计算机中的存储结构[J].信阳农林学院学报,2002,12(1):91-92.

[2]陈桂英,王亚鹏.哈夫曼树及其应用[J].河南科技,2014(24):256-257.

[3]刘洋.一种统一的二叉树结构遍历算法及其实现[J].赣南师范大学学报,2004,25(3):10-13.

[4]韩相军,郭春英.浅谈哈夫曼树及其应用[J].濮阳教育学院学报,2001(03):45-49.

[5]张静,邬恩杰.二叉树的二叉链表存储结构的构造算法[J].电脑编程技巧与维

护,2018(05):59-60+63.