递归的迭代

Source: Dev.to

请提供您希望翻译的完整文本内容，我将按照要求保留源链接并翻译其余部分。

Source: …

将简化 HTML 转换为 Markdown 并生成语法树

在我的一个副项目（或“宠物”项目）中，我编写了一个小型 parser 来处理简化的 HTML，目的是用于记事本应用。
目标是让用户能够像在小型文字处理器中一样编写内容，且最终结果保存为 Markdown。

所有这些的支持都依赖 JEditorPane，因为该应用是基于 Swing 用 Java 编写的（我非常喜欢 C#，但能够把整个应用打包成单个 .jar 文件是个大优势）。

---

示例 HTML 输入

A realizar:

    - Recoger la bici del taller.

    - Dar de comer a las tortugas.

    - Pedir cita para colonoscopia.

期望的 Markdown 输出

# Tareas cotidianas

A realizar:

1. Recoger la bici del taller.
2. Dar de comer a las tortugas.
3. Pedir cita para colonoscopia.

虽然看起来像是直接的转换（也许通过某种预处理器），但如果不使用 parser，问题会立刻出现：我们需要把 HTML 输入转换成 语法树。

---

示例的语法树

Root
|________________________|
p                        ol
|                        |______________________________|________|
"A realizar"             li                             li       li
                         |                              |        |
                         "把自行车从车间取回。" "喂乌龟。" "预约结肠镜检查。"

树遍历生成 Markdown

一种遍历树的方式是利用 递归 和 Visitor 设计模式。

Tree 类（递归）

class Tree {
    // ...

    public void run(Visitor v) {
        this.runOver(v, this.root);
    }

    private void runOver(Visitor v, Element element) {
        v.visit(element);

        for (Element subElement : element.getSubElements()) {
            this.runOver(v, subElement);
        }
    }
}

通过此方法，将处理树的代码与对树执行各种任务的代码分离。
runOver(v, element) 使用 深度优先（DFS）策略遍历所有元素。

Visitor 类

class Visitor {
    // ...

    private final StringBuilder text = new StringBuilder();

    public void visit(Element element) {
        String elementText = element.toString();

        if (!elementText.isEmpty()) {
            text.append(elementText);
            text.append('\n');
        }
    }

    public String getResult() {
        return text.toString();
    }
}

执行（调用栈表示）

runOver(root, v)
 ├─ runOver(p, v)
 │   └─ runOver(p.get(0), v)
 ├─ runOver(ol, v)
 │   ├─ runOver(ol.get(0), v)
 │   │   └─ runOver(li.get(0), v)
 │   ├─ runOver(ol.get(1), v)
 │   │   └─ runOver(li.get(0), v)
 │   └─ runOver(ol.get(2), v)
 │       └─ runOver(li.get(0), v)

获得的输出

A realizar:
Recoger la bici del taller.
Dar de comer a las tortugas.
Pedir cita para colonoscopia.

递归的缺点

1. 理解 – 起初很难思考和理解自调用的代码。
2. 性能 – 每一次递归调用都会占用调用栈中的一个位置。
   如果树的深度例如达到 100 层，将在栈中预留 100 条条目，这可能导致 StackOverflowError。

迭代方法（使用队列）

为了避免前面的这些问题，我们可以用显式集合来替代隐式调用栈。
与使用栈（需要逆序插入子元素）不同，我们将使用队列（ArrayDeque），它保持节点的自然顺序。

Tree 类（迭代版）

class Tree {
    // ...

    public void run(Visitor v) {
        Deque<Element> elements = new ArrayDeque<>();
        elements.add(this.getRoot());          // se inserta la raíz

        while (!elements.isEmpty()) {
            Element element = elements.removeFirst(); // se saca del frente
            v.visit(element);                         // se procesa

            // se añaden los sub‑elementos al final de la cola
            for (Element sub : element.getSubElements()) {
                elements.addLast(sub);
            }
        }
    }
}

使用这个 while 循环，应用程序以 广度优先（BFS）方式遍历树，无需递归调用，从而消除栈溢出的风险。

概要

• Parser → 简化的 HTML → 语法树。
• Visitor → 遍历树并生成 Markdown 文本。
• 递归 → 简单但可能导致栈溢出。
• 迭代（队列） → 防止栈溢出并保持节点的自然顺序。

采用这种方式，笔记应用可以接受简易的 HTML，将其转换为内部树结构，并安全高效地生成 Markdown。

t = elements.peek();

elements.remove();
elements.addAll(element.getSubElements());

v.visit(element);
}

步骤示例（任务笔记）

1. 第一轮 – 引入根节点，移除它并加入其子元素。

   • elementos → [ p, ol ]
   • text → ""

2. 第二步 – 处理 p，其唯一子节点是文本 “A realizar.”。

   • elementos → [ ol, "A realizar." ]
   • text → ""

3. 下一步 – 添加 ol 的子节点。

   • elementos → [ "A realizar.", li, li, li ]
   • text → ""

4. 取出第一个元素 – 包含文本，加入 StringBuilder。

   • elementos → [ li, li, li ]
   • text → "A realizar.\n"

5. 添加子元素 – 处理第一个 li。

   • elementos → [ li, li, "Recoger la bici del taller." ]
   • text → "A realizar.\n"

6. 重复 – 处理下一个 li。

   • elementos → [ li, "Recoger la bici del taller.", "Dar de comer a las tortugas." ]
   • text → "A realizar.\n"

7. 再一次 – 处理最后一个 li。

   • elementos → [ "Recoger la bici del taller.", "Dar de comer a las tortugas.", "Pedir cita para colonoscopia." ]
   • text → "A realizar.\n"

8. 添加剩余文本 – 这些文本已没有子元素，直接加入。

   • elementos → [ "Dar de comer a las tortugas.", "Pedir cita para colonoscopia." ]
   • text → "A realizar.\nRecoger la bici del taller.\n"

9. 继续 –

   • elementos → [ "Pedir cita para colonoscopia." ]
   • text → "A realizar.\nRecoger la bici del taller.\nDar de comer a las tortugas.\n"

10. 结束 – 队列为空。

    • elementos → []
    • text → "A realizar.\nRecoger la bici del taller.\nDar de comer a las tortugas.\nPedir cita para colonoscopia.\n"

太棒了！我们的代码能够在不担心树的复杂度是否会导致 stack 溢出的情况下运行。此外，由于函数调用更少，执行速度也更快。

当然，这意味着我们使用了更多的内存（elementos 队列）。性能和内存之间总是需要权衡的！