求教大家一个小算法问题-tutoriel php-php.cn

求教大家一个小算法问题

WBOY

Libérer： 2016-06-23 13:49:08

original

723 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

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

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;}