php如何实现的二叉树遍历(示例)
来源:才华咖 本文已影响9.03K人
来源:才华咖 本文已影响9.03K人
本文主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考一下!想了解更多相关信息请持续关注我们应届毕业生考试网!
创建的二叉树如下图所示
php代码如下所示:
<?php
class Node {
public $value;
public $child_left;
public $child_right;
}
final class Ergodic {
//前序遍历:先访问根节点,再遍历左子树,最后遍历右子树;并且在遍历左右子树时,仍需先遍历根节点,然后访问左子树,最后遍历右子树
public static function preOrder($root){
$stack = array();
array_push($stack, $root);
while(!empty($stack)){
$center_node = array_pop($stack);
echo $center_node->value . ' ';
//先把右子树节点入栈,以确保左子树节点先出栈
if($center_node->child_right != null) array_push($stack, $center_node->child_right);
if($center_node->child_left != null) array_push($stack, $center_node->child_left);
}
}
//中序遍历:先遍历左子树、然后访问根节点,最后遍历右子树;并且在遍历左右子树的`时候。仍然是先遍历左子树,然后访问根节点,最后遍历右子树
public static function midOrder($root){
$stack = array();
$center_node = $root;
while (!empty($stack) || $center_node != null) {
while ($center_node != null) {
array_push($stack, $center_node);
$center_node = $center_node->child_left;
}
$center_node = array_pop($stack);
echo $center_node->value . ' ';
$center_node = $center_node->child_right;
}
}
//后序遍历:先遍历左子树,然后遍历右子树,最后访问根节点;同样,在遍历左右子树的时候同样要先遍历左子树,然后遍历右子树,最后访问根节点
public static function endOrder($root){
$push_stack = array();
$visit_stack = array();
array_push($push_stack, $root);
while (!empty($push_stack)) {
$center_node = array_pop($push_stack);
array_push($visit_stack, $center_node);
//左子树节点先入$pushstack的栈,确保在$visitstack中先出栈
if ($center_node->child_left != null) array_push($push_stack, $center_node->child_left);
if ($center_node->child_right != null) array_push($push_stack, $center_node->child_right);
}
while (!empty($visit_stack)) {
$center_node = array_pop($visit_stack);
echo $center_node->value . ' ';
}
}
}
//创建二叉树
$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();
$g = new Node();
$h = new Node();
$i = new Node();
$a->value = 'A';
$b->value = 'B';
$c->value = 'C';
$d->value = 'D';
$e->value = 'E';
$f->value = 'F';
$g->value = 'G';
$h->value = 'H';
$i->value = 'I';
$a->child_left = $b;
$a->child_right = $c;
$b->child_left = $d;
$b->child_right = $g;
$c->child_left = $e;
$c->child_right = $f;
$d->child_left = $h;
$d->child_right = $i;
//前序遍历
Ergodic::preOrder($a); //结果是:A B D H I G C E F
echo '<br/>';
//中序遍历
Ergodic::midOrder($a); //结果是: H D I B G A E C F
echo '<br/>';
//后序遍历
Ergodic::endOrder($a); //结果是: H I D G B E F C A
关于PHP var-dump遍历对象属性的函数与应用代码
PHP如何实现注册后邮箱验证和帐号激活
php代码如何实现命令行执行
Java认证辅导:Java实现二叉树遍历算法
php如何快速实现两表合并并有序排列
php递归遍历多维数组的方法
php如何实现只替换一次或N次
如何写现实表现
php递归遍历删除文件的方法
php实现伪静态的方法实例
php使用curl访问https示例分享
如何使用php自定义函数实现汉字分割替换
如何实现个人简历投递效
履历中如何显示实力?
用PHP遍历目录下的全部文件
如何实现PHP静态新闻列表自动生成代码
php使用html5实现多文件上传实例
php指定长度分割字符串str-split函数如何实现
PHP字符串如何实现word末字符实现大小写互换
PHP中使用crypt()实现用户身份验证的实例
php实现36进制与10进制转换功能示例
PHP遍历目录文件常用方法
ThinkPHP实现支付宝接口功能实例
如何实现php登陆表单提交CSRF及验证码
如何使用php操作redis队列实例