1. 云栖社区>
  2. PHP教程>
  3. 正文

PHP实现二叉树遍历(非递归方式,栈模拟实现)

作者:用户 来源:互联网 时间:2017-12-01 09:47:56

二叉树

PHP实现二叉树遍历(非递归方式,栈模拟实现) - 摘要: 本文讲的是PHP实现二叉树遍历(非递归方式,栈模拟实现),二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式:① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式:
① NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN:后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
如下图:

<a href=PHP实现二叉树遍历(非递归方式,栈模拟实现)">
对于二叉树的以前都是用C写的,递归遍历, 用PHP也可以简单模拟,下面这个例子算是最简单的一种遍历了(参考网络的)。
/** * 二叉树遍历 * @blog<http://www.phpddt.com> */class Node {    public $value;    public $left;    public $right;}//前序遍历,访问根节点->遍历子左树->遍历右左树function preorder($root){    $stack = array();    array_push($stack, $root);    while(!empty($stack)){$center_node = array_pop($stack);echo $center_node->value.' ';if($center_node->right != null) array_push($stack, $center_node->right);if($center_node->left != null) array_push($stack, $center_node->left);    }}//中序遍历,遍历子左树->访问根节点->遍历右右树function inorder($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->left;     }      $center_node = array_pop($stack);     echo $center_node->value . " ";      $center_node = $center_node->right; }}//后序遍历,遍历子左树->访问子右树->遍历根节点function postorder($root){$pushstack = array();$visitstack = array();array_push($pushstack, $root);while (!empty($pushstack)) {    $center_node = array_pop($pushstack);    array_push($visitstack, $center_node);    if ($center_node->left != null) array_push($pushstack, $center_node->left);    if ($center_node->right != null) array_push($pushstack, $center_node->right);}while (!empty($visitstack)) {    $center_node = array_pop($visitstack);    echo $center_node->value. " ";}}//创建如上图所示的二叉树$a = new Node();$b = new Node();$c = new Node();$d = new Node();$e = new Node();$f = new Node();$a->value = 'A';$b->value = 'B';$c->value = 'C';$d->value = 'D';$e->value = 'E';$f->value = 'F';$a->left = $b;$a->right = $c;$b->left = $d;$c->left = $e;$c->right = $f;//前序遍历preorder($a);  //结果是:A B D C E Finorder($a);  //结果是: D B A E C Fpostorder($a); //结果是:  D B E F C A

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索二叉树 ,以便于您获取更多的相关知识。