二叉树遍历,是值从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问依次。
图是百度搜的。。。谢谢提供图的英雄。。
图是百度搜的。。。谢谢提供图的英雄。。
前序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则先遍历左树,再遍历右树,遍历顺序为ABCDEGF。
中序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从根节点开始,中序遍历根节点的左子树,然后是访问根节点,最后中序遍历右子树,遍历顺序为CBEGDFA。
后序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从左到右先叶子后节点的访问遍历访问左右子树,最后是访问根节点。访问顺序为CGEFDBA。
层序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从树的第一层,也就是根节点开始访问,从上而下逐层遍历,在同一层中,按照从左到右的顺序对节点逐个访问。访问顺序为ABCDEFG。
现在,我们用PHP代码,来遍历二叉树结构。二叉树是放一个大数组,每一个节点都有三个字段,data表示这个节点的值,lChild表示这个节点的左边子节点,rChild表示这个节点的右边子节点。二叉树的结构我们用上面那张图。
二叉树结构代码如下:
<?php //二叉树 $arr = array( 'data' => 'A', 'lChild' => array( 'data' => 'B', 'lChild' => array( 'data' => 'C', 'lChild' => array(), 'rChild' => array(), ), 'rChild' => array( 'data' => 'D', 'lChild' => array( 'data' => 'E', 'lChild' => array(), 'rChild' => array( 'data' => 'G', 'lChild' => array(), 'rChild' => array(), ), ), 'rChild' => array( 'data' => 'F', 'lChild' => array(), 'rChild' => array(), ), ), ), 'rChild' => array(), );遍历算法一:前序遍历二叉树
<?php //前序遍历二叉树算法 echo '前序遍历二叉树算法:'; PreOrderTraverse($arr); echo '<Br>'; function PreOrderTraverse($node){ if(empty($node)){ return; } //输出值 print_r($node['data']); //左节点 PreOrderTraverse($node['lChild']); //右节点 PreOrderTraverse($node['rChild']); }遍历算法二:中序遍历二叉树
<?php //中序遍历二叉树算法 echo '中序遍历二叉树算法:'; inOrderTraverse($arr); echo '<Br>'; function inOrderTraverse($node){ if(empty($node)){ return; } //左节点 inOrderTraverse($node['lChild']); //输出值 print_r($node['data']); //右节点 inOrderTraverse($node['rChild']); }遍历算法三:后序遍历二叉树
<?php //后序遍历二叉树算法 echo '后序遍历二叉树算法:'; postOrderTraverse($arr); echo '<Br>'; function postOrderTraverse($node){ if(empty($node)){ return; } //左节点 postOrderTraverse($node['lChild']); //右节点 postOrderTraverse($node['rChild']); //输出值 print_r($node['data']); }
友情提示:垃圾评论一律封号...