最新消息:

PHP实现二叉树的后序非递归遍历算法(2)

PHP pengchengdewebxuexibiji 120浏览 0评论

现在我们用PHP代码来实现二叉树的后序非递归遍历算法。

定义二叉树的节点类

我们首先定义一个类,取名为node,我们给它定义三个属性$v(值),$lchild(左孩子),$rchild(右孩子),如下所示:

<?php

class node{

public $v;

public $lchild;

public $rchild;

}

生成二叉树

我们来生成一棵如图所示的二叉树:

PHP实现二叉树的后序非递归遍历算法(2)

第一步,我们把如图所示的二叉树上的节点全部实例化

$a=new node(); //A节点

$b=new node(); //B节点

$c=new node(); //C节点

$d=new node(); //D节点

$e=new node(); //E节点

$f=new node(); //F节点

第二步,我们从A节点开始,依次给他们赋值,并指定左右孩子

//A节点的值为A,有BC两个孩子

$a->v = ‘A’;

$a->lchild = $b;

$a->rchild = $c;

//B节点值为B,有DE两个孩子

$b->v = ‘B’;

$b->lchild = $d;

$b->rchild = $e;

//D节点值为D,无孩子

$d->v=’D’;

$e->v=’E’;

$c->v=’C’;

$c->lchid=’F’;

$f->v=’F’;

开始遍历

提示:在这里我们使用一个数组来模拟栈 $stack=array(),通过往array_push往栈里压入数据。

通过array_pop 从栈里弹出数据,通过end($stack)取出栈顶元素。

下面是代码。不知道为啥编辑的时候代码里的缩进都会自动被清除,大家将就看下。

$cur=null;//用来存放当前节点的变量

$pre=null;//用来存放最近一次被输出节点的变量

$stack=array();//用来模拟栈

$output=array();//存放输出值的数组

array_push($stack,$a);//首先把A(根节点)放入栈中

while(!empty($stack)){//在栈不为空的时候一直循环

if($cur->left==null&&$cur->right==null){//当前节点无孩子时

$temp = array_pop($stack);

array_push($output,$temp->value);

$pre = $cur;

$cur = end($stack);//模拟出栈

}elseif ($pre!=null&&($pre===$cur->left||$pre===$cur->right)) {//当前节点的孩子都被输出时

$temp = array_pop($stack);

array_push($output,$temp->value);

$pre = $cur;

$cur = end($stack);

}else{//当前节点有孩子时

//遵循右孩子先入栈的原则

if($cur->right!=null){

array_push($stack,$cur->right);

}

if($cur->left!=null){

array_push($stack,$cur->left);

}

$cur = end($stack);

}

}

print_r($output);

输出结果

Array

(

[0] => D

[1] => E

[2] => B

[3] => F

[4] => C

[5] => A

)

转载请注明:PHP学习 » PHP实现二叉树的后序非递归遍历算法(2)

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址