Re: Walk DOM Tree in Reverse?

"Csaba Gabor" <danswer@xxxxxxxxx> writes:

Lasse Reichstein Nielsen wrote:

your traverse is doing what my lessSimpleTraverseDFRTL is doing two
posts above.

I guess the "continue" threw me off :)
I *think* I understand it now :)

An iterative function that works like the original traversal could be:
...
function traverse(element, action) {
var next = leftMostInnerMostDescendent(element);

I think of .lastChild as a rightmost child

*cough*right*cough*

[traversal by pointer reversal]

I never saw this before - it's interesting, reminding me of splay trees
- would you be a little more specific, please.

I *wish* I could find a reference for this on the web (or in any of my
books). It was just something my advisor mentioned to me at some point,
as a well known method for traversing trees.


Assume that we have some node structure with the operations of DOM
nodes, but without the HTML structure requirements. Then the following
algorithm will traverse all nodes (sadly not necessarily visiting each
just once):


function traverseByPointerReversal(node, action) {
// A sentinel node for knowing when to end.
var root = new Node("fakeroot"); // or something.
root.appendChild(node);

node = root;
do { // invariant: node is the root of a tree containing all the nodes.
// node always has at least one child
var child = node.firstChild;
node.removeChild(child);
child.appendChild(node);
node = child;
if (node != root) { action(node); }
} while (node != root);
}


// example code, with "mockup" nodes to show the transformations:
function Node(name) {
this.name = name;
this.children = [];
}
Node.prototype.appendChild = function(childNode) {
this.children.push(childNode);
if (this.children.length == 1) {
this.firstChild = childNode;
}
};
Node.prototype.removeChild = function(childNode) {
this.children.shift(); // for this algorithm, only first child is removed
this.firstChild = this.children[0];
}
Node.prototype.toString = function() { // show tree structure
var cs = [];
for (var i = 0; i < this.children.length; i++) {
cs[i] = this.children[i].toString();
}
return this.name + ((cs.length > 0) ? ":[" + cs + "]" : "");
};
// example tree:
// A
// / | \
// B C D
// / \
// E F
var A = new Node("A");
var B = new Node("B");
var C = new Node("C");
var D = new Node("D");
var E = new Node("E");
var F = new Node("F");
A.appendChild(B);
A.appendChild(C);
A.appendChild(D);
D.appendChild(E);
D.appendChild(F);
alert(A); // A:[B,C,D:[E,F]]

traverseByPointerReversal(A, function(node){alert(node);});

This shows how the tree looks at each step, since the node in question
is always the root at the time it is "action"'ed.



By putting the parent as the last child of its first child, do you
also mean that the parent should disconnect that first child as its
child?

It should, yes.

And where does the action come in?

That is a problem, since some nodes are traversed more than once,
and the algorithm doesn't store information about where it came
from or what nodes are really pointer-reversed parent nodes.
So for the purpose of the OP, it's not very usable. I do think it's
a neat algorithm, though :)

If you would give the recursive form of the function, at least in
some pseudo code, that would be great.

The point is to not be recursive, and not use extra space for a stack.
I believe (without knowing for sure) that a similar method is used by
garbage collectors to traverse a tree without using more than constant
extra space.

/L
--
Lasse Reichstein Nielsen - lrn@xxxxxxxxxx
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
.

Relevant Pages

  • Re: Walk DOM Tree in Reverse?
    ... algorithm will traverse all nodes (sadly not necessarily visiting each ... the right child of the current root (plus at the beginning of the ... var fakeParent =!elem.parentNode; ... tree may be passed in. ...
    (comp.lang.javascript)
  • Re: How to solve the following binary search tree problem
    ... using a method that traverses the tree and prints to standard output ... Traverse the tree visiting each node in turn, ... traverse the sub-tree rooted at that child ... sum += grandchildren of that child ...
    (comp.lang.java.help)
  • Re: strange mouse behaviour on dialog called frm a tree
    ... > functions to add/ delete/ rename nodes of the tree. ... > Everything worked fine when I call this dialog on rightclicking the ... > root or its child.Problem comes up on rightclick of a node on the third ... > input the name on right click of the child of the child of the root, ...
    (microsoft.public.vc.mfc)
  • Re: strange mouse behaviour on dialog called frm a tree
    ... > functions to add/ delete/ rename nodes of the tree. ... > Everything worked fine when I call this dialog on rightclicking the ... > root or its child.Problem comes up on rightclick of a node on the third ... > input the name on right click of the child of the child of the root, ...
    (microsoft.public.vc.mfc)
  • Re: start with parent but dont include parent in results
    ... | Trying to get all of the child records for a node in a tree without ... | getting a record for the parent record and can't seem to do it ... | child = 'ROOT' ...
    (comp.databases.oracle.misc)