How do I get the "depth" of a tree?

6 次查看（过去 30 天）
Staffan Sevon
Staffan Sevon 2015-5-7
评论： Igor 2017-7-12
Hi,
I'm looking for the node that is the farthest from the "top" of the tree and in particular: how far the distance to the farthest node is? (I continue using the tree in another place, where there is a restriction on how many levels the tree can have, rather than on how many splits there are - which, as I understand it, is what You can limit when building the tree)
In the tree below, the distance would be 7, which is the number of steps between the topmost point on the one hand and either one of the -1 and 1 lowest in the picture.
Does any one know an elegant solution? The tree-object has a lot of information, but I can't figure out how to use it for this objective.
bw, Staffan

请先登录，再回答此问题。

采纳的回答

Ilya
Ilya 2015-5-8
This should work:
function depth = treedepth(tree)
parent = tree.Parent;
depth = 0;
node = parent(end);
while node~=0
depth = depth + 1;
node = parent(node);
end
end
  1 个评论
Staffan Sevon
Staffan Sevon 2015-5-8
Fantastic!!!!
It works like we - for some reason say in my country - like a toilet on a train.
Which, surprisingly means that it works like a charm
Many, many thanks to both of You for the help, and in particular to Ilya, Staffan

请先登录，再进行评论。

更多回答（2 个）

Geoff Hayes
Geoff Hayes 2015-5-7
Staffan - how is your tree represented? As a matrix or some sort of list of nodes connected to other nodes? I suspect that you want to create some sort of recursive function that counts the depth of each node (or subtree of the parent tree). For example, if tree is your top-level tree/node, then you could do something like
maxDepth = getDepth(tree)
where
function [depth] = getDepth(tree)
maxDepth = 0;
for each childNode of tree do
depthChild = 1 + getDepth(childNode);
if depthChild > maxDepth
maxDepth = depthChild;
end
end
Note how we recursively check the depth of each child node of the main tree, treating each as if it were a tree itself. We only ever stop recursing when we reach a node without any children.
Staffan Sevon
Staffan Sevon 2015-5-8
Hi,
thanks for Your answer!
The trees generated by the fitctree function are described as a list of nodes. So, the two primary descriptions are the variables t.Children and t.Parent which in part have "overlapping" information (the variables are shown in the picture below).
The method You propose seems very good, but I can't figure out how to concretize it to fit the information I have. Any additional help/pointers in the right direction that anyone can give, is greatly appreciated
bw, Staffan
<<
<<
>>
>>
  1 个评论
Igor
Igor 2017-7-12
I've just check this with a bit of brute-force. And I can confirm it works. It looks like tree nodes are stored in "t.Parent" in a "sorted by depth" manner. Thus only checking the last one is sufficient.
function max_depth = treedepth(tree)
parent = tree.Parent;
max_depth=0;
depthA = NaN([1 numel(parent)]);
for start_node_ind = 1:numel(parent)
node = parent(start_node_ind);
depth = 0;
while node~=0
depth = depth + 1;
node = parent(node);
end
depthA(start_node_ind) = depth;
end
max_depth = max(depthA);
% it looks like parents list is stored in a way, that depths are sorted
assert(issorted(depthA));
% thus, the last "parent" is always the deepest
assert(max(depthA)==depthA(end));
end

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Data Distribution Plots 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by