二叉树遍历算法

	二叉树遍历，是值从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问依次。



	 



	图是百度搜的。。。谢谢提供图的英雄。。



	    前序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则先遍历左树，再遍历右树，遍历顺序为ABCDEGF。



	    中序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从根节点开始，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树，遍历顺序为CBEGDFA。



	    后序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从左到右先叶子后节点的访问遍历访问左右子树，最后是访问根节点。访问顺序为CGEFDBA。



	    层序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对节点逐个访问。访问顺序为ABCDEFG。



	





	    现在，我们用PHP代码，来遍历二叉树结构。二叉树是放一个大数组，每一个节点都有三个字段，data表示这个节点的值，lChild表示这个节点的左边子节点，rChild表示这个节点的右边子节点。二叉树的结构我们用上面那张图。



	





	二叉树结构代码如下：



	





	





	


	//二叉树



	$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(),



	);



	





	



	



	遍历算法一：前序遍历二叉树


	



	





	


	//前序遍历二叉树算法



	echo '前序遍历二叉树算法：';



	PreOrderTraverse($arr);



	echo '
';



	function PreOrderTraverse($node){



	    if(empty($node)){



	        return;



	    }



	    //输出值



	    print_r($node['data']);



	    //左节点



	    PreOrderTraverse($node['lChild']);



	    //右节点



	    PreOrderTraverse($node['rChild']);



	}



	





	



	



	遍历算法二：中序遍历二叉树


	



	





	


	//中序遍历二叉树算法



	echo '中序遍历二叉树算法：';



	inOrderTraverse($arr);



	echo '
';



	function inOrderTraverse($node){



	    if(empty($node)){



	        return;



	    }



	    //左节点



	    inOrderTraverse($node['lChild']);



	    //输出值



	    print_r($node['data']);



	    //右节点



	    inOrderTraverse($node['rChild']);



	}



	





	



	



	遍历算法三：后序遍历二叉树


	



	





	


	//后序遍历二叉树算法



	echo '后序遍历二叉树算法：';



	postOrderTraverse($arr);



	echo '
';



	function postOrderTraverse($node){



	    if(empty($node)){



	        return;



	    }



	    //左节点



	    postOrderTraverse($node['lChild']);



	    //右节点



	    postOrderTraverse($node['rChild']);



	    //输出值



	    print_r($node['data']);



	}