ちょっとしたアルゴリズムの問​​題を教えたいと思います。

ツリー フローチャート:


テーブル構造


このテーブル構造は、各ノードに左、中央、右の 3 つの子ノードがあるというものです。挿入ルールは次のとおりです。 id= 1 から開始し、その下の 3 つのサブノードを検索します。3 つのサブノードがすべて存在する場合は、3 つのサブノードのサブノードをそれぞれ検索します。子ノードにデータがなくなるまで、子ノードを挿入できます
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 を確認してから、その左、中央、右をすべて確認できます

(1) 左、中央、右がすべてある場合は、いっぱいであることを意味し、左を直接挿入します新しいレコードの

(2) 左と中央がある場合は右を挿入

(3) 左がある場合は中央を挿入
現時点でのフローチャート (増分フィールド) の最大の問題は、ID がある場合にその ID を調整する方法です。削除する必要があります

三分木を形成するために、実際にセンターを追加します
ノードオブジェクト

*RECURSION *

[親] => Node Object
*RECURSION* [left] = >
最初に最大の ID を確認し、次にその左、中央、右をすべて確認できます
(1) がある場合、説明は次のようになりますフル、新しいレコードの左を直接挿入
(2) 左と中央が存在する場合は右を挿入
(3) 左が存在する場合は中央を挿入
現時点でのフローチャート (増分フィールド) の最大の問題は、は削除要件、IDの調整方法です
削除要件はなく、追加のみです

実際の使い方はわかりませんが、実装するのは難しくありません

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*/

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