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

⑵ 二叉樹的遍歷演算法

void
preorder(BiTree
root)
/*先序遍歷輸出二叉樹結點，root為指向二叉樹根節點的指針*/
{
if（root!=NULL）
{
printf(root->data);
preorder(root->Lchild);
preorder(root->Rchild);
}
}
你看好這個程序,你首先定義了一個preorder函數,然後在函數體中又調用了本函數,這是函數的自調用.執行printf(root->data);語句的時候輸出當前遍歷的數據,preorder(root->Lchild);在執行到4的時候,root->Lchild=NULL,但是執行preorder(root->Rchild);語句,由此轉向下一個結點,即5

⑶ 請高手發一下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 }

⑷ 二叉樹的遍歷方法通常有

二叉樹的遍歷方法通常有：
先根遍歷或先序遍歷：首先訪問根節點，接著遍歷左子樹，最後遍歷右子樹。
中根遍歷或中序遍歷：首先遍歷左子樹，然後訪問根節點，最後遍歷右子樹。
後根遍歷或後序遍歷：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
按層次遍歷或寬度優先遍歷，從根節點開始訪問，從上往下訪問每一層節點，在同一層節點中，從左到右訪問每一個節點。

⑸ 二叉樹三種遍歷技巧

在二叉樹的前序遍歷，中序遍歷，後序遍歷這三種遍歷方式中，有兩個相同的特點就是左子樹總是在右子樹的之前遍歷。還有他們的遍歷都可以用遞歸的方式來描述。
前序遍歷的方式是：首先訪問根節點，然後訪問左子樹，最後訪問右子樹。
中序遍歷的方式是：首先訪問左子樹，接著訪問根結點，最後訪問右子樹。
後序遍歷的方式是：首先訪問左子樹，接著訪問右子樹，最後訪問根結點。

⑹ 二叉樹的遍歷演算法

這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
1.先序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{

Bitree
Elem[maxsize];

int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞歸演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec

⑺ php 二叉樹查詢法請教下

function binarysearch(&$arr,$findval,$lelf,$right)這一行里的$lelf寫錯了，應該是left

⑻ 二叉樹遍歷方法有幾種

二叉樹遍歷方法最常用的大致有四種：
先序遍歷，也叫先根遍歷。就是先訪問根結點，再訪問左子樹，最後訪問右子樹。
中序遍歷，也叫中根遍歷。就是先訪問左子樹，再訪問根節點，最後訪問右子樹。
後序遍歷，也叫後根遍歷。就是先訪問左子樹，再訪問右子樹，最後訪問根結點。
按層次遍歷，就是對二叉樹從上到下訪問每一層，在每一層中都是按從左到右進行訪問該層中的每一個節點。

⑼ 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();

⑽ 二叉樹如何遍歷

二叉樹的遍歷，通常用遞歸的方法來描述。
先根遍歷或者先序遍歷：首先訪問根結點，然後訪問左子樹，最後訪問右子樹。
中根便利或者中序遍歷：先訪問左子樹，然後訪問根節點，最後訪問右子樹。

後根遍歷或者先後序遍歷：首先訪問左子樹，然後訪問根節點，最後訪問右子樹。
按層次遍歷：從最上面一層，也就是根節點所在的一層開始，從上往下從左到右，訪問二叉樹中的每一個節點。