6

为什么是 DOM 树oder preorder，？depth-first traversal

与 BFT 等其他遍历相比，这种设计选择有哪些优势？

我只是在研究DOM 标准，发现了 before 和 following 的定义：

如果 A 和 B 在同一棵树中并且 A 在树顺序中位于 B 之前，则对象 A 在对象 B 之前。

如果 A 和 B 在同一棵树中并且 A 按树顺序在 B 之后，则对象 A 跟随对象 B。

就像大多数编程范例一样，Web 平台具有有限的层次树结构，简称为树。树顺序是前序，深度优先遍历。

4

2 回答 2

11

深度优先遍历通常是最简单的遍历方式，因为您可以递归或使用显式堆栈进行；广度优先需要一个队列，从某种意义上说，它是一种更复杂的数据结构。但我认为有一个比传统或简单更简单的答案：（X）HTML 树的深度搜索遍历导致文本节点按表示顺序遍历。

考虑这个相对简单的HTML子树。

或者，以原始形式：

<p>Consider this <emph>relatively</emph> simple <a href="...">HTML</a> subtree</p>

作为一棵树（省略空格和属性）：

                      <P>
                       |
      +-----------+----+----+-----+------+               
______|______   __|___   ___|__  _|_  ___|___
Consider this   <EMPH>   simple  <A>  subtree
                  |               |
              ____|_____        __|__
              relatively         HTML

深度优先遍历：

<P>, Consider this, <EMPH>, relatively, simple, <A>, HTML, subtree

广度优先遍历：

<P>, Consider this, <EMPH>, simple, <A>, subtree, relatively, HTML
于 2013-04-19T21:48:03.043 回答
2

深度优先搜索需要树的高度顺序的内存，但广度优先搜索需要树顶点的基数顺序的内存。换句话说，与深度优先搜索相比，广度优先搜索是一种内存消耗。

于 2013-04-19T20:55:36.253 回答