二叉树的遍历

不同于线性数据结构，二叉树的遍历需要将非线性关联的节点转化为线性序列，因此转换遍历的方式不同，遍历的结果也各有区别。从大角度来说，二叉树有两种遍历方式：

深度优先遍历（前序遍历，中序遍历，后序遍历）
广度优先遍历（层序遍历）

首先定义一个简单的二叉树结构，用代码实现一个基本的二叉树的示例如下：

# 单节点 结构定义
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


# 创建二叉树
def create_binary_tree(input_list):
    if input_list is None or len(input_list) == 0:
        return None
    data = input_list.pop(0)
    if data is None:
        return None

    node = TreeNode(data)
    node.left = create_binary_tree(input_list)
    node.right = create_binary_tree(input_list)
    return node

如图：。

深度优先遍历

所谓深度优先遍历，顾名思义就是在一个纵深的角度访问到底，下面分别说明下深度优先下的各个遍历方式。

1.前序遍历

前序遍历顺序是根节点 -> 左子树 -> 右子树示例中的访问顺序是 1->2->4->5->3->6

def pre_order_traversal(node):
    if node is None:
        return
    print(node.data)
    pre_order_traversal(node.left)
    pre_order_traversal(node.right)
    return node

2.中序遍历

中序遍历顺序是左子树 -> 根节点 -> 右子树示例中的访问顺序是 4->2->5->1->3->6

def in_order_traversal(node):
    if node is None:
        return
    in_order_traversal(node.left)
    print(node.data)
    in_order_traversal(node.right)
    return node

3.后序遍历

后序遍历顺序是右子树 -> 左子树 -> 根节点示例中的访问顺序是 4->5->2->6->3->1

def post_order_traversal(node):
    if node is None:
        return
    post_order_traversal(node.left)
    post_order_traversal(node.right)
    print(node.data)
    return node

广度优先遍历

广度优先的定义比较难理解，在各个方向上逐步去访问，直到当前的方向已经没有有效值了。

3.层序遍历

以层序遍历作为例子：在二叉树的每依次层上面横向遍历所有的节点，直到没有节点可以访问为止。那示例的二叉树的访问结果为 1->2->3->4->5->6

def level_order_traversal(node):
    queue = Queue()
    queue.put(node)

    while not queue.empty():
        node = queue.get()
        print(node.data)
        if node.left is not None:
            queue.put(node.left)
        if node.right is not None:
            queue.put(node.right)

作为理解的练习代码，下面贴上PHP的实现：

class TreeNode
{
    public $data = null;
    public $left = null;
    public $right = null;

    public function __construct($data)
    {
        $this->data = $data;
    }
}

function create_tree(array &$list)
{
    if ($list === null || empty($list)) {
        return null;
    }

    $data = array_shift($list);
    if ($data === null) {
        return null;
    }

    $node = new TreeNode($data);
    $node->left = create_tree($list);
    $node->right = create_tree($list);
    return $node;
}

function pre_order_traversal($node)
{
    if ($node === null) {
        return;
    }

    echo $node->data . PHP_EOL;
    pre_order_traversal($node->left);
    pre_order_traversal($node->right);
    return $node;
}

function in_order_traversal($node)
{
    if ($node === null) {
        return;
    }

    in_order_traversal($node->left);
    echo $node->data . PHP_EOL;
    in_order_traversal($node->right);
    return $node;

}

function post_order_traversal($node)
{
    if ($node === null) {
        return;
    }

    post_order_traversal($node->left);
    post_order_traversal($node->right);
    echo $node->data . PHP_EOL;
    return $node;
}

function level_order_traversal($node)
{
    $queue = [];
    array_push($queue, $node);

    while (!empty($queue)) {
        $node = array_shift($queue);
        echo $node->data.PHP_EOL;

        if($node->left) {
            array_push($queue, $node->left);
        }
        if($node->right) {
            array_push($queue, $node->right);
        }
    }
}