首页  >  文章  >  后端开发  >  求教大家一个小算法问题

求教大家一个小算法问题

WBOY
WBOY原创
2016-06-23 13:49:08720浏览

树状流程图:


表结构


这个表结构就是每个节点都有三个子节点,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

可以先查最大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 "<pre class="brush:php;toolbar:false">";print_r($root);echo "
";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 "
";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;}
1	2	3	42	5	6	73	8		4			5			6			7			8	

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn