c++ - 如何构建从叶子到根的二叉树

Question

如何构建从叶子到根的二叉树是相反的方向。我正在为字符串编写一个压缩算法并 xor 应用这种加密，例如我们将原始字符串作为**44**333**55**555**4**333**,

让xo = 44, x1 = 333, x2 = 55, x3 = 555, x4 = 4, x5 = 333 <=> **x0**x1**x2**x3**x4**x5,

应用这个算法，我们得到：

x01 = x0 xor x1, x23 = x2 xor x3, x45 = x4 xor x5 <=> **x01**x23**x45**

再次，

x0123 = x01 xor x23 and x012345 = x0123 xor x23.

这种结构在二叉树中很容易保持，但是如何在二叉树的方向上构建一个反向。

score 1 · Accepted Answer

为此，您可以轻松地使用简单的 std::vector。如果你回想一下堆是如何在堆排序中构建的，你会很容易弄清楚它的结构。这实际上不是原始堆，但这种二叉树表示可能非常有用。

因此，我宁愿使用 std::vector 以“反向”堆形式表示最终结构：初始向量将具有 n=6 个元素：{ 44, 333, 55, 555, 4, 333 }

下一步您进行 n-1=5 操作并将总和添加到向量的末尾，例如：{ 44, 333, 55, 555, 4, 333, 44333, 33355, 55555, 5554, 4333 }

使用尾元素的下一步 4 操作：{ 44, 333, 55, 555, 4, 333, 44333, 33355, 55555, 5554, 4333, 4433333355, 3335555555, 555555554, 55544333 }

因此，在 (n - 1) + (n - 2) + (n - 3) + ... + 1 = (n - 1) * n / 2 次操作之后，您将以相反的顺序获得树。

通过从右到左，您将按照 BFS 顺序遍历您的树。

score 0 · Accepted Answer

一种可能的解决方案可能是这样

制作所有给定值的树节点并将它们放入队列中。
从队列中弹出第一个元素，将其命名为 FIRST。2.1 从队列中弹出下一个元素并将其命名为 SECOND。如果不存在休息。2.2创建一个节点TEMP treenode（这是FIRST和SECOND的XOR）。2.3 将 FIRST 和 SECOND 设为 TEMP 的子级。2.4 将 TEMP 推入队列。2.5 从 2 重复步骤，直到队列只有一个元素。
首先标记为根。

2 回答 2