生成树是无向图的一个子集，它通过最少的边连接所有顶点。如果图中所有顶点都已连接，则至少存在一个生成树。在一个图中，可能存在多个生成树。最小生成树最小生成树 (MST) 是连接加权无向图中所有顶点的边的子集，其总边权重最小。要推导出 MST，可以使用 Prim 算法或 Kruskal 算法。因此，我们将在本章中讨论 Prim 算法。正如…… 阅读更多

在这里，我们将了解图的 DFS 和 BFS 算法的不同应用。深度优先搜索 (DFS) 用于不同的位置。一些常见的用途是：如果我们在无权图上执行 DFS，它将为所有对最短路径树创建最小生成树。我们可以使用 DFS 检测图中的循环。如果在 BFS 期间得到一条后向边，则一定存在一个循环。使用 DFS，我们可以找到给定顶点 u 和 v 之间的路径。可以使用拓扑排序来安排给定作业之间依赖关系的作业。拓扑排序…… 阅读更多

在本节中，我们将了解什么是图数据结构及其遍历算法。图是一种非线性数据结构。它由一些节点及其连接的边组成。边可以是有向的或无向的。此图可以表示为 G(V, E)。下图可以表示为 G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A)})图具有两种类型的遍历算法。它们被称为广度优先搜索和深度优先搜索。广度优先搜索 (BFS)广度优先搜索 (BFS) 遍历是一种算法，…… 阅读更多

二叉搜索树是具有某些属性的二叉树。这些属性如下：每个二叉搜索树都是一个二叉树每个左子节点的值都小于根每个右子节点的值都大于根理想的二叉搜索树不会两次持有相同的值。假设我们有一棵这样的树：这棵树是一个二叉搜索树。它遵循所有提到的属性。如果我们以中序遍历模式遍历元素，我们可以得到 5、8、10、15、16、20、23。让我们看一段代码来了解我们如何实现它…… 阅读更多

在本节中，我们将了解二叉搜索树的先序遍历技术（递归）。假设我们有一棵这样的树：遍历序列将如下所示：10、5、8、16、15、20、23算法先序遍历(root)：开始如果root不为空，则打印root的值先序遍历(root的左子树)先序遍历(root的右子树)结束如果结束示例实时演示#include using namespace std; class node{ public int h_left, h_right, bf, value; node *left, *right; }; class tree{ private node *get_node(int key); ... 阅读更多

在本节中，我们将了解二叉搜索树的后序遍历技术（递归）。假设我们有一棵这样的树：遍历序列将如下所示：8、5、15、23、20、16、10算法后序遍历(root)：开始如果root不为空，则后序遍历(root的左子树)后序遍历(root的右子树)打印root的值结束如果结束示例实时演示#include using namespace std; class node{ public int h_left, h_right, bf, value; node *left, *right; }; class tree{ private node *get_node(int key); ... 阅读更多

在本节中，我们将了解二叉搜索树的层序遍历技术。假设我们有一棵这样的树：遍历序列将如下所示：10、5、16、8、15、20、23算法层序遍历(root)：开始定义队列que来存储节点将root插入到que中。当que不为空时，执行item := 队列前端的item打印item的值如果item的左子树不为空，则将item的左子树插入到que中结束如果…… 阅读更多

在本节中，我们将了解遍历二叉搜索树中存在的键的不同遍历算法。这些遍历是中序遍历、先序遍历、后序遍历和层序遍历。假设我们有一棵这样的树：中序遍历序列将如下所示：5 8 10 15 16 20 23先序遍历序列将如下所示：10 5 8 16 15 20 23后序遍历序列将如下所示：8 5 15 23 20 16 10层序遍历序列将如下所示：10、5、16、8、15、20、23算法中序遍历(root)：开始如果root不…… 阅读更多

在本节中，我们将了解二叉树数据结构的一些重要性质。假设我们有这样的二叉树。一些属性是：第“l”级的最大节点数为$2^{l-1}$。这里级别是从根到节点的路径上的节点数，包括根本身。我们认为根的级别是 1。高度为 h 的二叉树中存在的最大节点数为$2^{h}-1$。这里高度是从根到叶路径上的最大节点数。我们认为…… 阅读更多

在这里，我们将了解如何在计算机内存中表示二叉树。有两种不同的表示方法。这些是使用数组和使用链表。假设我们有这样的树：数组表示通过使用层序方式扫描元素来存储树数据。因此，它逐层存储节点。如果缺少某些元素，则会为其留出空白空间。上面树的表示如下：12345678910111213141510516-81520-------23索引 1 存储根，它有两个子节点 5 和 16，它们分别位于位置 2 和 3。一些子节点是…… 阅读更多