C++ 中的二叉树剪枝

引言

二叉树是一种分层数据结构，由节点组成，每个节点最多有两个子节点：节点必须有一个左子节点和一个右子节点。由于其在表示分层关系方面的卓越性，二叉树是当今计算机科学中最常用的数据结构之一。二叉树中的每个节点都有一个值，并且一个节点被定义为根节点，同时有两个子分支，一个左分支和一个右分支。

• 使用二叉树的一些应用包括表达式解析和其他分层系统，如文件系统。树的直接形式是递归的，许多关于二叉树的问题最好使用递归方法来解决。对应于节点的组件可以单独处理，并且其子节点可以递归地处理。
• 在这方面，二叉树的剪枝是指消除不满足规定标准的树的部分的过程。剪枝的需求也可能源于减少树结构的复杂性、释放一些内存空间或使未来的树算法更有效率的意图。剪枝也可以应用于决策树，其中一些分支可能被认为是不重要的，并且可以出于多种原因对其进行剪枝。这个过程对于许多涉及大量数据收集和缩减的应用来说是基本的。
• 但是二叉树具有一些使其适合在此处进行剪枝的特性。首先，它自然是分层的；因此，可以在处理其其余子树的同时，为树的一个级别执行操作。其次，在二叉树中，剪枝的概念可以通过递归很好地定义，其中每个节点及其分支的决策取决于其子树。最后，由于每个节点最多有两个子节点，剪枝是直接的，不需要记录保存，这在其他方法中很常见。

二叉树中剪枝的概念

基于定义，二叉树中的剪枝可以操作性地定义为在具有某些特征后规则性地删除某些子树。在涉及二叉树的计算问题中，通常使用剪枝来通过删除与当前问题不相关的分支来简化树。当解决具有大量重复数据或分支的树的问题时，它特别有用，这些分支在确定问题的解决方案方面没有用处。

• 最好通过一个值是 0 或 1 的节点的二叉树的例子来解释二叉树剪枝。剪枝的目的是消除仅包含值 0 的子树和边缘节点。
• 在这种特定情况下，只有 0 的子树被完全忽略，因为它不提供任何额外信息，因此被认为无用。因此，可以说当这些子树被剪枝后，树就变小了，所有不必要的节点，即除包含值 1 的节点之外的所有节点，都被删除了。
• 总的来说，当对二叉树进行剪枝时，这是一个自下而上的方法。也就是说，首先运行两个兄弟节点，然后才在下一步仅对单个节点做出决定。
• 这保证了当做出是否剪枝子树的决定时，所有与被询问的子树相关的信息都在手边。对于给定的情况，如果一个节点的左子节点和右子节点都是 nullptr 并且其值为 0，则该节点本身可以被剪枝。然而，如果任何子节点包含 '1'，则不能剪枝该节点，它构成了有意义的结构树的一部分。
• 实际上，二叉树被剪枝主要有两个原因。首先，它可以增强其结构，从而可以释放树中可能在其他操作中需要的结构。一棵小的树包含的节点更少，因此会减少在树上运行的任何算法所需的计算量。
• 其次，它可以改善其应用时的内存消耗。这样，与初始树结构相比，组装后的树改善了内存消耗，并且当决策树包含少量分支但有很多节点，并且我们将大量数据加载到树中时，它非常有用。

用于剪枝的递归树遍历

使用递归树遍历可以简单地解决二叉树剪枝问题。分而治之的方法利用了二叉树的这个属性，因为每个节点都可以再次看作是某个子树的根节点。这种递归结构使我们能够在每个节点上执行剪枝操作，通过首先在子节点上解决问题来实现递归。

在进行剪枝的二叉树遍历中，常用的方法是后序遍历。在后序遍历中，在遍历节点之前，先遍历节点的左子树和右子树。这在剪枝中特别有用，因为它意味着只有在所有子节点都已被剪枝后，才会做出剪枝节点的决定。换句话说，从决策树的底部开始，任何剪枝都包含有关被询问节点所代表的树的完整信息。

用于二叉树剪枝的后序遍历算法如下：

• 基本情况：如果当前节点是 nullptr，则最新节点是 nullptr。这是递归的停止条件，因为当树为空时，没有什么可剪枝的。
• 递归情况：关于未来的步骤，必须对当前节点的左子节点和右子节点使用相同的剪枝算法。之后，遍历到当前节点的左子树和右子树并进行剪枝；现在检查当前节点是否需要剪枝。如果其剪枝后的左右子树都为 nullptr 并且节点的值为 nil，则该节点可以被剪枝，即可以将其设置为 nullptr。如果不是这种情况，它将保持为一个节点。

这确保了剪枝是基于从每个被评估的节点开始的子树的状态进行的，并且是其他节点的前提。由于后序遍历在处理父节点之前先处理两个子节点，因此该算法可以删除不必要的子树。

例如，在剪枝值为 0 和 1 的二叉树的决策树情况下，该技术将首先应用于当前节点的左子树和右子树。基本上，如果两个子树都被剪枝且当前节点的值为 0，则剪枝该节点。事实上，如果节点的值为 1 或其子节点未被剪枝，则会进一步保留该节点。这种方法保证了生成的树只包含输入树的重要部分；即包含 1 的节点或具有有意义子树的节点。

递归树遍历用于剪枝的时间复杂度为 O(n)，其中 n 是树中的节点数，因为所有节点都只处理一次。至于空间复杂度，它等于 O(h)，其中 h 是树的高度，因为存在递归栈。我们知道，平衡树的高度 h 是节点数的对数，这使得该算法在时间和空间上都最优。

后序遍历的理论依据

后序遍历是二叉树剪枝中的一项重要策略，因为它能够在进行任何剪枝操作之前遍历整个子树。这种“自下而上”的方法至关重要，因为剪枝决策取决于节点子节点中包含的值。本质上，鉴于后序遍历在处理父节点之前从子节点开始，后序遍历能够在确定父节点的命运之前获取有关子节点的所有信息。

• 在二叉树剪枝问题中，特别是当节点包含二进制信息时，我们试图消除不提供有益信息的划分。例如，如果我们要在一步中删除所有包含 0 的子树，我们将不得不查看节点的左子树和右子树。这个论点声称，如果我们在检查其他子节点之前就剪枝一个节点，很容易就会提供不完整或错误的解决方案。
• 算法中使用的后序遍历确保在对一个节点进行操作之前，已对其所有子节点进行了操作，从而使我们能够知道哪个节点对树的含义有贡献。如果左子节点和右子节点都被剪枝，也就是说，我们将它们设置为空，并且节点也包含 0，那么它也会被剪枝。然而，如果任一子节点包含 1 或该节点本身包含 1，那么该节点就需要保留，因为它在树结构中有某种作用。
• 回想一下，通过以后序方式跟踪树，可以保证在完成其直接子树之前，没有任何节点会被删除。这种方法相当逻辑化且基于理论，因为在选择了子节点之后，我们只修剪树中不必要的部分。

算法的属性

根据以下重要的理论属性，二叉树剪枝算法可以被认为是高效实用的。这些属性包括：时间复杂度、空间复杂度以及算法对于各种二叉树结构的效率。

时间复杂度

• 二叉树剪枝的时间复杂度为 O(n)，它们取决于解释特定树的时间复杂度。这是因为要剪枝一个节点，算法必须访问所有节点一次。换句话说，算法所做的是遍历树中的所有节点，并且遍历它们的方式是通过树的前序和后序遍历。
• 由于每个节点都单独处理，因此随着节点数量的增加，总工作量呈线性增长。在剪枝问题的时序分析中，这是可以获得的最佳增长阶数，因为必须至少检查一次每个节点以验证剪枝操作的正确性。

空间复杂度

• 关于二叉树剪枝的空间复杂度，称为 h，空间复杂度可以表示为 h。在最坏的情况下，树是倾斜的，其中每个节点只有一个子节点，如线性形式，在任何给定时间，递归栈中将有 h 个函数调用。因此，通过最坏情况场景定义空间复杂度为 O(h)。
• 在最佳情况下，运行一个二叉树会使其成为一个平衡二叉树，其中树的高度是节点数对数的阶数，h = O(log n)。对于平衡树，上述给出了 O(log n) 的空间复杂度，这是非常高效的，并且即使有很多节点，它也能进入递归栈而不会变得太大。
• 我们应该注意到，大多数现实世界的二叉树都接近平衡，因此在实际部署中经常会遇到 O(log n) 的空间复杂度。然而，如果我们设想一个具有明确定义的最大深度的树，情况就不同了，因此在最坏的情况下，空间复杂度甚至可能是 O(n)。

不同类型树的效率

算法编程的理念是它能够处理各种类型的二叉树，包括有序、已排序或倾斜的二叉树。在平衡树中，避免了过度的递归结构，因此所需的时间和空间得到了优化。对于倾斜树，它可能需要更多的空间，但所需的时间仍然相当少，因为即使递归深度增加了，每个节点也只处理一次。

该剪枝算法在处理包含可能不同的节点值的树方面也很有效。对于某些节点包含 0 而其他节点包含 1 的树，该算法会剪除不重要的分支，同时保留重要的分支。由于我们只剪除选定的节点，因此可以保证生成的树只包含真正需要的作为树一部分的节点，这有助于节省内存的可消耗空间和用于对该树执行的任何进一步操作的最小计算能力。

边缘情况和注意事项

在使用二叉树实现剪枝算法并分析结果时，应考虑算法执行期间可能出现的其他边缘情况。这些极端情况通常在具有非典型结构或节点值可能影响剪枝过程的树上遇到。处理这种情况可以使算法更全面，因为它能够接受各种形式的输入。

空树

• 最简单的情感情况是树，它有一个空的根节点，换句话说，是 nullptr。在这种情况下，剪枝算法应立即返回 nullptr，因为没有节点可供剪枝。
• 递归函数的基线情况执行此操作。我们测试当前节点“this”是否等于 nullptr，在这种情况下，我们返回 nullptr。
• 如果树为空，技术上没有什么可做的，时间复杂度为 O(1)。

单节点树

• 另一个关键的特殊情况是绝对最小尺寸的树，即只有单个节点的树。
• 在这种情况下，剪枝决策完全取决于该节点的值，正如在评估和剪枝决策树中所见。如果节点值为 0，则剪枝该节点，随后树变为空。如果节点的值为 1，则保留该节点，树保持不变。
• 这个边缘案例对于理解如何在此类递归中正确设置基线案例可能特别有用。在单节点树中，将存在确定节点值以及是否应在递归函数中剪枝该节点的问题。

值为 0 的完整子树

• 在某些情况下，树可能甚至由整个子树组成，其中所有节点值都可能为 0。这些子树绝对应该被剪枝，因为它们根本不携带任何有用的信息。
• 算法通过递归消除子树中的每个节点来控制这一点。
• 在整个子树被剪枝之后，如果父节点的值为 0 并且子节点包含 nullptr，则可以剪枝父节点的所有字段。

编码

输出

剪枝前

这是原始树的中序遍历。这里显示的树的节点值为 0 和 1。

剪枝后

如果我们剪枝，我们会得到一棵只包含值为 1 的节点的树。这使得下面的结构更加浅显，因为所有只包含 0 的子树都已被消除。

剪枝后的二叉树结构

正如我们所见，剪枝后只剩下有意义的节点。值为 1 的节点由于其重要性而被保留，而只包含 0 的子树则被剪枝。