我使用了大约15000个节点，并试图从中构建层次结构。节点在任何方面都是不可排序的，每个节点都可以有无限数量的子节点——但父母总是在他们的子节点之前被提供给函数。我的代码适用于较小的N值，但最终超过了服务器上N>2000的最大执行时间。我不确定是否有更好的方法可以做到这一点，但我有以下方法：
function insertNode(&$treeNode, $insertNode) {
if($insertNode['DEPTH'] <= $treeNode['DEPTH']) return false;
if($treeNode['ID'] == $insertNode['PARENT_ID']) {
$treeNode['CHILDREN'][] = $insertNode;
$treeNode['CHILD_COUNT']++;
return true;
}
else {
foreach($treeNode['CHILDREN'] as $key=>$value) {
$found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
if($found) {
$treeNode['CHILD_COUNT']++;
return true;
}
}
}
}
我现在最好的解决方案是将递归限制为只构建几千个深度节点，然后在Javascript中为每个底部节点调用脚本，直到树真正完成。不过，我宁愿一次搞定。
我自己想好了。关键是：
父母总是在他们的孩子之前被灌输给函数
我使用的SQL查询（Oracle CONNECT BY）直接打印出每个孩子（以及他们的所有孩子）的直系祖先。例如，数据集：
|id|parent_id|
|A-|---------|
|C-|-----A---|
|Bb|-----B---|
|B-|-----A---|
将由查询传递为：
|id|parent_id|
|A-|---------|
|B-|-----A---|
|Bb|-----B---|
|C-|-----A---|
我按顺序遍历查询的每一行，然后为每一行调用递归插入函数。在每个函数调用中，我都使用foreach循环对树中当前节点的每个子节点进行递归调用，直到找到行的父节点，这里是：
foreach($treeNode['CHILDREN'] as $key=>$value) {
$found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
if($found) {
$treeNode['CHILD_COUNT']++;
return true;
}
}
但是，因为每个子项的父项总是其深度的最新插入项（因为这是我循环遍历其深度的最后一行），所以父项保证是树最右侧分支中最右侧的子项。循环不仅是不必要的，而且实际上是我能做的最糟糕的事情——它从左到右循环子级，但父级始终是最右边分支的最右边的子级，也是函数循环和遍历的最后一项。（那是什么，O(N^2)？）难怪时间不合适。
我剪切了foreach，并将其替换为end()调用。
$lastChild = $treeNode['CHILDREN'];
end($lastChild);
$key = key($lastChild);
$found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
if($found) {
$treeNode['CHILD_COUNT']++;
return true;
}
这大大缩短了执行时间，因为它按指数减少了函数每行递归调用自己的次数。它现在在大约6秒内工作N=15000（之前它在30秒内工作，低至N=2000）。不需要节点号上限或通过JS延迟加载。