数据结构系列 - 图的遍历

与树类似,遍历也是图的一种重要的操作,图的遍历是访问图中每个顶点仅被访问一次的操作。图的遍历方式主要有两种:深度优先遍历和广度优先遍历。本节的主要学习内容包括图的深度优先遍历、图的广度优先遍历。

 

1. 图的深度优先遍历

 

深度优先遍历可定义如[......]

查看全文

数据结构系列 - 图

1. 前言

图是一种非线性数据结构,是一种更为复杂的数据结构,在图中,数据元素之间时多对多的关系,即一个数据元素对应多个直接前驱和多个直接后继元素。图的应用领域十分广泛,如化学分析,工程设计、遗传学、人工智能等。

2. 图的定义和相关概念

图是一种数据元素间为多对多关系的数据结构,[......]

查看全文

数据结构系列 - 哈夫曼树

1.树的路径长度
     树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。

2.树的带权路径长度(Weighted Path Length of Tree,简记为WPL)
结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。[......]

查看全文

数据结构系列 - 树的转换

1. 树的存储结构

    通常,树的存储结构有三种,双亲表示法、孩子表示法和孩子兄弟表示法。

(1)双亲表示法

双亲表示法是利用一组连续的存储单元存储树的每个结点,并利用一个指示器表示结点的双亲结点在树中的位置。

树的双亲表示法存储表示描述如下:

 

[......]

查看全文

数据结构系列 - 线索二叉树

1. 前言

n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。
这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded   BinaryTree)。根据线索性质的不[......]

查看全文

1 2 3