まぁ、ちょっとしたおさらい。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; } }
計算量はツリーにおける全ノードの数に比例するよね。