余读

用 PHP 实现二叉树的遍历

#二进制树(二叉树)
在计算机科学中,一个二进制树是一个树形的数据结构,其中的每一个节点最多拥有两个子节点:左子节点 和 右子节点。

树的遍历

通过 递归访问根节点的左子树和右子树的每一个节点 的方法,叫做遍历。
二进制树的遍历主要有两种方式:深度优先遍历(Depth-first order)和宽度优先遍历(Breath-first order)。

深度优先遍历

在深度优先遍历中,我们总是尝试先去访问离根节点最远的节点,但有一个限制条件:它必须是被我们访问过的节点的子节点。
其中深度优先遍历又有三种方式:先序(Pre-order)、中序(In-order)和后序(Post-order)遍历。用L,N,R分别代表左子节点,根节点和右子节点,那么三种方式的遍历顺序是:

  • 先序:N->L->R
  • 中序:L->N->R
  • 后序:L->R->N

宽度优先遍历

与深度优先遍历相对的是宽度优先遍历,它总是先去访问离根节点最近的节点,同样有个限制条件:该节点尚未被访问过。宽度优先遍历又叫做层次优先遍历(Level-order)。

作者非常不喜欢 二叉 树和 广度 优先遍历这两个翻译
摘自 维基百科 Binary tree Tree traversal

简单介绍完了什么是二进制树和树的遍历,接下来我们就用代码来实现树的遍历。

创建节点

一棵树由 N 个节点组成,于是我们先建立一个类来代表节点

1
2
3
4
5
6
7
8
9
10
11
12
<?php
class Node
{
public $data = null;
public $left = null;
public $right = null;
public __construct($data = null)
{
$this->data = $data;
}
}

深度优先遍历

深度优先遍历可以用栈来实现,我们用数组来模拟栈,分别用 array_pusharray_pop 来做入栈、出栈操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php
**
* @param $btree 二进制树的根节点
*
function depth_first_traverse($btree) {
$traverseData = [];
$stack = [];
array_push($stack, $btree); // 根节点入栈
while(!empty($stack)) { // 持续输出节点,直到栈为空
$curNode = array_pop($stack); // 栈顶元素出栈
$traverseData[] = $curNode->data;
// 右节点先入栈,然后左节点入栈
if ($curNode->right != null) array_push($stack, $curNode->right);
if ($curNode->left != null) array_push($stack, $curNode->left);
}
return $traverseData;
}

在这里我们采用的是先序遍历:N->L->R。

宽度优先遍历

实现宽度优先遍历我们需要一个队列,同样我们用数组来模拟,这次我们需要 array_unshiftarray_pop 来做入队、出队操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php
**
* @param $btree 二进制树的根节点
*
function breadth_first_traverse($btree) {
$traverseData = [];
$queue = [];
array_unshift($stack, $btree); // 根节点入队
while(!empty($queue)) { // 持续输出节点,知道队列为空
$curNode = array_pop($queue); // 对尾元素出队
$traverseData[] = $curNode->data;
// 左节点先入队,然后右节点入队
if ($curNode->left != null) array_unshift($queue, $curNode->left);
if ($curNode->right != null) array_unshift($queue, $curNode->right);
}
return $traverseData;
}

测试代码

是时候来跑一跑我们的代码了,用维基的例图来测试我们的代码

Pre-order: F, B, A, D, C, E, G, I, H.

Level-order: F, B, G, A, D, I, C, E, H.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?php
$root = new Node('F');
$a = new Node('A');
$b = new Node('B');
$c = new Node('C');
$d = new Node('D');
$e = new Node('E');
$g = new Node('G');
$h = new Node('H');
$i = new Node('I');
b
$root->left = $b;
$root->right = $g;
$b->left = $a;
$b->right = $d;
$d->left = $c;
$d->right = $e;
$g->right = $i;
$i->left = $h;
$traverse = depth_first_traverse($root);
print_r($traverse); // 输出 F, B, A, D, C, E, G, I, H
echo '<br>';
$traverse = breadth_first_traverse($root);
print_r($traverse); // 输出 F, B, G, A, D, I, C, E, H