遍历二叉树
深度优先遍历 DFS
二叉树的深度优先遍历可以细分为:先序遍历、中序遍历、后续遍历。
- 前序遍历:根节点 -> 左子树 -> 右子树
- 中序遍历:左子树 -> 根节点 -> 右子树
- 后续遍历:左子树 -> 右子树 -> 根节点
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class BTreeNode {
public $data; //数据域
public $LeftHand = NULL; //左指针
public $RightHand = NULL ; //右指针
public function __construct($data) {
if(!empty($data)) {
$this->data = $data;
}
}
//先序遍历(根,左,右)递归实现
public function PreTraverseBTree($BTree){
if (NULL !== $BTree){
var_dump($BTree->data);//根
if (NULL !== $BTree->LeftHand){
$this->PreTraverseBTree($BTree->LeftHand); //递归遍历左树
}
if (NULL !== $BTree->RightHand){
$this->PreTraverseBTree($BTree->RightHand); //递归遍历右树
}
}
}
//中序遍历(左,根,右)递归实现
public function InTraverseBTree($BTree){
if (NULL !== $BTree){
if (NULL !== $BTree->LeftHand){
$this->InTraverseBTree($BTree->LeftHand); //递归遍历左树
}
var_dump($BTree->data); //根
if (NULL !== $BTree->RightHand){
$this->InTraverseBTree($BTree->RightHand); //递归遍历右树
}
}
}
//后序遍历(左,右,根)递归实现
public function FexTarverseBTree($BTree){
if (NULL !== $BTree){
if (NULL !== $BTree->LeftHand){
$this->FexTarverseBTree($BTree->LeftHand); //递归遍历左树
}
if (NULL !== $BTree->RightHand){
$this->FexTarverseBTree($BTree->RightHand); //递归遍历右树
}
var_dump($BTree->data); //根
}
}
}
header("Content-Type:text/html;charset=utf-8");
echo '先的内存为'.var_dump(memory_get_usage());
echo '<hr/>';
//创建五个节点
$A = new BTreeNode('A');
$B = new BTreeNode('B');
$C = new BTreeNode('C');
$D = new BTreeNode('D');
$E = new BTreeNode('E');
//连接形成一个二叉树
$A->LeftHand = $B;
$A->RightHand = $C;
$C->LeftHand = $D;
$D->RightHand = $E;
//先序遍历
echo '先序遍历的结果'.'<br>';
$A->PreTraverseBTree($A);
echo '<br/>中序遍历的结果'.'<br>';
$A->InTraverseBTree($A);
echo '<br/>后序列遍历的结果'.'<br/>';
$A->FexTarverseBTree($A);
echo '<hr/>';
echo '后的内存为'.var_dump(memory_get_usage());
广度优先遍历 BFS
广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
1 | // Definition for a binary tree node |
版本1:数组模拟队列,先入先出
1 | class Solution { |
版本2:使用PHP SplQueue
SplQueue 类通过使用一个双向链表来提供队列的主要功能。
1 | class Solution { |
版本3:递归
1 | class Solution { |
判断是否是二叉搜索树
判断一颗树是否是二叉搜索树,一棵树是BST需要满足
- 一个节点的值大于它左子树所有节点的值
- 一个节点的值小于它右子树所有节点的值
- 左右子树也必须是二叉搜索树
所以只需要遍历每个节点,判断
- 该节点值是否大于左子树的最大值
- 该节点值是否小于右子树的最小值
1 | /** |