树和图的区别

在了解树和图这两种数据结构之前，我们应该先了解线性数据结构和非线性数据结构。线性数据结构是一种所有元素都按顺序存储并且只有单层的数据结构。相比之下，非线性数据结构是一种遵循层级结构的数据结构，即元素排列在多个层级上。

让我们来理解一下形成层级结构的数据结构。

在上面的图中，我们可以设想公司的层级结构，其中 A 代表公司的 CEO，B、C 和 D 代表公司的经理，E 和 F 代表团队领导，G 和 H 代表团队成员。这种类型的结构有多个层级，因此被称为非线性数据结构。

什么是树？

树是一种表示层级结构的非线性数据结构。树是连接在一起形成层级结构的节点的集合。

让我们看一些在树数据结构中使用的术语。

• 根节点：树数据结构中最顶层的节点称为根节点。根节点是没有父节点的节点。
• 节点的父节点：节点的直接前驱节点称为节点的父节点。这里的“前驱”指的是该特定节点之前的节点。
• 节点的子节点：节点的直接后继节点称为节点的子节点。
• 叶子节点：叶子节点是没有子节点的节点。它也称为外部节点。
• 非叶子节点：非叶子节点是至少有一个子节点的节点。它也称为内部节点。
• 路径：它是从源节点到目标节点的一系列连续边。这里的边是连接两个节点的链接。
• 祖先：从根到该节点路径上出现的、该节点的前驱节点称为祖先。
• 后代：从该节点到叶子节点路径上存在的、该节点的后继节点。
• 兄弟节点：具有相同父节点的子节点称为兄弟节点。
• 度：特定节点的子节点数量称为度。
• 节点深度：从根到该节点的路径长度称为节点的深度。
• 节点高度：从该节点到叶子节点的最长路径上的边数称为节点的高度。
• 节点层级：从根节点到给定节点的边数称为节点的层级。

注意：如果树中有 n 个节点，那么会有 (n-1) 条边。

树在内存中如何表示？

每个节点将包含三个部分：数据部分、左子树的地址和右子树的地址。如果任何节点没有子节点，则这两个链接部分都将为空值。

什么是图？

图是一种类似于树的数据结构，它是由一组称为节点（或顶点）的对象或实体组成的，这些节点通过一组边相互连接。树遵循一些规则来确定节点之间的关系，而图不遵循任何规则来定义节点之间的关系。图包含一组边和节点，并且边可以以任何可能的方式连接节点。

在数学上，它可以定义为一对有序集合，其中第一个集合是顶点集，第二个集合是边集。顶点用“V”表示，边用“E”表示。

G= (V , E)

这里我们指的是有序对，因为第一个对象必须是顶点集，第二个对象必须是边集。

在图中，每个节点都有一个不同的名称或索引来唯一标识图中的每个节点。下图显示了八个顶点，分别命名为 v1、v2、v3、v4、v5、v6、v7 和 v8。没有第一个节点、第二个节点、第三个节点等。节点没有排序。现在，我们将看到如何表示图中的边？边可以通过图中的两个端点来表示。我们可以将两个端点的名称写成一对，这代表了图中的一条边。

有两种类型的边

• 有向边：有向边将一个端点表示为起点，另一个点表示为终点。有向边是单向的。例如，如果有两个顶点 U 和 V，那么有向边将表示从 U 到 V 的链接或路径，但不存在从 V 到 U 的路径。如果我们想创建从 V 到 U 的路径，那么我们需要从 V 到 U 再有一条有向边。
  有向边可以表示为有序对，其中第一个元素是起点，第二个元素是终点。
• 无向边：无向边是双向的，意味着没有起点和终点。例如，如果有两个顶点 U 和 V，那么无向边将表示两条路径，即从 U 到 V 以及从 V 到 U。无向边可以表示为无序对，因为边是双向的。

树数据结构只包含有向边，而图可以同时包含这两种类型的边，即有向边和无向边。但是，我们考虑的图是所有边都是有向边或无向边。

图有两种类型

有向图：具有有向边的图称为有向图。

无向图：具有无向边的图称为无向图。有向图是所有边都是单向的图，而无向图是所有边都是双向的图。

树和图数据结构之间的区别。