求教大家一个小算法问题

树状流程图：


表结构


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