Php二叉树

二叉树

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
<?php
/**
* Created by PhpStorm.
* User: Alex
* Date: 2019/5/13
* Time: 12:02
*/


// 排序二叉树
// 完成以下任务.
// 1. 将节点插入到对应位置
// 2. 使用中序遍历遍历这个二叉树
// 3. 找到这个二叉树的极值
// 4. 搜索一个特定的值
class Node
{
public $key, $left, $right;

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

class BinaryTree
{
public $root;
public $sortArr = [];

public function insertNode($node, $newNode)
{
if ($node->key < $newNode->key) {
//新节点大于旧节点; 在右边位置找到一个合适位置插入,如果右边空就直接插入,如果右边不为空,使用右边节点作为根节点递归找到合适位置
if (empty($node->right)) {
$node->right = $newNode;
} else {
$this->insertNode($node->right, $newNode);
}
} else if ($node->key > $newNode->key) {
//新节点小于旧节点,往左边插入
if (empty($node->left)) {
$node->left = $newNode;
} else {
$this->insertNode($node->left, $newNode);
}
}
}

//插入节点
public function insert($key)
{
$newNodes = new Node($key);
if (empty($this->root)) {
$this->root = $newNodes;
} else {
$this->insertNode($this->root, $newNodes);
}
}

//中序遍历 : 左、根、右
public function midSort()
{
$this->sortArr = [];
$this->midSortNode($this->root);
}

public function midSortNode($node)
{
if (!empty($node)) {
$this->midSortNode($node->left);
array_push($this->sortArr, $node->key); //递归遍历后,从里往外打印 ,一次最小到最大值
$this->midSortNode($node->right);
}
}


//先序遍历 : 根、左、右
public function preSort()
{
$this->sortArr = [];
$this->preSortNode($this->root);
}

public function preSortNode($node)
{
if (!empty($node)) {
$this->sortArr[] = $node->key;

if (!empty($node->left)) {
$this->preSortNode($node->left);
}

if (!empty($node->right)) {
$this->preSortNode($node->right);
}

}
}

//后续遍历:左、右、根
public function lastSort()
{
$this->sortArr = [];
$this->lastSortNode($this->root);
}

public function lastSortNode($node)
{
if (!empty($node)) {
if (!empty($node->left)) {
$this->lastSortNode($node->left);
}


if (!empty($node->right)) {
$this->lastSortNode($node->right);
}

$this->sortArr[] = $node->key;
}
}

//层次遍历 : 先根、然后层级左右,依次层级往下遍历完
public function levelSort()
{
$this->sortArr = [];
$this->levelSortNode($this->root);
}

//如果使用地柜就需要先获取层级、不适用递归直接顺序遍历即可
public function levelSortNode($root, $level = 0)
{
if (!empty($root)) {
$node = $root;
$queue = [];

array_push($queue,$node);
$this->sortArr[] = $node->key;
while (!empty($queue)) {
$node = array_shift($queue);


if (!empty($node->left)) {
array_push($queue,$node->left);
$this->sortArr[] = $node->left->key;
}

if (!empty($node->right)) {
array_push($queue,$node->right);
$this->sortArr[] = $node->right->key;
}
}
}

}

//寻找极值
public function findMin()
{
if (!empty($this->root)) {
$this->findMinNode($this->root);
}
}

public function findMinNode($node)
{
if (!empty($node->left)) {
$this->findMinNode($node->left);
} else {
echo "min node key " . $node->key . "\n";
}
}

//寻找最大值
public function findMax()
{
if (!empty($this->root)) {
$this->findMaxNode($this->root);
}
}

public function findMaxNode($node)
{
if (!empty($node->right)) {
$this->findMaxNode($node->right);
} else {
echo "max node key " . $node->key . "\n";
}
}

//查找特殊值
public function find($val = "")
{
if (!empty($val)) {
$this->findNode($this->root, $val);
}
}

public function findNode($node, $val)
{
if ($node->key == $val) {
echo "finded key " . $node->key . "\n";
//var_dump($node);
} else if ($node->key > $val) { //做子树查找
if (!empty($node->left)) {
$this->findNode($node->left, $val);
} else {
echo "左子树未找到 \n";
}
} else if ($node->key < $val) { //右子树查找
if (!empty($node->right)) {
$this->findNode($node->right, $val);
} else {
echo "右子树未找到\n";
}
}
}


}

function dump($arr)
{
$res = json_encode($arr);
echo $res . " \n";
}

$tree = new BinaryTree();
$nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
foreach ($nodes as $k => $v) {
$tree->insert($v);
}
dump($tree);
$tree->midSort();
dump($tree->sortArr);

$tree->findMin();
$tree->findMax();

$tree->find(8);

$tree->preSort();
dump($tree->sortArr);

$tree->lastSort();
dump($tree->sortArr);

$tree->levelSort();
dump($tree->sortArr);

//先序遍历 根节点 ---> 左子树 ---> 右子树
//中序遍历,左子树---> 根节点 ---> 右子树
//后序遍历,左子树 ---> 右子树 ---> 根节点

//广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
//二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。