97. 一网打尽面试中常被问及的8种数据结构（三）

6.树

树是一种层次结构，其中数据按层次进行组织并链接在一起。此结构与链接列表不同，而在链接列表中，项目以线性顺序链接。

在过去的几十年中，已经开发出各种类型的树木，以适合某些应用并满足某些限制。一些示例是二叉搜索树，B树，红黑树，展开树，AVL树和n元树。

二叉搜索树

顾名思义，二进制搜索树（BST）是一种二进制树，其中数据以分层结构进行组织。此数据结构按排序顺序存储值，我们将在本课程中详细研究这些值。

二叉搜索树中的每个节点都包含以下属性。

key：存储在节点中的值。

left：指向左孩子的指针。

右：指向正确孩子的指针。

p：指向父节点的指针。

二叉搜索树具有独特的属性，可将其与其他树区分开。此属性称为binary-search-tree属性。

令x为二叉搜索树中的一个节点。

如果y是x左子树中的一个节点，则y.key≤x.key

如果y是x的右子树中的节点，则y.key≥x.key

Fig 6. Visualization of Basic Terminology of Trees.

树的应用

• 二叉树：用于实现表达式解析器和表达式求解器。
  
• 二进制搜索树：用于许多不断输入和输出数据的搜索应用程序中。
  
• 堆：由JVM（Java虚拟机）用来存储Java对象。
  
• Trap：用于无线网络。
  

7.堆

堆是二叉树的一种特殊情况，其中将父节点与其子节点的值进行比较，并对其进行相应排列。

让我们看看如何表示堆。堆可以使用树和数组表示。图7和8显示了我们如何使用二叉树和数组来表示二叉堆。

Fig 7. Binary Tree Representation of a Heap

Fig 8. Array Representation of a Heap

堆可以有2种类型。

• 最小堆-父项的密钥小于或等于子项的密钥。这称为min-heap属性。根将包含堆的最小值。
  
• 最大堆数-父项的密钥大于或等于子项的密钥。这称为max-heap属性。根将包含堆的最大值。
  

堆的应用

• 用于实现优先级队列，因为可以根据堆属性对优先级值进行排序。
  
• 可以在O（log n）时间内使用堆来实现队列功能。
  
• 用于查找给定数组中k个最小（或最大）的值。
  
• 用于堆排序算法。
  

8.图

一个图由一组有限的顶点或节点以及一组连接这些顶点的边组成。

图的顺序是图中的顶点数。图的大小是图中的边数。

如果两个节点通过同一边彼此连接，则称它们为相邻节点。

有向图

如果图形G的所有边缘都具有指示什么是起始顶点和什么是终止顶点的方向，则称该图形为有向图。

我们说（u，v）从顶点u入射或离开顶点u，然后入射到或进入顶点v。

自环：从顶点到自身的边。

无向图

如果图G的所有边缘均无方向，则称其为无向图。它可以在两个顶点之间以两种方式传播。

如果顶点未连接到图中的任何其他节点，则称该顶点为孤立的。

Fig 9. Visualization of Terminology of Graphs

图的应用

用于表示社交媒体网络。每个用户都是一个顶点，并且在用户连接时会创建一条边。

用于表示搜索引擎的网页和链接。互联网上的网页通过超链接相互链接。每页是一个顶点，两页之间的超链接是一条边。用于Google中的页面排名。

用于表示GPS中的位置和路线。位置是顶点，连接位置的路线是边。用于计算两个位置之间的最短路径。