求教大家一个小算法问题

Question

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

Answer 1

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

Answer 2

以前在网上找到的php二叉树，我改了一点，变成三叉树，其实就加了个centerclass 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>";
print_r($root);
echo "</pre>";
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 "<pre>";
print_r($root);
echo "</pre>";
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] => 
                )
就是插入进去的位置

Answer 3

虽然不明白这个有什么实际用途，但是实现起来也还是不算难的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 4
2 5 6 7
3 8
4
5
6
7
8