生成树是无向图的一个子集，它通过最少的边将所有顶点连接起来。如果图中所有顶点都连接，则至少存在一个生成树。在一个图中，可能存在多个生成树。最小生成树最小生成树 (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算法先序遍历(根)：开始    如果根不为空，则       打印根的值       先序遍历(根的左子树)       先序遍历(根的右子树)    结束 if 结束示例  实时演示#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算法后序遍历(根)：开始    如果根不为空，则       后序遍历(根的左子树)       后序遍历(根的右子树)       打印根的值    结束 if 结束示例  实时演示#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算法层序遍历(根)：开始    定义队列 que 用于存储节点    将根插入队列。    当队列不为空时，执行       item := 队列前端的项目       打印 item 的值       如果 item 的左子节点不为空，则          将 item 的左子节点插入队列       结束 ... 阅读更多

在本节中，我们将了解遍历二叉搜索树中存在的键的不同遍历算法。这些遍历是中序遍历、先序遍历、后序遍历和层序遍历。假设我们有一棵这样的树 -中序遍历序列将如下所示 - 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算法中序遍历(根)：开始    如果根不为空... 阅读更多

在本节中，我们将了解二叉树数据结构的一些重要属性。假设我们有如下所示的二叉树。一些属性是 -第 'l' 层的最大节点数为 $2^{l-1}$ 。此处，层级是从根节点到节点的路径上的节点数，包括根节点本身。我们认为根节点的层级为 1。高度为 h 的二叉树中存在的最大节点数为 $2^{h}-1$ 。此处，高度是从根节点到叶节点路径上的最大节点数。在这里，我们认为一棵树的高度为... 阅读更多

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