php实现二叉树的前序，中序，后序，和层次遍历

上一篇博客已经介绍了二叉树的前序，中序，后序，以及层次遍历（递归和非递归）的实现思路，接下来，采用php 语言具体实现

一、、先序（跟--左---右）

<?php

class Node{
public $data;
public $left;
public $right;

}
（1） //先序--递归方式实现。
function preOrder($tree){

echo($tree->data);
if($tree->left!=null){
preOrder($tree->left);
}

if($tree->right!=null){
preOrder($tree->right);
}

}

（2 非递归方式） function preOrderNotRecrusive($tree){

//前序遍历:先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先遍历根节点，然后访问左子树，最后遍历右子树

$arr_stack=array();
array_push($arr_stack,$tree);
while(!empty($arr_stack)){
$center_node=array_pop($arr_stack);
echo $center_node->data.' ';
if($center_node->right!=null){
array_push($arr_stack,$center_node->right);
}

if($center_node->left!=null){
array_push($arr_stack,$center_node->left);
}


}


}

二、中序实现（左-跟-右）（DEBAFCG）

1、递归方式

function centerRecrusiveOrder($tree){


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

centerRecrusiveOrder($tree->left);
}
echo($tree->data);

if($tree->right!=null){
centerRecrusiveOrder($tree->right);
}

}

2、非递归方式

//中序遍历:先遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树

三、后序遍历方式（左-右-跟）

1、递归方式（DEBFGCA）

function lastRecrusiveOrder($tree){


if($tree->left!=null){
lastRecrusiveOrder($tree->left);
}

if($tree->right!=null){
lastRecrusiveOrder($tree->right);
}
echo($tree->data);

}

2、非递归方式

//后序遍历:先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点

四、层次遍历

function breath_order($tree){
$traverse_data = array();
$queue = array();
array_unshift($queue, $tree); #根节点入队
while (!empty($queue)) { #持续输出节点，直到队列为空
$cnode = array_pop($queue); #队尾元素出队
echo $cnode->data.' ';
$traverse_data[] = $cnode->data;
#左节点先入队，然后右节点入队
if ($cnode->left != null) array_unshift($queue, $cnode->left);
if ($cnode->right != null) array_unshift($queue, $cnode->right);

}

二叉树的层次遍历思路，借助队列来实现。相当于广度优先搜索，使用队列（深度优先搜索的话，使用栈）。


       若根节点为空，直接返回；

       若根节点非空，则将根节点入队，然后，判断队列是否为空，若不为空，则将队首节点出队，访问，并判断其左右子节点是否为空，若不为空，则压入队列。

$tree=new Node();

$b=new Node();
$c=new Node();
$d=new Node();
$f=new Node();
$g =new Node();


$tree->data='A';
$b->data='B';
$c->data='C';
$d->data='D';
$e->data='E';
$f->data='F';
$g->data='G';

$tree->left=$b;
$tree->right=$c;
$b->left=$d;
$b->right=$e;
$c->left=$f;
$c->right=$g;

preOrder($tree);


?>

php实现二叉树的前序，中序，后序，和层次遍历

相关推荐