Maison > développement back-end > tutoriel php > 求教大家一个小算法问题

求教大家一个小算法问题

WBOY
Libérer: 2016-06-23 13:49:08
original
734 Les gens l'ont consulté

树状流程图:


表结构


这个表结构就是每个节点都有三个子节点,left、center、right,要求就是在适当的位置插入节点,插入的规则就是:假设从id=1开始,然后找出其下的三个子节点,如果三个子节点都存在,就分别查找三个子节点的子节点。直到所在的子节点没有数据,就可以插入了
        
        
具体流程走法:如树状图:id = 1开始查找,查找其子节点,有2 ,3, 4,都是存在的,然后在查找2的子节点,5,6,7也都是存在的,然后在查找3的子节点,只有8,然后就可以在3的中间的子节点插入了。当然数据越多,查找的也会越多。一直在想,没想出来,急的很,希望大神给个具体代码的算法,万分感谢。


回复讨论(解决方案)

这么有规律的东西,不用考虑那么复杂吧
从1开始,每个数字3个子节点,可以推导出公式计算任何位置所处层数和上下层的数字
数据表正常记录就好

我上面说的数字只是举例,有可能id=1下面是111,121,220,靠公式推导这个会出问题恩

#1说的没错,你自左向右依次填写就可以了,填满就加一条记录

话说你虽然画了个树,实际上并没用枝叶间的关系

 三叉?,可以?考二叉?的算法。

select id from table where left_id is null order by id limit 1;//如果存在 则可以往这个id 插入 左节点,然后结束return;select id from table where center_id is null order by id limit 1;//如果存在 则可以往这个id 插入 中间节点,然后结束return;select id from table where right_id is null order by id limit 1;//如果存在 则可以往这个id 插入 右节点,然后结束return;//直接插入id
Copier après la connexion

可以先查最大id,然后查它的所有left、center、right
(1)如果都有,说明已满,直接插入新纪录的left
(2)如果left、center有,插入right
(3)如果left有,插入center
目前你这个流程图(递增字段)最大的问题是,如果有删除需求,怎么调整id

以前在网上找到的php二叉树,我改了一点,变成三叉树,其实就加了个center

class Node {	public $data = null;	public $parent = null;	public $left = null;	public $center =null;	public $right = null;}function build_cbtree($a) {	$root = new Node();	$root->data = $a[0];	for ($i = 1; $i < count($a); $i++) {		$node = new Node();		$node->data = $a[$i];		insert_node($root, $node);	}	return $root;}function insert_node($root, $inode) {	$queue = array();	array_unshift($queue, $root);	while (!empty($queue)) {		$cnode = array_pop($queue);		if ($cnode->left == null) {			$cnode->left = $inode;			$inode->parent = $cnode;			return $root;		} else {			array_unshift($queue, $cnode->left);                		}		if ($cnode->center == null) {			$cnode->center = $inode;			$inode->parent = $cnode;			return $root;		} else {			array_unshift($queue, $cnode->center);		}		if ($cnode->right == null) {			$cnode->right = $inode;			$inode->parent = $cnode;			return $root;		} else {			array_unshift($queue, $cnode->right);		}	}	return $root;}//广度优先遍历(先遍历一层,再遍历下一层)function bf_traverse($root) {	$queue = array();	array_unshift($queue, $root);	while (!empty($queue)) {		$cnode = array_pop($queue);		echo $cnode->data . " ";		if ($cnode->left !== null) array_unshift($queue, $cnode->left);		if ($cnode->center !== null) array_unshift($queue, $cnode->center);		if ($cnode->right !== null) array_unshift($queue, $cnode->right);	}}$a = array(1,2,3,4,5,6,7,8);//先把数组变成三叉树$root = build_cbtree($a);echo "<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">";print_r($root);echo "
Copier après la connexion
Copier après la connexion
";bf_traverse($root);/*$root数据太多就不打出来了根据广度优先遍历规则得1 2 3 4 5 6 7 8*///此时$root就是一个三叉树//插入9,其实就是重复build_cbtree的方法中for循环的代码$node1 = new Node();$node1->data =9;insert_node($root, $node1);echo "
";print_r($root);echo "
Copier après la connexion
";bf_traverse($root);/*Node Object( [data] => 1 [parent] => [left] => Node Object ( [data] => 2 [parent] => Node Object *RECURSION* [left] => Node Object ( [data] => 5 [parent] => Node Object *RECURSION* [left] => [center] => [right] => ) [center] => Node Object ( [data] => 6 [parent] => Node Object *RECURSION* [left] => [center] => [right] => ) [right] => Node Object ( [data] => 7 [parent] => Node Object *RECURSION* [left] => [center] => [right] => ) ) [center] => Node Object ( [data] => 3 [parent] => Node Object *RECURSION* [left] => Node Object ( [data] => 8 [parent] => Node Object *RECURSION* [left] => [center] => [right] => ) [center] => Node Object ( [data] => 9 [parent] => Node Object *RECURSION* [left] => [center] => [right] => ) [right] => ) [right] => Node Object ( [data] => 4 [parent] => Node Object *RECURSION* [left] => [center] => [right] => ))根据广度优先遍历规则得1 2 3 4 5 6 7 8 9*/

[center] => Node Object
(
[data] => 9
[parent] => Node Object
*RECURSION*
[left] =>
[center] =>
[right] =>
)
就是插入进去的位置

可以先查最大id,然后查它的所有left、center、right
(1)如果都有,说明已满,直接插入新纪录的left
(2)如果left、center有,插入right
(3)如果left有,插入center
目前你这个流程图(递增字段)最大的问题是,如果有删除需求,怎么调整id

这个没有删除需求,只有增加

虽然不明白这个有什么实际用途,但是实现起来也还是不算难的

mysql_connect();mysql_selectdb('test');mysql_query("create temporary table T (id int, left_id int null, conter_id int null, right_id int null)");for($i=1; $i<=8; $i++) {  $rs = mysql_query("select * from T where right_id is null limit 1");  if(mysql_num_rows($rs) == 0) {    mysql_query("insert into T (id) values ($i)");    continue;  }  foreach($r = mysql_fetch_assoc($rs) as $k=>$v) {    if($k == 'id') continue;    if(empty($v)) {      mysql_query("insert into T (id) values ($i)");      mysql_query("update T set $k=$i where id=$r[id]");      break;    }  }}$rs = mysql_query('select * from T');while($r = mysql_fetch_row($rs)) {  echo join("\t", $r), PHP_EOL;}
Copier après la connexion
1	2	3	42	5	6	73	8		4			5			6			7			8	
Copier après la connexion

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Recommandations populaires
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal