二叉树遍历算法-php教程-PHP中文網

首頁

後端開發

php教程

二叉树遍历算法

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 05, 2016 am 11:50 AM

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	二叉树遍历，是值从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问依次。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;text-align:center;">
	<img src="/static/imghwm/default1.png" data-src="http://lanecn-upload.stor.sinaapp.com/image/20140709_1404896527_874807.gif" class="lazy" title="20140709_1404896527_874807.gif" alt="tupan062.gif"   style="max-width:90%"> 
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;text-align:center;">
	图是百度搜的。。。谢谢提供图的英雄。。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    前序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则先遍历左树，再遍历右树，遍历顺序为ABCDEGF。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    中序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从根节点开始，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树，遍历顺序为CBEGDFA。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    后序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从左到右先叶子后节点的访问遍历访问左右子树，最后是访问根节点。访问顺序为CGEFDBA。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    层序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对节点逐个访问。访问顺序为ABCDEFG。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br>

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    现在，我们用PHP代码，来遍历二叉树结构。二叉树是放一个大数组，每一个节点都有三个字段，data表示这个节点的值，lChild表示这个节点的左边子节点，rChild表示这个节点的右边子节点。二叉树的结构我们用上面那张图。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br>

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	二叉树结构代码如下：
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br>

</p>

<pre class='brush:php;toolbar:false;'>
<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<?php
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	//二叉树
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	$arr = array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    'data' => 'A',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    'lChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        'data' => 'B',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        'lChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'data' => 'C',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        'rChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'data' => 'D',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'lChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'data' => 'E',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'rChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                    'data' => 'G',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                    'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                    'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'rChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'data' => 'F',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

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

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<?php
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	//前序遍历二叉树算法
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	echo '前序遍历二叉树算法：';
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	PreOrderTraverse($arr);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	echo '<Br>';
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	function PreOrderTraverse($node){
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    if(empty($node)){
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        return;
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    }
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //输出值
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    print_r($node['data']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //左节点
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    PreOrderTraverse($node['lChild']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //右节点
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    PreOrderTraverse($node['rChild']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	}
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

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

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<?php
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	//中序遍历二叉树算法
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	echo '中序遍历二叉树算法：';
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	inOrderTraverse($arr);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	echo '<Br>';
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	function inOrderTraverse($node){
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    if(empty($node)){
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        return;
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    }
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //左节点
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    inOrderTraverse($node['lChild']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //输出值
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    print_r($node['data']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //右节点
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    inOrderTraverse($node['rChild']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	}
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

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

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;white-space:normal;">
	<?php
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	//后序遍历二叉树算法
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	echo '后序遍历二叉树算法：';
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	postOrderTraverse($arr);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	echo '<Br>';
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	function postOrderTraverse($node){
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    if(empty($node)){
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        return;
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    }
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //左节点
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    postOrderTraverse($node['lChild']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //右节点
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    postOrderTraverse($node['rChild']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    //输出值
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    print_r($node['data']);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	}
</p>

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

在Laravel中使用Flash會話數據Mar 12, 2025 pm 05:08 PM

Laravel使用其直觀的閃存方法簡化了處理臨時會話數據。這非常適合在您的應用程序中顯示簡短的消息，警報或通知。默認情況下，數據僅針對後續請求： $請求 -

php中的捲曲：如何在REST API中使用PHP捲曲擴展Mar 14, 2025 am 11:42 AM

PHP客戶端URL（curl）擴展是開發人員的強大工具，可以與遠程服務器和REST API無縫交互。通過利用Libcurl（備受尊敬的多協議文件傳輸庫），PHP curl促進了有效的執行

簡化的HTTP響應在Laravel測試中模擬了Mar 12, 2025 pm 05:09 PM

Laravel 提供简洁的 HTTP 响应模拟语法，简化了 HTTP 交互测试。这种方法显著减少了代码冗余，同时使您的测试模拟更直观。基本实现提供了多种响应类型快捷方式： use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>