二叉树遍历算法-PHP Tutorial-php.cn

Home

Backend Development

PHP Tutorial

二叉树遍历算法

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>

Statement

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Working with Flash Session Data in LaravelMar 12, 2025 pm 05:08 PM

Laravel simplifies handling temporary session data using its intuitive flash methods. This is perfect for displaying brief messages, alerts, or notifications within your application. Data persists only for the subsequent request by default: $request-

cURL in PHP: How to Use the PHP cURL Extension in REST APIsMar 14, 2025 am 11:42 AM

The PHP Client URL (cURL) extension is a powerful tool for developers, enabling seamless interaction with remote servers and REST APIs. By leveraging libcurl, a well-respected multi-protocol file transfer library, PHP cURL facilitates efficient execution of various network protocols, including HTTP, HTTPS, and FTP. This extension offers granular control over HTTP requests, supports multiple concurrent operations, and provides built-in security features.

Simplified HTTP Response Mocking in Laravel TestsMar 12, 2025 pm 05:09 PM

Laravel provides concise HTTP response simulation syntax, simplifying HTTP interaction testing. This approach significantly reduces code redundancy while making your test simulation more intuitive. The basic implementation provides a variety of response type shortcuts: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

12 Best PHP Chat Scripts on CodeCanyonMar 13, 2025 pm 12:08 PM

Do you want to provide real-time, instant solutions to your customers' most pressing problems? Live chat lets you have real-time conversations with customers and resolve their problems instantly. It allows you to provide faster service to your custom

Explain the concept of late static binding in PHP.Mar 21, 2025 pm 01:33 PM

Article discusses late static binding (LSB) in PHP, introduced in PHP 5.3, allowing runtime resolution of static method calls for more flexible inheritance.Main issue: LSB vs. traditional polymorphism; LSB's practical applications and potential perfo

PHP Logging: Best Practices for PHP Log AnalysisMar 10, 2025 pm 02:32 PM

PHP logging is essential for monitoring and debugging web applications, as well as capturing critical events, errors, and runtime behavior. It provides valuable insights into system performance, helps identify issues, and supports faster troubleshoot

Discover File Downloads in Laravel with Storage::downloadMar 06, 2025 am 02:22 AM

The Storage::download method of the Laravel framework provides a concise API for safely handling file downloads while managing abstractions of file storage. Here is an example of using Storage::download() in the example controller:

HTTP Method Verification in LaravelMar 05, 2025 pm 04:14 PM

Laravel simplifies HTTP verb handling in incoming requests, streamlining diverse operation management within your applications. The method() and isMethod() methods efficiently identify and validate request types. This feature is crucial for building

See all articles

Hot AI Tools

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress images for free

Clothoff.io

AI clothes remover

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)

2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hello Kitty Island Adventure: How To Get Giant Seeds

1 months agoBy尊渡假赌尊渡假赌尊渡假赌

How Long Does It Take To Beat Split Fiction?

4 weeks agoByDDD

R.E.P.O. Save File Location: Where Is It & How to Protect It?

4 weeks agoByDDD

Two Point Museum: All Exhibits And Where To Find Them

1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SublimeText3 Chinese version

Chinese version, very easy to use

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),