- From: John Cowan <cowan@locke.ccil.org>
- Date: Tue, 03 Nov 1998 13:21:56 -0500
- To: DOM List <www-dom@w3.org>
Stephen R. Savitzky wrote: > [T]he classic algorithm for traversing a tree is: > > traverse(node) { > visit(node); > if (node.firstChild != null) traverse(node.firstChild); > if (node.nextSibling != null) traverse(node.nextSibling); > } The trouble with that algorithm is that it is recursive. It will blow up if the tree is sufficiently deep. Indeed, in languages that cannot be relied on to do tail recursion, like Java, it will blow up if the tree is merely sufficiently wide. Furthermore, if there is any end-of-node processing to do, such as emitting an end tag indication, then the algorithm is no longer even partly tail recursive and will blow up on both depth and width even in safe-tail-recursion languages. The algorithm I use in DOMParser, therefore, is non-recursive: traverse(Node node) { Node currentNode = node; while (currentNode != null) { visit(currentNode); // Move down to first child Node nextNode = currentNode.getFirstChild(); if (nextNode != null) { currentNode = nextNode; continue; } // No child nodes, so walk tree while (currentNode != null) { revisit(currentNode) // do end-of-node processing, if any // Move to sibling if possible. nextNode = currentNode.getNextSibling(); if (nextNode != null) { currentNode = nextNode; break; } // Move up if (currentNode = node) currentNode = null; else currentNode = currentNode.getParentNode(); } } } Because of the reliability of this algorithm vis-a-vis the recursive one, I believe it should be the standard way of walking DOM trees, and therefore it is essential that DOM implementations make the structural access methods fast. -- John Cowan http://www.ccil.org/~cowan cowan@ccil.org You tollerday donsk? N. You tolkatiff scowegian? Nn. You spigotty anglease? Nnn. You phonio saxo? Nnnn. Clear all so! 'Tis a Jute.... (Finnegans Wake 16.5)
Received on Tuesday, 3 November 1998 13:20:54 UTC