admin管理员组

文章数量:1277304

why is DOM tree oder preorder, depth-first traversal?

What are the advantages of this design choice pared to other traversal like BFT?

I was just looking into DOM standard and found the definition of preceding and following :

An object A is preceding an object B if A and B are in the same tree and A es before B in tree order.

An object A is following an object B if A and B are in the same tree and A es after B in tree order.

Just like most programming paradigms the Web platform has finite hierarchical tree structures, simply named trees. The tree order is preorder, depth-first traversal.

why is DOM tree oder preorder, depth-first traversal?

What are the advantages of this design choice pared to other traversal like BFT?

I was just looking into DOM standard and found the definition of preceding and following :

An object A is preceding an object B if A and B are in the same tree and A es before B in tree order.

An object A is following an object B if A and B are in the same tree and A es after B in tree order.

Just like most programming paradigms the Web platform has finite hierarchical tree structures, simply named trees. The tree order is preorder, depth-first traversal.

  • javascript
  • algorithm
  • dom
  • graph-algorithm
Share Improve this question edited May 26, 2014 at 11:12 brunnerh 185k30 gold badges357 silver badges430 bronze badges asked Apr 19, 2013 at 18:50 P KP K 10.2k13 gold badges56 silver badges99 bronze badges 1
  • 3 This might do better over on cs.stackexchange. – j08691 Commented Apr 19, 2013 at 18:53
Add a ment  | 

2 Answers 2

Reset to default 12

Depth-first traversal is generally the easiest traversal style, since you can do it recursively or with an explicit stack; breadth-first requires a queue which is, in some sense, a more plicated data-structure. But I think there is a simpler answer than tradition or simplicity: depth-search traversal of an (X)HTML tree results in the text nodes being traversed in presentation order.

Consider this relatively simple HTML subtree.

Or, in HTML:

<p>Consider this <em>relatively</em> simple <a href="http://en.wikipedia/wiki/HTML">HTML</a> subtree</p>

As a tree (leaving out whitespace and attributes):

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

Depth-first traverse:

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

Breadth-first traverse:

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

A depth-first search requires memory on the order of the tree's height, but a breadth-first search requires memory on the order of the cardinality of the tree's vertices. In other words, breadth-first search is a memory hog pared to depth-first search.

本文标签： javascriptwhy is DOM tree oder preorderdepthfirst traversalStack Overflow

版权声明：本文标题：javascript - why is DOM tree oder preorder, depth-first traversal? - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1741267761a2368802.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。