求教大家一个小算法问题
- 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