在二叉树的同一级别上获取所有 children
Getting all children on same level of binary tree
我想在同一层树上显示所有 children。所以如果我有这样一棵树:
A
B C D
E F G H I J
例如,级别 3 将 return E、F、G、H、I 和 J 节点。我在 TreeNode
class 中有一个方法,即 return 给定节点的所有 children,所以我想做这样的事情:
static Collection<ITreeNode<IProduct>> getOnLevel(ITree<IProduct> tree, int level)
{
Collection<ITreeNode<IProduct>> temp;
int i;
Iterator<ITreeNode<IProduct>> iterator = tree.getRoot().getChildren().iterator();
for(i=0; i<=(level); i++)
{
while(iterator.hasNext())
{
ITreeNode<IProduct> elem = iterator.next();
if(i == (level))
{
temp = elem.getChildren();
return temp;
}
}
}
return tree.getRoot().getChildren();
}
但后来我意识到我只是遍历第一级 children,所以我可能必须以某种方式递归地执行此操作?
提前致谢,阿马尔!
您可以递归地或迭代地完成它,这取决于您。
我发现递归解决方案更容易阅读。它看起来像这样:
static Collection<ITreeNode<IProduct>> getOnLevel(
ITree<IProduct> tree
, int desiredLevel
) {
List<ITreeNode<IProduct>> result = new ArrayList<>();
findOneLevel(tree.getRoot(), desiredLevel, 0, result);
return result;
}
static void findOnLevel(
ITreeNode<IProduct> node
, int desiredLevel
, int currentLevel
, List<ITreeNode<IProduct>> result
) {
if (currentLevel == desiredLevel) {
result.add(node);
return;
}
Iterator<ITreeNode<IProduct>> iterator = node.getChildren().iterator();
while(iterator.hasNext()) {
findOnLevel(iterator.next(), desiredLevel, currentLevel+1, result);
}
}
该方法非常简单:顶级方法创建一个列表来存储结果,然后调用递归 findOnLevel
。递归方法检查我们是否达到了所需的级别,如果达到了,则将当前节点添加到结果中。否则,我们在递归调用中遍历当前节点的所有子节点,为新的当前级别传递 currentLevel+1
。
我想在同一层树上显示所有 children。所以如果我有这样一棵树:
A
B C D
E F G H I J
例如,级别 3 将 return E、F、G、H、I 和 J 节点。我在 TreeNode
class 中有一个方法,即 return 给定节点的所有 children,所以我想做这样的事情:
static Collection<ITreeNode<IProduct>> getOnLevel(ITree<IProduct> tree, int level)
{
Collection<ITreeNode<IProduct>> temp;
int i;
Iterator<ITreeNode<IProduct>> iterator = tree.getRoot().getChildren().iterator();
for(i=0; i<=(level); i++)
{
while(iterator.hasNext())
{
ITreeNode<IProduct> elem = iterator.next();
if(i == (level))
{
temp = elem.getChildren();
return temp;
}
}
}
return tree.getRoot().getChildren();
}
但后来我意识到我只是遍历第一级 children,所以我可能必须以某种方式递归地执行此操作? 提前致谢,阿马尔!
您可以递归地或迭代地完成它,这取决于您。
我发现递归解决方案更容易阅读。它看起来像这样:
static Collection<ITreeNode<IProduct>> getOnLevel(
ITree<IProduct> tree
, int desiredLevel
) {
List<ITreeNode<IProduct>> result = new ArrayList<>();
findOneLevel(tree.getRoot(), desiredLevel, 0, result);
return result;
}
static void findOnLevel(
ITreeNode<IProduct> node
, int desiredLevel
, int currentLevel
, List<ITreeNode<IProduct>> result
) {
if (currentLevel == desiredLevel) {
result.add(node);
return;
}
Iterator<ITreeNode<IProduct>> iterator = node.getChildren().iterator();
while(iterator.hasNext()) {
findOnLevel(iterator.next(), desiredLevel, currentLevel+1, result);
}
}
该方法非常简单:顶级方法创建一个列表来存储结果,然后调用递归 findOnLevel
。递归方法检查我们是否达到了所需的级别,如果达到了,则将当前节点添加到结果中。否则,我们在递归调用中遍历当前节点的所有子节点,为新的当前级别传递 currentLevel+1
。