正文
php数据库无限二叉树 php实现二叉树
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
如何根据制定的数据使用PHP生成一个二叉树
假如你所说的二叉树是指这种的话
那么你的数据结构一定要满足一个条件，则每一条数据必须记录好父级的标识
?php
$data = array(
array(
'id' = 1,
'pid' = 0,
'name' = ""新建脑图,
),
array(
'id' = 2,
'pid' = 1,
'name' = "分支主题",
),
array(
'id' = 3,
'pid' = 1,
'name' = "分支主题",
),
);
?
上述二位数组中的 id为2，3的子数组的父级（pid）id均是1，则他们的父级就是id为1的数组
?php
foreach($data as $key=$value){
if( $value['pid'] == '0'){
$parent[] = $value;
unset($data[$key]);
}
}
foreach($parent as $key=$value){
foreach($data as $k=$v){
if( $v['pid'] == $value['id'] ){
$parent[$key]['_child'][] = $v;
unset($data[$k]);
}
}
}
?
通过以上循环过后，对应二叉树关系的数组就可以做出来了
当然上述代码只能进行到二级二叉树，如果想做出无限级二叉树的数组，则必须使用到递归函数了
PS：上述代码是网页里手打的，没经过测试，但思路肯定是没问题的哈
相关问答
Q1: PHP版本二叉树按层 从上到下左到右完全二叉树
?php
/** * 二叉树的定义 */
class BinaryTree {
protected $key = NULL; // 当前节点的值
protected $left = NULL; // 左子树
protected $right = NULL; // 右子树
/** * 以指定的值构造二叉树php数据库无限二叉树，并指定左右子树 *
* @param mixed $key 节点的值.
* @param mixed $left 左子树节点.
* @param mixed $right 右子树节点.
*/
public function __construct( $key = NULL, $left = NULL, $right = NULL) {
$this-key = $key;
if ($key === NULL) {
$this-left = NULL;
$this-right = NULL;
}
elseif ($left === NULL) {
$this-left = new BinaryTree();
$this-right = new BinaryTree();
}
else {
$this-left = $left;
$this-right = $right;
}
}
/**
* 析构方法.
*/
public function __destruct() {
$this-key = NULL;
$this-left = NULL;
$this-right = NULL;
}
/**
* 清空二叉树.
**/
public function purge () {
$this-key = NULL;
$this-left = NULL;
$this-right = NULL;
}
/**
* 测试当前节点是否是叶节点.
*
* @return boolean 如果节点非空并且有两个空的子树时为真php数据库无限二叉树，否则为假.
*/
public function isLeaf() {
return !$this-isEmpty()
$this-left-isEmpty()
$this-right-isEmpty();
}
/**
* 测试节点是否为空
*
* @return boolean 如果节点为空返回真，否则为假.
*/
public function isEmpty() {
return $this-key === NULL;
}
/**
* Key getter.
*
* @return mixed 节点的值.
*/
public function getKey() {
if ($this-isEmpty()) {
return false;
}
return $this-key;
}
/**
* 给节点指定Key值,节点必须为空
*
* @param mixed $object 添加的Key值.
*/
public function attachKey($obj) {
if (!$this-isEmpty())
return false;
$this-key = $obj;
$this-left = new BinaryTree();
$this-right = new BinaryTree();
}
/**
* 删除key值，使得节点为空.
*/
public function detachKey() {
if (!$this-isLeaf())
return false;
$result = $this-key;
$this-key = NULL;
$this-left = NULL;
$this-right = NULL;
return $result;
}
/**
* 返回左子树
*
* @return object BinaryTree 当前节点的左子树.
*/
public function getLeft() {
if ($this-isEmpty())
return false;
return $this-left;
}
/**
* 给当前结点添加左子树
*
* @param object BinaryTree $t 给当前节点添加的子树.
*/
public function attachLeft(BinaryTree $t) {
if ($this-isEmpty() || !$this-left-isEmpty())
return false;
$this-left = $t;
}
/**
* 删除左子树
*
* @return object BinaryTree 返回删除的左子树.
*/
public function detachLeft() {
if ($this-isEmpty())
return false;
$result = $this-left;
$this-left = new BinaryTree();
return $result;
}
/**
* 返回当前节点的右子树
*
* @return object BinaryTree 当前节点的右子树.
*/
public function getRight() {
if ($this-isEmpty())
return false;
return $this-right;
}
/**
* 给当前节点添加右子树
*
* @param object BinaryTree $t 需要添加的右子树.
*/
public function attachRight(BinaryTree $t) {
if ($this-isEmpty() || !$this-right-isEmpty())
return false;
$this-right = $t;
}
/**
* 删除右子树，并返回此右子树
* @return object BinaryTree 删除的右子树.
*/
public function detachRight() {
if ($this-isEmpty ())
return false;
$result = $this-right;
$this-right = new BinaryTree();
return $result;
}
/**
* 先序遍历
*/
public function preorderTraversal() {
if ($this-isEmpty()) {
return ;
}
echo ' ', $this-getKey();
$this-getLeft()-preorderTraversal();
$this-getRight()-preorderTraversal();
}
/**
* 中序遍历
*/
public function inorderTraversal() {
if ($this-isEmpty()) {
return ;
}
$this-getLeft()-preorderTraversal();
echo ' ', $this-getKey();
$this-getRight()-preorderTraversal();
}
/**
* 后序遍历
*/
public function postorderTraversal() {
if ($this-isEmpty()) {
return ;
}
$this-getLeft()-preorderTraversal();
$this-getRight()-preorderTraversal();
echo ' ', $this-getKey();
}
}
/**
* 二叉排序树的PHP实现
*/
class BST extends BinaryTree {
/**
* 构造空的二叉排序树
*/
public function __construct() {
parent::__construct(NULL, NULL, NULL);
}
/**
* 析构
*/
public function __destruct() {
parent::__destruct();
}
/**
* 测试二叉排序树中是否包含参数所指定的值
*
* @param mixed $obj 查找的值.
* @return boolean True 如果存在于二叉排序树中则返回真，否则为假期
*/
public function contains($obj) {
if ($this-isEmpty())
return false;
$diff = $this-compare($obj);
if ($diff == 0) {
return true;
}elseif ($diff 0) return $this-getLeft()-contains($obj);
else
return $this-getRight()-contains($obj);
}
/**
* 查找二叉排序树中参数所指定的值的位置
*
* @param mixed $obj 查找的值.
* @return boolean True 如果存在则返回包含此值的对象，否则为NULL
*/
public function find($obj) {
if ($this-isEmpty())
return NULL;
$diff = $this-compare($obj);
if ($diff == 0)
return $this-getKey();
elseif ($diff 0) return $this-getLeft()-find($obj);
else
return $this-getRight()-find($obj);
}
/**
* 返回二叉排序树中的最小值
* @return mixed 如果存在则返回最小值，否则返回NULL
*/
public function findMin() {
if ($this-isEmpty ())
return NULL;
elseif ($this-getLeft()-isEmpty())
return $this-getKey();
else
return $this-getLeft()-findMin();
}
/**
* 返回二叉排序树中的最大值
* @return mixed 如果存在则返回最大值，否则返回NULL
*/
public function findMax() {
if ($this-isEmpty ())
return NULL;
elseif ($this-getRight()-isEmpty())
return $this-getKey();
else
return $this-getRight()-findMax();
}
/**
* 给二叉排序树插入指定值
*
* @param mixed $obj 需要插入的值.
* 如果指定的值在树中存在，则返回错误
*/
public function insert($obj) {
if ($this-isEmpty()) {
$this-attachKey($obj);
} else {
$diff = $this-compare($obj);
if ($diff == 0)
die('argu error');
if ($diff 0) $this-getLeft()-insert($obj);
else
$this-getRight()-insert($obj);
}
$this-balance();
}
/**
* 从二叉排序树中删除指定的值
*
* @param mixed $obj 需要删除的值.
*/
public function delete($obj) {
if ($this-isEmpty ())
die();
$diff = $this-compare($obj);
if ($diff == 0) {
if (!$this-getLeft()-isEmpty()) {
$max = $this-getLeft()-findMax();
$this-key = $max;
$this-getLeft()-delete($max);
}
elseif (!$this-getRight()-isEmpty()) {
$min = $this-getRight()-findMin();
$this-key = $min;
$this-getRight()-delete($min);
} else
$this-detachKey();
} else if ($diff 0) $this-getLeft()-delete($obj);
else
$this-getRight()-delete($obj);
$this-balance();
}
public function compare($obj) {
return $obj - $this-getKey();
}
/**
* Attaches the specified object as the key of this node.
* The node must be initially empty.
*
* @param object IObject $obj The key to attach.
* @exception IllegalOperationException If this node is not empty.
*/
public function attachKey($obj) {
if (!$this-isEmpty())
return false;
$this-key = $obj;
$this-left = new BST();
$this-right = new BST();
}
/**
* Balances this node.
* Does nothing in this class.
*/
protected function balance () {}
/**
* Main program.
*
* @param array $args Command-line arguments.
* @return integer Zero on success; non-zero on failure.
*/
public static function main($args) {
printf("BinarySearchTree main program.\n");
$root = new BST();
foreach ($args as $row) {
$root-insert($row);
}
return $root;
}
}
$root = BST::main(array(50, 3, 10, 5, 100, 56, 78));
echo $root-findMax();
$root-delete(100);
echo $root-findMax();
Q2: 求php+mysql 的二叉树每一层的叶子统计
Hi，这是一个很有意思的问题，二叉树，无限极分类一般都会用到递归。这里使用函数来模拟mysql查询，解决思路如下：
?php
header("Content-type:text/html;charset=utf-8");
$data = array(
array('id'=1, 'pid'= 0, 'name'= 'name1'),
array('id'=2, 'pid'= 1, 'name'= 'name2'),
array('id'=3, 'pid'= 2, 'name'= 'name3'),
array('id'=4, 'pid'= 3, 'name'= 'name4'),
array('id'=5, 'pid'= 2, 'name'= 'name5'),
array('id'=6, 'pid'= 2, 'name'= 'name6'),
array('id'=7, 'pid'= 2, 'name'= 'name7'),
array('id'=8, 'pid'= 7, 'name'= 'name8'),
array('id'=9, 'pid'= 8, 'name'= 'name9'),
array('id'=10, 'pid'= 9, 'name'= 'name10'),
array('id'=11, 'pid'= 10, 'name'= 'name11'),
array('id'=12, 'pid'= 11, 'name'= 'name12'),
array('id'=13, 'pid'= 12, 'name'= 'name13'),
array('id'=14, 'pid'= 13, 'name'= 'name14'),
array('id'=15, 'pid'= 14, 'name'= 'name15'),
array('id'=16, 'pid'= 1, 'name'= 'name16'),
array('id'=17, 'pid'= 16, 'name'= 'name17'),
array('id'=18, 'pid'= 17, 'name'= 'name18'),
array('id'=19, 'pid'= 18, 'name'= 'name19'),
array('id'=20, 'pid'= 3, 'name'= 'name20'),
array('id'=21, 'pid'= 3, 'name'= 'name21'),
array('id'=22, 'pid'= 2, 'name'= 'name22'),
);
$result = array();
$id = 2;
$lv = 20;
get_child_node_nums($id, $lv, $result);
foreach($result as $no = $row)
{
echo '第'.($lv-$no+1).'层有'.count($row).'个叶子节点'.'br/';
}
p($result);
//模拟mysql根据pid获取多行记录
function fetch_rows($pid=0)
{
global $data;
$pid = (int)$pid;
$items = array();
//相当于sql语句:select * from test where pid=$pid
echo "select * from test where pid=$pid;br/";
foreach($data as $row)
{
if($row['pid'] == $pid)
{
$items[] = $row;
}
}
return $items;
}
//$id为父节点id, $lv为深度, $result为引用传值结果数组
function get_child_node_nums($id, $lv, $result)
{
//首先根据其id作为子节点的pid获取其所有子节点
$children = fetch_rows($id);
if($children)
{
//存储其叶子节点
if(isset($result[$lv]))
{
$result[$lv] = array_merge($result[$lv], $children);
}else{
$result[$lv] = $children;
}
$lv--;
if($lv 0)
{
foreach($children as $child)
{
$id = $child['id'];
get_child_node_nums($id, $lv, $result);
}
}
}
}
function p($var)
{
echo 'pre';
if($var === false)
{
echo 'false';
}else if($var === null){
print_r("null");
}else if($var === ''){
print_r("''");
}else{
print_r($var);
}
echo '/pre';
}
输出结果如下：
select * from test where pid=2;
select * from test where pid=3;
select * from test where pid=4;
select * from test where pid=20;
select * from test where pid=21;
select * from test where pid=5;
select * from test where pid=6;
select * from test where pid=7;
select * from test where pid=8;
select * from test where pid=9;
select * from test where pid=10;
select * from test where pid=11;
select * from test where pid=12;
select * from test where pid=13;
select * from test where pid=14;
select * from test where pid=15;
select * from test where pid=22;
第1层有5个叶子节点
第2层有4个叶子节点
第3层有1个叶子节点
第4层有1个叶子节点
第5层有1个叶子节点
第6层有1个叶子节点
第7层有1个叶子节点
第8层有1个叶子节点
第9层有1个叶子节点
Array
(
[20] = Array
(
[0] = Array
(
[id] = 3
[pid] = 2
[name] = name3
)
[1] = Array
(
[id] = 5
[pid] = 2
[name] = name5
)
[2] = Array
(
[id] = 6
[pid] = 2
[name] = name6
)
[3] = Array
(
[id] = 7
[pid] = 2
[name] = name7
)
[4] = Array
(
[id] = 22
[pid] = 2
[name] = name22
)
)
[19] = Array
(
[0] = Array
(
[id] = 4
[pid] = 3
[name] = name4
)
[1] = Array
(
[id] = 20
[pid] = 3
[name] = name20
)
[2] = Array
(
[id] = 21
[pid] = 3
[name] = name21
)
[3] = Array
(
[id] = 8
[pid] = 7
[name] = name8
)
)
[18] = Array
(
[0] = Array
(
[id] = 9
[pid] = 8
[name] = name9
)
)
[17] = Array
(
[0] = Array
(
[id] = 10
[pid] = 9
[name] = name10
)
)
[16] = Array
(
[0] = Array
(
[id] = 11
[pid] = 10
[name] = name11
)
)
[15] = Array
(
[0] = Array
(
[id] = 12
[pid] = 11
[name] = name12
)
)
[14] = Array
(
[0] = Array
(
[id] = 13
[pid] = 12
[name] = name13
)
)
[13] = Array
(
[0] = Array
(
[id] = 14
[pid] = 13
[name] = name14
)
)
[12] = Array
(
[0] = Array
(
[id] = 15
[pid] = 14
[name] = name15
)
)
)
亲测，望采纳^_^。
关于php数据库无限二叉树和php实现二叉树的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
