欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

程序员文章站 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

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] =>
求教大家一个小算法有关问题

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频