从起始编码树获取子树

Question

我的树编码如下：

A ➜ B ➜ C ➜ -1 ➜ D

A ➜ B ➜ C ➜ -1 ➜ -1 ➜ D

当有

-1

时，意味着你必须上升一级，所以在第一个例子中，

B

有两个孩子（

C

和

D

）。在第二个示例中，

A

有两个子级（

B

和

D

）。

我的目标是一次移除一片叶子，得到剩下的树，参考第一个例子，有两片叶子（

C

和

D

），所以我想要得到的是：

A ➜ B ➜ D

A ➜ B ➜ C

参考第二个例子，总是有两个叶子（

C

和

D

），所以我想要得到的是：

A ➜ B ➜ -1 ➜ D

A ➜ B ➜ C

我编写了一些复杂的代码，但它并不适用于所有应用程序，您有什么想法吗？或者是否已经有一些库可以完成这项工作？

Answer 1

在我看来，在你的符号中，叶子要么是描述末尾的标签，要么是上下文中的标签

➜ [X] ➜ -1

。无论哪种情况，您都可以移除叶子：

• 如果标签位于末尾，请将其及其前面的 ➜（如果有）删除，然后重复删除

  ➜ -1

  （如果它出现在说明末尾）。

• 如果标签在上下文中

  ➜ [X] ➜ -1

  ，请删除这四个标记。