求教大家一个小算法有关问题

求教大家一个小算法问题
树状流程图：


表结构


这个表结构就是每个节点都有三个子节点，left、center、right，要求就是在适当的位置插入节点，插入的规则就是：假设从id=1开始，然后找出其下的三个子节点，如果三个子节点都存在，就分别查找三个子节点的子节点。直到所在的子节点没有数据，就可以插入了
        
        
具体流程走法：如树状图：id = 1开始查找，查找其子节点，有2 ，3， 4，都是存在的，然后在查找2的子节点，5,6,7也都是存在的，然后在查找3的子节点，只有8，然后就可以在3的中间的子节点插入了。当然数据越多，查找的也会越多。一直在想，没想出来，急的很，希望大神给个具体代码的算法，万分感谢。
------解决思路----------------------
以前在网上找到的php二叉树，我改了一点，变成三叉树，其实就加了个center

<br />class Node {<br />	public $data = null;<br />	public $parent = null;<br />	public $left = null;<br />	public $center =null;<br />	public $right = null;<br />}<br /><br />function build_cbtree($a) {<br />	$root = new Node();<br />	$root->data = $a[0];<br />	for ($i = 1; $i < count($a); $i++) {<br />		$node = new Node();<br />		$node->data = $a[$i];<br />		insert_node($root, $node);<br />	}<br />	return $root;<br />}<br /><br />function insert_node($root, $inode) {<br />	$queue = array();<br />	array_unshift($queue, $root);<br />	while (!empty($queue)) {<br />		$cnode = array_pop($queue);<br />		if ($cnode->left == null) {<br />			$cnode->left = $inode;<br />			$inode->parent = $cnode;<br />			return $root;<br />		} else {<br />			array_unshift($queue, $cnode->left);                <br />		}<br />		if ($cnode->center == null) {<br />			$cnode->center = $inode;<br />			$inode->parent = $cnode;<br />			return $root;<br />		} else {<br />			array_unshift($queue, $cnode->center);<br />		}<br />		if ($cnode->right == null) {<br />			$cnode->right = $inode;<br />			$inode->parent = $cnode;<br />			return $root;<br />		} else {<br />			array_unshift($queue, $cnode->right);<br />		}<br />	}<br />	return $root;<br />}<br />//广度优先遍历（先遍历一层，再遍历下一层）<br />function bf_traverse($root) {<br />	$queue = array();<br />	array_unshift($queue, $root);<br />	while (!empty($queue)) {<br />		$cnode = array_pop($queue);<br />		echo $cnode->data . " ";<br />		if ($cnode->left !== null) array_unshift($queue, $cnode->left);<br />		if ($cnode->center !== null) array_unshift($queue, $cnode->center);<br />		if ($cnode->right !== null) array_unshift($queue, $cnode->right);<br />	}<br />}<br /><br />$a = array(1,2,3,4,5,6,7,8);<br />//先把数组变成三叉树<br />$root = build_cbtree($a);<br /><br />echo "<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">";<br />print_r($root);<br />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 "

";<br />print_r($root);<br />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] =>