Java 如何使用递归获取父母的所有孩子，然后是他们的孩子
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2275833/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to get all children of a parent and then their children using recursion
提问by jseals
Greetings:
你好：
I have the metaphor of Parent Transactions in my JSP web application. I have transaction ID's stored in a database and the requirement is to display all of the children of the parent and then the subsequent children of the parent's children. In reality this list of parents and their children will never be more than 4 or 5 levels deep but I need to take into account that it can go more layers than that.
我的 JSP Web 应用程序中有父事务的隐喻。我将事务 ID 存储在数据库中，要求是显示父级的所有子级，然后显示父级子级的后续子级。实际上，这份父母和他们的孩子的清单永远不会超过 4 或 5 层深，但我需要考虑到它可以有更多层。
I have tried doing this will recursion as follows:
我试过这样做会递归如下：
private static void processChildrenTransactions(
AllTremorTransactionsVO parentBean,
ArrayList<AllTremorTransactionsVO> childCandidatesList )
{
ArrayList<AllTremorTransactionsVO> childList =
new ArrayList<AllTremorTransactionsVO>();
for (AllTremorTransactionsVO childTransactions : childCandidatesList)
{
if (childTransactions.getParentGuid() != null)
{
if (childTransactions.getParentGuid().equals(parentBean.getTransactionGuid()))
{
childList.add(childTransactions);
}
}
}
for (AllTremorTransactionsVO allTremorTransactionsVO : childList)
{
processChildrenTransactions(allTremorTransactionsVO, childList);
}
return;
}
This does not work, generates a stack overflow as the loop runs on. Any ideas on best how to do this?
这不起作用，在循环运行时会产生堆栈溢出。关于如何最好地做到这一点的任何想法？
采纳答案by BalusC
There's means of deep recursion (with risks to get the stack to blow up) if the argument of the method is not immediately resolveable. I.e. the final result of the called method depends on the result of the method itself. Pseudo:
如果方法的参数不能立即解析，则有深度递归的方法（有使堆栈爆炸的风险）。即被调用方法的最终结果取决于方法本身的结果。伪：
Result process(Parent parent) {
Result result = new Result();
for (Child child : parent.getChildren()) {
result.update(process(child));
}
return result;
}
This causes the code to wait with update()until the result is known and therefore it get kept on the stack. And it accumulates with every method invocation.
这会导致代码等待update()直到结果已知，因此它会保留在堆栈中。它随着每次方法调用而累积。
You can optimize it to use tail recursioninstead with a mutable result object as argument:
您可以优化它以使用尾递归而不是可变结果对象作为参数：
void process(Parent parent, Result result) {
for (Child child : parent.getChildren()) {
result.update(child);
process(child, result);
}
}
This way the update()can be executed immediately as the argument is immediately resolveable. As long as there's no return value or any other logic to happen after the call to process(), the runtime can optimize it by dropping the call from the stack. Also see the aforelinked wiki article about tail recursion and this website.
这样update()就可以立即执行，因为参数可以立即解析。只要在调用 之后没有返回值或任何其他逻辑发生process()，运行时就可以通过从堆栈中删除调用来优化它。另请参阅上述有关尾递归的 wiki 文章和此网站。
However .. The code which you posted seems to be already tail-recursive. So the problem lies somewhere else. After studying your code it look like that you're iterating over the samechildren everytime. I.e. there's just means of an infinite loop. Probably the ifcheck is bogus and/or the children have backreferences in its own parent-child tree.
但是..您发布的代码似乎已经是尾递归的。所以问题出在其他地方。在研究了您的代码后，您似乎每次都在迭代相同的孩子。即只有无限循环的手段。可能if支票是伪造的和/或孩子在自己的父子树中有反向引用。
回答by Femaref
If there is a stack overflow happening, your recursion runs too deep. You will have to rewrite the algorithm as an iterative (i.e. using a for/while/foreach loop) construct.
如果发生堆栈溢出，则您的递归运行得太深。您必须将算法重写为迭代（即使用 for/while/foreach 循环）构造。
回答by ewernli
I guess you have an infinite loop...
我猜你有一个无限循环......
childListhave the same parentallTremorTransactionsVOis by definition one of the element ofchildList- --> when you recurse, you will again build the same
childListand pick the firstallTremorTransactionsVOas before
childList有相同的父母allTremorTransactionsVO根据定义是元素之一childList- --> 当你递归时，你将再次构建相同的
childList并allTremorTransactionsVO像以前一样选择第一个
I usually build such recursive code like this:
我通常会像这样构建这样的递归代码：
public List allChildren( Transaction trans )
{
List allChildren = new List();
for( Transaction childTrans : trans.getChildren() )
{
allChildren.addAll( allChildren( childTrans ));
}
return allChildren;
}
回答by Vivin Paliath
I was running into the same problem recently (using too much stack) and used an iterative algorithm. The example is in Javascript, but can be easily adapted:
我最近遇到了同样的问题（使用太多堆栈）并使用了迭代算法。该示例使用 Javascript，但可以轻松修改：
var nodeStack = new Array();
nodeStack.push(root);
while(nodeStack.length > 0) {
var currentNode = nodeStack.pop();
var data = currentNode.data;
var children = currentNode.children;
/* do stuff with data */
if(children.length > 0) {
jQuery.each(children, function(index, value) {
nodeStack.push(value);
});
}
回答by jseals
I was able to solve my StackOverflow condition as follows:
我能够解决我的 StackOverflow 条件如下：
private static void processChildrenTransactions(AllTremorTransactionsVO parentBean, ArrayList<AllTremorTransactionsVO> childCandidatesList ) {
ArrayList<AllTremorTransactionsVO> childList = new ArrayList<AllTremorTransactionsVO>();
ArrayList<AllTremorTransactionsVO> childListTwo = new ArrayList<AllTremorTransactionsVO>();
for (AllTremorTransactionsVO childTransactions : childCandidatesList) {
childListTwo.add(childTransactions);
if (childTransactions.getParentGuid() != null) {
//gets a list of every trans with a child
if (childTransactions.getParentGuid().equalsIgnoreCase(parentBean.getTransactionGuid())){
childList.add(childTransactions);
childListTwo.remove(childTransactions);
}
}
}
parentBean.setChildTransactions(childList);
for (AllTremorTransactionsVO allTremorTransactionsVO : childList) {
processChildrenTransactions(allTremorTransactionsVO, childListTwo);
//processChildrenTransactions(allTremorTransactionsVO, childList);
}
return;
}
I now have all of the children but I am struggling with grouping them properly. They need to be listed like this:
我现在有所有的孩子，但我正在努力将他们正确分组。他们需要像这样列出：
Parent --Child/Parent ----Child Parent --Child/Parnet ----Child/Parent ------Child
父--子/父----子父--子/Parnet ----子/父------子
And so on.
等等。
