-
Notifications
You must be signed in to change notification settings - Fork 0
/
ba945d0d.html
525 lines (487 loc) · 243 KB
/
ba945d0d.html
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
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><div id="myscoll"></div><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>数据结构与算法2 | Miaow.Y.Hu的博客🥝</title><meta name="keywords" content="java学习"><meta name="author" content="Miaow.Y.Hu🥝"><meta name="copyright" content="Miaow.Y.Hu🥝"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="ffffff"><meta name="description" content="本文主要是笔者在学习java数据结构和算法的笔记">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法2">
<meta property="og:url" content="https://www.blog.909111.xyz/posts/ba945d0d.html">
<meta property="og:site_name" content="Miaow.Y.Hu的博客🥝">
<meta property="og:description" content="本文主要是笔者在学习java数据结构和算法的笔记">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg">
<meta property="article:published_time" content="2023-11-09T02:50:23.344Z">
<meta property="article:modified_time" content="2023-11-09T02:50:23.344Z">
<meta property="article:author" content="Miaow.Y.Hu🥝">
<meta property="article:tag" content="java学习">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg"><link rel="shortcut icon" href="/"><link rel="canonical" href="https://www.blog.909111.xyz/posts/ba945d0d"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://lf6-cdn-tos.bytecdntp.com/cdn/expire-1-M/font-awesome/6.0.0/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.staticfile.org/fancyapps-ui/4.0.31/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: {"path":"/search.xml","preload":true,"languages":{"hits_empty":"找不到您查询的内容：${query}"}},
translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"简"},
noticeOutdate: {"limitDay":365,"position":"top","messagePrev":"It has been","messageNext":"days since the last update, the content of the article may be outdated."},
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":230},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: true,
post: true
},
runtime: '',
date_suffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: undefined,
lightbox: 'fancybox',
Snackbar: undefined,
source: {
justifiedGallery: {
js: 'https://cdnjs.cloudflare.com/ajax/libs/flickr-justified-gallery/2.1.2/fjGallery.min.js',
css: 'https://cdnjs.cloudflare.com/ajax/libs/flickr-justified-gallery/2.1.2/fjGallery.min.css'
}
},
isPhotoFigcaption: false,
islazyload: true,
isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: '数据结构与算法2',
isPost: true,
isHome: false,
isHighlightShrink: false,
isToc: true,
postUpdate: '2023-11-09 10:50:23'
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', 'ffffff')
}
}
const t = saveToLocal.get('theme')
const now = new Date()
const hour = now.getHours()
const isNight = hour <= 6 || hour >= 18
if (t === undefined) isNight ? activateDarkMode() : activateLightMode()
else if (t === 'light') activateLightMode()
else activateDarkMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><link rel="stylesheet" href="/css/custom.css" media="defer" onload="this.media='all'"><style id="themeColor"></style><style id="rightSide"></style><style id="transPercent"></style><style id="blurNum"></style><style id="settingStyle"></style><span id="fps"></span><style id="defineBg"></style><style id="menu_shadow"></style><link rel="stylesheet" href="/css/universe.css"><link rel="stylesheet" href="https://cdn1.tianli0.top/npm/[email protected]/packages/theme-chalk/lib/index.css"><link rel="stylesheet" href="/css/aplayer.css"><script src="https://npm.elemecdn.com/[email protected]/dist/echarts.min.js"></script><svg aria-hidden="true" style="position:absolute; overflow:hidden; width:0; height:0"><symbol id="icon-sun" viewBox="0 0 1024 1024"><path d="M960 512l-128 128v192h-192l-128 128-128-128H192v-192l-128-128 128-128V192h192l128-128 128 128h192v192z" fill="#FFD878" p-id="8420"></path><path d="M736 512a224 224 0 1 0-448 0 224 224 0 1 0 448 0z" fill="#FFE4A9" p-id="8421"></path><path d="M512 109.248L626.752 224H800v173.248L914.752 512 800 626.752V800h-173.248L512 914.752 397.248 800H224v-173.248L109.248 512 224 397.248V224h173.248L512 109.248M512 64l-128 128H192v192l-128 128 128 128v192h192l128 128 128-128h192v-192l128-128-128-128V192h-192l-128-128z" fill="#4D5152" p-id="8422"></path><path d="M512 320c105.888 0 192 86.112 192 192s-86.112 192-192 192-192-86.112-192-192 86.112-192 192-192m0-32a224 224 0 1 0 0 448 224 224 0 0 0 0-448z" fill="#4D5152" p-id="8423"></path></symbol><symbol id="icon-moon" viewBox="0 0 1024 1024"><path d="M611.370667 167.082667a445.013333 445.013333 0 0 1-38.4 161.834666 477.824 477.824 0 0 1-244.736 244.394667 445.141333 445.141333 0 0 1-161.109334 38.058667 85.077333 85.077333 0 0 0-65.066666 135.722666A462.08 462.08 0 1 0 747.093333 102.058667a85.077333 85.077333 0 0 0-135.722666 65.024z" fill="#FFB531" p-id="11345"></path><path d="M329.728 274.133333l35.157333-35.157333a21.333333 21.333333 0 1 0-30.165333-30.165333l-35.157333 35.157333-35.114667-35.157333a21.333333 21.333333 0 0 0-30.165333 30.165333l35.114666 35.157333-35.114666 35.157334a21.333333 21.333333 0 1 0 30.165333 30.165333l35.114667-35.157333 35.157333 35.157333a21.333333 21.333333 0 1 0 30.165333-30.165333z" fill="#030835" p-id="11346"></path></symbol></svg><!-- hexo injector head_end start --><link rel="stylesheet" href="https://cdn.cbd.int/hexo-butterfly-clock-anzhiyu/lib/clock.min.css" /><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-tag-plugins-plus@latest/lib/assets/font-awesome-animation.min.css" media="defer" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-tag-plugins-plus@latest/lib/tag_plugins.css" media="defer" onload="this.media='all'"><script src="https://npm.elemecdn.com/hexo-butterfly-tag-plugins-plus@latest/lib/assets/carousel-touch.js"></script><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiperstyle.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-wowjs/lib/animate.min.css" media="print" onload="this.media='screen'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.css" media="print" onload="this.media='all'"><!-- hexo injector head_end end --><meta name="generator" content="Hexo 6.3.0"><link rel="alternate" href="/atom.xml" title="Miaow.Y.Hu的博客🥝" type="application/atom+xml">
</head><body><div id="loading-box" onclick="document.getElementById("loading-box").classList.add("loaded")"><div class="loading-bg"><div class="loading-img"></div><div class="loading-image-dot"></div></div></div><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221548536.png" onerror="onerror=null;src='/assets/r1.jpg'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">32</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">19</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">17</div></a></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-home"></use></svg><span class="menu_word" style="font-size:17px"> 首页</span></a></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon--article"></use></svg><span class="menu_word" style="font-size:17px"> 文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-guidang1"> </use></svg><span class="menu_word" style="font-size:17px"> 归档</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-sekuaibiaoqian"> </use></svg><span class="menu_word" style="font-size:17px"> 标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-fenlei"> </use></svg><span class="menu_word" style="font-size:17px"> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-pinweishenghuo"></use></svg><span class="menu_word" style="font-size:17px"> 休闲</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/life/music/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-yinle"> </use></svg><span class="menu_word" style="font-size:17px"> 八音盒</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/life/movies/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-dianying1"> </use></svg><span class="menu_word" style="font-size:17px"> 影院</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/life/games/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-youxishoubing"> </use></svg><span class="menu_word" style="font-size:17px"> 游戏</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-xiangzi"></use></svg><span class="menu_word" style="font-size:17px"> 八宝箱</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/box/gallery/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-tubiaozhizuomoban"> </use></svg><span class="menu_word" style="font-size:17px"> 画廊</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/box/animation/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-nvwumao"> </use></svg><span class="menu_word" style="font-size:17px"> 动画</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/box/nav/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-zhifengche"> </use></svg><span class="menu_word" style="font-size:17px"> 网址导航</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-shejiaoxinxi"></use></svg><span class="menu_word" style="font-size:17px"> 社交</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/social/fcircle/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-pengyouquan"> </use></svg><span class="menu_word" style="font-size:17px"> 朋友圈</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/comments/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-liuyan"> </use></svg><span class="menu_word" style="font-size:17px"> 留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/social/link/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-lianjie"> </use></svg><span class="menu_word" style="font-size:17px"> 友人帐</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-maoliang"></use></svg><span class="menu_word" style="font-size:17px"> 个人</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/personal/echarts/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-shujutongji1"> </use></svg><span class="menu_word" style="font-size:17px"> 文章统计</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/personal/love/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-love-sign"> </use></svg><span class="menu_word" style="font-size:17px"> 恋爱小屋</span></a></li></ul></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">Miaow.Y.Hu的博客🥝</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-home"></use></svg><span class="menu_word" style="font-size:17px"> 首页</span></a></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon--article"></use></svg><span class="menu_word" style="font-size:17px"> 文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-guidang1"> </use></svg><span class="menu_word" style="font-size:17px"> 归档</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-sekuaibiaoqian"> </use></svg><span class="menu_word" style="font-size:17px"> 标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-fenlei"> </use></svg><span class="menu_word" style="font-size:17px"> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-pinweishenghuo"></use></svg><span class="menu_word" style="font-size:17px"> 休闲</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/life/music/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-yinle"> </use></svg><span class="menu_word" style="font-size:17px"> 八音盒</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/life/movies/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-dianying1"> </use></svg><span class="menu_word" style="font-size:17px"> 影院</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/life/games/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-youxishoubing"> </use></svg><span class="menu_word" style="font-size:17px"> 游戏</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-xiangzi"></use></svg><span class="menu_word" style="font-size:17px"> 八宝箱</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/box/gallery/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-tubiaozhizuomoban"> </use></svg><span class="menu_word" style="font-size:17px"> 画廊</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/box/animation/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-nvwumao"> </use></svg><span class="menu_word" style="font-size:17px"> 动画</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/box/nav/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-zhifengche"> </use></svg><span class="menu_word" style="font-size:17px"> 网址导航</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-shejiaoxinxi"></use></svg><span class="menu_word" style="font-size:17px"> 社交</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/social/fcircle/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-pengyouquan"> </use></svg><span class="menu_word" style="font-size:17px"> 朋友圈</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/comments/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-liuyan"> </use></svg><span class="menu_word" style="font-size:17px"> 留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/social/link/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-lianjie"> </use></svg><span class="menu_word" style="font-size:17px"> 友人帐</span></a></li></ul></div><div class="menus_item"><a class="site-page group faa-parent animated-hover hide" href="javascript:void(0);"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-maoliang"></use></svg><span class="menu_word" style="font-size:17px"> 个人</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/personal/echarts/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-shujutongji1"> </use></svg><span class="menu_word" style="font-size:17px"> 文章统计</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/personal/love/"><svg class="menu_icon faa-tada" aria-hidden="true" style="width:1.30em;height:1.30em;vertical-align:-0.15em;fill:currentColor;overflow:hidden;"><use xlink:href="#icon-love-sign"> </use></svg><span class="menu_word" style="font-size:17px"> 恋爱小屋</span></a></li></ul></div></div><center id="name-container"><a id="page-name" href="javascript:scrollToTop()">PAGE_NAME</a></center><div id="nav-right"><div id="search-button"><a class="search faa-parent animated-hover" title="检索站内任何你想要的信息"><svg class="faa-tada icon" style="height:24px;width:24px;fill:currentColor;position:relative;top:6px" aria-hidden="true"><use xlink:href="#icon-valentine_-search-love-find-heart"></use></svg><span> 搜索</span></a></div><a class="meihua faa-parent animated-hover" onclick="toggleWinbox()" title="美化设置-自定义你的风格" id="meihua-button"><svg class="faa-tada icon" style="height:26px;width:26px;fill:currentColor;position:relative;top:8px" aria-hidden="true"><use xlink:href="#icon-tupian1"></use></svg></a><a class="sun_moon faa-parent animated-hover" onclick="switchNightMode()" title="浅色和深色模式转换" id="nightmode-button"><svg class="faa-tada" style="height:25px;width:25px;fill:currentColor;position:relative;top:7px" viewBox="0 0 1024 1024"><use id="modeicon" xlink:href="#icon-moon"> </use></svg></a><div id="toggle-menu"><a><i class="fas fa-bars fa-fw"></i></a></div></div></div></nav><div id="post-info"><h1 class="post-title">数据结构与算法2</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><svg class="meta_icon post-meta-icon" style="width:30px;height:30px;position:relative;top:10px"><use xlink:href="#icon-rili"></use></svg><span class="post-meta-label">发表于 </span><time class="post-meta-date-created" datetime="2023-11-09T02:50:23.344Z" title="发表于 2023-11-09 10:50:23">2023-11-09</time><span class="post-meta-separator">|</span><svg class="meta_icon post-meta-icon" style="width:18px;height:18px;position:relative;top:5px"><use xlink:href="#icon-gengxin1"></use></svg><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-11-09T02:50:23.344Z" title="更新于 2023-11-09 10:50:23">2023-11-09</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><svg class="meta_icon post-meta-icon" style="width:18px;height:18px;position:relative;top:5px"><use xlink:href="#icon-biaoqian"></use></svg><a class="post-meta-categories" href="/categories/java%E5%AD%A6%E4%B9%A0/">java学习</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><svg class="meta_icon post-meta-icon" style="width:25px;height:25px;position:relative;top:8px"><use xlink:href="#icon-charuword"></use></svg><span class="post-meta-label">字数总计:</span><span class="word-count">7858</span><span class="post-meta-separator">|</span><svg class="meta_icon post-meta-icon" style="width:20px;height:20px;position:relative;top:5px"><use xlink:href="#icon-shizhong"></use></svg><span class="post-meta-label">阅读时长:</span><span>33分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="数据结构与算法2"><svg class="meta_icon post-meta-icon" style="width:25px;height:25px;position:relative;top:5px"><use xlink:href="#icon-eye"></use></svg><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div><section class="main-hero-waves-area waves-area"><svg class="waves-svg" xmlns="http://www.w3.org/2000/svg" xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M -160 44 c 30 0 58 -18 88 -18 s 58 18 88 18 s 58 -18 88 -18 s 58 18 88 18 v 44 h -352 Z"></path></defs><g class="parallax"><use href="#gentle-wave" x="48" y="0"></use><use href="#gentle-wave" x="48" y="3"></use><use href="#gentle-wave" x="48" y="5"></use><use href="#gentle-wave" x="48" y="7"></use></g></svg></section></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><p>由于上个文件字数到达2w以上，本软件加载比较麻烦，故而新建一个文件用来记录。</p>
<h1 id="数据结构与算法"><a href="#数据结构与算法" class="headerlink" title="数据结构与算法"></a>数据结构与算法</h1><h2 id="9-哈希表"><a href="#9-哈希表" class="headerlink" title="9 哈希表"></a>9 哈希表</h2><p>一种数据结构</p>
<p>一般有hashMap,hashtable</p>
<p>哈希表，是一种数据结构，主要是key 与value的关系，了解hash表之前，我们需要了解的是哈希表，需要知道哈希函数，在jdk1.8之后，采用的红黑树进行一定的存储，其是根据关键码值而进行访问的数据结构，也就是说，<strong>其通过把关键码映射到表中的一个位置来访问记录，以加快查找的速度，这个映射函数我们称之为散列函数，存放记录的数组叫做散列表。</strong></p>
<p>hashtable来存储雇员信息。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">HashtableDemo</span> {</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="type">hashTable</span> <span class="variable">hashtab</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">hashTable</span>(<span class="number">8</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp1</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">10</span>,<span class="string">"社会虎"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp2</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">18</span>,<span class="string">"废物刀"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp3</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">26</span>,<span class="string">"黑牛"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp4</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">3</span>,<span class="string">"白牛"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp5</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">193</span>,<span class="string">"小亮"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp6</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">231</span>,<span class="string">"唐老鸭"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp7</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">12</span>,<span class="string">"百特曼"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp8</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">1</span>,<span class="string">"独爱小尹"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp9</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">123</span>,<span class="string">"丽丽"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp10</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">126</span>,<span class="string">"带篮子"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp11</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">29</span>,<span class="string">"刘墉"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp12</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">86</span>,<span class="string">"丁真"</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">Emp13</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Emp</span>(<span class="number">800</span>,<span class="string">"王冰冰"</span>);<span class="comment">//定义数据</span></span><br><span class="line"></span><br><span class="line"> hashtab.add(Emp1);</span><br><span class="line"> hashtab.add(Emp2);</span><br><span class="line"> hashtab.add(Emp3);</span><br><span class="line"> hashtab.add(Emp4);</span><br><span class="line"> hashtab.add(Emp5);</span><br><span class="line"> hashtab.add(Emp6);</span><br><span class="line"> hashtab.add(Emp7);</span><br><span class="line"> hashtab.add(Emp8);</span><br><span class="line"> hashtab.add(Emp9);</span><br><span class="line"> hashtab.add(Emp10);</span><br><span class="line"> hashtab.add(Emp11);</span><br><span class="line"> hashtab.add(Emp12);</span><br><span class="line"> hashtab.add(Emp13);<span class="comment">//插入数据</span></span><br><span class="line"> </span><br><span class="line"> hashtab.list();</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//创建hashtable</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">hashTable</span>{</span><br><span class="line"> <span class="keyword">private</span> <span class="type">int</span> size;</span><br><span class="line"> <span class="keyword">private</span> EmpLinkedList[] empLinkedLists;</span><br><span class="line"> <span class="comment">//创建一个构造器</span></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">hashTable</span><span class="params">(<span class="type">int</span> size)</span> {</span><br><span class="line"> <span class="built_in">this</span>.size = size;</span><br><span class="line"> <span class="comment">//初始化empLinkedListArray</span></span><br><span class="line"> empLinkedLists = <span class="keyword">new</span> <span class="title class_">EmpLinkedList</span>[size];</span><br><span class="line"> <span class="comment">//细节，引用类型的变量在声明后如果不初始化那么默认值就是null</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span> ; i < size; i++) {</span><br><span class="line"> <span class="comment">//这个循环体就是在初始化</span></span><br><span class="line"> empLinkedLists[i] = <span class="keyword">new</span> <span class="title class_">EmpLinkedList</span>();<span class="comment">//在这里必须要逐一为每个元素实例化</span></span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">hash</span><span class="params">(<span class="type">int</span> id)</span> {</span><br><span class="line"> <span class="keyword">return</span> id % size;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//添加雇员</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">add</span><span class="params">(Emp emp)</span>{</span><br><span class="line"> <span class="comment">//根据员工的id得到该员工应该加入</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">num</span> <span class="operator">=</span> hash(emp.id);</span><br><span class="line"> empLinkedLists[num].add(emp);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">list</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span> ; i < size ; i ++ ) {</span><br><span class="line"> System.out.println(<span class="string">"第"</span>+i+<span class="string">"个链表状况"</span>);</span><br><span class="line"> empLinkedLists[i].list();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//表是</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Emp</span>{</span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> id;</span><br><span class="line"> <span class="keyword">public</span> String name;</span><br><span class="line"> <span class="keyword">public</span> Emp next; <span class="comment">//next 默认为空</span></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">Emp</span><span class="params">()</span> {</span><br><span class="line"> <span class="built_in">super</span>();</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">Emp</span><span class="params">(<span class="type">int</span> id, String name)</span> {</span><br><span class="line"> <span class="built_in">super</span>();</span><br><span class="line"> <span class="built_in">this</span>.id = id;</span><br><span class="line"> <span class="built_in">this</span>.name = name;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getId</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> id;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setId</span><span class="params">(<span class="type">int</span> id)</span> {</span><br><span class="line"> <span class="built_in">this</span>.id = id;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> String <span class="title function_">getName</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> name;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setName</span><span class="params">(String name)</span> {</span><br><span class="line"> <span class="built_in">this</span>.name = name;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> Emp <span class="title function_">getNext</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> next;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setNext</span><span class="params">(Emp next)</span> {</span><br><span class="line"> <span class="built_in">this</span>.next = next;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="comment">//创建一个EmpLinkList,表示链表</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">EmpLinkedList</span>{</span><br><span class="line"> <span class="comment">//投指针，执行第一个Emp,因此我们这个链表的head是直接指向第一个Emp</span></span><br><span class="line"> <span class="keyword">private</span> Emp head; <span class="comment">//默认为空</span></span><br><span class="line"> <span class="comment">//添加雇员到链表</span></span><br><span class="line"> <span class="comment">//说明</span></span><br><span class="line"> <span class="comment">//假定，当添加雇员时候，id是自增长，即id的分配总数从小到大的</span></span><br><span class="line"> <span class="comment">//因此我们将该雇员直接加入到本链表的最后即可</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">add</span><span class="params">(Emp emp)</span> {</span><br><span class="line"> <span class="comment">//如果是第一个雇员</span></span><br><span class="line"> <span class="keyword">if</span>(head == <span class="literal">null</span> ) {</span><br><span class="line"> head = emp;</span><br><span class="line"> <span class="keyword">return</span> ;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后</span></span><br><span class="line"> <span class="type">Emp</span> <span class="variable">curEmp</span> <span class="operator">=</span> head;</span><br><span class="line"> <span class="keyword">while</span>(<span class="literal">true</span>) {</span><br><span class="line"> <span class="keyword">if</span>(curEmp.next == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> curEmp = curEmp.next; <span class="comment">//后移</span></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//退出时直接将emp加入链表</span></span><br><span class="line"> curEmp.next = emp;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//遍历链表的雇员信息</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">list</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span>(head == <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//如果链表为空</span></span><br><span class="line"> System.out.println(<span class="string">"当前链表为空"</span>);</span><br><span class="line"> <span class="keyword">return</span> ;</span><br><span class="line"> }</span><br><span class="line"> System.out.println(<span class="string">"当前链表的信息为："</span>);</span><br><span class="line"> <span class="type">Emp</span> <span class="variable">cuEmp</span> <span class="operator">=</span> head ; <span class="comment">//辅助指针</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">count</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(<span class="literal">true</span>) {</span><br><span class="line"> System.out.printf(<span class="string">"id = %d name = %s\n"</span>,cuEmp.id,cuEmp.name);</span><br><span class="line"> count ++;</span><br><span class="line"> <span class="keyword">if</span>(cuEmp.next == <span class="literal">null</span> ) {</span><br><span class="line"> <span class="comment">//说明cuEmp已经是最后的节点</span></span><br><span class="line"> System.out.println(<span class="string">"共计有"</span>+ count+ <span class="string">"个"</span>);</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> cuEmp = cuEmp.next;<span class="comment">//后移，遍历</span></span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="10-数据结构的存储方式"><a href="#10-数据结构的存储方式" class="headerlink" title="10.数据结构的存储方式"></a>10.数据结构的存储方式</h2><h3 id="10-1二叉树"><a href="#10-1二叉树" class="headerlink" title="10.1二叉树"></a>10.1二叉树</h3><ol>
<li><p>数组的存储方式的分析<br><strong>优点：</strong>通过下标方式访问元素，速度快。对于有序数组，还可以使用二分查找提高检索速度。</p>
<p><strong>缺点：</strong>如果要检索具体某个值，或者插入值（按照一定顺序）会整体移动，效率较低。</p>
</li>
</ol>
<ol>
<li><p>链式存储方式的分析</p>
<p><strong>优点：</strong>在一定程度上对数组的存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好）</p>
<p><strong>缺点：</strong>在进行<strong>检索</strong>时，效率仍然比较低，比如（检索某个值，需要从头结点开始遍历）</p>
</li>
<li><p>树存储方式的分析</p>
<p><strong>优点：</strong>可以提高数据存储，读取的效率，比如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。</p>
<p><strong>缺点：</strong>顺序存储可能会浪费空间（在非完全二叉树的时候，但是读取某个特定的节点的时候效率比较高O(0)）;链式存储相对于二叉树，浪费空间较少，但是读取某个结点时效率偏低O(nlogn)。</p>
</li>
</ol>
<h3 id="10-2-二叉树的概率和常用术语"><a href="#10-2-二叉树的概率和常用术语" class="headerlink" title="10.2 二叉树的概率和常用术语"></a>10.2 二叉树的概率和常用术语</h3><p><strong>满二叉树：</strong>在一个二叉树中，如果所有分支节点都有左孩子节点和右孩子节点，并且叶节点都集中在二叉树中的最下一层，这样的二叉树被称为满二叉树。</p>
<p><strong>完全二叉树：</strong>若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子节点，都依次排列在该层最左边的位置上，这样的二叉树称为完全二叉树。</p>
<h4 id="遍历和节点删除"><a href="#遍历和节点删除" class="headerlink" title="遍历和节点删除"></a>遍历和节点删除</h4><p>二叉树是一种非常重要的数据结构，非常多的数据结构都是基于二叉树的基础演变而来的。对于二叉树有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义，因此采用递归的方法实现树的三种遍历。 </p>
<ul>
<li>前序遍历：根结点 —>左子树—>右子树；</li>
<li>中序遍历：左子树 —>根结点—>右子树；</li>
<li>后续遍历：左子树 —>右子树—>根结点；</li>
<li>层次遍历：仅仅需按成次遍历即可；</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BinaryTreeDemo</span> {</span><br><span class="line"> <span class="comment">//定义一个自定义二叉树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="comment">//创建一个二叉树</span></span><br><span class="line"> <span class="comment">//创建一个二叉树</span></span><br><span class="line"> <span class="type">BinaryTree</span> <span class="variable">binaryTree</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BinaryTree</span>();</span><br><span class="line"> <span class="comment">//创建结点</span></span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">root</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">HeroNode</span>(<span class="number">1</span>, <span class="string">"宋江"</span>);</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">node2</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">HeroNode</span>(<span class="number">2</span>, <span class="string">"卢俊义"</span>);</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">node3</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">HeroNode</span>(<span class="number">3</span>, <span class="string">"吴用"</span>);</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">node4</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">HeroNode</span>(<span class="number">4</span>, <span class="string">"公孙胜"</span>);</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">node5</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">HeroNode</span>(<span class="number">5</span>, <span class="string">"关胜"</span>);</span><br><span class="line"> root.setLeft(node2);</span><br><span class="line"> root.setRight(node3);</span><br><span class="line"> node3.setLeft(node4);</span><br><span class="line"> node3.setRight(node5);</span><br><span class="line"> binaryTree.setRoot(root);</span><br><span class="line"> System.out.println(<span class="string">"前序遍历"</span>);</span><br><span class="line"> binaryTree.preOrder();</span><br><span class="line"> System.out.println(<span class="string">"中序遍历"</span>);</span><br><span class="line"> binaryTree.midOrder();</span><br><span class="line"> System.out.println(<span class="string">"后序遍历"</span>);</span><br><span class="line"> binaryTree.postOrder();</span><br><span class="line"> binaryTree.delNode(<span class="number">3</span>);</span><br><span class="line"> System.out.println(<span class="string">"删除结点3，前序遍历"</span>);</span><br><span class="line"> binaryTree.preOrder();</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="comment">//定义BinaryTree 二叉树</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">BinaryTree</span> {</span><br><span class="line"> <span class="keyword">private</span> HeroNode root;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> HeroNode <span class="title function_">getRoot</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> root;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setRoot</span><span class="params">(HeroNode root)</span> {</span><br><span class="line"> <span class="built_in">this</span>.root = root;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//前序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">preOrder</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.root != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.root.preOrder();</span><br><span class="line"> }<span class="keyword">else</span> {</span><br><span class="line"> System.out.println(<span class="string">"二叉树为空，不能遍历"</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">midOrder</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.root != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.root.midOrder();</span><br><span class="line"> }<span class="keyword">else</span> {</span><br><span class="line"> System.out.println(<span class="string">"二叉树为空，无法遍历"</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//后序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">postOrder</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.root != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.root.postOrder();</span><br><span class="line"> }<span class="keyword">else</span> {</span><br><span class="line"> System.out.println(<span class="string">"二叉树为空，无法遍历"</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除结点</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delNode</span><span class="params">(<span class="type">int</span> no)</span> {</span><br><span class="line"> <span class="keyword">if</span>(root != <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//如果只有一个root结点, 这里立即判断root是不是就是要删除结点</span></span><br><span class="line"> <span class="keyword">if</span>(root.getNo() == no) {</span><br><span class="line"> root = <span class="literal">null</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">//递归删除</span></span><br><span class="line"> root.delNode(no);</span><br><span class="line"> }</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> System.out.println(<span class="string">"空树，不能删除~"</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//先创建HeroNode 结点</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">HeroNode</span> {</span><br><span class="line"> <span class="keyword">private</span> <span class="type">int</span> no;</span><br><span class="line"> <span class="keyword">private</span> String name;</span><br><span class="line"> <span class="keyword">private</span> HeroNode left; <span class="comment">//默认null</span></span><br><span class="line"> <span class="keyword">private</span> HeroNode right; <span class="comment">//默认null</span></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">HeroNode</span><span class="params">(<span class="type">int</span> no, String name)</span> {</span><br><span class="line"> <span class="built_in">this</span>.no = no;</span><br><span class="line"> <span class="built_in">this</span>.name = name;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getNo</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> no;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setNo</span><span class="params">(<span class="type">int</span> no)</span> {</span><br><span class="line"> <span class="built_in">this</span>.no = no;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> String <span class="title function_">getName</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> name;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setName</span><span class="params">(String name)</span> {</span><br><span class="line"> <span class="built_in">this</span>.name = name;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> HeroNode <span class="title function_">getLeft</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> left;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setLeft</span><span class="params">(HeroNode left)</span> {</span><br><span class="line"> <span class="built_in">this</span>.left = left;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> HeroNode <span class="title function_">getRight</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> right;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setRight</span><span class="params">(HeroNode right)</span> {</span><br><span class="line"> <span class="built_in">this</span>.right = right;</span><br><span class="line"> }</span><br><span class="line"> <span class="meta">@Override</span></span><br><span class="line"> <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> <span class="string">"HeroNode [no="</span> + no + <span class="string">", name="</span> + name + <span class="string">"]"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//前序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">preOrder</span><span class="params">()</span> {</span><br><span class="line"> System.out.println(<span class="built_in">this</span>);<span class="comment">//先输出父节点</span></span><br><span class="line"> <span class="comment">//递归向左子树前序遍历</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.left != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.left.preOrder();</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//递归向右子树前序遍历</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.right != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.right.preOrder();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">midOrder</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//递归向左子树中序遍历</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.left != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.left.midOrder();</span><br><span class="line"> }</span><br><span class="line"> System.out.println(<span class="built_in">this</span>);<span class="comment">//输出父节点</span></span><br><span class="line"> <span class="comment">//递归向右子树前序遍历</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.right != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.right.midOrder();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//后序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">postOrder</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//递归向左子树后序遍历</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.left != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.left.postOrder();</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//递归向右子树前序遍历</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.right != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.right.postOrder();</span><br><span class="line"> }</span><br><span class="line"> System.out.println(<span class="built_in">this</span>);<span class="comment">//输出父节点</span></span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//递归删除结点</span></span><br><span class="line"> <span class="comment">//1.如果删除的节点是叶子节点，则删除该节点</span></span><br><span class="line"> <span class="comment">//2.如果删除的节点是非叶子节点，则删除该子树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delNode</span><span class="params">(<span class="type">int</span> no)</span> {</span><br><span class="line"> <span class="comment">//思路</span></span><br><span class="line"> <span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.</span></span><br><span class="line"><span class="comment"> 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)</span></span><br><span class="line"><span class="comment"> 3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)</span></span><br><span class="line"><span class="comment"> 4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除</span></span><br><span class="line"><span class="comment"> 5. 如果第4步也没有删除结点，则应当向右子树进行递归删除.</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="comment">//2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.left != <span class="literal">null</span> && <span class="built_in">this</span>.left.no == no) {</span><br><span class="line"> <span class="built_in">this</span>.left = <span class="literal">null</span>;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.right != <span class="literal">null</span> && <span class="built_in">this</span>.right.no == no) {</span><br><span class="line"> <span class="built_in">this</span>.right = <span class="literal">null</span>;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//4.我们就需要向左子树进行递归删除</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.left != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.left.delNode(no);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//5.则应当向右子树进行递归删除</span></span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">this</span>.right != <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.right.delNode(no);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="10-3链式存储"><a href="#10-3链式存储" class="headerlink" title="10.3链式存储"></a>10.3链式存储</h3><p><strong>查找节点</strong>：先对树进行一次遍历，然后找出要找的那个数；因为有三种排序方法，所以查找节点也分为先序查找，中序查找，后序查找；</p>
<p><strong>删除节点</strong>：由于链式存储，不能找到要删的数直接删除，需要找到他的父节点，然后将指向该数设置为null；所以需要一个变量来指向父节点，找到数后，再断开连接。</p>
<p>树：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BinaryTree</span> {</span><br><span class="line"></span><br><span class="line"> TreeNode root;</span><br><span class="line"></span><br><span class="line"> <span class="comment">//设置根节点</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setRoot</span><span class="params">(TreeNode root)</span> {</span><br><span class="line"> <span class="built_in">this</span>.root = root;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//获取根节点</span></span><br><span class="line"> <span class="keyword">public</span> TreeNode <span class="title function_">getRoot</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> root;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">frontShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (root != <span class="literal">null</span>) {</span><br><span class="line"> root.frontShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">middleShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (root != <span class="literal">null</span>) {</span><br><span class="line"> root.middleShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//后序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">afterShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (root != <span class="literal">null</span>) {</span><br><span class="line"> root.afterShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序查找</span></span><br><span class="line"> <span class="keyword">public</span> TreeNode <span class="title function_">frontSearch</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="keyword">return</span> root.frontSearch(i);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除一个子树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delete</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="keyword">if</span> (root.value == i) {</span><br><span class="line"> root = <span class="literal">null</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> root.delete(i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<ul>
<li>节点类</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">TreeNode</span> {</span><br><span class="line"> <span class="comment">//节点的权</span></span><br><span class="line"> <span class="type">int</span> value;</span><br><span class="line"> <span class="comment">//左儿子</span></span><br><span class="line"> TreeNode leftNode;</span><br><span class="line"> <span class="comment">//右儿子</span></span><br><span class="line"> TreeNode rightNode;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">TreeNode</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="built_in">this</span>.value = value;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//设置左儿子</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setLeftNode</span><span class="params">(TreeNode leftNode)</span> {</span><br><span class="line"> <span class="built_in">this</span>.leftNode = leftNode;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//设置右儿子</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setRightNode</span><span class="params">(TreeNode rightNode)</span> {</span><br><span class="line"> <span class="built_in">this</span>.rightNode = rightNode;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">frontShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//先遍历当前节点的值</span></span><br><span class="line"> System.out.print(value + <span class="string">" "</span>);</span><br><span class="line"> <span class="comment">//左节点</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> leftNode.frontShow(); <span class="comment">//递归思想</span></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//右节点</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> rightNode.frontShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">middleShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//左节点</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> leftNode.middleShow(); <span class="comment">//递归思想</span></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//先遍历当前节点的值</span></span><br><span class="line"> System.out.print(value + <span class="string">" "</span>);</span><br><span class="line"> <span class="comment">//右节点</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> rightNode.middleShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//后续遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">afterShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//左节点</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> leftNode.afterShow(); <span class="comment">//递归思想</span></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//右节点</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> rightNode.afterShow();</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//先遍历当前节点的值</span></span><br><span class="line"> System.out.print(value + <span class="string">" "</span>);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序查找</span></span><br><span class="line"> <span class="keyword">public</span> TreeNode <span class="title function_">frontSearch</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="type">TreeNode</span> <span class="variable">target</span> <span class="operator">=</span> <span class="literal">null</span>;</span><br><span class="line"> <span class="comment">//对比当前节点的值</span></span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.value == i) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>;</span><br><span class="line"> <span class="comment">//当前节点不是要查找的节点</span></span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">//查找左儿子</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//查找的话t赋值给target，查不到target还是null</span></span><br><span class="line"> target = leftNode.frontSearch(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果target不为空，说明在左儿子中已经找到</span></span><br><span class="line"> <span class="keyword">if</span> (target != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> target;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果左儿子没有查到，再查找右儿子</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> target = rightNode.frontSearch(i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> target;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除一个子树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delete</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="type">TreeNode</span> <span class="variable">parent</span> <span class="operator">=</span> <span class="built_in">this</span>;</span><br><span class="line"> <span class="comment">//判断左儿子</span></span><br><span class="line"> <span class="keyword">if</span> (parent.leftNode != <span class="literal">null</span> && parent.leftNode.value == i) {</span><br><span class="line"> parent.leftNode = <span class="literal">null</span>;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//判断右儿子</span></span><br><span class="line"> <span class="keyword">if</span> (parent.rightNode != <span class="literal">null</span> && parent.rightNode.value == i) {</span><br><span class="line"> parent.rightNode = <span class="literal">null</span>;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果都不是，递归检查并删除左儿子</span></span><br><span class="line"> parent = leftNode;</span><br><span class="line"> <span class="keyword">if</span> (parent != <span class="literal">null</span>) {</span><br><span class="line"> parent.delete(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//递归检查并删除右儿子</span></span><br><span class="line"> parent = rightNode;</span><br><span class="line"> <span class="keyword">if</span> (parent != <span class="literal">null</span>) {</span><br><span class="line"> parent.delete(i);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>测试</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Demo</span> {</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="comment">//创建一棵树</span></span><br><span class="line"> <span class="type">BinaryTree</span> <span class="variable">binaryTree</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BinaryTree</span>();</span><br><span class="line"> <span class="comment">//创建一个根节点</span></span><br><span class="line"> <span class="type">TreeNode</span> <span class="variable">root</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">TreeNode</span>(<span class="number">1</span>);</span><br><span class="line"> <span class="comment">//把根节点赋给树</span></span><br><span class="line"> binaryTree.setRoot(root);</span><br><span class="line"> <span class="comment">//创建左,右节点</span></span><br><span class="line"> <span class="type">TreeNode</span> <span class="variable">rootLeft</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">TreeNode</span>(<span class="number">2</span>);</span><br><span class="line"> <span class="type">TreeNode</span> <span class="variable">rootRight</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">TreeNode</span>(<span class="number">3</span>);</span><br><span class="line"> <span class="comment">//把新建的节点设置为根节点的子节点</span></span><br><span class="line"> root.setLeftNode(rootLeft);</span><br><span class="line"> root.setRightNode(rootRight);</span><br><span class="line"> <span class="comment">//为第二层的左节点创建两个子节点</span></span><br><span class="line"> rootLeft.setLeftNode(<span class="keyword">new</span> <span class="title class_">TreeNode</span>(<span class="number">4</span>));</span><br><span class="line"> rootLeft.setRightNode(<span class="keyword">new</span> <span class="title class_">TreeNode</span>(<span class="number">5</span>));</span><br><span class="line"> <span class="comment">//为第二层的右节点创建两个子节点</span></span><br><span class="line"> rootRight.setLeftNode(<span class="keyword">new</span> <span class="title class_">TreeNode</span>(<span class="number">6</span>));</span><br><span class="line"> rootRight.setRightNode(<span class="keyword">new</span> <span class="title class_">TreeNode</span>(<span class="number">7</span>));</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序遍历</span></span><br><span class="line"> binaryTree.frontShow(); <span class="comment">//1 2 4 5 3 6 7</span></span><br><span class="line"> System.out.println();</span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> binaryTree.middleShow(); <span class="comment">//4 2 5 1 6 3 7</span></span><br><span class="line"> System.out.println();</span><br><span class="line"> <span class="comment">//后序遍历</span></span><br><span class="line"> binaryTree.afterShow(); <span class="comment">//4 5 2 6 7 3 1</span></span><br><span class="line"> System.out.println();</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序查找</span></span><br><span class="line"> <span class="type">TreeNode</span> <span class="variable">result</span> <span class="operator">=</span> binaryTree.frontSearch(<span class="number">5</span>);</span><br><span class="line"> System.out.println(result); <span class="comment">//binarytree.TreeNode@1b6d3586</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除一个子树</span></span><br><span class="line"> binaryTree.delete(<span class="number">2</span>);</span><br><span class="line"> binaryTree.frontShow(); <span class="comment">//1 3 6 7 ，2和他的子节点被删除了</span></span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="10-4顺序存储的二叉树"><a href="#10-4顺序存储的二叉树" class="headerlink" title="10.4顺序存储的二叉树"></a>10.4顺序存储的二叉树</h3><p><strong>概述</strong>：顺序存储使用数组的形式实现；由于非完全二叉树会导致数组中出现空缺，有的位置不能填上数字，所以顺序存储二叉树通常情况下只考虑<strong>完全二叉树</strong></p>
<p><strong>原理</strong>： 顺序存储在数组中是按照第一层第二层一次往下存储的，遍历方式也有先序遍历、中序遍历、后续遍历</p>
<p><strong>性质</strong>：</p>
<ul>
<li>第n个元素的左子节点是：2*n+1；</li>
<li>第n个元素的右子节点是：2*n+2；</li>
<li>第n个元素的父节点是：（n-1)/2</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ArrayBinaryTree</span> {</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="type">int</span>[] data = {<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">7</span>};</span><br><span class="line"> <span class="type">ArrayBinaryTree</span> <span class="variable">tree</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">ArrayBinaryTree</span>(data);</span><br><span class="line"> <span class="comment">//先序遍历</span></span><br><span class="line"> tree.frontShow(); <span class="comment">//1 2 4 5 3 6 7</span></span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="type">int</span>[] data;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">ArrayBinaryTree</span><span class="params">(<span class="type">int</span>[] data)</span> {</span><br><span class="line"> <span class="built_in">this</span>.data = data;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//重载先序遍历方法，不用每次传参数了,保证每次从头开始</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">frontShow</span><span class="params">()</span> {</span><br><span class="line"> frontShow(<span class="number">0</span>);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">frontShow</span><span class="params">(<span class="type">int</span> index)</span> {</span><br><span class="line"> <span class="keyword">if</span> (data == <span class="literal">null</span> || data.length == <span class="number">0</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//先遍历当前节点的内容</span></span><br><span class="line"> System.out.print(data[index] + <span class="string">" "</span>);</span><br><span class="line"> <span class="comment">//处理左子树：2*index+1</span></span><br><span class="line"> <span class="keyword">if</span> (<span class="number">2</span> * index + <span class="number">1</span> < data.length) {</span><br><span class="line"> frontShow(<span class="number">2</span> * index + <span class="number">1</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//处理右子树：2*index+2</span></span><br><span class="line"> <span class="keyword">if</span> (<span class="number">2</span> * index + <span class="number">2</span> < data.length) {</span><br><span class="line"> frontShow(<span class="number">2</span> * index + <span class="number">2</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="10-5线索二叉树"><a href="#10-5线索二叉树" class="headerlink" title="10.5线索二叉树"></a>10.5线索二叉树</h3><p><strong>为什么使用线索二叉树？</strong></p>
<p>当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点</p>
<p><strong>原理</strong>：n个结点的二叉链表中含有n+1(2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针。</p>
<p><strong>例如</strong>：某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继（这种附加的指针称为”线索”）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ThreadedBinaryTree</span> {</span><br><span class="line"></span><br><span class="line"> ThreadedNode root;</span><br><span class="line"> <span class="comment">//用于临时存储前驱节点</span></span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">pre</span> <span class="operator">=</span> <span class="literal">null</span>;</span><br><span class="line"> </span><br><span class="line"> <span class="comment">//设置根节点</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setRoot</span><span class="params">(ThreadedNode root)</span> {</span><br><span class="line"> <span class="built_in">this</span>.root = root;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序线索化二叉树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">threadNodes</span><span class="params">()</span> {</span><br><span class="line"> threadNodes(root);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">threadNodes</span><span class="params">(ThreadedNode node)</span> {</span><br><span class="line"> <span class="comment">//当前节点如果为null，直接返回</span></span><br><span class="line"> <span class="keyword">if</span> (node == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//处理左子树</span></span><br><span class="line"> threadNodes(node.leftNode);</span><br><span class="line"></span><br><span class="line"> <span class="comment">//处理前驱节点</span></span><br><span class="line"> <span class="keyword">if</span> (node.leftNode == <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//让当前节点的左指针指向前驱节点</span></span><br><span class="line"> node.leftNode = pre;</span><br><span class="line"> <span class="comment">//改变当前节点左指针类型</span></span><br><span class="line"> node.leftType = <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//处理前驱的右指针，如果前驱节点的右指针是null（没有右子树）</span></span><br><span class="line"> <span class="keyword">if</span> (pre != <span class="literal">null</span> && pre.rightNode == <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//让前驱节点的右指针指向当前节点</span></span><br><span class="line"> pre.rightNode = node;</span><br><span class="line"> <span class="comment">//改变前驱节点的右指针类型</span></span><br><span class="line"> pre.rightType = <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//每处理一个节点，当前节点是下一个节点的前驱节点</span></span><br><span class="line"> pre = node;</span><br><span class="line"></span><br><span class="line"> <span class="comment">//处理右子树</span></span><br><span class="line"> threadNodes(node.rightNode);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//遍历线索二叉树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">threadIterate</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//用于临时存储当前遍历节点</span></span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">node</span> <span class="operator">=</span> root;</span><br><span class="line"> <span class="keyword">while</span> (node != <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//循环找到最开始的节点</span></span><br><span class="line"> <span class="keyword">while</span> (node.leftType == <span class="number">0</span>) {</span><br><span class="line"> node = node.leftNode;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//打印当前节点的值</span></span><br><span class="line"> System.out.print(node.value + <span class="string">" "</span>);</span><br><span class="line"> <span class="comment">//如果当前节点的右指针指向的是后继节点，可能后继节点还有后继节点</span></span><br><span class="line"> <span class="keyword">while</span> (node.rightType == <span class="number">1</span>) {</span><br><span class="line"> node = node.rightNode;</span><br><span class="line"> System.out.print(node.value + <span class="string">" "</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//替换遍历的节点</span></span><br><span class="line"> node = node.rightNode;</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//获取根节点</span></span><br><span class="line"> <span class="keyword">public</span> ThreadedNode <span class="title function_">getRoot</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> root;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">frontShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (root != <span class="literal">null</span>) {</span><br><span class="line"> root.frontShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">middleShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (root != <span class="literal">null</span>) {</span><br><span class="line"> root.middleShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//后序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">afterShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (root != <span class="literal">null</span>) {</span><br><span class="line"> root.afterShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序查找</span></span><br><span class="line"> <span class="keyword">public</span> ThreadedNode <span class="title function_">frontSearch</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="keyword">return</span> root.frontSearch(i);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除一个子树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delete</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="keyword">if</span> (root.value == i) {</span><br><span class="line"> root = <span class="literal">null</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> root.delete(i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ThreadedNode</span> {</span><br><span class="line"> <span class="comment">//节点的权</span></span><br><span class="line"> <span class="type">int</span> value;</span><br><span class="line"> <span class="comment">//左儿子</span></span><br><span class="line"> ThreadedNode leftNode;</span><br><span class="line"> <span class="comment">//右儿子</span></span><br><span class="line"> ThreadedNode rightNode;</span><br><span class="line"> <span class="comment">//标识指针类型,1表示指向上一个节点，0</span></span><br><span class="line"> <span class="type">int</span> leftType;</span><br><span class="line"> <span class="type">int</span> rightType;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">ThreadedNode</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="built_in">this</span>.value = value;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//设置左儿子</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setLeftNode</span><span class="params">(ThreadedNode leftNode)</span> {</span><br><span class="line"> <span class="built_in">this</span>.leftNode = leftNode;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//设置右儿子</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setRightNode</span><span class="params">(ThreadedNode rightNode)</span> {</span><br><span class="line"> <span class="built_in">this</span>.rightNode = rightNode;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">frontShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//先遍历当前节点的值</span></span><br><span class="line"> System.out.print(value + <span class="string">" "</span>);</span><br><span class="line"> <span class="comment">//左节点</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> leftNode.frontShow(); <span class="comment">//递归思想</span></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//右节点</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> rightNode.frontShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">middleShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//左节点</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> leftNode.middleShow(); <span class="comment">//递归思想</span></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//先遍历当前节点的值</span></span><br><span class="line"> System.out.print(value + <span class="string">" "</span>);</span><br><span class="line"> <span class="comment">//右节点</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> rightNode.middleShow();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//后续遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">afterShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//左节点</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> leftNode.afterShow(); <span class="comment">//递归思想</span></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//右节点</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> rightNode.afterShow();</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//先遍历当前节点的值</span></span><br><span class="line"> System.out.print(value + <span class="string">" "</span>);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//先序查找</span></span><br><span class="line"> <span class="keyword">public</span> ThreadedNode <span class="title function_">frontSearch</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">target</span> <span class="operator">=</span> <span class="literal">null</span>;</span><br><span class="line"> <span class="comment">//对比当前节点的值</span></span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.value == i) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>;</span><br><span class="line"> <span class="comment">//当前节点不是要查找的节点</span></span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">//查找左儿子</span></span><br><span class="line"> <span class="keyword">if</span> (leftNode != <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//查找的话t赋值给target，查不到target还是null</span></span><br><span class="line"> target = leftNode.frontSearch(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果target不为空，说明在左儿子中已经找到</span></span><br><span class="line"> <span class="keyword">if</span> (target != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> target;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果左儿子没有查到，再查找右儿子</span></span><br><span class="line"> <span class="keyword">if</span> (rightNode != <span class="literal">null</span>) {</span><br><span class="line"> target = rightNode.frontSearch(i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> target;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除一个子树</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delete</span><span class="params">(<span class="type">int</span> i)</span> {</span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">parent</span> <span class="operator">=</span> <span class="built_in">this</span>;</span><br><span class="line"> <span class="comment">//判断左儿子</span></span><br><span class="line"> <span class="keyword">if</span> (parent.leftNode != <span class="literal">null</span> && parent.leftNode.value == i) {</span><br><span class="line"> parent.leftNode = <span class="literal">null</span>;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//判断右儿子</span></span><br><span class="line"> <span class="keyword">if</span> (parent.rightNode != <span class="literal">null</span> && parent.rightNode.value == i) {</span><br><span class="line"> parent.rightNode = <span class="literal">null</span>;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果都不是，递归检查并删除左儿子</span></span><br><span class="line"> parent = leftNode;</span><br><span class="line"> <span class="keyword">if</span> (parent != <span class="literal">null</span>) {</span><br><span class="line"> parent.delete(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//递归检查并删除右儿子</span></span><br><span class="line"> parent = rightNode;</span><br><span class="line"> <span class="keyword">if</span> (parent != <span class="literal">null</span>) {</span><br><span class="line"> parent.delete(i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Demo</span> {</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="comment">//创建一棵树</span></span><br><span class="line"> <span class="type">ThreadedBinaryTree</span> <span class="variable">binaryTree</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">ThreadedBinaryTree</span>();</span><br><span class="line"> <span class="comment">//创建一个根节点</span></span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">root</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">ThreadedNode</span>(<span class="number">1</span>);</span><br><span class="line"> <span class="comment">//把根节点赋给树</span></span><br><span class="line"> binaryTree.setRoot(root);</span><br><span class="line"> <span class="comment">//创建左,右节点</span></span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">rootLeft</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">ThreadedNode</span>(<span class="number">2</span>);</span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">rootRight</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">ThreadedNode</span>(<span class="number">3</span>);</span><br><span class="line"> <span class="comment">//把新建的节点设置为根节点的子节点</span></span><br><span class="line"> root.setLeftNode(rootLeft);</span><br><span class="line"> root.setRightNode(rootRight);</span><br><span class="line"> <span class="comment">//为第二层的左节点创建两个子节点</span></span><br><span class="line"> rootLeft.setLeftNode(<span class="keyword">new</span> <span class="title class_">ThreadedNode</span>(<span class="number">4</span>));</span><br><span class="line"> <span class="type">ThreadedNode</span> <span class="variable">fiveNode</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">ThreadedNode</span>(<span class="number">5</span>);</span><br><span class="line"> rootLeft.setRightNode(fiveNode);</span><br><span class="line"> <span class="comment">//为第二层的右节点创建两个子节点</span></span><br><span class="line"> rootRight.setLeftNode(<span class="keyword">new</span> <span class="title class_">ThreadedNode</span>(<span class="number">6</span>));</span><br><span class="line"> rootRight.setRightNode(<span class="keyword">new</span> <span class="title class_">ThreadedNode</span>(<span class="number">7</span>));</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> binaryTree.middleShow(); <span class="comment">//4 2 5 1 6 3 7</span></span><br><span class="line"> System.out.println();</span><br><span class="line"> <span class="comment">//中序线索化二叉树</span></span><br><span class="line"> binaryTree.threadNodes();</span><br><span class="line"><span class="comment">// //获取5的后继节点</span></span><br><span class="line"><span class="comment">// ThreadedNode afterFive = fiveNode.rightNode;</span></span><br><span class="line"><span class="comment">// System.out.println(afterFive.value); //1</span></span><br><span class="line"> binaryTree.threadIterate(); <span class="comment">//4 2 5 1 6 3 7</span></span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="10-6二叉排序树"><a href="#10-6二叉排序树" class="headerlink" title="10.6二叉排序树"></a>10.6二叉排序树</h3><p><strong>概述</strong>：二叉排序树（Binary Sort Tree）也叫二叉查找树或者是一颗空树，对于二叉树中的任何一个非叶子节点，要求左子节点比当前节点值小，右子节点比当前节点值大</p>
<p><strong>特点</strong>：</p>
<ul>
<li>查找性能与插入删除性能都适中还不错</li>
<li>中序遍历的结果刚好是从大到小</li>
</ul>
<p><strong>创建二叉排序树原理</strong>：其实就是不断地插入节点，然后进行比较。</p>
<p><strong>删除节点</strong></p>
<ul>
<li>删除叶子节点，只需要找到父节点，将父节点与他的连接断开即可</li>
<li>删除有一个子节点的就需要将他的子节点换到他现在的位置</li>
<li>删除有两个子节点的节点，需要使用他的前驱节点或者后继节点进行替换，就是左子树最右下方的数（最大的那个）或右子树最左边的树（最小的数）；即离节点值最接近的值；（还要注解要去判断这个值有没有右节点，有就要将右节点移上来）</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BinarySortTree</span> {</span><br><span class="line"> Node root;</span><br><span class="line"></span><br><span class="line"> <span class="comment">//添加节点</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">add</span><span class="params">(Node node)</span> {</span><br><span class="line"> <span class="comment">//如果是一颗空树</span></span><br><span class="line"> <span class="keyword">if</span> (root == <span class="literal">null</span>) {</span><br><span class="line"> root = node;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> root.add(node);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">middleShow</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (root != <span class="literal">null</span>) {</span><br><span class="line"> root.middleShow(root);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找节点</span></span><br><span class="line"> <span class="keyword">public</span> Node <span class="title function_">search</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="keyword">if</span> (root == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> root.search(value);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找父节点</span></span><br><span class="line"> <span class="keyword">public</span> Node <span class="title function_">searchParent</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="keyword">if</span> (root == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> root.searchParent(value);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除节点</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delete</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="keyword">if</span> (root == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">//找到这个节点</span></span><br><span class="line"> <span class="type">Node</span> <span class="variable">target</span> <span class="operator">=</span> search(value);</span><br><span class="line"> <span class="comment">//如果没有这个节点</span></span><br><span class="line"> <span class="keyword">if</span> (target == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//找到他的父节点</span></span><br><span class="line"> <span class="type">Node</span> <span class="variable">parent</span> <span class="operator">=</span> searchParent(value);</span><br><span class="line"> <span class="comment">//要删除的节点是叶子节点</span></span><br><span class="line"> <span class="keyword">if</span> (target.left == <span class="literal">null</span> && target.left == <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//要删除的节点是父节点的左子节点</span></span><br><span class="line"> <span class="keyword">if</span> (parent.left.value == value) {</span><br><span class="line"> parent.left = <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//要删除的节点是父节点的右子节点</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> parent.right = <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//要删除的节点有两个子节点的情况</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (target.left != <span class="literal">null</span> && target.right != <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//删除右子树中值最小的节点，并且获取到值</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">min</span> <span class="operator">=</span> deletMin(target.right);</span><br><span class="line"> <span class="comment">//替换目标节点中的值</span></span><br><span class="line"> target.value = min;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//要删除的节点有一个左子节点或右子节点</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">//有左子节点</span></span><br><span class="line"> <span class="keyword">if</span> (target.left != <span class="literal">null</span>) {</span><br><span class="line"> <span class="comment">//要删除的节点是父节点的左子节点</span></span><br><span class="line"> <span class="keyword">if</span> (parent.left.value == value) {</span><br><span class="line"> parent.left = target.left;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//要删除的节点是父节点的右子节点</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> parent.right = target.left;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//有右子节点</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">//要删除的节点是父节点的左子节点</span></span><br><span class="line"> <span class="keyword">if</span> (parent.left.value == value) {</span><br><span class="line"> parent.left = target.right;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//要删除的节点是父节点的右子节点</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> parent.right = target.right;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除一棵树中最小的节点</span></span><br><span class="line"> <span class="keyword">private</span> <span class="type">int</span> <span class="title function_">deletMin</span><span class="params">(Node node)</span> {</span><br><span class="line"> <span class="type">Node</span> <span class="variable">target</span> <span class="operator">=</span> node;</span><br><span class="line"> <span class="comment">//递归向左找最小值</span></span><br><span class="line"> <span class="keyword">while</span> (target.left != <span class="literal">null</span>) {</span><br><span class="line"> target = target.left;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//删除最小的节点</span></span><br><span class="line"> delete(target.value);</span><br><span class="line"> <span class="keyword">return</span> target.value;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Node</span> {</span><br><span class="line"> <span class="type">int</span> value;</span><br><span class="line"> Node left;</span><br><span class="line"> Node right;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="built_in">this</span>.value = value;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//向子树中添加节点</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">add</span><span class="params">(Node node)</span> {</span><br><span class="line"> <span class="keyword">if</span> (node == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">/*判断传入的节点的值比当前紫薯的根节点的值大还是小*/</span></span><br><span class="line"> <span class="comment">//添加的节点比当前节点更小(传给左节点）</span></span><br><span class="line"> <span class="keyword">if</span> (node.value < <span class="built_in">this</span>.value) {</span><br><span class="line"> <span class="comment">//如果左节点为空</span></span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.left == <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.left = node;</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果不为空</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="built_in">this</span>.left.add(node);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//添加的节点比当前节点更大(传给右节点）</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.right == <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.right = node;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="built_in">this</span>.right.add(node);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历二叉排序树，结果刚好是从小到大</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">middleShow</span><span class="params">(Node node)</span> {</span><br><span class="line"> <span class="keyword">if</span> (node == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> middleShow(node.left);</span><br><span class="line"> System.out.print(node.value + <span class="string">" "</span>);</span><br><span class="line"> middleShow(node.right);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找节点</span></span><br><span class="line"> <span class="keyword">public</span> Node <span class="title function_">search</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.value == value) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>;</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (value < <span class="built_in">this</span>.value) {</span><br><span class="line"> <span class="keyword">if</span> (left == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> left.search(value);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (right == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> right.search(value);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找父节点</span></span><br><span class="line"> <span class="keyword">public</span> Node <span class="title function_">searchParent</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="keyword">if</span> ((<span class="built_in">this</span>.left != <span class="literal">null</span> && <span class="built_in">this</span>.left.value == value) || (<span class="built_in">this</span>.right != <span class="literal">null</span> && <span class="built_in">this</span>.right.value == value)) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.value > value && <span class="built_in">this</span>.left != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>.left.searchParent(value);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">this</span>.value < value && <span class="built_in">this</span>.right != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>.right.searchParent(value);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Demo</span> {</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="type">int</span>[] arr = {<span class="number">8</span>, <span class="number">3</span>, <span class="number">10</span>, <span class="number">1</span>, <span class="number">6</span>, <span class="number">14</span>, <span class="number">4</span>, <span class="number">7</span>, <span class="number">13</span>};</span><br><span class="line"> <span class="comment">//创建一颗二叉排序树</span></span><br><span class="line"> <span class="type">BinarySortTree</span> <span class="variable">bst</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BinarySortTree</span>();</span><br><span class="line"> <span class="comment">//循环添加</span></span><br><span class="line"><span class="comment">/* for(int i=0;i< arr.length;i++) {</span></span><br><span class="line"><span class="comment"> bst.add(new Node(arr[i]));</span></span><br><span class="line"><span class="comment"> }*/</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i : arr) {</span><br><span class="line"> bst.add(<span class="keyword">new</span> <span class="title class_">Node</span>(i));</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历</span></span><br><span class="line"> bst.middleShow(); <span class="comment">//1 3 4 6 7 8 10 13 14</span></span><br><span class="line"> System.out.println();</span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找节点</span></span><br><span class="line"> <span class="type">Node</span> <span class="variable">node</span> <span class="operator">=</span> bst.search(<span class="number">10</span>);</span><br><span class="line"> System.out.println(node.value);<span class="comment">//10</span></span><br><span class="line"></span><br><span class="line"> <span class="type">Node</span> <span class="variable">node2</span> <span class="operator">=</span> bst.search(<span class="number">20</span>);</span><br><span class="line"> System.out.println(node2); <span class="comment">//null</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找父节点</span></span><br><span class="line"> <span class="type">Node</span> <span class="variable">node3</span> <span class="operator">=</span> bst.searchParent(<span class="number">1</span>);</span><br><span class="line"> <span class="type">Node</span> <span class="variable">node4</span> <span class="operator">=</span> bst.searchParent(<span class="number">14</span>);</span><br><span class="line"> System.out.println(node3.value); <span class="comment">//3</span></span><br><span class="line"> System.out.println(node4.value); <span class="comment">//10</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除叶子节点</span></span><br><span class="line"><span class="comment">// bst.delete(13);</span></span><br><span class="line"><span class="comment">// bst.middleShow(); //1 3 4 6 7 8 10 14</span></span><br><span class="line"><span class="comment">// System.out.println();</span></span><br><span class="line"><span class="comment">// //删除只有一个子节点的节点</span></span><br><span class="line"><span class="comment">// bst.delete(10);</span></span><br><span class="line"><span class="comment">// bst.middleShow(); //1 3 4 6 7 8 ；10和14都没了</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">//删除有两个子节点的节点</span></span><br><span class="line"> bst.delete(<span class="number">3</span>);</span><br><span class="line"> bst.middleShow(); <span class="comment">//1 4 6 7 8 10 13 14</span></span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="10-7平衡二叉树"><a href="#10-7平衡二叉树" class="headerlink" title="10.7平衡二叉树"></a>10.7平衡二叉树</h3><p>平衡二叉树（Balanced Binary Tree）又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在<code>O(logN)</code>。但是频繁旋转会使插入和删除牺牲掉<code>O(logN)</code>左右的时间，不过相对二叉查找树来说，时间上稳定了很多。 </p>
<p><strong>平衡因子 BF</strong></p>
<ul>
<li>定义：左子树和右子树高度差</li>
<li>计算：<code>左子树高度 - 右子树高度的值</code></li>
<li>别名：简称 BF（Balance Factor）</li>
<li>一般来说 BF 的绝对值大于 1，,平衡树二叉树就失衡，需要旋转纠正</li>
</ul>
<p><strong>最小不平衡子树</strong></p>
<ul>
<li>距离插入节点最近的，并且 BF 的绝对值大于 1 的节点为根节点的子树。</li>
<li>旋转纠正只需要纠正最小不平衡子树即可</li>
</ul>
<h4 id="旋转方式"><a href="#旋转方式" class="headerlink" title="旋转方式"></a>旋转方式</h4><p><strong>2 种旋转方式</strong>:</p>
<p>左旋 :</p>
<ul>
<li>旧根节点为新根节点的左子树</li>
<li>新根节点的左子树（如果存在）为旧根节点的右子树</li>
</ul>
<p>右旋：</p>
<ul>
<li>旧根节点为新根节点的右子树</li>
<li>新根节点的右子树（如果存在）为旧根节点的左子树</li>
</ul>
<p><strong>4 种旋转纠正类型</strong>：</p>
<ul>
<li>左左型：插入左孩子的左子树，右旋</li>
<li>右右型：插入右孩子的右子树，左旋</li>
<li>左右型：插入左孩子的右子树，先左旋，再右旋</li>
<li>右左型：插入右孩子的左子树，先右旋，再左旋</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Node</span> {</span><br><span class="line"> <span class="type">int</span> value;</span><br><span class="line"> Node left;</span><br><span class="line"> Node right;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="built_in">this</span>.value = value;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//获取当前节点高度</span></span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">height</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">return</span> Math.max(left == <span class="literal">null</span> ? <span class="number">0</span> : left.height(), right == <span class="literal">null</span> ? <span class="number">0</span> : right.height()) + <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//获取左子树高度</span></span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">leftHeight</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (left == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> left.height();</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//获取右子树高度</span></span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">rightHeight</span><span class="params">()</span> {</span><br><span class="line"> <span class="keyword">if</span> (right == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> right.height();</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"> <span class="comment">//向子树中添加节点</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">add</span><span class="params">(Node node)</span> {</span><br><span class="line"> <span class="keyword">if</span> (node == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">/*判断传入的节点的值比当前紫薯的根节点的值大还是小*/</span></span><br><span class="line"> <span class="comment">//添加的节点比当前节点更小(传给左节点）</span></span><br><span class="line"> <span class="keyword">if</span> (node.value < <span class="built_in">this</span>.value) {</span><br><span class="line"> <span class="comment">//如果左节点为空</span></span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.left == <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.left = node;</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//如果不为空</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="built_in">this</span>.left.add(node);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//添加的节点比当前节点更大(传给右节点）</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.right == <span class="literal">null</span>) {</span><br><span class="line"> <span class="built_in">this</span>.right = node;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="built_in">this</span>.right.add(node);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//查询是否平衡</span></span><br><span class="line"> <span class="comment">//右旋转</span></span><br><span class="line"> <span class="keyword">if</span> (leftHeight() - rightHeight() >= <span class="number">2</span>) {</span><br><span class="line"> <span class="comment">//双旋转，当左子树左边高度小于左子树右边高度时</span></span><br><span class="line"> <span class="keyword">if</span> (left != <span class="literal">null</span> && left.leftHeight() < left.rightHeight()) {</span><br><span class="line"> <span class="comment">//左子树先进行左旋转</span></span><br><span class="line"> left.leftRotate();</span><br><span class="line"> <span class="comment">//整体进行右旋转</span></span><br><span class="line"> rightRotate();</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//单旋转</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> rightRotate();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//左旋转</span></span><br><span class="line"> <span class="keyword">if</span> (leftHeight() - rightHeight() <= -<span class="number">2</span>) {</span><br><span class="line"> <span class="comment">//双旋转</span></span><br><span class="line"> <span class="keyword">if</span> (right != <span class="literal">null</span> && right.rightHeight() < right.leftHeight()) {</span><br><span class="line"> right.rightRotate();</span><br><span class="line"> leftRotate();</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//单旋转</span></span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> leftRotate();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//右旋转</span></span><br><span class="line"> <span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">rightRotate</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//创建一个新的节点，值等于当前节点的值</span></span><br><span class="line"> <span class="type">Node</span> <span class="variable">newRight</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(value);</span><br><span class="line"> <span class="comment">//把新节点的右子树设置为当前节点的右子树</span></span><br><span class="line"> newRight.right = right;</span><br><span class="line"> <span class="comment">//把新节点的左子树设置为当前节点的左子树的右子树</span></span><br><span class="line"> newRight.left = left.right;</span><br><span class="line"> <span class="comment">//把当前节点的值换位左子节点的值</span></span><br><span class="line"> value = left.value;</span><br><span class="line"> <span class="comment">//把当前节点的左子树设置为左子树的左子树</span></span><br><span class="line"> left = left.left;</span><br><span class="line"> <span class="comment">//把当前节点设置为新节点</span></span><br><span class="line"> right = newRight;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//左旋转</span></span><br><span class="line"> <span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">leftRotate</span><span class="params">()</span> {</span><br><span class="line"> <span class="comment">//创建一个新的节点，值等于当前节点的值</span></span><br><span class="line"> <span class="type">Node</span> <span class="variable">newLeft</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(value);</span><br><span class="line"> <span class="comment">//把新节点的左子树设置为当前节点的左子树</span></span><br><span class="line"> newLeft.left = left;</span><br><span class="line"> <span class="comment">//把新节点的右子树设置为当前节点的右子树的左子树</span></span><br><span class="line"> newLeft.right = right.left;</span><br><span class="line"> <span class="comment">//把当前节点的值换位右子节点的值</span></span><br><span class="line"> value = right.value;</span><br><span class="line"> <span class="comment">//把当前节点的右子树设置为右子树的右子树</span></span><br><span class="line"> right = right.right;</span><br><span class="line"> <span class="comment">//把当前节点设置为新节点</span></span><br><span class="line"> left = newLeft;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//中序遍历二叉排序树，结果刚好是从小到大</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">middleShow</span><span class="params">(Node node)</span> {</span><br><span class="line"> <span class="keyword">if</span> (node == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> middleShow(node.left);</span><br><span class="line"> System.out.print(node.value + <span class="string">" "</span>);</span><br><span class="line"> middleShow(node.right);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找节点</span></span><br><span class="line"> <span class="keyword">public</span> Node <span class="title function_">search</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.value == value) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>;</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (value < <span class="built_in">this</span>.value) {</span><br><span class="line"> <span class="keyword">if</span> (left == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> left.search(value);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (right == <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> right.search(value);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//查找父节点</span></span><br><span class="line"> <span class="keyword">public</span> Node <span class="title function_">searchParent</span><span class="params">(<span class="type">int</span> value)</span> {</span><br><span class="line"> <span class="keyword">if</span> ((<span class="built_in">this</span>.left != <span class="literal">null</span> && <span class="built_in">this</span>.left.value == value) || (<span class="built_in">this</span>.right != <span class="literal">null</span> && <span class="built_in">this</span>.right.value == value)) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">this</span>.value > value && <span class="built_in">this</span>.left != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>.left.searchParent(value);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">this</span>.value < value && <span class="built_in">this</span>.right != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">this</span>.right.searchParent(value);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Demo</span> {</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="type">int</span>[] arr = {<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>};</span><br><span class="line"> <span class="comment">//创建一颗二叉排序树</span></span><br><span class="line"> <span class="type">BinarySortTree</span> <span class="variable">bst</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BinarySortTree</span>();</span><br><span class="line"> <span class="comment">//循环添加</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i : arr) {</span><br><span class="line"> bst.add(<span class="keyword">new</span> <span class="title class_">Node</span>(i));</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//查看高度</span></span><br><span class="line"> System.out.println(bst.root.height()); <span class="comment">//3</span></span><br><span class="line"> <span class="comment">//查看节点值</span></span><br><span class="line"> System.out.println(bst.root.value); <span class="comment">//根节点为4</span></span><br><span class="line"> System.out.println(bst.root.left.value); <span class="comment">//左子节点为2</span></span><br><span class="line"> System.out.println(bst.root.right.value); <span class="comment">//右子节点为5</span></span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__title"><span class="post-copyright-info"><h>数据结构与算法2</h></span></div><div class="post-copyright__type"><span class="post-copyright-info"><a href="https://www.blog.909111.xyz/posts/ba945d0d.html">https://www.blog.909111.xyz/posts/ba945d0d.html</a></span></div><div class="post-copyright-m"><div class="post-copyright-m-info"><div class="post-copyright-a"><h>作者</h><div class="post-copyright-cc-info"><h>Miaow.Y.Hu🥝</h></div></div><div class="post-copyright-c"><h>发布于</h><div class="post-copyright-cc-info"><h>2023-11-09</h></div></div><div class="post-copyright-u"><h>更新于</h><div class="post-copyright-cc-info"><h>2023-11-09</h></div></div><div class="post-copyright-c"><h>许可协议</h><div class="post-copyright-cc-info"><a class="icon" rel="noopener" target="_blank" title="Creative Commons" href="https://creativecommons.org/"><i class="fab fa-creative-commons"></i></a><a rel="noopener" target="_blank" title="CC BY-NC-SA 4.0" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a></div></div></div></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/java%E5%AD%A6%E4%B9%A0/"><div class="tags-punctuation"><svg class="faa-tada icon" style="height:1.1em;width:1.1em;fill:currentColor;position:relative;top:2px;margin-right:3px" aria-hidden="true"><use xlink:href="#icon-sekuaibiaoqian"></use></svg></div>java学习</a></div></div><link rel="stylesheet" href="/css/coin.css" media="defer" onload="this.media='all'"/><div class="post-reward"><button class="tip-button reward-button"><span class="tip-button__text">投喂作者</span><div class="coin-wrapper"><div class="coin"><div class="coin__middle"></div><div class="coin__back"></div><div class="coin__front"></div></div></div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221535811.png" target="_blank"><img class="post-qr-code-img" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221535811.png" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221544615.png" target="_blank"><img class="post-qr-code-img" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221544615.png" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></button></div><audio id="coinAudio" src="https://npm.elemecdn.com/[email protected]/audio/aowu.m4a"></audio><script defer="defer" src="/js/coin.js"></script><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/0.html"><img class="prev-cover" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531409.jpg" onerror="onerror=null;src='/assets/r2.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">pdf阅读器</div></div></a></div><div class="next-post pull-right"><a href="/posts/7593676.html"><img class="next-cover" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531409.jpg" onerror="onerror=null;src='/assets/r2.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">系统架构师上午题知识点</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/posts/e45e7a2d.html" title="JavaJUC学习篇"><img class="cover" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531380.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="fas fa-history fa-fw"></i> 2024-04-22</div><div class="title">JavaJUC学习篇</div></div></a></div><div><a href="/posts/f7912a82.html" title="力扣刷题"><img class="cover" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="fas fa-history fa-fw"></i> 2023-05-09</div><div class="title">力扣刷题</div></div></a></div><div><a href="/posts/135de23b.html" title="牛客刷题笔记1"><img class="cover" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="fas fa-history fa-fw"></i> 2023-04-21</div><div class="title">牛客刷题笔记1</div></div></a></div><div><a href="/posts/4b0178e0.html" title="数据结构与算法"><img class="cover" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="fas fa-history fa-fw"></i> 2023-11-09</div><div class="title">数据结构与算法</div></div></a></div><div><a href="/posts/ac133265.html" title="线程池学习"><img class="cover" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="fas fa-history fa-fw"></i> 2024-04-02</div><div class="title">线程池学习</div></div></a></div></div></div><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div id="twikoo-wrap"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><svg class="meta_icon" style="width:22px;height:22px;position:relative;top:5px"><use xlink:href="#icon-mulu1"></use></svg><span style="font-weight:bold">目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95"><span class="toc-text">数据结构与算法</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#9-%E5%93%88%E5%B8%8C%E8%A1%A8"><span class="toc-text">9 哈希表</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#10-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F"><span class="toc-text">10.数据结构的存储方式</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#10-1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">10.1二叉树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#10-2-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%A6%82%E7%8E%87%E5%92%8C%E5%B8%B8%E7%94%A8%E6%9C%AF%E8%AF%AD"><span class="toc-text">10.2 二叉树的概率和常用术语</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%81%8D%E5%8E%86%E5%92%8C%E8%8A%82%E7%82%B9%E5%88%A0%E9%99%A4"><span class="toc-text">遍历和节点删除</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#10-3%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8"><span class="toc-text">10.3链式存储</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#10-4%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">10.4顺序存储的二叉树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#10-5%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">10.5线索二叉树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#10-6%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91"><span class="toc-text">10.6二叉排序树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#10-7%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">10.7平衡二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%97%8B%E8%BD%AC%E6%96%B9%E5%BC%8F"><span class="toc-text">旋转方式</span></a></li></ol></li></ol></li></ol></li></ol></div></div></div></div></main><footer id="footer" style="background-color: transparent;"><div id="footer-wrap"><div id="ft"><div class="ft-item-1"><div class="t-top"><div class="t-t-l"><p class="ft-t t-l-t">格言🧬</p><div class="bg-ad"><div>再看看那个光点，它就在这里，这是家园，这是我们 —— 你所爱的每一个人，你认识的一个人，你听说过的每一个人，曾经有过的每一个人，都在它上面度过他们的一生✨</div><div class="btn-xz-box"><a class="btn-xz" target="_blank" rel="noopener" href="https://stellarium.org/">点击开启星辰之旅</a></div></div></div><div class="t-t-r"><p class="ft-t t-l-t">猜你想看💡</p><ul class="ft-links"><li><a href="/box/nav/">网址导航</a></li><li><a href="/social/link/">我的朋友</a><a href="/comments/">留点什么</a></li><li><a href="/personal/about/">关于作者</a><a href="/archives/">文章归档</a></li><li><a href="/categories/">文章分类</a><a href="/tags/">文章标签</a></li><li><a href="/box/gallery/">我的画廊</a></li></ul></div></div></div><div class="ft-item-2"><p class="ft-t">推荐友链⌛</p><div class="ft-img-group"><div class="img-group-item"><a href="javascript:void(0)" title="广告位招租"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://lskypro.acozycotage.net/LightPicture/2022/12/65307a5828af6790.webp" alt=""/></a></div><div class="img-group-item"><a href="javascript:void(0)" title="广告位招租"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://lskypro.acozycotage.net/LightPicture/2022/12/65307a5828af6790.webp" alt=""/></a></div><div class="img-group-item"><a href="javascript:void(0)" title="广告位招租"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://lskypro.acozycotage.net/LightPicture/2022/12/65307a5828af6790.webp" alt=""/></a></div><div class="img-group-item"><a href="javascript:void(0)" title="广告位招租"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://lskypro.acozycotage.net/LightPicture/2022/12/65307a5828af6790.webp" alt=""/></a></div><div class="img-group-item"><a href="javascript:void(0)" title="广告位招租"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://lskypro.acozycotage.net/LightPicture/2022/12/65307a5828af6790.webp" alt=""/></a></div><div class="img-group-item"><a href="javascript:void(0)" title="广告位招租"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://lskypro.acozycotage.net/LightPicture/2022/12/65307a5828af6790.webp" alt=""/></a></div><div class="img-group-item"><a href="javascript:void(0)" title="广告位招租"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://lskypro.acozycotage.net/LightPicture/2022/12/65307a5828af6790.webp" alt=""/></a></div></div></div></div><div class="copyright"><span><b>©2023-2024</b></span><span><b> By Miaow.Y.Hu🥝</b></span></div><div class="footer_custom_text">我希望你能每一天都过得快乐，并且每一天都有收获！！！</div><div id="workboard"></div><p id="ghbdages"><a class="github-badge" target="_blank" href="https://hexo.io/" style="margin-inline:5px" title="博客框架为Hexo_v6.3.0"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://sourcebucket.s3.ladydaily.com/badge/Frame-Hexo-blue.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://butterfly.js.org/" style="margin-inline:5px" title="主题版本Butterfly_v4.3.1"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://sourcebucket.s3.ladydaily.com/badge/Theme-Butterfly-6513df.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://vercel.com/" style="margin-inline:5px" title="本站采用多线部署，主线路托管于Vercel"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://sourcebucket.s3.ladydaily.com/badge/Hosted-Vercel-brightgreen.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://user.51.la/" style="margin-inline:5px" title="本站数据分析得益于51la技术支持"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://sourcebucket.s3.ladydaily.com/badge/Analytics-51la-3db1eb.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://bitiful.dogecast.com/buckets" style="margin-inline:5px" title="本网站经Service Worker分流至缤纷云对象存储"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src=" https://sourcebucket.s3.ladydaily.com/badge/Bucket-缤纷云-9c62da.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://www.netdun.net/" style="margin-inline:5px" title="本站使用网盾星球提供CDN加速与防护"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://sourcebucket.s3.ladydaily.com/badge/CDN-网盾星球-fff2cc.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://github.com/" style="margin-inline:5px" title="本网站源码由Github提供存储仓库"><img src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src=" https://sourcebucket.s3.ladydaily.com/badge/Source-Github-d021d6.svg" alt=""/></a></p></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><a class="icon-V hidden" onclick="switchNightMode()" title="浅色和深色模式转换"><svg width="25" height="25" viewBox="0 0 1024 1024"><use id="modeicon" xlink:href="#icon-moon"></use></svg></a><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button><button class="share" type="button" title="右键模式" onclick="changeMouseMode()"><i class="fas fa-mouse"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog right_side"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button class="share" type="button" title="分享链接" onclick="share()"><i class="fas fa-share-nodes"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i><span id="percent">0<span>%</span></span></button><button id="go-down" type="button" title="直达底部" onclick="btf.scrollToDest(document.body.scrollHeight, 500)"><i class="fas fa-arrow-down"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div class="js-pjax" id="rightMenu"><div class="rightMenu-group rightMenu-small"><a class="rightMenu-item" href="javascript:window.history.back();"><i class="fa fa-arrow-left"></i></a><a class="rightMenu-item" href="javascript:window.history.forward();"><i class="fa fa-arrow-right"></i></a><a class="rightMenu-item" href="javascript:window.location.reload();"><i class="fa fa-refresh"></i></a><a class="rightMenu-item" href="javascript:rmf.scrollToTop();"><i class="fa fa-arrow-up"></i></a></div><div class="rightMenu-group rightMenu-line hide" id="menu-text"><a class="rightMenu-item" href="javascript:rmf.copySelect();"><i class="fa fa-copy"></i><span>复制</span></a><a class="rightMenu-item" href="javascript:window.open("https://www.baidu.com/s?wd="+window.getSelection().toString());window.location.reload();"><i class="fa fa-search"></i><span>百度搜索</span></a></div><div class="rightMenu-group rightMenu-line hide" id="menu-too"><a class="rightMenu-item" href="javascript:window.open(window.getSelection().toString());window.location.reload();"><i class="fa fa-link"></i><span>转到链接</span></a></div><div class="rightMenu-group rightMenu-line hide" id="menu-paste"><a class="rightMenu-item" href="javascript:rmf.paste()"><i class="fa fa-copy"></i><span>粘贴</span></a></div><div class="rightMenu-group rightMenu-line hide" id="menu-post"><a class="rightMenu-item" href="#post-comment"><i class="fas fa-comment"></i><span>空降评论</span></a><a class="rightMenu-item" href="javascript:rmf.copyWordsLink()"><i class="fa fa-link"></i><span>复制本文地址</span></a></div><div class="rightMenu-group rightMenu-line hide" id="menu-to"><a class="rightMenu-item" href="javascript:rmf.openWithNewTab()"><i class="fa fa-window-restore"></i><span>新窗口打开</span></a><a class="rightMenu-item" id="menu-too" href="javascript:rmf.open()"><i class="fa fa-link"></i><span>转到链接</span></a><a class="rightMenu-item" href="javascript:rmf.copyLink()"><i class="fa fa-copy"></i><span>复制链接</span></a></div><div class="rightMenu-group rightMenu-line hide" id="menu-img"><a class="rightMenu-item" href="javascript:rmf.saveAs()"><i class="fa fa-download"></i><span>保存图片</span></a><a class="rightMenu-item" href="javascript:rmf.openWithNewTab()"><i class="fa fa-window-restore"></i><span>在新窗口打开</span></a><a class="rightMenu-item" href="javascript:rmf.copyLink()"><i class="fa fa-copy"></i><span>复制图片链接</span></a></div><div class="rightMenu-group rightMenu-line"><a class="rightMenu-item" href="javascript:randomPost()"><i class="fa fa-paper-plane"></i><span>随便逛逛</span></a><a class="rightMenu-item" href="javascript:switchNightMode();"><i class="fa fa-moon"></i><span>昼夜切换</span></a><a class="rightMenu-item" href="/personal/about/"><i class="fa fa-info-circle"></i><span>关于博客</span></a><a class="rightMenu-item" href="javascript:toggleWinbox();"><i class="fas fa-cog"></i><span>美化设置</span></a><a class="rightMenu-item" href="javascript:rmf.fullScreen();"><i class="fas fa-expand"></i><span>切换全屏</span></a><a class="rightMenu-item" href="javascript:window.print();"><i class="fa-solid fa-print"></i><span>打印页面</span></a></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.staticfile.org/fancyapps-ui/4.0.31/fancybox.umd.min.js"></script><script src="https://lf3-cdn-tos.bytecdntp.com/cdn/expire-1-M/instant.page/5.1.0/instantpage.min.js" type="module"></script><script src="https://lf3-cdn-tos.bytecdntp.com/cdn/expire-1-M/vanilla-lazyload/17.3.1/lazyload.iife.min.js"></script><script src="/js/search/local-search.js"></script><script async="async">var preloader = {
endLoading: () => {
document.body.style.overflow = 'auto';
document.getElementById('loading-box').classList.add("loaded")
},
initLoading: () => {
document.body.style.overflow = '';
document.getElementById('loading-box').classList.remove("loaded")
}
}
window.addEventListener('load',preloader.endLoading())
setTimeout(function(){preloader.endLoading();}, 5000);
document.getElementById('loading-box').addEventListener('click',()=> {preloader.endLoading()})</script><div class="js-pjax"><script>if (!window.MathJax) {
window.MathJax = {
tex: {
inlineMath: [ ['$','$'], ["\\(","\\)"]],
tags: 'ams'
},
chtml: {
scale: 1.2
},
options: {
renderActions: {
findScript: [10, doc => {
for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
const display = !!node.type.match(/; *mode=display/)
const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
const text = document.createTextNode('')
node.parentNode.replaceChild(text, node)
math.start = {node: text, delim: '', n: 0}
math.end = {node: text, delim: '', n: 0}
doc.math.push(math)
}
}, ''],
insertScript: [200, () => {
document.querySelectorAll('mjx-container:not\([display]\)').forEach(node => {
const target = node.parentNode
if (target.nodeName.toLowerCase() === 'li') {
target.parentNode.classList.add('has-jax')
} else {
target.classList.add('has-jax')
}
});
}, '', false]
}
}
}
const script = document.createElement('script')
script.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.2/es5/tex-mml-chtml.min.js'
script.id = 'MathJax-script'
script.async = true
document.head.appendChild(script)
} else {
MathJax.startup.document.state(0)
MathJax.texReset()
MathJax.typeset()
}</script><script>(()=>{
const init = () => {
twikoo.init(Object.assign({
el: '#twikoo-wrap',
envId: 'https://twikoo.909111.xyz/',
region: '',
onCommentLoaded: function () {
btf.loadLightbox(document.querySelectorAll('#twikoo .tk-content img:not(.tk-owo-emotion)'))
}
}, null))
}
const getCount = () => {
const countELement = document.getElementById('twikoo-count')
if(!countELement) return
twikoo.getCommentsCount({
envId: 'https://twikoo.909111.xyz/',
region: '',
urls: [window.location.pathname],
includeReply: false
}).then(function (res) {
countELement.innerText = res[0].count
}).catch(function (err) {
console.error(err);
});
}
const runFn = () => {
init()
GLOBAL_CONFIG_SITE.isPost && getCount()
}
const loadTwikoo = () => {
if (typeof twikoo === 'object') {
setTimeout(runFn,0)
return
}
getScript('https://cdn.staticfile.org/twikoo/1.6.8/twikoo.all.min.js').then(runFn)
}
if ('Twikoo' === 'Twikoo' || !true) {
if (true) btf.loadComment(document.getElementById('twikoo-wrap'), loadTwikoo)
else loadTwikoo()
} else {
window.loadOtherComment = () => {
loadTwikoo()
}
}
})()</script></div><canvas id="universe"></canvas><script defer src="/js/universe.js"></script><script src="https://cdn.staticfile.org/jquery/3.6.3/jquery.min.js"></script><script async src="https://cdn1.tianli0.top/npm/[email protected]/dist/vue.min.js"></script><script async src="https://cdn1.tianli0.top/npm/[email protected]/lib/index.js"></script><script async src="https://cdn.bootcdn.net/ajax/libs/clipboard.js/2.0.11/clipboard.min.js"></script><script defer type="text/javascript" src="https://cdn1.tianli0.top/npm/[email protected]/dist/sweetalert2.all.js"></script><script async src="//npm.elemecdn.com/[email protected]/pace.min.js"></script><script defer src="https://cdn1.tianli0.top/gh/nextapps-de/winbox/dist/winbox.bundle.min.js"></script><script async src="//at.alicdn.com/t/c/font_3586335_hsivh70x0fm.js"></script><script async src="//at.alicdn.com/t/c/font_3636804_gr02jmjr3y9.js"></script><script async src="//at.alicdn.com/t/c/font_3612150_kfv55xn3u2g.js"></script><script async src="https://cdn.wpon.cn/2022-sucai/Gold-ingot.js"></script><canvas id="universe"></canvas><canvas id="snow"></canvas><script defer src="/js/music.js"></script><script defer src="/js/fomal.js"></script><script defer src="/js/emoji.js"></script><script src="https://npm.elemecdn.com/[email protected]/dist/echarts.min.js"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/butterfly-extsrc/1.1.3/activate-power-mode.min.js"></script><script>POWERMODE.colorful = true;
POWERMODE.shake = true;
POWERMODE.mobile = false;
document.body.addEventListener('input', POWERMODE);
</script><script id="click-heart" src="https://cdnjs.cloudflare.com/ajax/libs/butterfly-extsrc/1.1.3/click-heart.min.js" async="async" mobile="true"></script><link rel="stylesheet" href="/css/aplayer_css.css" media="print" onload="this.media='all'"><script src="/js/aplayer.js"></script><script src="/js/meting_js.js"></script><script src="https://lib.baomitu.com/pjax/0.2.8/pjax.min.js"></script><script>let pjaxSelectors = ["head > title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show","#web_bg",".js-pjax","#bibi","body > title","#app","#tag-echarts","#posts-echart","#categories-echarts"]
var pjax = new Pjax({
elements: 'a:not([target="_blank"])',
selectors: pjaxSelectors,
cacheBust: false,
analytics: false,
scrollRestoration: false
})
document.addEventListener('pjax:send', function () {
// removeEventListener scroll
window.tocScrollFn && window.removeEventListener('scroll', window.tocScrollFn)
window.scrollCollect && window.removeEventListener('scroll', scrollCollect)
typeof preloader === 'object' && preloader.initLoading()
document.getElementById('rightside').style.cssText = "opacity: ''; transform: ''"
if (window.aplayers) {
for (let i = 0; i < window.aplayers.length; i++) {
if (!window.aplayers[i].options.fixed) {
window.aplayers[i].destroy()
}
}
}
typeof typed === 'object' && typed.destroy()
//reset readmode
const $bodyClassList = document.body.classList
$bodyClassList.contains('read-mode') && $bodyClassList.remove('read-mode')
typeof disqusjs === 'object' && disqusjs.destroy()
})
document.addEventListener('pjax:complete', function () {
window.refreshFn()
document.querySelectorAll('script[data-pjax]').forEach(item => {
const newScript = document.createElement('script')
const content = item.text || item.textContent || item.innerHTML || ""
Array.from(item.attributes).forEach(attr => newScript.setAttribute(attr.name, attr.value))
newScript.appendChild(document.createTextNode(content))
item.parentNode.replaceChild(newScript, item)
})
GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()
typeof chatBtnFn === 'function' && chatBtnFn()
typeof panguInit === 'function' && panguInit()
// google analytics
typeof gtag === 'function' && gtag('config', '', {'page_path': window.location.pathname});
// baidu analytics
typeof _hmt === 'object' && _hmt.push(['_trackPageview',window.location.pathname]);
typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()
// prismjs
typeof Prism === 'object' && Prism.highlightAll()
typeof preloader === 'object' && preloader.endLoading()
})
document.addEventListener('pjax:error', (e) => {
if (e.request.status === 404) {
pjax.loadUrl('/404.html')
}
})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><div id="nav-music"><div id="nav-music-hoverTips" onclick="anzhiyu.musicToggle()">播放音乐</div><meting-js id="8152976493" server="netease" type="playlist" mutex="true" preload="none" theme="var(--anzhiyu-main)" data-lrctype="0" order="random"></meting-js></div><!-- hexo injector body_end start --> <script data-pjax>if(document.getElementById('recent-posts') && (location.pathname ==='/'|| '/' ==='all')){
var parent = document.getElementById('recent-posts');
var child = '<div class="recent-post-item" style="width:100%;height: auto"><div id="catalog_magnet"><div class="magnet_item"><a class="magnet_link" href="https://www.blog.909111.xyz/categories/java学习/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">📚 Miaow.Y.Huのjava学习笔记 (5)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://www.blog.909111.xyz/categories/前端/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">🎮 Miaow.Y.Huの前端学习笔记 (2)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://www.blog.909111.xyz/categories/演示/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">🐱👓 Miaow.Y.Huの演示文档 (2)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://www.blog.909111.xyz/categories/面试题/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">👩💻 Miaow.Y.Huの求职面试 (2)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><a class="magnet_link_more" href="https://www.blog.909111.xyz/categories/" style="flex:1;text-align: center;margin-bottom: 10px;">查看更多...</a></div></div>';
console.log('已挂载magnet')
parent.insertAdjacentHTML("afterbegin",child)}
</script><style>#catalog_magnet{flex-wrap: wrap;display: flex;width:100%;justify-content:space-between;padding: 10px 10px 0 10px;align-content: flex-start;}.magnet_item{flex-basis: calc(50% - 5px);background: #e9e9e9;margin-bottom: 10px;border-radius: 8px;transition: all 0.2s ease-in-out;}.magnet_item:hover{background: var(--text-bg-hover)}.magnet_link_more{color:#555}.magnet_link{color:black}.magnet_link:hover{color:white}@media screen and (max-width: 600px) {.magnet_item {flex-basis: 100%;}}.magnet_link_context{display:flex;padding: 10px;font-size:16px;transition: all 0.2s ease-in-out;}.magnet_link_context:hover{padding: 10px 20px;}</style>
<style></style><script data-pjax>
function butterfly_clock_anzhiyu_injector_config(){
var parent_div_git = document.getElementsByClassName('sticky_layout')[0];
var item_html = '<div class="card-widget card-clock"><div class="card-glass"><div class="card-background"><div class="card-content"><div id="hexo_electric_clock"><img class="entered loading" id="card-clock-loading" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.cbd.int/hexo-butterfly-clock-anzhiyu/lib/loading.gif" style="height: 120px; width: 100%;" data-ll-status="loading"/></div></div></div></div></div>';
console.log('已挂载butterfly_clock_anzhiyu')
if(parent_div_git) {
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
}
}
var elist = 'null'.split(',');
var cpage = location.pathname;
var epage = '/';
var qweather_key = '0c32fd4718b345988056812b5c304e80';
var gaud_map_key = 'c050791b2b4806d9287232d3688ca41b';
var baidu_ak_key = 'undefined';
var flag = 0;
var clock_rectangle = '113.34532,23.15624';
var clock_default_rectangle_enable = 'false';
for (var i=0;i<elist.length;i++){
if (cpage.includes(elist[i])){
flag++;
}
}
if ((epage ==='all')&&(flag == 0)){
butterfly_clock_anzhiyu_injector_config();
}
else if (epage === cpage){
butterfly_clock_anzhiyu_injector_config();
}
</script><script src="https://widget.qweather.net/simple/static/js/he-simple-common.js?v=2.0"></script><script data-pjax src="https://cdn.cbd.int/hexo-butterfly-clock-anzhiyu/lib/clock.min.js"></script><script data-pjax>
function butterfly_swiper_injector_config(){
var parent_div_git = document.getElementById('recent-posts');
var item_html = '<div class="recent-post-item" style="height: auto;width: 100%"><div class="blog-slider swiper-container-fade swiper-container-horizontal" id="swiper_container"><div class="blog-slider__wrp swiper-wrapper" style="transition-duration: 0ms;"><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" onclick="pjax.loadUrl("posts/ece28c36.html");" href="javascript:void(0);" alt=""><img width="48" height="48" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531380.jpg" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-04-27</span><a class="blog-slider__title" onclick="pjax.loadUrl("posts/ece28c36.html");" href="javascript:void(0);" alt="">二十三种设计模式</a><div class="blog-slider__text">我其实很多时候都想放弃这23种鬼东西，看着头疼，二十三种设计模式，那是真的头疼，不仅仅要了解原图还要了解相关代码，但是这东西又贼重要，没办法，我只能搞了，毕竟软考确实蛮重要的，并且这23种模式也确实很重要。</div><a class="blog-slider__button" onclick="pjax.loadUrl("posts/ece28c36.html");" href="javascript:void(0);" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" onclick="pjax.loadUrl("posts/afe2faba.html");" href="javascript:void(0);" alt=""><img width="48" height="48" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531409.jpg" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2024-04-02</span><a class="blog-slider__title" onclick="pjax.loadUrl("posts/afe2faba.html");" href="javascript:void(0);" alt="">Mybatis框架学习</a><div class="blog-slider__text">本文将从0到1搭建Mybatis项目，并实现使用mybatis完成简单的对数据库的增删改查操作</div><a class="blog-slider__button" onclick="pjax.loadUrl("posts/afe2faba.html");" href="javascript:void(0);" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" onclick="pjax.loadUrl("posts/a378bd8e.html");" href="javascript:void(0);" alt=""><img width="48" height="48" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531380.jpg" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-05-10</span><a class="blog-slider__title" onclick="pjax.loadUrl("posts/a378bd8e.html");" href="javascript:void(0);" alt="">Python</a><div class="blog-slider__text">作为目前的主流编程语言之一，Python有着他自己的特点，本篇将纪录python的部分知识点。</div><a class="blog-slider__button" onclick="pjax.loadUrl("posts/a378bd8e.html");" href="javascript:void(0);" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" onclick="pjax.loadUrl("posts/135de23b.html");" href="javascript:void(0);" alt=""><img width="48" height="48" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-04-20</span><a class="blog-slider__title" onclick="pjax.loadUrl("posts/135de23b.html");" href="javascript:void(0);" alt="">牛客刷题笔记1</a><div class="blog-slider__text">本文来自笔者牛客刷题的笔记，以及错误的记录</div><a class="blog-slider__button" onclick="pjax.loadUrl("posts/135de23b.html");" href="javascript:void(0);" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" onclick="pjax.loadUrl("posts/f7912a82.html");" href="javascript:void(0);" alt=""><img width="48" height="48" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-05-09</span><a class="blog-slider__title" onclick="pjax.loadUrl("posts/f7912a82.html");" href="javascript:void(0);" alt="">力扣刷题</a><div class="blog-slider__text">快毕业了，发现自己写代码的能力还是不是很强，CV工程师倒是玩得挺6，但是自己去解决对字符的处理，对数组的处理，对文件的处理，发现自己真的太逊了，早知如此何必当初呢？没办法，东西还是得学，选择了这条路，总不能不走吧，不过说真的，到时候该转行还是得转行，但是现在该学学还是学学。</div><a class="blog-slider__button" onclick="pjax.loadUrl("posts/f7912a82.html");" href="javascript:void(0);" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" onclick="pjax.loadUrl("posts/42904f32.html");" href="javascript:void(0);" alt=""><img width="48" height="48" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2024-04-02</span><a class="blog-slider__title" onclick="pjax.loadUrl("posts/42904f32.html");" href="javascript:void(0);" alt="">java多线程面试题</a><div class="blog-slider__text">🥧本文主要介绍对多线程面试题的总结</div><a class="blog-slider__button" onclick="pjax.loadUrl("posts/42904f32.html");" href="javascript:void(0);" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" onclick="pjax.loadUrl("posts/fd5ae9cb.html");" href="javascript:void(0);" alt=""><img width="48" height="48" src= "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-src="https://cdn.jsdelivr.net/gh/luoxiaohei520/MyPics@img/img/202404221531394.jpg" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2024-04-02</span><a class="blog-slider__title" onclick="pjax.loadUrl("posts/fd5ae9cb.html");" href="javascript:void(0);" alt="">IDEA全家桶激活激活码</a><div class="blog-slider__text">本文将重点介绍IDEA全家桶激活方式和相关的全家桶激活码，本系列全部使用的是2022.1月份的激活码</div><a class="blog-slider__button" onclick="pjax.loadUrl("posts/fd5ae9cb.html");" href="javascript:void(0);" alt="">详情 </a></div></div></div><div class="blog-slider__pagination swiper-pagination-clickable swiper-pagination-bullets"></div></div></div>';
console.log('已挂载butterfly_swiper')
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
}
var elist = 'undefined'.split(',');
var cpage = location.pathname;
var epage = '/';
var flag = 0;
for (var i=0;i<elist.length;i++){
if (cpage.includes(elist[i])){
flag++;
}
}
if ((epage ==='all')&&(flag == 0)){
butterfly_swiper_injector_config();
}
else if (epage === cpage){
butterfly_swiper_injector_config();
}
</script><script defer src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.js"></script><script defer data-pjax src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper_init.js"></script><div class="js-pjax"><script async="async">var arr = document.getElementsByClassName('recent-post-item');
for(var i = 0;i<arr.length;i++){
arr[i].classList.add('wow');
arr[i].classList.add('animate__rubberBand');
arr[i].setAttribute('data-wow-duration', '2s');
arr[i].setAttribute('data-wow-delay', '200ms');
arr[i].setAttribute('data-wow-offset', '30');
arr[i].setAttribute('data-wow-iteration', '1');
}</script><script async="async">var arr = document.getElementsByClassName('card-widget');
for(var i = 0;i<arr.length;i++){
arr[i].classList.add('wow');
arr[i].classList.add('animate__backInRight');
arr[i].setAttribute('data-wow-duration', '2s');
arr[i].setAttribute('data-wow-delay', '200ms');
arr[i].setAttribute('data-wow-offset', '30');
arr[i].setAttribute('data-wow-iteration', '1');
}</script></div><script defer src="https://npm.elemecdn.com/hexo-butterfly-wowjs/lib/wow.min.js"></script><script defer src="https://npm.elemecdn.com/hexo-butterfly-wowjs/lib/wow_init.js"></script><script data-pjax src="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.js"></script><script data-pjax>
function gitcalendar_injector_config(){
var parent_div_git = document.getElementById('gitZone');
var item_html = '<div class="recent-post-item" id="gitcalendarBar" style="width:100%;height:auto;padding:10px;"><style>#git_container{min-height: 320px}@media screen and (max-width:650px) {#git_container{min-height: 0px}}</style><div id="git_loading" style="width:10%;height:100%;margin:0 auto;display: block;"><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 50 50" style="enable-background:new 0 0 50 50" xml:space="preserve"><path fill="#d0d0d0" d="M25.251,6.461c-10.318,0-18.683,8.365-18.683,18.683h4.068c0-8.071,6.543-14.615,14.615-14.615V6.461z" transform="rotate(275.098 25 25)"><animatetransform attributeType="xml" attributeName="transform" type="rotate" from="0 25 25" to="360 25 25" dur="0.6s" repeatCount="indefinite"></animatetransform></path></svg><style>#git_container{display: none;}</style></div><div id="git_container"></div></div>';
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
console.log('已挂载gitcalendar')
}
if( document.getElementById('gitZone') && (location.pathname ==='/site/census/'|| '/site/census/' ==='all')){
gitcalendar_injector_config()
GitCalendarInit("python-github-calendar-api-sand.vercel.app/api?luoxiaohei520",['#d9e0df', '#c6e0dc', '#a8dcd4', '#9adcd2', '#89ded1', '#77e0d0', '#5fdecb', '#47dcc6', '#39dcc3', '#1fdabe', '#00dab9'],'luoxiaohei520')
}
</script><!-- hexo injector body_end end --><script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"/live2dw/assets/koharu.model.json"},"display":{"position":"left","width":120,"height":240},"mobile":{"show":false},"log":false});</script></body></html>