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：上述代碼是網頁裏手打的，沒經過測試，但思路肯定是沒問題的哈