我有树结构:
public class Tree{
int topSize = 10 ;
Tree[] children2 = new Tree[topSize];
Tree parent;
String data;
int i = 0;
public void addChild(Tree child) {
child.setParent(this);
this.children2[i++] = child;
}
}
我在我的程序中使用它,例如:
example 1: example 2:
F H
/ / \
E I J
/ /
D T
/
C
我想要给我一片叶子作为结果的函数:
示例 1:函数应返回一个数组:C(树节点)
示例 2:函数返回结果为 array[0] = T(包含数据 T 的树节点),array[1] = J(树节点)。
我需要将示例 1 和示例 2 中的发束压平为:
example 1 example 2
solution solution
F H
/ | \ / | \
E D C I J T
我有以下函数接受叶子作为参数:
public static Tree find(Tree edge){
if(edge != edge.parent){
edge.parent = find(edge.parent);
edge.parent.addChild(edge);
}
return edge.parent;
}
因此,在示例 1 中,我使用:find(C)
例如2我认为我应该使用:find(T)然后find(edge J)。
在 main 中,我给出的数组包含:
treeArray[0]
data="d", children[] - children[3]->data="c",children[0]->data="a", children[0]=null
/ \
children[0]->data="b",children[0]=null children[1]->data="b",children[0]=null
我有相同的 child ,但后来我删除了它,所以我认为
最佳答案
我认为您正在寻找如下方法:
public static void findLeaves(Tree root, List<Tree> leaves){
//iterate over children
for(Tree child : root.children2) { //better use getter
//if child has no children it is a leaf. Add it to list
if(! hasChildren(child)) leaves.add(child);
//if child has children, check them
else findLeaves(child, leaves);
}
return ;
}
static boolean hasChildren(Tree child) {
for(int i=0; i < child.children2.length; i++) {
if(child.children2[i] != null) return true;
}
return false;
}
该方法应将所有叶子(没有子节点的节点)添加到 List<Tree> leaves
(如果需要,您可以将其转换为数组)。
使用方式:
List<Tree> leaves = new ArrayList<>();//a list to hold leaves after method runs
findLeaves(root, leaves);
请注意:
1.我无法运行并检查该方法。请仔细检查。
2. 该方法不是 null 安全的。两者root
和leaves
不应为空
关于java - 函数返回树的叶子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42870060/