why is DOM tree oder preorder
, depth-first traversal
?
What are the advantages of this design choice compared 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 comes before B in tree order.
An object A is following an object B if A and B are in the same tree and A comes 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.
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 complicated 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 raw form:
<p>Consider this <emph>relatively</emph> simple <a href="...">HTML</a> subtree</p>
As a tree (leaving out whitespace and attributes):
<P>
|
+-----------+----+----+-----+------+
______|______ __|___ ___|__ _|_ ___|___
Consider this <EMPH> simple <A> subtree
| |
____|_____ __|__
relatively HTML
Depth-first traverse:
<P>, Consider this, <EMPH>, relatively, simple, <A>, HTML, subtree
Breadth-first traverse:
<P>, Consider this, <EMPH>, 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 compared to depth-first search.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With