离散数学中树的应用

树

树可以被描述为节点的集合，称为图，节点之间有连接线或边。因此我们可以说线用于连接所有节点。树的第一个节点称为根。

树的各种应用如下所述

二叉搜索树

最重要的任务是搜索列表中的项目。我们的主要目标是通过实现搜索算法来有效地搜索有序的项目。我们可以使用二叉搜索树来完成此任务。在二叉搜索树中，每个顶点子节点被分为右子节点或子树或左子节点或子树。一个顶点（左子节点或右子节点）的两个子树只能有一个。树的每个顶点都有一个值，称为键。顶点的左子树用于包含具有各种键的顶点，但此键必须小于顶点的键。顶点的右子树用于包含具有各种键的顶点，但此键必须大于顶点的键。右子树和左子树都应该是二叉搜索树。

二叉树的插入方法

开始时，树只包含一个顶点，称为根。之后，我们将分配第一个项目，称为根的键。

例如：假设我们想插入 45。那么 45 将成为这棵树的根，如下所述

如果我们要将项目插入树中，首先，我们必须将其与根的键进行比较。如果它小于键，它将向左移动并被称为左子节点，否则，它将向右移动并被称为右子节点。根的左子节点和右子节点不能超过一个。

例如

• 假设根是 45，我们想插入 39 和 50。在这种情况下，首先，39 将与 45 进行比较。项目 39 小于 45，因此它将添加到 45 的左侧。项目 39 将被称为根 45 的左子节点。
• 之后，我们将插入 50。我们也会将其与 45 进行比较。项目 50 大于 45，因此它将添加到 45 的右侧。项目 50 将被称为根 45 的右子节点。

如果我们要插入更多项目，我们必须遵循上述步骤。这意味着我们将首先将项目与根进行比较。根据此比较，我们将它与左子节点或右子节点进行比较。如果新项目小于左子节点，它将移动到此左子节点的左侧，否则，它将移动到此左子节点的右侧。否则，我们将新项目与右子节点进行比较。如果新项目大于右子节点，它将移动到此右子节点的右侧，否则，它将移动到此右子节点的左侧。

例如

• 在上面的树中，假设我们想插入 33、41、47 和 52。在这种情况下，首先，我们必须遵循上述步骤。因此，我们首先尝试插入 33。为此，我们将 33 与 45 进行比较。它小于 45，因此它将向左移动。现在我们将 33 与 39 进行比较。它小于 39，因此它将向左移动，33 将添加到那里。
• 现在我们将插入 41。因此，我们将其与 45 进行比较。它小于 45，因此它将向左移动。现在我们将它与 39 进行比较。它大于 39，因此它将向右移动，41 将添加到那里。
• 之后，我们将插入 47。因此，我们将 47 与 45 进行比较。它大于 45，因此它将向右移动。现在我们将 47 与 50 进行比较。它小于 50，因此它将移动到 50 的左侧，47 将添加到那里。
• 现在我们将插入 52。因此，我们将 52 与 45 进行比较。它大于 45，因此它将向右移动。现在我们将 52 与 50 进行比较。它大于 50，因此它将移动到 50 的右侧，52 将添加到那里。

还存在另一种情况，即左子节点或右子节点也可以有多个子节点。在这种情况下，我们必须比较最后一个节点的所有项目，并根据它们的比较将其放在左侧或右侧。

例如

• 在上面的树中，假设我们想插入 31、35、37、40、44、46、48、51 和 55。在这种情况下，首先，我们必须遵循上述步骤。因此，首先，我们将尝试插入 31。为此，我们将 31 与 45 进行比较。它小于 45，因此它将向左移动。现在我们将 31 与 39 进行比较。它小于 39，因此它将向左移动并再次与 33 进行比较。它小于 33，因此 31 将添加到 33 的左侧。
• 现在我们将尝试插入 35。因此，我们将其与 45 进行比较。它小于 45，因此它将向左移动。现在我们将它与 39 进行比较。它小于 39，因此 35 将向左移动并再次与 33 进行比较。项目 35 大于 33，因此它将向右移动。
• 现在我们将尝试插入 37。因此，我们将其与 45 进行比较。它小于 39，因此它将向左移动并再次与 33 进行比较。它大于 33，因此它将向右移动，但 33 已经有右子节点 35。所以我们必须再次将 37 与 35 进行比较。它大于 35，因此 37 将添加到 35 之后。
• 将遵循相同的步骤插入所有剩余的项目。因此，40 将添加到 41 的左侧，44 将添加到 41 的右侧。当我们尝试插入 46 和 48 时，46 将插入到 47 的左侧，48 将插入到 47 的右侧。最后，如果我们尝试插入 51 和 55，那么 51 将插入到 52 的左侧，55 将插入到 52 的右侧。

二叉搜索树插入算法

步骤 1：开始

步骤 2：存储要插入的键 (x)

步骤 3：检查树中是否存在元素，如果不存在则转到步骤 4，否则转到步骤 5

步骤 4：将插入的键设为根节点

步骤 5：将 x 与根节点进行比较，如果小于则转到步骤 6，否则转到步骤 7，如果没有找到根节点则转到步骤 9。

步骤 6：元素到达左子树，重复步骤 5

步骤 7：元素到达右子树，重复步骤 5

步骤 8：插入键

步骤 9：停止

决策树

决策树是一种分层树结构或图表，它帮助我们选择各种行动。它主要用于决策目的。它是一种有根树，其中每个内部顶点对应一个决策。这些顶点包含每个决策的每个可能结果的子树。通向叶子顶点的路径对应于问题的可能解决方案。决策树包含类似树的结构，这就是为什么人们可以很容易地理解这棵树背后的逻辑。使用这棵树，人们可以很容易地做出决定，因为它将我们的问题分解成更小的部分，这有助于我们非常容易地做出决定。

基于属性值测试，决策树将子集分割成更小的子集。我们将以递归方式在每个派生子集上重复此过程。此过程称为递归分区。当目标变量和节点处的子集都具有相同的值时，递归过程将完成。如果我们不知道如何构建决策树分类器，那么我们不需要任何参数设置或领域知识。决策树可以轻松处理高维数据。决策树分类器的准确性非常好。

决策树的表示

在决策树中，我们将通过对实例进行排序来对它们进行分类。我们将它们从根排序到某个叶节点，这些叶节点用于提供实例的分类。要对实例进行分类，我们将从树的根节点开始。然后我们将测试此节点指定的属性。之后，我们将向下移动到与属性值对应的树分支。我们将对以新节点为根的子树重复此过程。

决策树的示例

假设我们收到一封录用信。现在我们必须决定是否接受这封信。

解决方案

对于这个问题，我们将创建一个决策树，它从根节点（即薪资属性）开始。现在我们的根节点将分为两个节点：一个决策节点，用于显示家庭和办公室之间的距离；一个叶节点，将根据相应的标签创建。之后，下一个决策节点将再次分为两个节点：一个决策节点，用于显示班车设施；一个叶节点。最后，决策节点将分为两个叶节点：一个用于接受的录用，另一个用于拒绝的录用。

博弈树

博弈树可以被描述为一种递归搜索函数，它用于检查策略游戏的所有可能走法。它还将检查结果，以便它们可以确定最佳走法。如果人工智能有一个场景，其中每个游戏回合的可能选择数量较少，并且不需要实时决策，在这种情况下，博弈树将对它们非常有用。通常，博弈树用于在棋盘游戏中找出最佳可能走法。为了解释博弈树，我们将使用井字棋游戏作为示例，如下所述

所以我们将从当前棋盘位置开始。现在我们必须检查计算机所做的所有可能走法。使用所有这些可能走法，我们将检查其他玩家可能做什么走法。之后，我们将查看计算机。现在计算机将翻转回来并为其他玩家和自己做出走法。计算机不断地做出走法直到游戏完成。对于每个可能的结果，计算机都会这样做，并且它会玩数千场游戏。最后，它通过查看这些游戏的输家和赢家的结果来找出最大的成功机会。如果我们正在玩的游戏没有结束，博弈树将无限延伸。

在博弈树中，我们检查每一个可能的走法以及对手的每一个走法。之后，我们会尝试查看他们多少步之后会赢。世界上有大量的可能游戏。在我们的例子中，我们使用一个井字棋游戏。在这个游戏中，第一步包含 9 种可能的走法。在第二回合中，它将减少到 8，然后是 7、6 等。因此，在这个游戏中，总共有 255,168 种可能的走法。在博弈树中，主要目标是查看所有这些走法并选择一个有所有机会赢得游戏的走法。

计算机在博弈树上的工作

计算机检查所有可能的走法，并开始评估一个获胜可能性高的走法。井字棋游戏有一个包含许多空白格子的网格。计算机可以填充任何空白格子。所以我们可以说空白格子的数量和可能走法的数量是相同的。当它们找到所有这些走法时，它们将对每个可能的走法创建一个循环，然后尝试确定该走法是否会导致胜利。

我们将博弈树扩展为分支，以确定走法是好是坏。我们将扩展树直到游戏完成或直到终端节点。树的最后一个节点称为终端节点。根据游戏的结果，分配终端节点的值。如果终端具有更高的值，那么结果对计算机来说将非常好，因为它们只有两种可能的结果，即赢或输。游戏的结果可以用 -1 和 1 的值表示。终端节点使用游戏规则并显示最大计算的支付值。终端节点、计算机走法和对手走法的图形表示如下所述

在下图中，我们可以看到终端节点的值已由节点 D、E、F 和 G 确定。为了找到其他节点的支付值，将使用 minimax 算法。如果节点显示计算机选择的走法，则该节点将显示为 Max。如果节点显示玩家选择的走法，则该节点将显示为 Min。最大节点的值成为其下方最高节点的值，并且与最小节点相同。

在这个例子中，D 的值是 4，E 的值是 1。B 的值是 1，这是 4 和 1 中最低的。如果我们在这张图片中向上移动，我们会看到每个节点都有一个值。我们将假设顶部节点 A 拥有其下方节点的最高或最大值。最高值节点显示了计算机应该进行的移动。如果对手赢得比赛，该位置将被称为对手的获胜位置。在这种情况下，计算机的移动将被视为糟糕的移动。如果计算机赢得比赛，该位置将被称为计算机的获胜位置。在这种情况下，对手的移动将被视为糟糕的移动。