二叉树遍历算法（PHP版）

1. Pre-order Traversal

Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree.

Pre-order Traversal

2. In-order Traversal

In-order traversal is to traverse the left subtree first. Then visit the root. Finally, traverse the right subtree.

In-order Traversal

3. Post-order Traversal

Post-order traversal is to traverse the left subtree first. Then traverse the right subtree. Finally, visit the root.

Post-order Traversal

4. Level-order Traversal

Level-order traversal is to traverse the tree level by level.

Level-order Traversal

5. PHP源码

<?php
class Node{
    public $val;
    public $left = null;
    public $right = null;
    public function __construct($val){
        $this->val = $val;
    }
}

class BTree{
    private $_head = null;
    private $_level = 0;
    private $_tree_traverse_values = [];
    const PRE_ORDER_TRAVERSE = 1;
    const IN_ORDER_TRAVERSE = 2;
    const POST_ORDER_TRAVERSE = 3;
    const LEVEL_ORDER_TRAVERSE = 4;

    public function __construct($data=[]){
        $this->_level = intval(log(count($data)+1, 2));
        $this->_head = $this->_init_tree($data);
    }

    private function _init_tree($data, $level=1, $index=1){
        $node = null;
        $n = pow(2, $level-1)-1+$index;
        if(isset($data[$n-1]) && $data[$n-1] != null){
            $node = new Node($data[$n-1]);
            $node->left = $this->_init_tree($data, $level+1, $index*2-1);
            $node->right = $this->_init_tree($data, $level+1, $index*2);
        }
        return $node;
    }

    public function traverse($traverse_order=self::PRE_ORDER_TRAVERSE){
        $this->_tree_traverse_values = [];
        if($traverse_order == self::PRE_ORDER_TRAVERSE){
            $this->_pre_order_traverse($this->_head);
        }
        if($traverse_order == self::IN_ORDER_TRAVERSE){
            $this->_in_order_traverse($this->_head);
        }
        if($traverse_order == self::POST_ORDER_TRAVERSE){
            $this->_post_order_traverse($this->_head);
        }
        if($traverse_order == self::LEVEL_ORDER_TRAVERSE){
            $this->_level_order_traverse($this->_head);
        }
        return $this->_tree_traverse_values;
    }

    /**
     * root -> left -> right
     */
    private function _pre_order_traverse($node){
        array_push($this->_tree_traverse_values, $node->val);
        if($node->left != null){
            $this->_pre_order_traverse($node->left);
        }
        if($node->right != null){
            $this->_pre_order_traverse($node->right);
        }
    }

    /**
     * left -> root -> right
     */
    private function _in_order_traverse($node){
        if($node->left != null){
            $this->_in_order_traverse($node->left);
        }
        array_push($this->_tree_traverse_values, $node->val);
        if($node->right != null){
            $this->_in_order_traverse($node->right);
        }
    }

    /**
     * left -> right -> root
     */
    private function _post_order_traverse($node){
        if($node->left != null){
            $this->_post_order_traverse($node->left);
        }
        if($node->right != null){
            $this->_post_order_traverse($node->right);
        }
        array_push($this->_tree_traverse_values, $node->val);
    }

    /*
     * breadth first traverse
     */
    private function _level_order_traverse($node, $level=0){
        if($node){
            if(!isset($this->_tree_traverse_values[$level])){
                $this->_tree_traverse_values[$level] = [];
            }
            array_push($this->_tree_traverse_values[$level], $node->val);
            if($node->left != null){
                $this->_level_order_traverse($node->left, $level+1);
            }
            if($node->right != null){
                $this->_level_order_traverse($node->right, $level+1);
            }
        }
    }
}

$bt = new BTree([
                    'F',
           'B',                'G',
      'A',      'D',      null,    'I',
    null,null,'C','E', null,null,'H',null
]);
echo 'pre-order traverse result:   '.json_encode($bt->traverse(BTree::PRE_ORDER_TRAVERSE)).PHP_EOL;
echo 'in-order traverse result:    '.json_encode($bt->traverse(BTree::IN_ORDER_TRAVERSE)).PHP_EOL;
echo 'post-order traverse result:  '.json_encode($bt->traverse(BTree::POST_ORDER_TRAVERSE)).PHP_EOL;
echo 'level-order traverse result: '.json_encode($bt->traverse(BTree::LEVEL_ORDER_TRAVERSE)).PHP_EOL;

6. 输出

pre-order traverse result:   ["F","B","A","D","C","E","G","I","H"]
in-order traverse result:    ["A","B","C","D","E","F","G","H","I"]
post-order traverse result:  ["A","C","E","D","B","H","I","G","F"]
level-order traverse result: [["F"],["B","G"],["A","D","I"],["C","E","H"]]