-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdata_structure_cpp_6_b-tree.html
More file actions
867 lines (674 loc) · 198 KB
/
data_structure_cpp_6_b-tree.html
File metadata and controls
867 lines (674 loc) · 198 KB
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
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
<!DOCTYPE html>
<html>
<head>
<title>
常用数据结构C++实现(6)：B树 | 雅乐网 </title>
<meta charset="UTF-8" />
<meta name="renderer" content="webkit">
<link rel="stylesheet" href="http://www.yalewoo.com/wp-content/themes/YLW3_lite/style.css" type="text/css" />
<link rel="alternate" type="application/rss+xml" title="RSS 2.0" href="http://www.yalewoo.com/feed" />
<!-- All in One SEO Pack 2.3.12.1 by Michael Torbert of Semper Fi Web Design[-1,-1] -->
<meta name="description" content="本文介绍的数据结构英文是B-tree，中文写作B-树，其中 - 并不是减号，而是连接符，读作B树。 B-树是一种平衡搜索树，但它的每个结点包含的元素可以多于2个，因此并不是严格意义上的二叉树。 B-树的结点类似如下： 这可以看做二叉搜索树通过多层合并得到的  " />
<link rel="canonical" href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html" />
<!-- /all in one seo pack -->
<link rel="alternate" type="application/rss+xml" title="雅乐网 » 常用数据结构C++实现(6)：B树评论Feed" href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html/feed" />
<link rel='stylesheet' id='crayon-css' href='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/css/min/crayon.min.css?ver=_2.7.2_beta' type='text/css' media='all' />
<link rel='stylesheet' id='crayon-theme-classic-css' href='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/themes/classic/classic.css?ver=_2.7.2_beta' type='text/css' media='all' />
<link rel='stylesheet' id='crayon-font-consolas-css' href='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/fonts/consolas.css?ver=_2.7.2_beta' type='text/css' media='all' />
<script type='text/javascript' src='https://lib.sinaapp.com/js/jquery/1.8.2/jquery.min.js'></script>
<script type='text/javascript'>
/* <![CDATA[ */
var CrayonSyntaxSettings = {"version":"_2.7.2_beta","is_admin":"0","ajaxurl":"http:\/\/www.yalewoo.com\/wp-admin\/admin-ajax.php","prefix":"crayon-","setting":"crayon-setting","selected":"crayon-setting-selected","changed":"crayon-setting-changed","special":"crayon-setting-special","orig_value":"data-orig-value","debug":""};
var CrayonSyntaxStrings = {"copy":"\u4f7f\u7528 %s \u590d\u5236\uff0c\u4f7f\u7528 %s \u7c98\u8d34\u3002","minimize":"\u70b9\u51fb\u5c55\u5f00\u4ee3\u7801"};
/* ]]> */
</script>
<script type='text/javascript' src='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/js/min/crayon.min.js?ver=_2.7.2_beta'></script>
<link rel='prev' title='常用数据结构C++实现(5)：伸展树' href='http://www.yalewoo.com/data_structure_cpp_5_splay_binary_tree.html' />
<link rel='next' title='从B-树角度理解红黑树背后的原理' href='http://www.yalewoo.com/red_black_tree_a_b-tree_view.html' />
<link rel='shortlink' href='http://www.yalewoo.com/?p=2251' />
<link rel="stylesheet" href="http://www.yalewoo.com/wp-content/plugins/wp-content-index/style.css" type="text/css" media="all" />
<!-- Start Of Script Generated By WP-PostViews -->
<script type="text/javascript">
/* <![CDATA[ */
jQuery.ajax({type:'GET',url:'http://www.yalewoo.com/wp-admin/admin-ajax.php',data:'postviews_id=2251&action=postviews',cache:false});/* ]]> */
jQuery(document).ready(function() {
var ajax_data = {
action: "show_postview",
postviews_id: 2251
};
$.post("http://www.yalewoo.com/wp-admin/admin-ajax.php", ajax_data,
function(data) {
$('.meta-view').html(data);
});
return false;
});
</script>
<!-- End Of Script Generated By WP-PostViews -->
<script src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/jquery.lazyload.min.js" type="text/javascript"></script>
<script type="text/javascript">
$(function() {
$("#secondary img").lazyload({
effect:"fadeIn"
});
});
$(function() {
$("img").lazyload({
effect:"fadeIn"
});
});
</script>
<!--[if lte IE 8]><script>document.write("<p style=\"color:red;font-size:40px;\">你正在使用 Internet Explorer 的过期版本（IE6、IE7、IE8）<br/>请<a href=\"#\" style=\"color:blue;\">升级您的浏览器</a>获得更好的浏览体验。</p>");</script><![endif]-->
</head><body>
<header id="topheader">
<hgroup>
<h1><a href = "http://www.yalewoo.com">雅乐网</a>
</h1>
<h2>计算机技术博客</h2>
</hgroup>
<div id="top_menu">
<div class="menu-%e6%9c%80%e9%a1%b6%e7%ab%af-container"><ul id="menu-%e6%9c%80%e9%a1%b6%e7%ab%af" class="menu"><li id="menu-item-663" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-663"><a href="http://www.yalewoo.com/about">关于本站</a></li>
<li id="menu-item-662" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-662"><a href="http://www.yalewoo.com/updates">雅乐网更新记录</a></li>
<li id="menu-item-661" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-661"><a target="_blank" href="http://www.yalewoo.com/old0/">老版网站</a></li>
</ul></div> <form method="get" id="searchform" action="http://www.yalewoo.com/">
<div>
<input type="text" value="" name="s" id="s" size="15" />
<input type="submit" id="searchsubmit" value="Search" />
</div>
</form> </div>
</header>
<nav class="main_nav">
<div class="menu-%e4%b8%bb%e8%8f%9c%e5%8d%9520171106-container"><ul id="menu-%e4%b8%bb%e8%8f%9c%e5%8d%9520171106" class="menu"><li id="menu-item-3235" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-home menu-item-3235"><a href="http://www.yalewoo.com/">首页</a></li>
<li id="menu-item-3237" class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor menu-item-has-children menu-item-3237"><a href="http://www.yalewoo.com/programming">编程</a>
<ul class="sub-menu">
<li id="menu-item-3238" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3238"><a href="http://www.yalewoo.com/programming/c_cpp">C/C++</a></li>
<li id="menu-item-3243" class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor current-menu-parent current-post-parent menu-item-3243"><a href="http://www.yalewoo.com/programming/data_structure">数据结构</a></li>
<li id="menu-item-3244" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3244"><a href="http://www.yalewoo.com/programming/basic_algorithm">算法</a></li>
<li id="menu-item-3240" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3240"><a href="http://www.yalewoo.com/programming/online_judge">OJ刷题</a></li>
<li id="menu-item-3239" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3239"><a href="http://www.yalewoo.com/programming/linux">Linux</a></li>
<li id="menu-item-3241" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3241"><a href="http://www.yalewoo.com/programming/web">Web</a>
<ul class="sub-menu">
<li id="menu-item-3242" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3242"><a href="http://www.yalewoo.com/programming/web/wordpress">wordpress</a></li>
</ul>
</li>
</ul>
</li>
<li id="menu-item-3245" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3245"><a href="http://www.yalewoo.com/algorithm">算法</a>
<ul class="sub-menu">
<li id="menu-item-3248" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3248"><a href="http://www.yalewoo.com/algorithm/maths">数学</a></li>
<li id="menu-item-3246" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3246"><a href="http://www.yalewoo.com/algorithm/ml_notes">机器学习</a></li>
<li id="menu-item-3281" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3281"><a href="http://www.yalewoo.com/algorithm/deep_learning">深度学习</a></li>
<li id="menu-item-3247" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3247"><a href="http://www.yalewoo.com/algorithm/python">python</a></li>
<li id="menu-item-3253" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3253"><a href="http://www.yalewoo.com/algorithm/%e7%a4%be%e5%9b%a2%e6%a3%80%e6%b5%8b">社团检测</a></li>
</ul>
</li>
<li id="menu-item-3254" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3254"><a href="http://www.yalewoo.com/tools">工具教程</a>
<ul class="sub-menu">
<li id="menu-item-3255" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3255"><a href="http://www.yalewoo.com/tools/git">Git/GitHub</a></li>
<li id="menu-item-3256" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3256"><a href="http://www.yalewoo.com/tools/sublime_text">Sublime Text</a></li>
<li id="menu-item-3257" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3257"><a href="http://www.yalewoo.com/tools/vs2013">VS2013</a></li>
<li id="menu-item-3259" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3259"><a href="http://www.yalewoo.com/tools/browser">浏览器</a></li>
<li id="menu-item-3258" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3258"><a href="http://www.yalewoo.com/tools/other_tools">其他工具</a></li>
</ul>
</li>
<li id="menu-item-3260" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3260"><a href="http://www.yalewoo.com/excellent_softwares">软件推荐</a>
<ul class="sub-menu">
<li id="menu-item-3261" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3261"><a href="http://www.yalewoo.com/excellent_softwares/zip">压缩加密</a></li>
<li id="menu-item-3262" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3262"><a href="http://www.yalewoo.com/excellent_softwares/pictools">图片工具</a></li>
<li id="menu-item-3263" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3263"><a href="http://www.yalewoo.com/excellent_softwares/media_tools">多媒体</a></li>
<li id="menu-item-3264" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3264"><a href="http://www.yalewoo.com/excellent_softwares/safe_software">安全清理</a></li>
<li id="menu-item-3265" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3265"><a href="http://www.yalewoo.com/excellent_softwares/android">安卓</a></li>
<li id="menu-item-3266" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3266"><a href="http://www.yalewoo.com/excellent_softwares/utility">实用工具</a></li>
<li id="menu-item-3267" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3267"><a href="http://www.yalewoo.com/excellent_softwares/search_tools">搜索词典</a></li>
<li id="menu-item-3268" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3268"><a href="http://www.yalewoo.com/excellent_softwares/efficiency_tools">效率提升</a></li>
<li id="menu-item-3269" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3269"><a href="http://www.yalewoo.com/excellent_softwares/programming_tools">编程开发</a></li>
<li id="menu-item-3270" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3270"><a href="http://www.yalewoo.com/excellent_softwares/internet_software">网络软件</a></li>
<li id="menu-item-3271" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3271"><a href="http://www.yalewoo.com/excellent_softwares/edit_and_reading">阅读编辑</a></li>
</ul>
</li>
<li id="menu-item-3272" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3272"><a href="http://www.yalewoo.com/it_resource">资源</a>
<ul class="sub-menu">
<li id="menu-item-3273" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3273"><a href="http://www.yalewoo.com/it_resource/good_websites">好网站</a></li>
<li id="menu-item-3274" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3274"><a href="http://www.yalewoo.com/it_resource/stuff">好资料</a></li>
<li id="menu-item-3275" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3275"><a href="http://www.yalewoo.com/it_resource/how">授人以渔</a></li>
<li id="menu-item-3276" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3276"><a href="http://www.yalewoo.com/it_resource/ebooks-share">电子书</a></li>
</ul>
</li>
<li id="menu-item-3277" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3277"><a href="http://www.yalewoo.com/learning">我爱学习</a>
<ul class="sub-menu">
<li id="menu-item-3278" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3278"><a href="http://www.yalewoo.com/learning/popular_science">科普</a></li>
</ul>
</li>
<li id="menu-item-3280" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-3280"><a href="http://www.yalewoo.com/about">关于本站</a></li>
</ul></div></nav>
<script type="text/javascript" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/dianzan.js"></script>
<div id="mbxdh">
<div>
<a href="http://www.yalewoo.com/programming">编程</a> » <a href="http://www.yalewoo.com/programming/data_structure">数据结构</a> » 常用数据结构C++实现(6)：B树 </div>
</div>
<div id="container">
<section class="whole_article" id="article-2251">
<article class="post-2251 post type-post status-publish format-standard hentry category-data_structure tag-242 tag-245" id="entry">
<h2 id="article-title">
<span class = "title-meta-yuanchuang title-meta-ico"></span>
<a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html" title="常用数据结构C++实现(6)：B树">常用数据结构C++实现(6)：B树</a>
</h2>
<div class="post-meta">
<span class="meta-author meta-ico"><a href="http://www.yalewoo.com/author/yalewoo" title="由yalewoo发布" rel="author">yalewoo</a> </span>
<span class="meta-time meta-ico"> 最后修改于 2016-01-17</span>
发表于 2016-01-17
<span class="meta-view meta-ico">939</span>
<span class="meta-comment meta-ico"><a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html#respond">0</a></span>
<br><br>
<span class="meta-category meta-ico"> <a href="http://www.yalewoo.com/programming/data_structure" rel="category tag">数据结构</a> </span>
<span class="meta-category meta-ico"> <a href="http://www.yalewoo.com/tag/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84" rel="tag">数据结构</a>, <a href="http://www.yalewoo.com/tag/%e6%a0%91" rel="tag">树</a> </span>
</div>
<div id="article-content">
<div id="content-index" class="content-index" style="margin:0 0 10px 10px;float:right;"><span class="content-index-toctoggle">[<a id="content-index-togglelink" href="javascript:content_index_toggleToc()">目录开关</a>]</span>
<script type="text/javascript" language="javascript">
window.content_index_showTocToggle=true;function content_index_toggleToc(){var tts="显示目录";var tth="隐藏目录";if(window.content_index_showTocToggle){window.content_index_showTocToggle=false;document.getElementById("content-index-contents").style.display="block";document.getElementById("content-index-togglelink").innerHTML=tth}else{window.content_index_showTocToggle=true;document.getElementById("content-index-contents").style.display="none";document.getElementById("content-index-togglelink").innerHTML=tts}}
</script>
<ul id="content-index-contents"><li class="content-index-level-1"><a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html#定义" title="定义"><em>1</em><span>定义</span></a></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html#查找" title="查找"><em>2</em><span>查找</span></a></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html#插入" title="插入"><em>3</em><span>插入</span></a></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html#删除" title="删除"><em>4</em><span>删除</span></a></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html#C++实现" title="C++实现"><em>5</em><span>C++实现</span></a></li></ul></div>
<p>本文介绍的数据结构英文是B-tree，中文写作B-树，其中 – 并不是减号，而是连接符，读作B树。</p>
<p>B-树是一种平衡搜索树，但它的每个结点包含的元素可以多于2个，因此并不是严格意义上的二叉树。</p>
<p>B-树的结点类似如下：</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117104547.png"><img class="alignnone size-full wp-image-2252" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117104547.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20160117104547" width="752" height="238" /></a></p>
<noscript><img class="alignnone size-full wp-image-2252" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117104547.png" alt="scrn20160117104547" width="752" height="238" /></a></p></noscript>
<p>这可以看做二叉搜索树通过多层合并得到的</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117111953.png"><img class="alignnone size-full wp-image-2253" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117111953.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20160117111953" width="740" height="193" /></a></p>
<noscript><img class="alignnone size-full wp-image-2253" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117111953.png" alt="scrn20160117111953" width="740" height="193" /></a></p></noscript>
<p> </p>
<p>相比与二叉树，B树显得更矮，更胖。它的每个结点包含多个数据，这特别适合于对外存的访问。由于硬盘等设备访问速度和内存相比非常慢，而从硬盘读取1个数据和读取10个数据用时几乎一样，这非常适合使用B-树这种结构。每个结点数据很多，就可以从磁盘依次取出大量数据，矮的特点可以减少磁盘的IO次数。</p>
<h3 id="定义">定义</h3>
<p>B-树的所有叶子结点都位于同一深度，同时对每个结点的分支数也有限制。一个m阶B-树满足</p>
<p>1. 每个结点的分支数最多m个，因此每个结点元素个数最多m-1个。</p>
<p>2. 除根节点外，每个结点的分支树最少 ⌈m/2⌉ 个（向上取整）。根节点例外，根节点可以只有2个分支。</p>
<p>这样，m阶B-树也可以叫做 (⌈m/2⌉ , m) -树 。</p>
<h3 id="查找">查找</h3>
<p>B树的查找和二分查找类似，只不多这里是多分的。详见代码。</p>
<h3 id="插入">插入</h3>
<p>插入元素总是插入到叶节点，如果插入后节点数多余m-1，则要修复上溢。</p>
<p>发生上溢时，有m个结点，则分裂为左右两部分和中间轴点，左半部分有 m/2 个结点，中间1个结点，有半部分有⌈m/2⌉-1 个结点。 中间节点上升一层。父节点可能因此继续上溢。</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117114224.png"><img class="alignnone size-full wp-image-2255" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117114224.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20160117114224" width="625" height="170" /></a></p>
<noscript><img class="alignnone size-full wp-image-2255" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117114224.png" alt="scrn20160117114224" width="625" height="170" /></a></p></noscript>
<h3 id="删除">删除</h3>
<p>通过和中序后继交换，实现删除元素总是位于叶子。删除后如果分支数小于要求，则称下溢。</p>
<p>发生下溢时，可以先看左右兄弟是否可借出一个孩子</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117115122.png"><img class="alignnone size-full wp-image-2256" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117115122.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20160117115122" width="751" height="214" /></a></p>
<noscript><img class="alignnone size-full wp-image-2256" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117115122.png" alt="scrn20160117115122" width="751" height="214" /></a></p></noscript>
<p>如果左右兄弟都不能借出，也就是都具有最少的结点，则可以进行合并。</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117122722.png"><img class="alignnone size-full wp-image-2257" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117122722.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20160117122722" width="665" height="195" /></a></p>
<noscript><img class="alignnone size-full wp-image-2257" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/scrn20160117122722.png" alt="scrn20160117122722" width="665" height="195" /></a></p></noscript>
<h3 id="C++实现">C++实现</h3>
<p>BTree.h</p>
<div id="crayon-5a0c2d06c8e5e118634538" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
#include "Vector.h"
#include "Queue.h"
#define BTNodePosi(T) BTNode<T>*
template <typename T>
class BTNode
{
public:
BTNodePosi(T) parent;
Vector<T> key;
Vector<BTNodePosi(T)> child;
BTNode() : parent(NULL) { child.push_back(NULL); }
BTNode(T e, BTNodePosi(T) lchild = NULL, BTNodePosi(T) rchild = NULL);
};
template <typename T>
BTNode<T>::BTNode(T e, BTNodePosi(T) lchild, BTNodePosi(T) rchild)
{
parent = NULL;
key.insert(e);
child.insert(0, lchild);
child.insert(1, rchild);
if (lchild) lchild->parent = this;
if (rchild) rchild->parent = this;
}
template <typename T>
class BTree
{
protected:
int _size;
int _order;
BTNodePosi(T) _root; //根节点
BTNodePosi(T) _hot;
void solveOverflow(BTNodePosi(T));
void solveUnderflow(BTNodePosi(T));
public:
BTNodePosi(T) search(const T & e);
bool insert(const T & e);
bool remove(const T & e);
void display();
BTree(int order) : _size(0), _order(order), _root(NULL), _hot(NULL) { }
};
template <typename T>
BTNodePosi(T) BTree<T>::search(const T & e)
{
BTNodePosi(T) p = _root;
_hot = NULL;
//反复循环直到到达外部结点 或者找到时直接return
while (p)
{
//向量的search接口返回不大于e的最后一个元素
int n = p->key.search(e);
//已经找到
if (p->key[n] == e)
return p;
//否则 下降一层
_hot = p;
p = p->child[n+1];
}
return NULL;
}
template <typename T>
bool BTree<T>::insert(const T & e)
{
//不允许重复元素
if (search(e)) return false;
//search执行后 _hot指向的是最终结点的父节点（search失败时指向外部结点的父节点 也就是叶子节点）
BTNodePosi(T) p = _hot;
if (!p)
{ //树为空的情况
p = new BTNode<T>;
_root = p;
p->key.push_back(e);
p->child.push_back(NULL);
++_size;
return true;
}
//树不为空时，将e插入到叶节点的适当位置
int n = p->key.search(e);
p->key.insert(n+1, e);
p->child.push_back(NULL); //叶节点的孩子是外部结点 全部为NULL 因此直接插入到最后面
++_size;
BTNodePosi(T) par;
//插入结点后 从该结点到其祖先结点 依次检测是否上溢并修复
while (p && p->child.size() > _order)
{
par = p->parent;
solveOverflow(p);
p = par;
}
return true;
}
template <typename T>
bool BTree<T>::remove(const T & e)
{
//找到e的位置
BTNodePosi(T) p = search(e);
if (!p) return false;
int n = p->key.search(e);
//若e所在结点不是叶子结点 用它的中序意义后继替代它 之后只需删除位于叶子节点的那个后继
if (p->child[0])
{
BTNodePosi(T) q = p->child[n+1];
while (q->child[0])
{
q = q->child[0];
}
p->key.put(n, q->key[0]);
n = 0;
p = q;
}
//现在待删除节点都位于叶子结点 开始删除
p->key.remove(n);
p->child.remove(n);
--_size;
//删除元素后解决下溢问题
if (p != _root && p->child.size() < (_order+1)/2)
{
solveUnderflow(p);
}
return true;
}
//解决上溢问题 即pn的分支数超过了B树的阶_order
template <typename T>
void BTree<T>::solveOverflow(BTNodePosi(T) pn)
{
BTNodePosi(T) p = pn->parent;
int n = (_order-1)/2; //n是最少结点数
//下面把pn结点分裂为lc和rc两个结点和中间一个只有一个元素的结点
//lc [0,n) 中间结点 [n] rc [n+1,size]
int i;
//左半部分
BTNodePosi(T) lc = new BTNode<T>;
for (i = 0; i < n; ++i)
{
lc->key.push_back(pn->key[i]);
if (i == 0)
lc->child.put(0, pn->child[0]);
else
lc->child.push_back(pn->child[i]);
}
lc->child.push_back(pn->child[i]);
for (i = 0; i < lc->child.size(); ++i)
if (lc->child[i]) lc->child[i]->parent = lc;
//右半部分
BTNodePosi(T) rc = new BTNode<T>;
for (i = n+1; i < pn->key.size(); ++i)
{
rc->key.push_back(pn->key[i]);
if (i == n+1)
rc->child.put(0, pn->child[i]);
else
rc->child.push_back(pn->child[i]);
}
rc->child.push_back(pn->child[i]);
for (i = 0; i < rc->child.size(); ++i)
if (rc->child[i]) rc->child[i]->parent = rc;
if (!p)
{ //上溢结点是树根节点的情况
p = new BTNode<T>;
_root = p;
}
//把中间节点插入到pn的父节点 其左右指针指向lc和rc两部分
lc->parent = p;
rc->parent = p;
int n1 = p->key.search(pn->key[n]);
p->key.insert(n1+1, pn->key[n]);
p->child.put(n1+1, lc);
p->child.insert(n1+2, rc);
delete pn;
}
template <typename T>
void BTree<T>::solveUnderflow(BTNodePosi(T) q)
{
//没有下溢则退出
if (q->child.size() >= (_order+1)/2) return;
if (q == _root)
{
if (q->key.empty())
{
//树根节点删除了最后一个元素变为空树的情况
_root = q->child[0];
delete q;
}
return; //树根节点最少可以是1个结点 没有下溢的问题
}
BTNodePosi(T) p = q->parent;
int n;
for (n = 0; n < p->child.size(); ++n)
{
if (p->child[n] == q)
break;
}
BTNodePosi(T) lc;
BTNodePosi(T) rc;
//q的左兄弟可以借出结点
if (n > 0 && p->child[n-1]->child.size() > (_order+1)/2)
{
lc = p->child[n-1];
q->key.insert(0, p->key[n-1]);
q->child.insert(0, lc->child.last());
if (q->child[0]) q->child[0]->parent = q;
p->key.put(n-1, lc->key.last());
lc->key.remove(lc->key.size() - 1);
lc->child.remove(lc->child.size() - 1);
return;
}
//q的右兄弟可以借出结点
if (n < p->child.size()-1 && p->child[n+1]->child.size() > (_order+1)/2)
{
rc = p->child[n+1];
q->key.push_back(p->key[n]);
q->child.push_back(rc->child[0]);
if (rc->child[0]) rc->child[0] = q;
p->key.put(n, rc->key[0]);
rc->key.remove(0);
rc->child.remove(0);
return;
}
//q的左右兄弟都不能借出 则合并
if (n > 0)
{
//有左兄弟时，与左兄弟合并
lc = p->child[n-1];
lc->key.push_back(p->key[n-1]);
int i;
for (i = 0; i < q->key.size(); ++i)
{
lc->key.push_back(q->key[i]);
lc->child.push_back(q->child[i]);
}
lc->child.push_back(q->child[i]);
p->key.remove(n-1);
p->child.remove(n);
delete q;
}
else
{
//否则和右兄弟合并
rc = p->child[n+1];
q->key.push_back(p->key[n]);
int i;
for (i = 0; i < rc->key.size(); ++i)
{
q->key.push_back(rc->key[i]);
q->child.push_back(rc->child[i]);
}
q->child.push_back(rc->child[i]);
p->key.remove(n);
p->child.remove(n+1);
delete rc;
}
//合并后，父节点的分支数减少，继续解决父节点的下溢问题
solveUnderflow(p);
}
template <typename T>
class MyPrint
{
public:
void operator()(T e)
{
cout << e << " ";
}
};
template <typename T>
void BTree<T>::display()
{
if (!_root) return;
MyPrint<T> visit;
Queue<BTNodePosi(T)> q;
BTNodePosi(T) x = _root;
BTNode<T> endl1;
q.enqueue(x);
q.enqueue(&endl1);
int i;
while (!q.empty())
{
x = q.dequeue();
if (!x) continue;
if (x == &endl1)
{
if (q.size() > 0)
q.enqueue(&endl1);
printf("\n");
continue;
}
printf("#");
x->key.travser(visit);
printf("#");
for (i = 0; i < x->child.size(); ++i)
{
q.enqueue(x->child[i]);
}
printf("----");
}
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-1">1</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-2">2</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-3">3</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-4">4</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-5">5</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-6">6</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-7">7</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-8">8</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-9">9</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-10">10</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-11">11</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-12">12</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-13">13</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-14">14</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-15">15</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-16">16</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-17">17</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-18">18</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-19">19</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-20">20</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-21">21</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-22">22</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-23">23</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-24">24</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-25">25</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-26">26</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-27">27</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-28">28</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-29">29</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-30">30</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-31">31</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-32">32</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-33">33</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-34">34</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-35">35</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-36">36</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-37">37</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-38">38</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-39">39</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-40">40</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-41">41</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-42">42</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-43">43</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-44">44</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-45">45</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-46">46</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-47">47</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-48">48</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-49">49</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-50">50</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-51">51</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-52">52</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-53">53</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-54">54</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-55">55</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-56">56</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-57">57</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-58">58</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-59">59</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-60">60</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-61">61</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-62">62</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-63">63</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-64">64</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-65">65</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-66">66</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-67">67</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-68">68</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-69">69</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-70">70</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-71">71</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-72">72</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-73">73</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-74">74</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-75">75</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-76">76</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-77">77</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-78">78</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-79">79</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-80">80</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-81">81</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-82">82</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-83">83</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-84">84</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-85">85</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-86">86</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-87">87</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-88">88</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-89">89</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-90">90</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-91">91</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-92">92</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-93">93</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-94">94</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-95">95</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-96">96</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-97">97</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-98">98</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-99">99</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-100">100</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-101">101</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-102">102</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-103">103</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-104">104</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-105">105</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-106">106</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-107">107</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-108">108</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-109">109</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-110">110</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-111">111</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-112">112</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-113">113</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-114">114</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-115">115</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-116">116</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-117">117</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-118">118</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-119">119</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-120">120</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-121">121</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-122">122</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-123">123</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-124">124</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-125">125</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-126">126</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-127">127</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-128">128</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-129">129</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-130">130</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-131">131</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-132">132</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-133">133</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-134">134</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-135">135</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-136">136</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-137">137</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-138">138</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-139">139</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-140">140</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-141">141</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-142">142</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-143">143</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-144">144</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-145">145</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-146">146</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-147">147</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-148">148</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-149">149</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-150">150</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-151">151</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-152">152</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-153">153</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-154">154</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-155">155</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-156">156</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-157">157</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-158">158</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-159">159</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-160">160</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-161">161</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-162">162</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-163">163</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-164">164</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-165">165</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-166">166</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-167">167</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-168">168</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-169">169</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-170">170</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-171">171</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-172">172</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-173">173</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-174">174</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-175">175</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-176">176</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-177">177</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-178">178</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-179">179</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-180">180</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-181">181</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-182">182</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-183">183</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-184">184</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-185">185</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-186">186</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-187">187</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-188">188</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-189">189</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-190">190</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-191">191</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-192">192</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-193">193</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-194">194</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-195">195</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-196">196</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-197">197</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-198">198</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-199">199</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-200">200</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-201">201</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-202">202</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-203">203</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-204">204</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-205">205</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-206">206</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-207">207</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-208">208</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-209">209</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-210">210</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-211">211</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-212">212</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-213">213</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-214">214</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-215">215</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-216">216</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-217">217</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-218">218</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-219">219</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-220">220</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-221">221</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-222">222</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-223">223</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-224">224</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-225">225</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-226">226</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-227">227</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-228">228</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-229">229</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-230">230</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-231">231</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-232">232</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-233">233</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-234">234</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-235">235</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-236">236</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-237">237</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-238">238</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-239">239</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-240">240</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-241">241</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-242">242</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-243">243</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-244">244</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-245">245</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-246">246</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-247">247</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-248">248</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-249">249</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-250">250</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-251">251</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-252">252</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-253">253</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-254">254</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-255">255</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-256">256</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-257">257</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-258">258</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-259">259</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-260">260</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-261">261</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-262">262</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-263">263</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-264">264</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-265">265</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-266">266</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-267">267</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-268">268</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-269">269</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-270">270</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-271">271</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-272">272</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-273">273</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-274">274</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-275">275</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-276">276</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-277">277</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-278">278</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-279">279</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-280">280</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-281">281</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-282">282</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-283">283</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-284">284</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-285">285</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-286">286</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-287">287</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-288">288</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-289">289</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-290">290</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-291">291</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-292">292</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-293">293</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-294">294</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-295">295</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-296">296</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-297">297</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-298">298</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-299">299</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-300">300</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-301">301</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-302">302</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-303">303</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-304">304</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-305">305</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-306">306</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-307">307</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-308">308</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-309">309</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-310">310</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-311">311</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-312">312</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-313">313</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-314">314</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-315">315</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-316">316</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-317">317</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-318">318</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-319">319</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-320">320</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-321">321</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-322">322</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-323">323</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-324">324</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-325">325</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-326">326</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-327">327</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-328">328</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-329">329</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-330">330</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-331">331</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-332">332</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-333">333</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-334">334</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-335">335</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-336">336</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-337">337</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-338">338</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-339">339</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-340">340</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-341">341</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-342">342</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-343">343</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-344">344</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-345">345</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-346">346</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e5e118634538-347">347</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-1"><span class="crayon-p">#include "Vector.h"</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-2"><span class="crayon-p">#include "Queue.h"</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-3"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-4"><span class="crayon-p">#define BTNodePosi(T) BTNode<T>*</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-5"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-6"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-e">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-7"><span class="crayon-t">class</span><span class="crayon-h"> </span><span class="crayon-e">BTNode</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-8"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-9"><span class="crayon-m">public</span><span class="crayon-o">:</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-10"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-r">parent</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-11"><span class="crayon-h"> </span><span class="crayon-v">Vector</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-v">key</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-12"><span class="crayon-h"> </span><span class="crayon-v">Vector</span><span class="crayon-o"><</span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-r">child</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-13"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-14"><span class="crayon-h"> </span><span class="crayon-e">BTNode</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">:</span><span class="crayon-h"> </span><span class="crayon-r">parent</span><span class="crayon-sy">(</span><span class="crayon-t">NULL</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-sy">{</span><span class="crayon-h"> </span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-t">NULL</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-15"><span class="crayon-h"> </span><span class="crayon-e">BTNode</span><span class="crayon-sy">(</span><span class="crayon-i">T</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">lchild</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-t">NULL</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">rchild</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-t">NULL</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-16"><span class="crayon-sy">}</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-17"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-18"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-19"><span class="crayon-v">BTNode</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-o">::</span><span class="crayon-e">BTNode</span><span class="crayon-sy">(</span><span class="crayon-i">T</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">lchild</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">rchild</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-20"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-21"><span class="crayon-h"> </span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-t">NULL</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-22"><span class="crayon-h"> </span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-23"><span class="crayon-h"> </span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">lchild</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-24"><span class="crayon-h"> </span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">1</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">rchild</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-25"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">lchild</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">lchild</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-r">this</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-26"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">rchild</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">rchild</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-r">this</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-27"><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-28"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-29"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-e">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-30"><span class="crayon-t">class</span><span class="crayon-h"> </span><span class="crayon-e">BTree</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-31"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-32"><span class="crayon-m">protected</span><span class="crayon-o">:</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-33"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">_size</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-34"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">_order</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-35"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-c">//根节点</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-36"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">_hot</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-37"><span class="crayon-h"> </span><span class="crayon-t">void</span><span class="crayon-h"> </span><span class="crayon-e">solveOverflow</span><span class="crayon-sy">(</span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-38"><span class="crayon-h"> </span><span class="crayon-t">void</span><span class="crayon-h"> </span><span class="crayon-e">solveUnderflow</span><span class="crayon-sy">(</span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-39"><span class="crayon-m">public</span><span class="crayon-o">:</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-40"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-m">const</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-h"> </span><span class="crayon-o">&</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-41"><span class="crayon-h"> </span><span class="crayon-t">bool</span><span class="crayon-h"> </span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-m">const</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-h"> </span><span class="crayon-o">&</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-42"><span class="crayon-h"> </span><span class="crayon-t">bool</span><span class="crayon-h"> </span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-m">const</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-h"> </span><span class="crayon-o">&</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-43"><span class="crayon-h"> </span><span class="crayon-t">void</span><span class="crayon-h"> </span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-44"><span class="crayon-h"> </span><span class="crayon-e">BTree</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">order</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">:</span><span class="crayon-h"> </span><span class="crayon-e">_size</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">)</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-e">_order</span><span class="crayon-sy">(</span><span class="crayon-v">order</span><span class="crayon-sy">)</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-e">_root</span><span class="crayon-sy">(</span><span class="crayon-t">NULL</span><span class="crayon-sy">)</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-e">_hot</span><span class="crayon-sy">(</span><span class="crayon-t">NULL</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-sy">{</span><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-45"><span class="crayon-sy">}</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-46"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-47"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-48"><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">BTree</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-o">::</span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-m">const</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-h"> </span><span class="crayon-o">&</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-49"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-50"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-51"><span class="crayon-h"> </span><span class="crayon-v">_hot</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-t">NULL</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-52"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-53"><span class="crayon-h"> </span><span class="crayon-c">//反复循环直到到达外部结点 或者找到时直接return</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-54"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-55"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-56"><span class="crayon-h"> </span><span class="crayon-c">//向量的search接口返回不大于e的最后一个元素</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-57"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-58"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-59"><span class="crayon-h"> </span><span class="crayon-c">//已经找到</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-60"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-o">==</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-61"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-62"><span class="crayon-h"> </span><span class="crayon-c">//否则 下降一层</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-63"><span class="crayon-h"> </span><span class="crayon-v">_hot</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-64"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-65"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-66"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-t">NULL</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-67"><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-68"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-69"><span class="crayon-t">bool</span><span class="crayon-h"> </span><span class="crayon-v">BTree</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-o">::</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-m">const</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-h"> </span><span class="crayon-o">&</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-70"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-71"><span class="crayon-h"> </span><span class="crayon-c">//不允许重复元素</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-72"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-t">false</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-73"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-74"><span class="crayon-h"> </span><span class="crayon-c">//search执行后 _hot指向的是最终结点的父节点（search失败时指向外部结点的父节点 也就是叶子节点）</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-75"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">_hot</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-76"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-o">!</span><span class="crayon-v">p</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-77"><span class="crayon-h"> </span><span class="crayon-sy">{</span><span class="crayon-h"> </span><span class="crayon-c">//树为空的情况</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-78"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-r">new</span><span class="crayon-h"> </span><span class="crayon-v">BTNode</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-79"><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-80"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-81"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-t">NULL</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-82"><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">_size</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-83"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-t">true</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-84"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-85"><span class="crayon-h"> </span><span class="crayon-c">//树不为空时，将e插入到叶节点的适当位置</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-86"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-87"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-88"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-t">NULL</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-c">//叶节点的孩子是外部结点 全部为NULL 因此直接插入到最后面</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-89"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-90"><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">_size</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-91"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-92"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">par</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-93"><span class="crayon-h"> </span><span class="crayon-c">//插入结点后 从该结点到其祖先结点 依次检测是否上溢并修复</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-94"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">&&</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-v">_order</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-95"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-96"><span class="crayon-h"> </span><span class="crayon-v">par</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-97"><span class="crayon-h"> </span><span class="crayon-e">solveOverflow</span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-98"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">par</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-99"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-100"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-101"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-102"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-t">true</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-103"><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-104"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-105"><span class="crayon-t">bool</span><span class="crayon-h"> </span><span class="crayon-v">BTree</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-o">::</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-m">const</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-h"> </span><span class="crayon-o">&</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-106"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-107"><span class="crayon-h"> </span><span class="crayon-c">//找到e的位置</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-108"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-109"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-o">!</span><span class="crayon-v">p</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-t">false</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-110"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-v">e</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-111"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-112"><span class="crayon-h"> </span><span class="crayon-c">//若e所在结点不是叶子结点 用它的中序意义后继替代它 之后只需删除位于叶子节点的那个后继</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-113"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-114"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-115"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-116"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-117"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-118"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-119"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-120"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">put</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-121"><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-122"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-123"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-124"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-125"><span class="crayon-h"> </span><span class="crayon-c">//现在待删除节点都位于叶子结点 开始删除</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-126"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-127"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-128"><span class="crayon-h"> </span><span class="crayon-o">--</span><span class="crayon-v">_size</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-129"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-130"><span class="crayon-h"> </span><span class="crayon-c">//删除元素后解决下溢问题</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-131"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">!=</span><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-h"> </span><span class="crayon-o">&&</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">_order</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-132"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-133"><span class="crayon-h"> </span><span class="crayon-e">solveUnderflow</span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-134"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-135"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-136"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-t">true</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-137"><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-138"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-139"><span class="crayon-c">//解决上溢问题 即pn的分支数超过了B树的阶_order</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-140"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-141"><span class="crayon-t">void</span><span class="crayon-h"> </span><span class="crayon-v">BTree</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-o">::</span><span class="crayon-e">solveOverflow</span><span class="crayon-sy">(</span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">pn</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-142"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-143"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-144"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">_order</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-c">//n是最少结点数</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-145"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-146"><span class="crayon-h"> </span><span class="crayon-c">//下面把pn结点分裂为lc和rc两个结点和中间一个只有一个元素的结点</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-147"><span class="crayon-h"> </span><span class="crayon-c">//lc [0,n) 中间结点 [n] rc [n+1,size]</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-148"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-149"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-150"><span class="crayon-h"> </span><span class="crayon-c">//左半部分</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-151"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-r">new</span><span class="crayon-h"> </span><span class="crayon-v">BTNode</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-152"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">i</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-153"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-154"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-155"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">==</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-156"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">put</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-157"><span class="crayon-h"> </span><span class="crayon-st">else</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-158"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-159"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-160"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-161"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">i</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-162"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-163"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-164"><span class="crayon-h"> </span><span class="crayon-c">//右半部分</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-165"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-r">new</span><span class="crayon-h"> </span><span class="crayon-v">BTNode</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-166"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">i</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-167"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-168"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-169"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">==</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-170"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">put</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-171"><span class="crayon-h"> </span><span class="crayon-st">else</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-172"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-173"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-174"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-175"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">i</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-176"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-177"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-178"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-179"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-o">!</span><span class="crayon-v">p</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-180"><span class="crayon-h"> </span><span class="crayon-sy">{</span><span class="crayon-h"> </span><span class="crayon-c">//上溢结点是树根节点的情况</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-181"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-r">new</span><span class="crayon-h"> </span><span class="crayon-v">BTNode</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-182"><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-183"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-184"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-185"><span class="crayon-h"> </span><span class="crayon-c">//把中间节点插入到pn的父节点 其左右指针指向lc和rc两部分</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-186"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-187"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-188"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">n1</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">search</span><span class="crayon-sy">(</span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-189"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-v">n1</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">pn</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-190"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">put</span><span class="crayon-sy">(</span><span class="crayon-v">n1</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-191"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-v">n1</span><span class="crayon-o">+</span><span class="crayon-cn">2</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-192"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-193"><span class="crayon-h"> </span><span class="crayon-e">delete </span><span class="crayon-v">pn</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-194"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-195"><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-196"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-197"><span class="crayon-t">void</span><span class="crayon-h"> </span><span class="crayon-v">BTree</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-o">::</span><span class="crayon-e">solveUnderflow</span><span class="crayon-sy">(</span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-198"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-199"><span class="crayon-h"> </span><span class="crayon-c">//没有下溢则退出</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-200"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">>=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">_order</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-201"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-202"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-h"> </span><span class="crayon-o">==</span><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-203"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-204"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-205"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">empty</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-206"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-207"><span class="crayon-h"> </span><span class="crayon-c">//树根节点删除了最后一个元素变为空树的情况</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-208"><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-209"><span class="crayon-h"> </span><span class="crayon-i">delete</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-210"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-211"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-c">//树根节点最少可以是1个结点 没有下溢的问题</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-212"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-213"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-214"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-215"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-216"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-217"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">n</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-218"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-219"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-o">==</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-220"><span class="crayon-h"> </span><span class="crayon-st">break</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-221"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-222"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-223"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-224"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-225"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-226"><span class="crayon-h"> </span><span class="crayon-c">//q的左兄弟可以借出结点</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-227"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-h"> </span><span class="crayon-o">&&</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">_order</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-228"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-229"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-230"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-231"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">last</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-232"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-o">-></span><span class="crayon-r">parent</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-233"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-234"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">put</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">last</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-235"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-236"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">-</span><span class="crayon-h"> </span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-237"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">-</span><span class="crayon-h"> </span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-238"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-239"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-240"><span class="crayon-h"> </span><span class="crayon-c">//q的右兄弟可以借出结点</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-241"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-h"> </span><span class="crayon-o">&&</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">_order</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-242"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-243"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-244"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-245"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-246"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-247"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-248"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">put</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-249"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-250"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-251"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">0</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-252"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-253"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-254"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-255"><span class="crayon-h"> </span><span class="crayon-c">//q的左右兄弟都不能借出 则合并</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-256"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-h"> </span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-257"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-258"><span class="crayon-h"> </span><span class="crayon-c">//有左兄弟时，与左兄弟合并</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-259"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-260"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-261"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-262"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">i</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-263"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-264"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-265"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-266"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-267"><span class="crayon-h"> </span><span class="crayon-v">lc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-268"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-269"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-270"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-271"><span class="crayon-h"> </span><span class="crayon-i">delete</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-272"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-273"><span class="crayon-h"> </span><span class="crayon-st">else</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-274"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-275"><span class="crayon-h"> </span><span class="crayon-c">//否则和右兄弟合并</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-276"><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-277"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-278"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">n</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-279"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-280"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">i</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-281"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-282"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-283"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-284"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-285"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">push_back</span><span class="crayon-sy">(</span><span class="crayon-v">rc</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-286"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-287"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-288"><span class="crayon-h"> </span><span class="crayon-v">p</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-v">n</span><span class="crayon-o">+</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-289"><span class="crayon-h"> </span><span class="crayon-e">delete </span><span class="crayon-v">rc</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-290"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-291"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-292"><span class="crayon-h"> </span><span class="crayon-c">//合并后，父节点的分支数减少，继续解决父节点的下溢问题</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-293"><span class="crayon-h"> </span><span class="crayon-e">solveUnderflow</span><span class="crayon-sy">(</span><span class="crayon-v">p</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-294"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-295"><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-296"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-297"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-e">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-298"><span class="crayon-t">class</span><span class="crayon-h"> </span><span class="crayon-e">MyPrint</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-299"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-300"><span class="crayon-m">public</span><span class="crayon-o">:</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-301"><span class="crayon-h"> </span><span class="crayon-t">void</span><span class="crayon-h"> </span><span class="crayon-t">operator</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">(</span><span class="crayon-i">T</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-302"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-303"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-v">e</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">" "</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-304"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-305"><span class="crayon-sy">}</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-306"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-307"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-308"><span class="crayon-t">template</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-r">typename</span><span class="crayon-h"> </span><span class="crayon-v">T</span><span class="crayon-o">></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-309"><span class="crayon-t">void</span><span class="crayon-h"> </span><span class="crayon-v">BTree</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-o">::</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-310"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-311"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-o">!</span><span class="crayon-v">_root</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-312"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-313"><span class="crayon-h"> </span><span class="crayon-v">MyPrint</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-v">visit</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-314"><span class="crayon-h"> </span><span class="crayon-v">Queue</span><span class="crayon-o"><</span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-315"><span class="crayon-h"> </span><span class="crayon-e">BTNodePosi</span><span class="crayon-sy">(</span><span class="crayon-v">T</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">_root</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-316"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-317"><span class="crayon-h"> </span><span class="crayon-v">BTNode</span><span class="crayon-o"><</span><span class="crayon-v">T</span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-v">endl1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-318"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-319"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">.</span><span class="crayon-e">enqueue</span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-320"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">.</span><span class="crayon-e">enqueue</span><span class="crayon-sy">(</span><span class="crayon-v">&endl1</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-321"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-322"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-323"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-o">!</span><span class="crayon-v">q</span><span class="crayon-sy">.</span><span class="crayon-e">empty</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-324"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-325"><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">.</span><span class="crayon-e">dequeue</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-326"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-327"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-o">!</span><span class="crayon-v">x</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-st">continue</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-328"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o">==</span><span class="crayon-h"> </span><span class="crayon-v">&endl1</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-329"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-330"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">q</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-331"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">.</span><span class="crayon-e">enqueue</span><span class="crayon-sy">(</span><span class="crayon-v">&endl1</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-332"><span class="crayon-h"> </span><span class="crayon-e">printf</span><span class="crayon-sy">(</span><span class="crayon-s">"\n"</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-333"><span class="crayon-h"> </span><span class="crayon-st">continue</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-334"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-335"><span class="crayon-h"> </span><span class="crayon-e">printf</span><span class="crayon-sy">(</span><span class="crayon-s">"#"</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-336"><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-o">-></span><span class="crayon-v">key</span><span class="crayon-sy">.</span><span class="crayon-e">travser</span><span class="crayon-sy">(</span><span class="crayon-v">visit</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-337"><span class="crayon-h"> </span><span class="crayon-e">printf</span><span class="crayon-sy">(</span><span class="crayon-s">"#"</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-338"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-339"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-340"><span class="crayon-h"> </span><span class="crayon-st">for</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-v">i</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">.</span><span class="crayon-e">size</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span><span class="crayon-h"> </span><span class="crayon-o">++</span><span class="crayon-v">i</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-341"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-342"><span class="crayon-h"> </span><span class="crayon-v">q</span><span class="crayon-sy">.</span><span class="crayon-e">enqueue</span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-o">-></span><span class="crayon-r">child</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-343"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-344"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-345"><span class="crayon-h"> </span><span class="crayon-e">printf</span><span class="crayon-sy">(</span><span class="crayon-s">"----"</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-346"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e5e118634538-347"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>BTree.cpp</p>
<div id="crayon-5a0c2d06c8e81636895333" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
#include <iostream>
using namespace std;
#include "BTree.h"
int main()
{
BTree<int> bt(4);
bt.insert(21);
bt.insert(48);
bt.insert(72);
bt.insert(12);
bt.insert(22);
bt.insert(50);
bt.insert(34);
bt.insert(42);
bt.insert(60);
bt.insert(67);
bt.insert(89);
bt.insert(13);
bt.display();
cout << "delete 50\n\n";
bt.remove(50);
bt.display();
cout << "delete 72\n\n";
bt.remove(72);
bt.display();
cout << "delete 89\n\n";
bt.remove(89);
bt.display();
cout << "delete 67\n\n";
bt.remove(67);
bt.display();
cout << "delete 48\n\n";
bt.remove(48);
bt.display();
cout << "delete 60\n\n";
bt.remove(60);
bt.display();
cout << "delete 42\n\n";
bt.remove(42);
bt.display();
cout << "delete 22\n\n";
bt.remove(22);
bt.display();
cout << "delete 34\n\n";
bt.remove(34);
bt.display();
cout << "delete 21\n\n";
bt.remove(21);
bt.display();
// int i;
// for (i = 0; i < 30; ++i)
// bt.insert(i);
printf("233");
return 0;
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-1">1</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-2">2</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-3">3</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-4">4</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-5">5</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-6">6</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-7">7</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-8">8</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-9">9</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-10">10</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-11">11</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-12">12</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-13">13</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-14">14</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-15">15</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-16">16</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-17">17</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-18">18</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-19">19</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-20">20</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-21">21</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-22">22</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-23">23</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-24">24</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-25">25</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-26">26</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-27">27</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-28">28</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-29">29</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-30">30</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-31">31</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-32">32</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-33">33</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-34">34</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-35">35</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-36">36</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-37">37</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-38">38</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-39">39</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-40">40</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-41">41</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-42">42</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-43">43</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-44">44</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-45">45</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-46">46</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-47">47</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-48">48</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-49">49</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-50">50</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-51">51</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-52">52</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-53">53</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-54">54</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-55">55</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-56">56</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-57">57</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-58">58</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-59">59</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-60">60</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-61">61</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-62">62</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-63">63</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-64">64</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-65">65</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-66">66</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-67">67</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-68">68</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-69">69</div><div class="crayon-num" data-line="crayon-5a0c2d06c8e81636895333-70">70</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-1"><span class="crayon-p">#include <iostream></span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-2"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-3"><span class="crayon-r">using</span><span class="crayon-h"> </span><span class="crayon-t">namespace</span><span class="crayon-h"> </span><span class="crayon-v">std</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-4"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-5"><span class="crayon-p">#include "BTree.h"</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-6"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-7"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-8"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">main</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-9"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-10"><span class="crayon-h"> </span><span class="crayon-v">BTree</span><span class="crayon-o"><</span><span class="crayon-t">int</span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-e">bt</span><span class="crayon-sy">(</span><span class="crayon-cn">4</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-11"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-12"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">21</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-13"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">48</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-14"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">72</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-15"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">12</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-16"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">22</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-17"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">50</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-18"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">34</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-19"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">42</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-20"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">60</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-21"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">67</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-22"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">89</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-23"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">insert</span><span class="crayon-sy">(</span><span class="crayon-cn">13</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-24"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-25"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-26"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 50\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-27"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">50</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-28"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-29"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 72\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-30"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">72</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-31"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-32"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 89\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-33"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">89</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-34"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-35"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 67\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-36"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">67</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-37"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-38"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-39"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 48\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-40"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">48</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-41"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-42"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 60\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-43"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">60</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-44"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-45"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 42\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-46"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">42</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-47"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-48"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 22\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-49"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">22</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-50"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-51"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 34\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-52"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">34</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-53"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-54"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-55"><span class="crayon-h"> </span><span class="crayon-r">cout</span><span class="crayon-h"> </span><span class="crayon-o"><<</span><span class="crayon-h"> </span><span class="crayon-s">"delete 21\n\n"</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-56"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">remove</span><span class="crayon-sy">(</span><span class="crayon-cn">21</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-57"><span class="crayon-h"> </span><span class="crayon-v">bt</span><span class="crayon-sy">.</span><span class="crayon-e">display</span><span class="crayon-sy">(</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-58"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-59"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-60"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-61"><span class="crayon-h"> </span><span class="crayon-c">// int i;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-62"><span class="crayon-h"> </span><span class="crayon-c">// for (i = 0; i < 30; ++i)</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-63"><span class="crayon-h"> </span><span class="crayon-c">// bt.insert(i);</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-64"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-65"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-66"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-67"><span class="crayon-h"> </span><span class="crayon-e">printf</span><span class="crayon-sy">(</span><span class="crayon-s">"233"</span><span class="crayon-sy">)</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-68"> </div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-69"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-cn">0</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a0c2d06c8e81636895333-70"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p> </p>
</div>
</article>
<div class="social-main">
<div class="post-like">
<a href="javascript:;" data-action="ding" data-id="2251" class="specsZan ">点赞 <span class="count">
0</span>
</a>
</div>
<div class="reward-button"><a href="http://www.yalewoo.com/denote" target="_blank">赏</a>
<span class="reward-code">
<span class="alipay-code"> <img class="alipay-img wdp-appear" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/alipay.png"><b>支付宝打赏</b> </span> <span class="wechat-code"> <img class="wechat-img wdp-appear" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/wechatpay.png"><b>微信打赏</b> </span>
</span>
</div>
<div class="post-like">
<a id="fenxianganniu" onClick="show_bdsharebox();">分享
</a>
</div>
<div class="bdsharebuttonbox" id="bdsharebuttonbox">
</div>
</div>
<div class="reward-notice">
<p class="">如果文章对你有帮助，欢迎点赞或打赏（金额不限）。你的打赏将全部用于支付网站服务器费用和提高网站文章质量，谢谢支持。</p>
</div>
<div class="article-copyright">
<b> 版权声明: </b>
<p> 本文由 <a href="http://www.yalewoo.com/author/yalewoo" title="由yalewoo发布" rel="author">yalewoo</a> 原创，商业转载请联系作者获得授权。 <br>非商业转载请注明作者 <a href="http://www.yalewoo.com/author/yalewoo" title="由yalewoo发布" rel="author">yalewoo</a> 或 <a href="http://www.yalewoo.com/" title="雅乐网" ?>雅乐网</a> ，并附带本文链接：<br><a href="http://www.yalewoo.com/data_structure_cpp_6_b-tree.html" title=常用数据结构C++实现(6)：B树>http://www.yalewoo.com/data_structure_cpp_6_b-tree.html</a></p>
</div>
<div class="post-navigation">
<div class="post-previous">
<p>上一篇：</p>
<a href="http://www.yalewoo.com/data_structure_cpp_5_splay_binary_tree.html" rel="prev">常用数据结构C++实现(5)：伸展树</a> </div>
<div class="post-next">
<p>下一篇：</p>
<a href="http://www.yalewoo.com/red_black_tree_a_b-tree_view.html" rel="next">从B-树角度理解红黑树背后的原理</a> </div>
</div>
<div class="related_posts">
<p>与 <a href="http://www.yalewoo.com/tag/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84" rel="tag">数据结构</a>, <a href="http://www.yalewoo.com/tag/%e6%a0%91" rel="tag">树</a> 相关的文章</p>
<ul>
<li><a rel="bookmark" href="http://www.yalewoo.com/data_structure_cpp_7_red_black_tree.html" title="常用数据结构C++实现(7)：红黑树" target="_blank">常用数据结构C++实现(7)：红黑树</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/red_black_tree_a_b-tree_view.html" title="从B-树角度理解红黑树背后的原理" target="_blank">从B-树角度理解红黑树背后的原理</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/data_structure_cpp_5_splay_binary_tree.html" title="常用数据结构C++实现(5)：伸展树" target="_blank">常用数据结构C++实现(5)：伸展树</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/data_structure_cpp_4_avl_tree.html" title="常用数据结构C++实现(4)：AVL树" target="_blank">常用数据结构C++实现(4)：AVL树</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/binary_tree_graphical_display.html" title="二叉树的图形化显示" target="_blank">二叉树的图形化显示</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/data_structure_cpp_3_binary_tree_and_binary_search_tree.html" title="常用数据结构C++实现(3)：二叉树和二叉搜索树" target="_blank">常用数据结构C++实现(3)：二叉树和二叉搜索树</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/data_structure_cpp_2_stack_and_queue.html" title="常用数据结构C++实现(2)：栈和队列" target="_blank">常用数据结构C++实现(2)：栈和队列</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/data_structure_cpp_1_vector_and_list.html" title="常用数据结构C++实现(1)：向量和列表" target="_blank">常用数据结构C++实现(1)：向量和列表</a></li>
</ul>
</div>
<div class="comments-template">
<div id="comments" class="comments-area">
<div id="respond" class="comment-respond">
<h3 id="reply-title" class="comment-reply-title">我要评论 <small><a rel="nofollow" id="cancel-comment-reply-link" href="/data_structure_cpp_6_b-tree.html#respond" style="display:none;">取消回复</a></small></h3> <form action="http://www.yalewoo.com/wp-comments-post.php" method="post" id="commentform" class="comment-form">
<p class="comment-form-comment"><textarea id="comment" name="comment" cols="45" rows="8" maxlength="65525" aria-required="true" required="required"></textarea></p>
<script type="text/javascript" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/show_smilies.js"></script>
<div class="ylw_comment_toolbar">
<a class="button-insert-smilies" id="button-insert-smilies" title="插入表情" onClick="show_smilies();"></a>
</div>
<div class="ylw_smilies_box_wrapper">
<div class="ylw_smilies_box" id="ylw_smilies_box">
</div>
</div><div class="comment-name-email-url"><p class="comment-form-author"><label for="author">姓名</label><input id="author" name="author" type="text" value="" size="30" /> </p>
<p class="comment-form-email"><label for="email">邮箱</label><input id="email" name="email" type="text" value="" size="30" /> </p>
<p class="comment-form-url"><label for="url">网址</label><input id="url" name="url" type="text" value="" size="30" /></p></div><div class='comment_yzm'>验证码*： 4 + 7 = <input type='text' name='sum' class='math_textfield' required='required' value='' size='25' tabindex='4'><input type='hidden' name='num1' value='4'><input type='hidden' name='num2' value='7'></div><div class="comment-right"><div class="comment-submit-button">
<p class="form-submit"><input name="submit" type="submit" id="submit" class="submit" value="发表评论" /> <input type='hidden' name='comment_post_ID' value='2251' id='comment_post_ID' />
<input type='hidden' name='comment_parent' id='comment_parent' value='0' />
</p></div><div class="ylw_comment_notifyme"><input type="checkbox" name="comment_mail_notify" id="comment_mail_notify" value="comment_mail_notify" checked="checked" style="margin-left:20px;" /><label for="comment_mail_notify">有人回复时邮件通知我</label></div></div></div><div class="clear"></div> </form>
</div><!-- #respond -->
</div><!-- .comments-area -->
</div>
</section>
</div>
<footer id="footer">
Copyright © <a title="雅乐网" href="http://www.yalewoo.com">雅乐网</a> /<a title="自豪地采用WordPress" href="https://cn.wordpress.org" target="_blank">WordPress</a> / <a title="YLW3.0主题" href="http://www.yalewoo.com/ylw3.html" target="_blank">YLW3.0</a> / <a title="老薛主机" href="https://my.laoxuehost.net/aff.php?aff=2518" target="_blank">老薛主机</a> / <a title="七牛云存储" href="https://portal.qiniu.com/signup?code=3li1yeb2ph1ea" target="_black">七牛云存储</a>
<div id="footer_menu">
<div class="menu-%e5%ba%95%e9%83%a8-container"><ul id="menu-%e5%ba%95%e9%83%a8" class="menu"><li id="menu-item-655" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-655"><a target="_blank" href="http://www.yalewoo.com/sitemap.xml">站点地图</a></li>
</ul></div> </div>
<div id="cnzztongji">
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1252889774'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s5.cnzz.com/stat.php%3Fid%3D1252889774%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));</script>
<script>
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "//hm.baidu.com/hm.js?e937132d7f7e86dfb5300ce1ab2c25f7";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
</script>
</div>
</footer>
<script type="text/javascript" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/backtop.js"></script>
<script type='text/javascript' src='http://www.yalewoo.com/wp-includes/js/comment-reply.min.js?ver=4.7.7'></script>
</body>
</html>
<!-- Dynamic page generated in 1.368 seconds. -->
<!-- Cached page generated by WP-Super-Cache on 2017-11-15 20:03:19 -->
<!-- Compression = gzip -->
<!-- super cache -->