如何避免在树上走两次

How to avoid walking the tree twice

本文关键字:两次 何避免      更新时间:2023-09-26

我有以下方法来初始化树:

function _initTree(treeObj, options){ 
    treeObj = treeObj || []; 
    if(!zpJSUtils.isArray(treeObj)) throw new Error("Input tree must be an array"); 
    this.tree = treeObj; 
    this.rootNode = treeObj[0]; 
    _buildNodes.call(this, treeObj); 
} 

init方法遍历树,将所有对象初始化为节点:

function _buildNodes(treeObj){ 
    traverseTree.call(treeObj, function(nodeObj){
        node = new Node(nodeObj); 
        return true; 
    }, this); 
} 

traverseTree方法(从开关中选择):

function _walkPreOrder(tree, callback, ctx){ 
    tree.forEach(function(node, idx){ 
        var continueWalk = callback.call(ctx, node); 
        if(continueWalk){
            if(node.hasChildren()){ 
                _walkPreOrder.call(this, node); 
            }; 
        }; 
    }, this); 
}

问题是这样的
我想计算init上树的高度,这是根节点和叶子之间最长向下路径上的边数
因此,似乎为了计算高度,我必须再次遍历树(以找到最深嵌套元素的级别)。

json的格式如下:

var json = [{ text: "root", children: [
    {id: "id_1", text: "node_1", children:[
        {id: "id_c1", text: "node_c1"}, 
        {id: "id_c2", text: "node_c2", children: [
            {id: "id_c2_c1", text: "node_c2_c1"}, 
            {id: "id_c2_c2", text: "node_c2_c2"}, 
            {id: "id_c2_c3", text: "node_c2_c3"}]},   
        {id: "id_c3", text: "node_c3"}]}, 
    {id: "id_2", text: "node_2"}]}]; 

问题是_walkPreOrder可以接受多个回调(例如数组),但这会导致一个可疑的api(因为传入多个函数会使在条件为true/false时继续遍历树的可能性变得可疑)。

解决这个问题的好方法是什么,即避免多次迭代?

  1. 在创建子节点时第一次遍历树时,返回或标记每个子节点的最大高度
  2. 然后,在访问所有子节点时,比较所有子节点高度的最大值,然后标记/返回当前节点,使其子节点的最大高度多出1