求教大家一个小算法有关问题
程序员文章站
2022-04-22 07:53:19
...
求教大家一个小算法问题
树状流程图:
表结构
这个表结构就是每个节点都有三个子节点,left、center、right,要求就是在适当的位置插入节点,插入的规则就是:假设从id=1开始,然后找出其下的三个子节点,如果三个子节点都存在,就分别查找三个子节点的子节点。直到所在的子节点没有数据,就可以插入了
具体流程走法:如树状图:id = 1开始查找,查找其子节点,有2 ,3, 4,都是存在的,然后在查找2的子节点,5,6,7也都是存在的,然后在查找3的子节点,只有8,然后就可以在3的中间的子节点插入了。当然数据越多,查找的也会越多。一直在想,没想出来,急的很,希望大神给个具体代码的算法,万分感谢。
------解决思路----------------------
以前在网上找到的php二叉树,我改了一点,变成三叉树,其实就加了个center
树状流程图:
表结构
这个表结构就是每个节点都有三个子节点,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] =>相关文章
相关视频
- 详解win10下PHP的安装配置(以php5.6为...
- php Swoole实现毫秒定时计划任务(详解)
- 一文详解Windows和Linux环境下怎么安装配...
- 【DTM】PHP协程客户端v0.1 beta版本发...
- 求教大家一个小算法有关问题
上一篇: 看到一个PHP题目,很费解不知道原因,求高人解决办法
下一篇: C++菱形继承