武汉PHP培训
达内武汉民大中心

15827352908

热门课程

武汉PHP培训丨PHP高级程序员一定要会的知识点

  • 时间:2018-01-31 11:25
  • 发布:武汉PHP培
  • 来源:互联网

    在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree).二叉树常被用于实现二叉查找树和二叉堆(引自百度百科).
    作为高级程序员,遍历二叉树即是最基本的技能,那么,用PHP如何遍历二叉树呢?
    二叉树遍历,是值从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问依次.
    前序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则先遍历左树,再遍历右树,遍历顺序为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培

    <?php
    //前序遍历二叉树算法
    echo '前序遍历二叉树算法:';
    PreOrderTraverse($arr);
    echo '<Br>';
    function PreOrderTraverse($node){
    if(empty($node)){
    return;
    }
    //输出值
    print_r($node['data']);
    //左节点
    PreOrderTraverse($node['lChild']);
    //右节点
    PreOrderTraverse($node['rChild']);
    }
    遍历算法二:中序遍历二叉树
    <?php
    //中序遍历二叉树算法
    echo '中序遍历二叉树算法:';
    inOrderTraverse($arr);
    echo '<Br>';
    function inOrderTraverse($node){
    if(empty($node)){
    return;
    }
    //左节点
    inOrderTraverse($node['lChild']);
    //输出值
    print_r($node['data']);
    //右节点
    inOrderTraverse($node['rChild']);
    }
    遍历算法三:后序遍历二叉树
    <?php
    //后序遍历二叉树算法
    echo '后序遍历二叉树算法:';
    postOrderTraverse($arr);
    echo '<Br>';
    function postOrderTraverse($node){
    if(empty($node)){
    return;
    }
    //左节点
    postOrderTraverse($node['lChild']);
    //右节点
    postOrderTraverse($node['rChild']);
    //输出值
    print_r($node['data']);
    }

    本篇文章是由武汉PHP培训为您呈现,希望给您带来更多更好的文章,喜欢的朋友们可以添加微信公众号.

更多武汉PHP培训相关咨询,请扫描下方二维码

武汉PHP培训

马上预约七天免费试听课

姓名:

电话:

上一篇:武汉PHP培训丨PHP 易错知识点整理
下一篇:武汉PHP培训丨PHP 与 .NET:你应该学习哪一个?
选择城市和中心
贵州省

广西省

海南省

有位老师想和您聊一聊