@blog.justoneplanet.info

$cat

以上

まぁ、ちょっとしたおさらい。JavaScript好きだし。( ´Д｀)ﾉ

■深さ

nodeの深さは以下のようにして求めるのがよいと思う。

var getDepth = function(tree, node){
    if(tree.isRoot(node)){
        return 0;
    }
    else{
        return getDepth(tree, node.getParent(node)) + 1;
    }
}

計算量は選択したnodeの深さに比例するよね。

■高さ

treeの高さは以下のようにして求めるのがよいと思う。

var getTreeHeight = function(tree, node){
    if(tree.isLeaf(node)){
        return 0;
    }
    else{
        var height = 0;
        var children = tree.children(node);
        for(var i = 0, n = children.length; i < n; i++){
            var h = getTreeHeight(tree, children[i]);
            height = (height < h)? h : height;
        }
        return h + 1;
    }
}

計算量はツリーにおける全ノードの数に比例するよね。