PHP遍历二叉树

时间: 2018-11-23阅读: 740标签: 遍历

遍历二叉树,这个相对比较复杂。

二叉树的便利,主要有两种,一种是广度优先遍历,一种是深度优先遍历。

什么是广度优先遍历?就是根节点进入,水平一行一行的便利。

什么是深度优先遍历呢?就是根节点进入,然后按照一个固定的规律,一直向下走,一个方向的子树遍历之后再遍历另一个方向的子树。

深度优先遍历,主要有三种顺序遍历:先序(先输出根节点),中序(第二个输出根节点),后序(最后输出根节点)。


直接上代码吧。 

class Node {
    public $data = null;
    public $left = null;
    public $right = null;
}

$node1 = new Node();
$node2 = new Node();
$node3 = new Node();
$node4 = new Node();
$node5 = new Node();
$node6 = new Node();
$node7 = new Node();
$node8 = new Node();
$node9 = new Node();

$node1->data = 1;
$node2->data = 2;
$node3->data = 3;
$node4->data = 4;
$node5->data = 5;
$node6->data = 6;
$node7->data = 7;
$node8->data = 8;
$node9->data = 9;

$node1->left = $node2;
$node1->right = $node3;
$node2->left = $node4;
$node2->right = $node5;
$node3->left = $node6;
$node3->right = $node7;
$node4->left = $node8;
$node4->right = $node9;

 以上代码,简单建立一个二叉树,如下图:



广度优先遍历 

// 二叉树广度优先遍历
function binary_tree1($node) {
    $result = [];//保存结果
    $memc = [];
    array_push($memc, $node);//根节点入队
    while (!empty($memc)) {//持续输出节点,直到队列为空
        $cnode = array_shift($memc);//最前边的元素出队
        $result[] = $cnode->data;//记录当前节点的值
        //左节点先入队,然后右节点入队
        if ($cnode->left != null) 
            array_push($memc, $cnode->left);
        if ($cnode->right != null) 
            array_push($memc, $cnode->right);
    }
    return $result;
}

print_r(binary_tree2($node1));


深度优先遍历(先序) 

// 二叉树深度优先遍历(先序)
function binary_tree2($node)
{
    $result = [];//结果数组
    $memc  = [];
    array_push($memc, $node);//将根节点压栈
    while (!empty($memc)) {
        $cnode = array_pop($memc);//弹出刚刚压栈的节点
        $result[] = $cnode->data;
        //因为先进后出原则,想先显示左子树,所以先压入右子树
        if ($cnode->right != null) {
            array_push($memc, $cnode->right);
        }
        if ($cnode->left != null) {
            array_push($memc, $cnode->left);
        }
    }
    return $result;
}

print_r(binary_tree2($node1));


 

 

站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/1872

关闭

Js中常见的几种循环遍历

项目开发中,不管是建立在哪个框架基础上,对数据的处理都是必须的,而处理数据离不开各种遍历循环。javascript中循环遍历有很多种方式,记录下几种常见的js循环遍历。

Js二叉树与多叉树的遍历

二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点,并且结点的存储位置能体现结点之间的逻辑关系。二叉树的遍历有三种方式,如下:

为什么 JS 对象内部属性遍历的顺序乱了

查阅了 ECMA-262 3rd edition ,如下文 It is an unordered collection of properties 就说到 ES3 标准的对象不排序,插入是啥顺序,遍历就是啥顺序

Js数组遍历方法总汇

for in语句用于遍历数组或者对象的属性(对数组或者对象的属性进行循环操作);For循环可以将代码块执行指定的次数。forEach按照原始数组元素顺序依次处理元素.

JavaScript数组遍历:for、foreach、for in、for of、$.each、$().each的区别

JavaScript数组遍历的区别,推荐在循环对象属性的时候使用for in,在遍历数组的时候的时候使用for of;for in循环出的是key,for of循环出的是value;for of是ES6新引入的特性。修复了ES5的for in的不足;

javascript如何遍历对象?

javascript遍历对象的方法:1、使用Object.keys()遍历。2、使用for..in.遍历。3、使用Object.getOwnPropertyNames(obj)遍历。4、使用Reflect.ownKeys(obj)遍历。

JavaScript中,数组和对象的遍历方法总结

循环遍历是写程序很频繁的操作,JavaScript 提供了很多方法来实现。这篇文章将分别总结数组和对象的遍历方法,新手可以通过本文串联起学过的知识。

javascript如何循环遍历对象?

在JavaScript中有多种循环遍历对象的方法,下面本篇文章就来给大家介绍一下使用JavaScript循环遍历对象的方法,希望对大家有所帮助。

JavaScript 中的遍历详解

编程这么多年,要是每次写遍历代码时都用 for 循环,真心感觉对不起 JavaScript 语言~对象遍历为了便于对象遍历的测试,我在下面定义了一个测试对象 obj。

js遍历对象的三种方法

for in 只能遍历可枚举属性和原型链的属性;通过Object.keys(obj) 只能遍历可枚举属性 不能遍历不可枚举和原型链上的属性 //Object.values(obj) //遍历可枚举的值

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!