二叉树DOM的遍历

image
第一次正式面试时,因为二叉树拉闸了。复习的时候抱着侥幸心里只看算法中的排序,到现在后悔也没用……好好学习,好好补充,好好提高吧

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能任意颠倒。

二叉排序树

二叉排序树,又称二叉查找树、二叉搜索树、B树。

二叉排序树是具有下列性质的二叉树:
若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
左、右子树也分别为二叉排序树。

image

也就是说,二叉排序树中,左子树都比节点小,右子树都比节点大,递归定义。

根据二叉排序树这个特点我们可以知道,二叉排序树的中序遍历一定是从小到大的,比如上图,中序遍历结果是:

1 3 4 6 7 8 13 14 19

二叉树节点定义

采用单项链表的形式,只从根节点指向孩子节点,子节点不保存父节点。

// 二叉树结点
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();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)        
        }     
};  
 关于图片懒加载和预加载
AngularJS中的作用域问题 
上一篇:关于图片懒加载和预加载
下一篇:AngularJS中的作用域问题


如果我的文章对你有帮助,或许可以打赏一下呀!

支付宝
微信
QQ