2014年7月

这篇其实就是记录一下2014年我所看书的list。

看到记录的增加,脑袋的知识增加,满满的成就感,很开心。


3月13:《高性能Mysql》 30%

4月15-5月4日:《大话设计模式》完结

4月:《Mysql必知必会》完结

5月:《Redis入门指南》完结

5月:《Python简明教程》完结

5月:《PHP核心技术与最佳实践》 完结。这本书推荐一下

6月:《MongoDB权威指南》 20%

6月:《PHP精粹》完结

6月:《莽荒记》 更新中……

6月25日 - 7月18日:《大话数据结构》完结

7月13日:《C程序语言设计》 50%

7月17日-8月底:《高性能程序员的修炼》完结

8月11日:《C语言入门经典》完结

8月12日-8月21日:《天才在左,疯子在右》完结

8月:《大主宰》更新中……

9月:《完美世界》更新中……

9月20:《PHP之道》完结

9月24:《PHP最佳实践》完结

9月25日:《深入理解PHP内核 - Thinking In PHP Internals》1%

10月24日:《啊哈!算法》50%


很多时候都是同时看几本,公司看一本,家里看一本。路上看小说。。。


    二叉树遍历,是值从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问依次。

tupan062.gif

图是百度搜的。。。谢谢提供图的英雄。。

    前序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则先遍历左树,再遍历右树,遍历顺序为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 '<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为代码环境,有人会说高级语言直接写表达式就好了,它们会算,可是他们为什么会算,怎么算的,还是需要把中缀表达式转为后缀表达式。因此本文代码只是模拟一个逻辑。

    比如:传统的四则运算表达式(中缀表达式)是9 + ( 3 - 1 ) * 3 + 10 / 2,对应的后缀表达式就是9 3 1 - 3 * + 10 2 / +。

    转换逻辑:一个字符一个字符的输入,如果是数字则直接输出;如果是左括号则直接入栈;如果是右括号则开始出栈,直到遇到第一次左括号为止;如果是加减乘除,则判断,如果栈顶也是符号,且输入的符号的优先级不高于栈顶的符号优先级,则全部出栈,否则该输入的符号入栈。

<?php

/**

 * 将输入的字符按照中缀表达式转后缀表达式的规则处理

 * @param $str 输入的字符

 * @param $stack 栈

 * @param $newStrList 新的表达式

 */

function suffix($str, &$stack, &$newStrList){

    //如果是数字则输出

    if(is_numeric($str)){

        $newStrList .= $str . ' ';

    }

    //如果是左括号则入栈

    else if($str == '('){

        $stack[] = $str;

    }

    //如果是右括号则将最近的左括号之前的所有数据出栈

    else if($str == ')'){

        while($arrPop = array_pop($stack)){

            if($arrPop == '('){

                break;

            }

            $newStrList .= $arrPop . ' ';

        }

    }

    //如果是加减乘除则判断与栈顶符号优先级

    else if(in_array($str, array('+', '-', '*', '/')) && count($stack) > 0){

        $key  = (count($stack) - 1);

        if(in_array($stack[$key], array('+', '-', '*', '/'))){

            //该符号优先级不高于栈顶符号的

            if(checkPriority($str, $stack[$key]) != 1){

                for($i=$key; $i>=0; $i--){

                    if($stack[$i] == '('){

                        break;

                    }

                    $newStrList .= $stack[$i] . ' ';

                    unset($stack[$i]);

                    $stack = array_values($stack);

                }

            }

        }

        //本次的符号入栈

        $stack[] = $str;

    }else{

        $stack[] = $str;

    }

}


/**

 * 判断运算符的优先级

 * @param $operatorA

 * @param $operatorB

 * @return A大于B返回1,A等于B返回0,A小于B返回-1

 */

function checkPriority($operatorA, $operatorB){

    switch($operatorA){

        case '+':

        case '-':

            if($operatorB == '+' || $operatorB == '-'){

                return 0;

            }else if($operatorB == '*' || $operatorB == '/'){

                return -1;

            }

            break;

        case '*':

        case '/':

            if($operatorB == '+' || $operatorB == '-'){

                return 1;

            }else if($operatorB == '*' || $operatorB == '/'){

                return 0;

            }

            break;

        default:

            exit('error');

    }

}

//栈

$stack = array();

//待转换的表达式

$strList = '9 + ( 3 - 1 ) * 3 + 10 / 2';

//新的表达式

$newStrList = '';

$strList = explode(' ', $strList);

foreach($strList as $str){

    if($str != ' '){

        suffix($str, $stack, $newStrList);

    }

}

//数组反转

while($s = array_pop($stack)){

    $newStrList .= $s . ' ';

}

echo $newStrList;