二叉树遍历算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树遍历算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2173字,纯文字阅读大概需要4分钟。
内容图文
![二叉树遍历算法](/upload/InfoBanner/zyjiaocheng/245/75a588a060314c3c80d81d90fdb1a05a.jpg)
二叉树遍历,是值从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问依次。
![]()
图是百度搜的。。。谢谢提供图的英雄。。
前序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则先遍历左树,再遍历右树,遍历顺序为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 '
';function PreOrderTraverse($node){
if(empty($node)){
return;
}
//
print_r($node['data']);
//左节点
PreOrderTraverse($node['lChild']);
//右节点
PreOrderTraverse($node['rChild']);
}
遍历算法二:中序遍历二叉树
输出值
<?php
//中序遍历二叉树算法
echo '中序遍历二叉树算法:';
inOrderTraverse($arr);
echo '
';function inOrderTraverse($node){
if(empty($node)){
return;
}
//左节点
inOrderTraverse($node['lChild']);
//
print_r($node['data']);
//右节点
inOrderTraverse($node['rChild']);
}
遍历算法三:后序遍历二叉树
输出值
<?php
//后序遍历二叉树算法
echo '后序遍历二叉树算法:';
postOrderTraverse($arr);
echo '
';function postOrderTraverse($node){
if(empty($node)){
return;
}
//左节点
postOrderTraverse($node['lChild']);
//右节点
postOrderTraverse($node['rChild']);
//
print_r($node['data']);
}
内容总结
以上是互联网集市为您收集整理的二叉树遍历算法全部内容,希望文章能够帮你解决二叉树遍历算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。