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

⑽ 二叉树如何遍历

二叉树的遍历，通常用递归的方法来描述。
先根遍历或者先序遍历：首先访问根结点，然后访问左子树，最后访问右子树。
中根便利或者中序遍历：先访问左子树，然后访问根节点，最后访问右子树。

后根遍历或者先后序遍历：首先访问左子树，然后访问根节点，最后访问右子树。
按层次遍历：从最上面一层，也就是根节点所在的一层开始，从上往下从左到右，访问二叉树中的每一个节点。