なぜDOMツリーのプリオーダー、深さ優先のトラバーサルですか？

Question

DOMツリーはなぜpreorder,depth-first traversalですか？

BFTのような他のトラバーサルと比べて、この設計の利点は何ですか？

私はちょうど DOM standardに見ていると、先行すると、次の定義を発見された

：

AとBが同じツリー であり、Aは、ツリー内のBの前に来る場合AがオブジェクトBに先行しているオブジェクト注文。

AとBが同じツリーにある場合、オブジェクトAはオブジェクトBの後にあります。 とAはツリー順序でBの後に来ます。

ほとんどのプログラミングパラダイムのように、Webプラットフォームには有限の 階層ツリー構造があります。ツリーの順序は、 のプリオーダー、深さ優先トラバーサルです。

Answer 1

再帰的に、または明示的なスタックで行うことができるため、深さ優先トラバーサルは一般的に最も簡単なトラバーサルスタイルです。幅優先は、ある意味ではより複雑なデータ構造である待ち行列を必要とする。しかし、私は伝統やシンプルさよりも簡単な答えがあると思います。（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 

Answer 2

深さ優先検索ではツリーの高さのオーダーでメモリが必要ですが、幅優先検索ではツリーの頂点のカーディナリティの順番でメモリが必要です。言い換えれば、幅優先検索は、深さ優先検索と比較してメモリー・ホッグです。