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

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


表结构


这个表结构就是每个节点都有三个子节点，left、center、right，要求就是在适当的位置插入节点，插入的规则就是：假设从id=1开始，然后找出其下的三个子节点，如果三个子节点都存在，就分别查找三个子节点的子节点。直到所在的子节点没有数据，就可以插入了


具体流程走法：如树状图：id = 1开始查找，查找其子节点，有2 ，3， 4，都是存在的，然后在查找2的子节点，5,6,7也都是存在的，然后在查找3的子节点，只有8，然后就可以在3的中间的子节点插入了。当然数据越多，查找的也会越多。一直在想，没想出来，急的很，希望大神给个具体代码的算法，万分感谢。
------解决思路----------------------
以前在网上找到的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 		$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 "
";
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] => 

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系[e-mail]核实处理。
相关文章
相关视频

• 详解win10下PHP的安装配置（以php5.6为...
• php Swoole实现毫秒定时计划任务（详解）
• 【DTM】PHP协程客户端v0.1 beta版本发...
• PHP 对 memcache操作类
• 求教大家一个小算法有关问题