6

なぜ DOM ツリーが優先されるpreorderのdepth-first traversalですか?

BFT のような他のトラバーサルと比較して、この設計の選択の利点は何ですか?

私はDOM標準を調べていて、先行と後続の定義を見つけました:

オブジェクト 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 に答える