php 家谱树的递归函数
php recursive function for genealogical tree
我在数据库中有与 parents 相关的人,我需要创建递归函数,其中 return 数组与家谱树。数据库示例:
NUMBER;NAME;FATHER;MOTHER
001;Name1;002;005
002;Name2;007;018
003;Name3;018;025
005;Name5;006;019
023;Name23;019;045
018;Name18;062;097
007;Name7;;-
...
我准备了两个函数 - 第一个用于 man 详细信息,第二个用于搜索祖先的递归。
我需要这个结果:
$out[0][0] // first person
$out[1][0] // mother of first person
$out[1][1] // father of first person
$out[2][0] // grandmother of first person (mother side)
$out[2][1] // grandfather of first person (mother side)
$out[2][2] // grandmother of first person (father side)
$out[2][3] // grandmother of first person (father side)
...
下一代有 8 项,接下来有 16 项,...最多是 6 代。
我准备了两个函数 - 第一个用于 man detail,第二个用于树构建的递归。在第二个函数中
define("MAX_GEN",5);
function detail($number) {
$d = mysql_query("select * from table where number = '$number'");
if(mysql_num_rows($d) == 0) {
$p[name] = "N/A";
$p[number] = "N/A";
$p[m_number] = "N/A";
$p[f_number] = "N/A";
}
else $p = mysql_fetch_assoc($d);
return $p;
}
function gen($number, $generation = 0, $out) {
if ($generation >= MAX_GEN) {
return false;
}
$record = detail($number);
if ($generation == 0) $out[0][] = $record; // first man
$generation++; // next generation
if (!$out[$generation] && ($generation != MAX_GEN)) $out[$generation] = array();
$x_mother = gen($record[m_number], $generation ); // continue with mother
$x_father = gen($record[f_number], $generation ); // continue with father
if ($out[$generation]) {
$out[$generation][] = $x_mother;
$out[$generation][] = $x_father;
}
return $out;
}
但是在第二个函数中有问题 - 我不知道如何将带有结果的数组传递给下一代。它仍然是 return 一个元素,或者(经过几次尝试)它是我想要的 returns 数组,但在几代之间插入数组,结果无法使用。谁能帮帮我?
我想要的结果示例在这里:http://www.foxterrier.cz/_TM_importy/example.php
这主要是评论 - 但有点长。
您非常受数据库设计和所需输出格式的限制。即使不去 a graph database there are lots of ways of representing hierarchical data in a relational database 的 cost/complexity。
您的输出格式列出每一代,但不维护父-母关联,也不适合横向或向前映射 - 只能向后映射。
您的实施要求您 运行 2^N(其中 N 是代数)查询,每次从 PHP 代码返回 DBMS 进行一次往返。性能会很差。
至少你应该考虑一次解决一代:
$ref=mysql_real_escape_string(session_id());
mysql_query(
"INSERT INTO results (generation, number, ref) VALUES (0, $start_number, '$ref')"
);
for ($x=1; $x<=max_gens; $x++) {
mysql_query(
"INSERT INTO results (generation, number, ref)
SELECT $x, father, '$ref'
FROM yourtable yt JOIN results rs ON yt.number=results.number
WHERE rs.generation=$x-1
UNION
SELECT $x, mother, '$ref'
FROM yourtable yt JOIN results rs ON yt.number=results.number
WHERE rs.generation=$x-1"
);
}
(但有更多的错误检查 - 并记得稍后清除数据)
我更喜欢使用迭代来创建 $out 数组
代替gen函数
迭代次数增加 1 -> 2 -> 4 ->8
= 2 ^($generation-1)
$parent=$generation-1;
for($j=0;$j<pow(2,$parent);$j++){
完整代码
define("MAX_GEN",5);
function detail($number) {
$d = mysql_query("select * from table where number = '$number'");
if(mysql_num_rows($d) == 0) {
$p[name] = "N/A";
$p[number] = "N/A";
$p[m_number] = "N/A";
$p[f_number] = "N/A";
}
else $p = mysql_fetch_assoc($d);
return $p;
}
$main_person_number=001;//number in database
$generation = 0;
$out[0][] =detail($number);// main person
$generation++; // next generation
for($i=1;$i<$MAX_GEN;$i++){
$parent=$generation-1;
for($j=0;$j<pow(2,$parent);$j++){
$record = detail($out[$parent][$j]['number']);
$out[$generation][] =$record[m_number];
$out[$generation][] =$record[m_number];
}
$generation++;
}
更新了 essam eg 的解决方案 - 现在完全有效:
- 在第一个 for cycle
中删除了 MAX_GET 之前的 char $
- 删除了循环中的 $generation ($i enough)
- 在 ($out[$i][] = $record[m_number]; 添加通话详情; -> $out[$i][] = detail($record[m_number]);)
- 修改添加父亲到数组(母亲两次,父亲失踪)
define("MAX_GEN",5);
function detail($number) {
$d = mysql_query("select * from table where number = '$number'");
if(mysql_num_rows($d) == 0) {
$p[name] = "N/A";
$p[number] = "N/A";
$p[m_number] = "N/A";
$p[f_number] = "N/A";
}
else $p = mysql_fetch_assoc($d);
return $p;
}
$main_person_number=001;//number in database
$out[0][] =detail($number);// main person
for($i=1;$i<MAX_GEN;$i++){
$parent=$i-1;
for($j=0;$j<pow(2,$parent);$j++){
$record = detail($out[$parent][$j]['number']);
$out[$i][] = detail($record[m_number]);
$out[$i][] = detail($record[f_number]);
}
}
我在数据库中有与 parents 相关的人,我需要创建递归函数,其中 return 数组与家谱树。数据库示例:
NUMBER;NAME;FATHER;MOTHER
001;Name1;002;005
002;Name2;007;018
003;Name3;018;025
005;Name5;006;019
023;Name23;019;045
018;Name18;062;097
007;Name7;;-
...
我准备了两个函数 - 第一个用于 man 详细信息,第二个用于搜索祖先的递归。
我需要这个结果:
$out[0][0] // first person
$out[1][0] // mother of first person
$out[1][1] // father of first person
$out[2][0] // grandmother of first person (mother side)
$out[2][1] // grandfather of first person (mother side)
$out[2][2] // grandmother of first person (father side)
$out[2][3] // grandmother of first person (father side)
...
下一代有 8 项,接下来有 16 项,...最多是 6 代。
我准备了两个函数 - 第一个用于 man detail,第二个用于树构建的递归。在第二个函数中
define("MAX_GEN",5);
function detail($number) {
$d = mysql_query("select * from table where number = '$number'");
if(mysql_num_rows($d) == 0) {
$p[name] = "N/A";
$p[number] = "N/A";
$p[m_number] = "N/A";
$p[f_number] = "N/A";
}
else $p = mysql_fetch_assoc($d);
return $p;
}
function gen($number, $generation = 0, $out) {
if ($generation >= MAX_GEN) {
return false;
}
$record = detail($number);
if ($generation == 0) $out[0][] = $record; // first man
$generation++; // next generation
if (!$out[$generation] && ($generation != MAX_GEN)) $out[$generation] = array();
$x_mother = gen($record[m_number], $generation ); // continue with mother
$x_father = gen($record[f_number], $generation ); // continue with father
if ($out[$generation]) {
$out[$generation][] = $x_mother;
$out[$generation][] = $x_father;
}
return $out;
}
但是在第二个函数中有问题 - 我不知道如何将带有结果的数组传递给下一代。它仍然是 return 一个元素,或者(经过几次尝试)它是我想要的 returns 数组,但在几代之间插入数组,结果无法使用。谁能帮帮我?
我想要的结果示例在这里:http://www.foxterrier.cz/_TM_importy/example.php
这主要是评论 - 但有点长。
您非常受数据库设计和所需输出格式的限制。即使不去 a graph database there are lots of ways of representing hierarchical data in a relational database 的 cost/complexity。
您的输出格式列出每一代,但不维护父-母关联,也不适合横向或向前映射 - 只能向后映射。
您的实施要求您 运行 2^N(其中 N 是代数)查询,每次从 PHP 代码返回 DBMS 进行一次往返。性能会很差。
至少你应该考虑一次解决一代:
$ref=mysql_real_escape_string(session_id());
mysql_query(
"INSERT INTO results (generation, number, ref) VALUES (0, $start_number, '$ref')"
);
for ($x=1; $x<=max_gens; $x++) {
mysql_query(
"INSERT INTO results (generation, number, ref)
SELECT $x, father, '$ref'
FROM yourtable yt JOIN results rs ON yt.number=results.number
WHERE rs.generation=$x-1
UNION
SELECT $x, mother, '$ref'
FROM yourtable yt JOIN results rs ON yt.number=results.number
WHERE rs.generation=$x-1"
);
}
(但有更多的错误检查 - 并记得稍后清除数据)
我更喜欢使用迭代来创建 $out 数组
代替gen函数
迭代次数增加 1 -> 2 -> 4 ->8
= 2 ^($generation-1)
$parent=$generation-1;
for($j=0;$j<pow(2,$parent);$j++){
完整代码
define("MAX_GEN",5);
function detail($number) {
$d = mysql_query("select * from table where number = '$number'");
if(mysql_num_rows($d) == 0) {
$p[name] = "N/A";
$p[number] = "N/A";
$p[m_number] = "N/A";
$p[f_number] = "N/A";
}
else $p = mysql_fetch_assoc($d);
return $p;
}
$main_person_number=001;//number in database
$generation = 0;
$out[0][] =detail($number);// main person
$generation++; // next generation
for($i=1;$i<$MAX_GEN;$i++){
$parent=$generation-1;
for($j=0;$j<pow(2,$parent);$j++){
$record = detail($out[$parent][$j]['number']);
$out[$generation][] =$record[m_number];
$out[$generation][] =$record[m_number];
}
$generation++;
}
更新了 essam eg 的解决方案 - 现在完全有效:
- 在第一个 for cycle
中删除了 MAX_GET 之前的 char $
- 删除了循环中的 $generation ($i enough)
- 在 ($out[$i][] = $record[m_number]; 添加通话详情; -> $out[$i][] = detail($record[m_number]);)
- 修改添加父亲到数组(母亲两次,父亲失踪)
define("MAX_GEN",5);
function detail($number) {
$d = mysql_query("select * from table where number = '$number'");
if(mysql_num_rows($d) == 0) {
$p[name] = "N/A";
$p[number] = "N/A";
$p[m_number] = "N/A";
$p[f_number] = "N/A";
}
else $p = mysql_fetch_assoc($d);
return $p;
}
$main_person_number=001;//number in database
$out[0][] =detail($number);// main person
for($i=1;$i<MAX_GEN;$i++){
$parent=$i-1;
for($j=0;$j<pow(2,$parent);$j++){
$record = detail($out[$parent][$j]['number']);
$out[$i][] = detail($record[m_number]);
$out[$i][] = detail($record[f_number]);
}
}