JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】

本文实例讲述了JavaScript实现的DOM树遍历方法。分享给大家供大家参考,具体如下:

二叉 DOM 树的遍历

function Tree() {

var Node = function(key){

this.key = key;

this.left = null;

this.right = null;

}

root =null;

}

前序遍历

首先访问根结点,然后遍历左子树,最后遍历右子树

Tree.prototype.preOrderTraverse = function(callback){

preOrder(root, callback);

}

var preOrder = function(node,callback){

if(node !== null){

callback(node.key);

preOrder(node.left, callback);

preOrder(node.right, callback);

}

}

修改为DOM二叉树:

var preOrder = function(node,callback) {

callback(node);

if(node.firstElementChild) {//先判断子元素节点是否存在

this.preOrder(node.firstElementChild,callback);

}

if(node.lastElementChild) {

this.preOrder(node.lastElementChild,callback);

}

};

中序遍历

首先遍历左子树,然后访问根结点,最后遍历右子树。

Tree.prototype.inOrderTraverse = function(callback){

inOrder(root, callback);

}

var inOrder = function(node,callback){

if(node !== null){

inOrder(node.left,callback);

callback(node.key);

inOrder(node.right, calback);

}

}

修改为DOM二叉树:

var inOrder = function(node,callback){

if(node.firstElementChild) {

this.inOrder(node.firstElementChild);

}

callback(node);

if(node.lastElementChild) {

this.inOrder(node.lastElementChild);

}

}

后序遍历

首先遍历左子树,然后遍历右子树,最后访问根结点。

Tree.prototype.postOrderTraverse = function(callback){

postOrder(root, callback);

}

var postOrder = function(node,callback){

if(node !== null){

postOrder(node.left,callback);

postOrder(node.right, calback);

callback(node.key);

}

}

修改为DOM二叉树:

var postOrder = function(node,callback){

if(node.firstElementChild) {

this.postOrder(node.firstElementChild);

}

if(node.lastElementChild) {

this.postOrder(node.lastElementChild);

}

callback(node);

}

多叉 DOM 树的遍历

广度优先遍历

首先遍历根节点,然后访问第一层节点,第二层节点,....,直到访问到最后一层。

借助于队列,用非递归的方式对多叉树进行遍历

Tree.prototype.BFSearch = function(node,callback){

var queue=[];

while(node!=null){

callback(node);

if(node.children.length!=0){

for (var i=0;i<node.children.length;i++){

queue.push(node.children[i]);//借助于队列,暂存当前节点的所有子节点

}

}

node=queue.shift();//先入先出,借助于数据结构:队列

}

};

深度优先遍历

首先遍历根节点,然后沿着一条路径遍历到最深的一层,最后在逐层返回。

借助于栈,实现多叉 DOM树 的深度优先遍历。

Tree.prototype.DFSearch = function(node,callback){

var stack=[];

while(node!=null){

callback(node);

if(node.children.length!=0){

for (var i=node.children.length-1;i>=0;i--){//按照相反的子节点顺序压入栈

stack.push(node.children[i]);//将该节点的所有子节点压入栈

}

}

node = stack.pop();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)

}

};

二叉 DOM 树的前序、中序、后序遍历,是深度优先遍历的特例

因此,参考深度优先遍历,借助栈,可以以非递归的方式,实现二叉 DOM 树的  前序、中序和后序遍历

非递归实现二叉 DOM 树的前序遍历

Tree.prototype.preOrder = function(node,callback) {

var stack=[];

while(node!== null || stack.length!=0){

while(node!==null){

stack.push(node);

callback.push(node);

node=node.firstElementChild;

}

node=stack.pop();

node=node.lastElementChild;

}

};

非递归实现二叉 DOM 树的中序遍历

Tree.prototype.inOrder = function(node,callback) {

var stack=[];

while(node!== null || stack.length!=0){

while(node!==null){

stack.push(node);

node=node.firstElementChild;

}

node=stack.pop();

callback(node);

node=node.lastElementChild;

}

};

非递归实现二叉 DOM 树的后序遍历

① 每个节点,都压入栈两次;

② 在循环体中,每次弹出一个节点赋给node

③ 如果node仍然等于栈的头结点,说明node的孩子们还没有被操作过,应该把它的孩子们加入栈中

④ 否则,说明是第二次弹出该节点,访问node。

也就是说,第一次弹出,将node的孩子压入栈中,第二次弹出,访问node

TreeWalker.prototype.postOrder = function(node,callback) {//非递归实现

var stack=[];

stack.push(node);

stack.push(node);

while(stack.length != 0)

{

node = stack.pop();

if(stack.length != 0 && node==stack[stack.length-1])

{

if(node.lastElementChild) stack.push(node.lastElementChild), stack.push(node.lastElementChild);

if(node.firstElementChild) stack.push(node.firstElementChild), stack.push(node.firstElementChild);

}

else

callback(node);

}

}

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript操作DOM技巧总结》、《JavaScript错误与调试技巧总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript遍历算法与技巧总结》及《JavaScript数学运算用法总结》

希望本文所述对大家JavaScript程序设计有所帮助。

以上是 JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】 的全部内容, 来源链接: utcz.com/z/333186.html

回到顶部