php二叉树

① 求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($resultas$no=>$row)
{
echo'第'.($lv-$no+1).'层有'.count($row).'个叶子节点'.'<br/>';
}

p($result);

//模拟mysql根据pid获取多行记录
functionfetch_rows($pid=0)
{
global$data;
$pid=(int)$pid;
$items=array();
//相当于sql语句:select*fromtestwherepid=$pid
echo"select*fromtestwherepid=$pid;<br/>";
foreach($dataas$row)
{
if($row['pid']==$pid)
{
$items[]=$row;
}
}
return$items;
}

//$id为父节点id,$lv为深度,$result为引用传值结果数组
functionget_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($childrenas$child)
{
$id=$child['id'];
get_child_node_nums($id,$lv,$result);
}
}
}
}

functionp($var)
{
echo'<pre>';
if($var===false)
{
echo'false';
}elseif($var===null){
print_r("null");
}elseif($var===''){
print_r("''");
}else{
print_r($var);
}
echo'</pre>';
}

输出结果如下：

select*fromtestwherepid=2;
select*fromtestwherepid=3;
select*fromtestwherepid=4;
select*fromtestwherepid=20;
select*fromtestwherepid=21;
select*fromtestwherepid=5;
select*fromtestwherepid=6;
select*fromtestwherepid=7;
select*fromtestwherepid=8;
select*fromtestwherepid=9;
select*fromtestwherepid=10;
select*fromtestwherepid=11;
select*fromtestwherepid=12;
select*fromtestwherepid=13;
select*fromtestwherepid=14;
select*fromtestwherepid=15;
select*fromtestwherepid=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，二叉树，求一个算法

var oNowNode;//现节点
var aArray;//所存数组

var i=0;
if(oNowNode.sibling.id>oNowNode.id){
alert(”位于左区“)；

}else{
alert(”位于右区“)；

}
while(oNowNode.id!=0){
oNowNode=oNowNode.parent;
aArray(i)=oNowNode.id;
i++;
}
print_r(aArray)；

③ 数据结构算法在php编程中的作用

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
使用php实现的基本的数据结构和算法，什么二叉树、二叉搜索树、AVL树、B树、链表和常见排序、搜索算法等等，而且全部是使用面向对象来实现的，确是是很强。

④ PHP版本二叉树按层 从上到下左到右完全二叉树

<?php
/***二叉树的定义*/
classBinaryTree{
protected$key=NULL;//当前节点的值
protected$left=NULL;//左子树
protected$right=NULL;//右子树
/***以指定的值构造二叉树，并指定左右子树*
*@parammixed$key节点的值.
*@parammixed$left左子树节点.
*@parammixed$right右子树节点.
*/
publicfunction__construct($key=NULL,$left=NULL,$right=NULL){
$this->key=$key;
if($key===NULL){
$this->left=NULL;
$this->right=NULL;
}
elseif($left===NULL){
$this->left=newBinaryTree();
$this->right=newBinaryTree();
}
else{
$this->left=$left;
$this->right=$right;
}
}

/**
*析构方法.
*/
publicfunction__destruct(){
$this->key=NULL;
$this->left=NULL;
$this->right=NULL;
}

/**
*清空二叉树.
**/
publicfunctionpurge(){
$this->key=NULL;
$this->left=NULL;
$this->right=NULL;
}

/**
*测试当前节点是否是叶节点.
*
*@returnboolean如果节点非空并且有两个空的子树时为真，否则为假.
*/
publicfunctionisLeaf(){
return!$this->isEmpty()&&
$this->left->isEmpty()&&
$this->right->isEmpty();
}

/**
*测试节点是否为空
*
*@returnboolean如果节点为空返回真，否则为假.
*/
publicfunctionisEmpty(){
return$this->key===NULL;
}

/**
*Keygetter.
*
*@returnmixed节点的值.
*/
publicfunctiongetKey(){
if($this->isEmpty()){
returnfalse;
}
return$this->key;
}

/**
*给节点指定Key值,节点必须为空
*
*@parammixed$object添加的Key值.
*/
publicfunctionattachKey($obj){
if(!$this->isEmpty())
returnfalse;
$this->key=$obj;
$this->left=newBinaryTree();
$this->right=newBinaryTree();
}

/**
*删除key值，使得节点为空.
*/
publicfunctiondetachKey(){
if(!$this->isLeaf())
returnfalse;
$result=$this->key;
$this->key=NULL;
$this->left=NULL;
$this->right=NULL;
return$result;
}

/**
*返回左子树
*
*@returnobjectBinaryTree当前节点的左子树.
*/
publicfunctiongetLeft(){
if($this->isEmpty())
returnfalse;
return$this->left;
}

/**
*给当前结点添加左子树
*
*@paramobjectBinaryTree$t给当前节点添加的子树.
*/
publicfunctionattachLeft(BinaryTree$t){
if($this->isEmpty()||!$this->left->isEmpty())
returnfalse;
$this->left=$t;
}

/**
*删除左子树
*
*@returnobjectBinaryTree返回删除的左子树.
*/
publicfunctiondetachLeft(){
if($this->isEmpty())
returnfalse;
$result=$this->left;
$this->left=newBinaryTree();
return$result;
}

/**
*返回当前节点的右子树
*
*@returnobjectBinaryTree当前节点的右子树.
*/
publicfunctiongetRight(){
if($this->isEmpty())
returnfalse;
return$this->right;
}

/**
*给当前节点添加右子树
*
*@paramobjectBinaryTree$t需要添加的右子树.
*/
publicfunctionattachRight(BinaryTree$t){
if($this->isEmpty()||!$this->right->isEmpty())
returnfalse;
$this->right=$t;
}

/**
*删除右子树，并返回此右子树
*@returnobjectBinaryTree删除的右子树.
*/
publicfunctiondetachRight(){
if($this->isEmpty())
returnfalse;
$result=$this->right;
$this->right=newBinaryTree();
return$result;
}

/**
*先序遍历
*/
(){
if($this->isEmpty()){
return;
}
echo'',$this->getKey();
$this->getLeft()->preorderTraversal();
$this->getRight()->preorderTraversal();
}

/**
*中序遍历
*/
(){
if($this->isEmpty()){
return;
}
$this->getLeft()->preorderTraversal();
echo'',$this->getKey();
$this->getRight()->preorderTraversal();
}

/**
*后序遍历
*/
(){
if($this->isEmpty()){
return;
}
$this->getLeft()->preorderTraversal();
$this->getRight()->preorderTraversal();
echo'',$this->getKey();
}
}

/**
*二叉排序树的PHP实现
*/

classBSTextendsBinaryTree{
/**
*构造空的二叉排序树
*/
publicfunction__construct(){
parent::__construct(NULL,NULL,NULL);
}

/**
*析构
*/
publicfunction__destruct(){
parent::__destruct();
}

/**
*测试二叉排序树中是否包含参数所指定的值
*
*@parammixed$obj查找的值.
*@returnbooleanTrue如果存在于二叉排序树中则返回真，否则为假期
*/
publicfunctioncontains($obj){
if($this->isEmpty())
returnfalse;
$diff=$this->compare($obj);
if($diff==0){
returntrue;
}elseif($diff<0)return$this->getLeft()->contains($obj);
else
return$this->getRight()->contains($obj);
}

/**
*查找二叉排序树中参数所指定的值的位置
*
*@parammixed$obj查找的值.
*@returnbooleanTrue如果存在则返回包含此值的对象，否则为NULL
*/
publicfunctionfind($obj){
if($this->isEmpty())
returnNULL;
$diff=$this->compare($obj);
if($diff==0)
return$this->getKey();
elseif($diff<0)return$this->getLeft()->find($obj);
else
return$this->getRight()->find($obj);
}

/**
*返回二叉排序树中的最小值
*@returnmixed如果存在则返回最小值，否则返回NULL
*/
publicfunctionfindMin(){
if($this->isEmpty())
returnNULL;
elseif($this->getLeft()->isEmpty())
return$this->getKey();
else
return$this->getLeft()->findMin();
}

/**
*返回二叉排序树中的最大值
*@returnmixed如果存在则返回最大值，否则返回NULL
*/
publicfunctionfindMax(){
if($this->isEmpty())
returnNULL;
elseif($this->getRight()->isEmpty())
return$this->getKey();
else
return$this->getRight()->findMax();
}

/**
*给二叉排序树插入指定值
*
*@parammixed$obj需要插入的值.
*如果指定的值在树中存在，则返回错误
*/
publicfunctioninsert($obj){
if($this->isEmpty()){
$this->attachKey($obj);
}else{
$diff=$this->compare($obj);
if($diff==0)
die('arguerror');
if($diff<0)$this->getLeft()->insert($obj);
else
$this->getRight()->insert($obj);
}
$this->balance();
}

/**
*从二叉排序树中删除指定的值
*
*@parammixed$obj需要删除的值.
*/
publicfunctiondelete($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();
}elseif($diff<0)$this->getLeft()->delete($obj);
else
$this->getRight()->delete($obj);
$this->balance();
}

publicfunctioncompare($obj){
return$obj-$this->getKey();
}

/**
*.
*Thenodemustbeinitiallyempty.
*
*@paramobjectIObject$objThekeytoattach.
*@.
*/
publicfunctionattachKey($obj){
if(!$this->isEmpty())
returnfalse;
$this->key=$obj;
$this->left=newBST();
$this->right=newBST();
}

/**
*Balancesthisnode.
*Doesnothinginthisclass.
*/
protectedfunctionbalance(){}

/**
*Mainprogram.
*
*@paramarray$argsCommand-linearguments.
*@returnintegerZeroonsuccess;non-zeroonfailure.
*/
publicstaticfunctionmain($args){
printf("BinarySearchTreemainprogram.
");
$root=newBST();
foreach($argsas$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();

⑤ 用php调数据库做树状显示

数据库设计的时候，通常的做法是用父ID来解决树状结构，也有二叉树等等

id pid category_name

然后，用递归就能实现，也有引用数组的方式

<?php

/**
*此方法由@Tonton提供
*http://my.oschina.net/u/918697
*@date2012-12-12
*/
functiongenTree5($items){
foreach($itemsas$item)
$items[$item['pid']]['son'][$item['id']]=&$items[$item['id']];
returnisset($items[0]['son'])?$items[0]['son']:array();
}

/**
*将数据格式化成树形结构
*@authorXuefen.Tong
*@paramarray$items
*@returnarray
*/
functiongenTree9($items){
$tree=array();//格式化好的树
foreach($itemsas$item)
if(isset($items[$item['pid']]))
$items[$item['pid']]['son'][]=&$items[$item['id']];
else
$tree[]=&$items[$item['id']];
return$tree;
}

$items=array(
1=>array('id'=>1,'pid'=>0,'name'=>'江西省'),
2=>array('id'=>2,'pid'=>0,'name'=>'黑龙江省'),
3=>array('id'=>3,'pid'=>1,'name'=>'南昌市'),
4=>array('id'=>4,'pid'=>2,'name'=>'哈尔滨市'),
5=>array('id'=>5,'pid'=>2,'name'=>'鸡西市'),
6=>array('id'=>6,'pid'=>4,'name'=>'香坊区'),
7=>array('id'=>7,'pid'=>4,'name'=>'南岗区'),
8=>array('id'=>8,'pid'=>6,'name'=>'和兴路'),
9=>array('id'=>9,'pid'=>7,'name'=>'西大直街'),
10=>array('id'=>10,'pid'=>8,'name'=>'东北林业大学'),
11=>array('id'=>11,'pid'=>9,'name'=>'哈尔滨工业大学'),
12=>array('id'=>12,'pid'=>8,'name'=>'哈尔滨师范大学'),
13=>array('id'=>13,'pid'=>1,'name'=>'赣州市'),
14=>array('id'=>14,'pid'=>13,'name'=>'赣县'),
15=>array('id'=>15,'pid'=>13,'name'=>'于都县'),
16=>array('id'=>16,'pid'=>14,'name'=>'茅店镇'),
17=>array('id'=>17,'pid'=>14,'name'=>'大田乡'),
18=>array('id'=>18,'pid'=>16,'name'=>'义源村'),
19=>array('id'=>19,'pid'=>16,'name'=>'上坝村'),
);
echo"<pre>";
print_r(genTree5($items));
print_r(genTree9($items));
?>

⑥ 数据结构一般用哪种语言学关于二叉树等的知识，用php可以实现吗

数据结构 跟语言没关系的。数据结构 是数据的一种组织关系跟运用在这种关系上的操作。
任何计算机语言都可以实现数据结构的内容。
c可以，C++可以 java ... php 甚至javascript 都可以。

⑦ php 二叉树查询法请教下

function binarysearch(&$arr,$findval,$lelf,$right)这一行里的$lelf写错了，应该是left

⑧ 请高手发一下PHP版本二叉树按层遍历

#二叉树的非递归遍历
3 class Node {
4 public $data;
5 public $left;
6 public $right;
7 }
8
9 #前序遍历，和深度遍历一样
10 function preorder($root) {
11 $stack = array();
12 array_push($stack, $root);
13 while (!empty($stack)) {
14 $cnode = array_pop($stack);
15 echo $cnode->data . " ";
16 if ($cnode->right != null) array_push($stack, $cnode->right);
17 if ($cnode->left != null) array_push($stack, $cnode->left);
18 }
19 }

⑨ php程序员有必要学习数据结构与算法吗

没必要去学什么排序、查找的算法，没别要去学什么链表、堆栈、队列等数据结构的细节。

提升主要是快速开发，接到项目可以一晚上交货的就是高手。

不过工资与上面的都无关，工资主要决定于你和领导的关系。

⑩ 如何根据制定的数据使用PHP生成一个二叉树

<?php
foreach($dataas$key=>$value){
if($value['pid']=='0'){
$parent[]=$value;
unset($data[$key]);
}
}

foreach($parentas$key=>$value){
foreach($dataas$k=>$v){
if($v['pid']==$value['id']){
$parent[$key]['_child'][]=$v;
unset($data[$k]);
}
}
}
?>

通过以上循环过后，对应二叉树关系的数组就可以做出来了

当然上述代码只能进行到二级二叉树，如果想做出无限级二叉树的数组，则必须使用到递归函数了

PS：上述代码是网页里手打的，没经过测试，但思路肯定是没问题的哈