@blog.justoneplanet.info

日々勉強

木構造における高さと深さ

まぁ、ちょっとしたおさらい。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;
    }
}

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

コメントはまだありません»

No comments yet.

RSS feed for comments on this post.TrackBack URL

Leave a comment