数据结构备忘录：B树的插入和删除

B树的删除(仅考虑阶数m>=3的情形)

在非叶节点中删除关键码，只需从关键码右侧指针指向的子树中寻找最小关键码(沿最左侧指针向下走到叶节点，叶节点最左侧关键码即是)替换该关键码，并从最小关键码所在叶节点删除该最小关键码即可。这样只讨论在叶节点中删除关键码。

在叶节点中删除给定关键码，先删去该关键码及其右侧空指针，然后若该叶节点为根节点，则删除操作结束(删除后的B树可能为空树)，若该叶节点不为根节点且关键码数大于等于ceil(m/2)-1,则删除操作结束。若该叶节点不为根节点且关键码数等于ceil(m/2)-2，则令该叶节点为当前节点，然后

设删除过程中当前节点关键数等于ceil(m/2)-2.

若当前节点为根节点且关键码数为0，则令根节点指针指向根节点唯一子树,删除根节点，删除操作结束

若当前节点不为根节点，则若该节点有右兄弟节点且右兄弟节点关键码数大于等于ceil(m/2)，则将父节点指向当前节点的指针右侧关键码下移至当前节点最右侧，将右兄弟节点最左侧指针移至当前节点最右侧，最后将右兄弟最左侧关键码上移至父节点指向其指针的左侧，删除操作结束。

若当前节点不为根节点，有右兄弟且右兄弟关键码数等于ceil(m/2)-1,则将父节点中指向当前节点的指针右侧关键码下移至当前节点最右侧，然后将右兄弟完整拼接至当前节点右侧，随后删除右兄弟节点和父节点中指向它的指针。此时父节点关键码子树数减一，若父节点为根节点且关键码数为0则回溯至父节点；若父节点不为根节点且关键码数大于等于ceil(m/2)-1，则删除操作结束；若父节点不为根节点且关键码数等于ceil(m/2)-2,则回溯至父节点

若当前节点不为根节点，没有右兄弟节点但有左兄弟节点，且左兄弟节点关键码数大于等于ceil(m/2),则将父节点中指向当前节点的指针左侧关键码下移至当前节点最左端，左兄弟最右侧关键码上移至父节点中指向它的指针右侧关键码位置，左兄弟最右侧指针移至当前节点最左端，随后删除操作结束

若当前节点不为根节点，没有右兄弟但有左兄弟，且左兄弟关键码数等于ceil(m/2)-1,则将父节点中指向当前节点的指针左侧关键码下移至当前节点最左端，左兄弟完整拼接至当前节点左侧，删除左兄弟和父节点中指向它的指针，此时父节点关键码子树数减一，若父节点为根节点且关键码数为0则回溯至父节点；若父节点不为根节点且关键码数大于等于ceil(m/2)-1，则删除操作结束；若父节点不为根节点且关键码数等于ceil(m/2)-2,则回溯至父节点

 

B树的插入(仅考虑阶数m>=3的情形)

在空树中插入直接新建根节点，两指针域置空，填入关键码,再令root指向根节点

若在非空树中插入

那么仅在叶节点上插入，通过搜索在叶节点中找到插入位置，将关键码和空指针构成的二元组插入至叶节点，若插入后叶节点关键码数小于等于m-1则插入结束，否则令叶节点为当前节点

现设插入过程中当前节点关键码数为m，以当前节点从左至右第ceil(m/2)个关键码为分割点将当前节点分隔为左右两部分(即分割点左侧和右侧的部分),左侧分割部分为原当前节点，若原当前节点为根节点，则直接新建根节点，两指针域分别指向左右分割部分，中间关键码即为原当前节点第ceil(m/2)个关键码，令root指向新根节点插入结束。

若原当前节点不为根节点，则将右侧分割部分的指针和原当前节点第ceil(m/2)个关键码构成的二元组插入至父节点中原当前节点对应的二元组右侧，此时父节点关键码子树数增一，若父节点关键码数小于等于m-1则插入结束，若父节点关键码数等于m,则以父节点为当前节点，回溯处理

 插入和删除的C++实现(如有错误欢迎指出)

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <map>
  4 #include <stack>
  5 #include <vector>
  6 using namespace std;
  7 
  8 const int M = 4;   //B树阶数
  9 template <typename T>
 10 struct BTreeNode
 11 {
 12     BTreeNode *p = nullptr;   
 13     map<T, BTreeNode<T> *> keyptrmap;   //节点数据域和指针域
 14 };
 15 
 16 template <typename T>
 17 pair<typename map<T, BTreeNode<T> *>::iterator, bool> SerachBTreeNode(BTreeNode<T> *ptr, pair<typename map<T, BTreeNode<T> *>::iterator, bool> d)  //返回值：尾后+fasle表示第一指针,尾后+true表示失败,非尾后+true即为对应指针
 18 {  
 19     typename map<T, BTreeNode<T> *>::iterator m;                                                                                          //实参pair:尾后+false表示从第一指针后一指针开始搜索,尾后+true表示从头搜索,非尾后+true表示从非尾后后一位置开始搜索
 20     if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
 21     {
 22         if (ptr->p != nullptr)
 23             return { d.first, false };
 24         m = ptr->keyptrmap.begin();
 25     }
 26     else if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), false))
 27     {
 28         m = ptr->keyptrmap.begin();
 29     }
 30     else
 31     {
 32         m = d.first;
 33         ++m;
 34     }
 35 
 36     for (; m != ptr->keyptrmap.end(); ++m)
 37     {
 38         if (m->second != nullptr)
 39             return { m, true };
 40     }
 41     return { m, true };
 42 }
 43 
 44 template <typename T>
 45 bool isBTree(BTreeNode<T> *root)  //判断给定多叉树是否为B树
 46 {
 47     struct temp
 48     {
 49         T min;  //节点某子树中最小节点值
 50         T max;  //节点某子树中最大节点值
 51         T nodemin;  //节点代表子树中最小值
 52         T nodemax;  //节点代表子树中最大值
 53     };
 54     struct memory
 55     {
 56         BTreeNode<T> *p;
 57         pair<map<T, BTreeNode<T> *>::iterator, bool> direction;
 58         temp minmax;
 59         memory(BTreeNode<T> *p, const pair<map<T, BTreeNode<T> *>::iterator, bool> &d) :p(p), direction(d) {}
 60     };
 61 
 62     BTreeNode<T> *ptr = root;
 63     pair<map<T, BTreeNode<T> *>::iterator, bool> d(ptr->keyptrmap.end(), true);
 64     BTreeNode<T> *const dest = ptr;
 65     stack<memory> arrange;
 66     bool TF = false;
 67     int level = 0;
 68     int beforelevel = 0;
 69     while (true)
 70     {
 71         if (SerachBTreeNode(ptr, d) == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
 72         {
 73             if (ptr == dest)
 74             {
 75                 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
 76                 {
 77                     if (1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M-1)
 78                       return true;
 79                     else
 80                     {
 81                         cout << "当前树只有根节点,但根节点子树数量不符合要求,非B树"<<endl;
 82                         return false;
 83                     }
 84                 }    
 85                 else
 86                 {
 87                     if (1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M - 1)
 88                     {
 89                         typename map<T, BTreeNode<T> *>::iterator temp = ptr->keyptrmap.end();
 90                         --temp;
 91                         if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
 92                         {
 93                             if (arrange.top().minmax.min > temp->first)
 94                             {
 95                                 return true;
 96                             }
 97                             else
 98                             {
 99                                 cout << "当前树不是" << M << "路搜索树,非B树" << endl;
100                                 return false;
101                             }
102                         }
103                         else
104                         {
105                             cout << "失败节点不在同一层,非B树" << endl;
106                             return false;
107                         }
108                     }
109                     else
110                     {
111                         cout << "当前树根节点子树数量不符合要求,非B树";
112                         return false;
113                     }
114                 }
115             }
116             else
117             {
118                 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
119                 {
120                     ++level;
121                     if (TF == false)
122                     {
123                         beforelevel = level;
124                         TF = true;
125                     }
126                     else
127                     {
128                         if (level != beforelevel)
129                         {
130                             cout << "失败节点不在同一层,非B树" << endl;
131                             return false;
132                         }
133                         beforelevel = level;
134                     }
135 
136                     if ((M + 1) / 2 - 1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M - 1)
137                     {
138                         typename map<T, BTreeNode<T> *>::iterator temp = arrange.top().p->keyptrmap.end();
139                         --temp;
140                         if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(arrange.top().p->keyptrmap.end(), false))
141                         {
142                             arrange.top().minmax.nodemin = ptr->keyptrmap.begin()->first;
143                             arrange.top().minmax.min = ptr->keyptrmap.begin()->first;
144                             typename map<T, BTreeNode<T> *>::iterator it = ptr->keyptrmap.end();
145                             --it;
146                             arrange.top().minmax.max = it->first;
147                         }
148                         else if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
149                         {
150                             typename map<T, BTreeNode<T> *>::iterator it = ptr->keyptrmap.end();
151                             --it;
152                             arrange.top().minmax.nodemax = it->first;
153                             arrange.top().minmax.min = ptr->keyptrmap.begin()->first;
154                             arrange.top().minmax.max = it->first;
155                         }
156                         else
157                         {
158                             arrange.top().minmax.min = ptr->keyptrmap.begin()->first;
159                             typename map<T, BTreeNode<T> *>::iterator it = ptr->keyptrmap.end();
160                             --it;
161                             arrange.top().minmax.max = it->first;
162                         }
163                     }
164                     else
165                     {
166                         cout << "当前树叶节点数量不符合要求,非B树" << endl;
167                         return false;
168                     }
169                 }
170                 else
171                 {
172                     if ((M + 1) / 2 - 1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M - 1)
173                     {
174                         typename map<T, BTreeNode<T> *>::iterator temp = ptr->keyptrmap.end();
175                         --temp;
176                         if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
177                         {
178                             if (arrange.top().minmax.min > temp->first)
179                             {
180                                 T key1 = arrange.top().minmax.nodemin;
181                                 T key2 = arrange.top().minmax.nodemax;
182                                 arrange.pop();
183                                 arrange.top().minmax.min = key1;
184                                 arrange.top().minmax.max = key2;
185                                 typename map<T, BTreeNode<T> *>::iterator temp = arrange.top().p->keyptrmap.end();
186                                 --temp;
187                                 if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(arrange.top().p->keyptrmap.end(), false))
188                                 {
189                                     arrange.top().minmax.nodemin = arrange.top().minmax.min;
190                                 }
191                                 else if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
192                                 {
193                                     arrange.top().minmax.nodemax = arrange.top().minmax.max;
194                                 }
195                             }
196                             else
197                             {
198                                 cout << "当前树不是" << M << "路搜索树,非B树" << endl;
199                                 return false;
200                             }
201                         }
202                         else
203                         {
204                             cout << "失败节点不在同一层,非B树" << endl;
205                             return false;
206                         }
207                     }
208                     else
209                     {
210                         cout << "当前树分支节点子树数量不符合要求,非B树" << endl;
211                         return false;
212                     }
213                 }
214                 --level;
215                 ptr = arrange.top().p;
216                 d = arrange.top().direction;
217             }
218         }
219         else
220         {
221             BTreeNode<T> *interval = nullptr;
222             if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
223             {
224                 if (SerachBTreeNode(ptr, d) != pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), false))
225                 {
226                     cout << "失败节点不在同一层,非B树" << endl;
227                     return false;
228                 }
229                 arrange.push(memory(ptr, SerachBTreeNode(ptr, d)));
230                 interval = ptr->p;
231                 ++level;
232             }
233             else
234             {
235                 typename map<T, BTreeNode<T> *>::iterator temp = SerachBTreeNode(ptr, d).first;
236                 if (d.first == ptr->keyptrmap.end())
237                 {
238                     if (temp == ptr->keyptrmap.begin())
239                     {
240                         if (!(arrange.top().minmax.max < temp->first))
241                         {
242                             cout << "当前树不是" << M << "路搜索树,非B树" << endl;
243                             return false;
244                         }
245                     }
246                     else
247                     {
248                         cout << "失败节点不在同一层,非B树"<<endl;
249                         return false;
250                     }
251                 }
252                 else
253                 {
254                     --temp;
255                     if (temp == d.first)
256                     {
257                         ++temp;
258                         if (!(arrange.top().minmax.max < temp->first && arrange.top().minmax.min > d.first->first))
259                         {
260                             cout << "当前树不是" << M << "路搜索树,非B树" << endl;
261                             return false;
262                         }
263                     }
264                     else
265                     {
266                         cout << "失败节点不在同一层,非B树" << endl;
267                         return false;
268                     }
269                 }
270                 
271                 arrange.top().direction = pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true);
272                 interval = temp->second;
273             }
274             ptr = interval;
275             d = pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true);
276         }
277     }
278 }
279 
280 template <typename T>
281 BTreeNode<T> *InsertBTree(BTreeNode<T> *root, T key)   //B树插入函数
282 {
283     if (root == nullptr)
284     {
285         root = new BTreeNode<T>;
286         root->keyptrmap.insert(make_pair(key, nullptr));
287         return root;
288     }
289     else
290     {
291         BTreeNode<T> *current = root;
292         stack<pair<BTreeNode<T> *, map<T, BTreeNode<T> *>::iterator>> stackforback;
293 
294         while (true)
295         {
296             typename map<T, BTreeNode<T> *>::iterator scankey = current->keyptrmap.begin();
297             while (key > scankey->first)
298             {
299                 ++scankey;
300                 if (scankey == current->keyptrmap.end())
301                 {
302                     break;
303                 }
304             }
305             if (scankey != current->keyptrmap.end())
306             {
307                 if (scankey->first == key)
308                 {
309                     cout << "关键码" << key << "已存在，插入失败" << endl;
310                     return root;
311                 }
312                 else
313                 {
314                     if (current->p == nullptr)
315                     {
316                         current->keyptrmap.insert(make_pair(key, nullptr));
317                         break;
318                     }
319                     else
320                     {
321                         stackforback.push(make_pair(current, scankey));
322                         if (scankey != current->keyptrmap.begin())
323                         {
324                             --scankey;
325                             current = scankey->second;
326                         }
327                         else
328                         {
329                             current = current->p;
330                         }
331                     }
332                 }
333             }
334             else
335             {
336                 if (current->p == nullptr)
337                 {
338                     current->keyptrmap.insert(make_pair(key, nullptr));
339                     break;
340                 }
341                 else
342                 {
343                     stackforback.push(make_pair(current, scankey));
344                     --scankey;
345                     current = scankey->second;
346                 }
347             }
348         }
349 
350         if (current->keyptrmap.size() <= M - 1)
351         {
352             return root;
353         }
354         else
355         {
356             while (true)
357             {
358                 BTreeNode<T> *ptr = new BTreeNode<T>;
359                 typename map<T, BTreeNode<T> *>::iterator temp = current->keyptrmap.begin();
360                 ptr->p = current->p;
361                 while (ptr->keyptrmap.size() < (M + 1) / 2 - 1)
362                 {
363                     ptr->keyptrmap.insert(*temp);
364                     temp = current->keyptrmap.erase(temp);
365                 }
366                 current->p = temp->second;
367 
368                 if (stackforback.empty() == true)
369                 {
370                     root = new BTreeNode<T>;
371                     root->p = ptr;
372                     root->keyptrmap.insert(make_pair(temp->first, current));
373                     current->keyptrmap.erase(temp);
374                     return root;
375                 }
376                 else
377                 {
378                     stackforback.top().first->keyptrmap.insert(make_pair(temp->first, current));
379                     current->keyptrmap.erase(temp);
380                     typename map<T, BTreeNode<T> *>::iterator it = stackforback.top().second;
381                     --it; 
382                     if (it == stackforback.top().first->keyptrmap.begin())
383                     {
384                         stackforback.top().first->p = ptr;
385                     }
386                     else
387                     {
388                         --it;
389                         it->second = ptr;
390                     }
391                     if (stackforback.top().first->keyptrmap.size() <= M - 1)
392                     {
393                         return root;
394                     }
395                     else
396                     {
397                         current = stackforback.top().first;
398                         stackforback.pop();
399                     }
400                 }
401             }
402         }
403     }
404 }
405 
406 template <typename T>
407 BTreeNode<T> *DelBTree(BTreeNode<T> *root, T key)   //B树删除函数
408 {
409     BTreeNode<T> *current = root;
410     stack<pair<BTreeNode<T> *, map<T, BTreeNode<T> *>::iterator>> stackforback;
411 
412     while (true)
413     {
414         typename map<T, BTreeNode<T> *>::iterator scankey = current->keyptrmap.begin();
415         while (key > scankey->first)
416         {
417             ++scankey;
418             if (scankey == current->keyptrmap.end())
419             {
420                 break;
421             }
422         }
423         if (scankey != current->keyptrmap.end())
424         {
425             if (scankey->first == key)
426             {
427                 if (current->p == nullptr)
428                 {
429                     current->keyptrmap.erase(scankey);
430                 }
431                 else
432                 {
433                     stackforback.push(make_pair(current, ++scankey));
434                     --scankey;
435                     BTreeNode<T> *q = scankey->second;
436                     while (q->p != nullptr)
437                     {    
438                         stackforback.push(make_pair(q, q->keyptrmap.begin()));
439                         q = q->p;
440                     }
441                     BTreeNode<T> *temp = scankey->second;
442                     current->keyptrmap.erase(scankey);
443                     current->keyptrmap.insert(make_pair(q->keyptrmap.begin()->first, temp));
444                     q->keyptrmap.erase(q->keyptrmap.begin());
445                     current = q;
446                 }
447                 break;
448             }
449             else
450             {
451                 if (current->p == nullptr)
452                 {
453                     cout << "关键字" << key << "不存在，删除失败" << endl;
454                     return root;
455                 }
456                 else
457                 {
458                     stackforback.push(make_pair(current, scankey));
459                     if (scankey != current->keyptrmap.begin())
460                     {
461                         --scankey;
462                         current = scankey->second;
463                     }
464                     else
465                     {
466                         current = current->p;
467                     }
468                 }
469             }
470         }
471         else
472         {
473             if (current->p == nullptr)
474             {
475                 cout << "关键字" << key << "不存在，删除失败" << endl;
476                 return root;
477             }
478             else
479             {
480                 stackforback.push(make_pair(current, scankey));
481                 --scankey;
482                 current = scankey->second;
483             }
484         }
485     }
486 
487     if (current == root)
488     {
489         if (current->keyptrmap.empty() == true)
490         {
491             delete current;
492             return nullptr;
493         }
494         else
495         {
496             return current;
497         }
498     }
499     else
500     {
501         if (current->keyptrmap.size() >= (M + 1) / 2 - 1)
502         {
503             return root;
504         }
505         else
506         {
507             while (true)
508             {
509                 if (current == root)
510                 {
511                     current = current->p;
512                     delete root;
513                     return current;
514                 }
515                 else
516                 {
517                     typename map<T, BTreeNode<T> *>::iterator temp = stackforback.top().second;
518                     if (temp != stackforback.top().first->keyptrmap.end())
519                     {
520                         if (temp->second->keyptrmap.size() >= (M + 1) / 2)
521                         {
522                             current->keyptrmap.insert(make_pair(temp->first, temp->second->p));
523                             BTreeNode<T> *ptr = temp->second;
524                             stackforback.top().first->keyptrmap.erase(temp);
525                             stackforback.top().first->keyptrmap.insert(make_pair(ptr->keyptrmap.begin()->first, ptr));
526                             ptr->p = ptr->keyptrmap.begin()->second;
527                             ptr->keyptrmap.erase(ptr->keyptrmap.begin());
528                             return root;
529                         }
530                         else
531                         {
532                             current->keyptrmap.insert(make_pair(temp->first, temp->second->p));
533                             current->keyptrmap.insert(temp->second->keyptrmap.begin(), temp->second->keyptrmap.end());
534                             delete temp->second;
535                             stackforback.top().first->keyptrmap.erase(temp);
536                             if (stackforback.top().first == root)
537                             {
538                                 if (stackforback.top().first->keyptrmap.size() == 0)
539                                 {
540                                     current = stackforback.top().first;
541                                     stackforback.pop();
542                                 }
543                                 else
544                                 {
545                                     return root;
546                                 }
547                             }
548                             else
549                             {
550                                 if (stackforback.top().first->keyptrmap.size() >= (M + 1) / 2 - 1)
551                                 {
552                                     return root;
553                                 }
554                                 else
555                                 {
556                                     current = stackforback.top().first;
557                                     stackforback.pop();
558                                 }
559                             }
560                         }
561                     }
562                     else
563                     {
564                         --temp;
565                         BTreeNode<T> *ptr = nullptr;
566                         if (temp != stackforback.top().first->keyptrmap.begin())
567                         {
568                             typename map<T, BTreeNode<T> *>::iterator before = temp;
569                             --before;
570                             ptr = before->second;
571                         }
572                         else
573                         {
574                             ptr = stackforback.top().first->p;
575                         }
576 
577                         if (ptr->keyptrmap.size() >= (M + 1) / 2)
578                         {
579                             current->keyptrmap.insert(make_pair(temp->first, current->p));
580                             typename map<T, BTreeNode<T> *>::iterator left = ptr->keyptrmap.end();
581                             --left;
582                             current->p = left->second;
583                             stackforback.top().first->keyptrmap.erase(temp);
584                             stackforback.top().first->keyptrmap.insert(make_pair(left->first, current));
585                             ptr->keyptrmap.erase(left);
586                             return root;
587                         }
588                         else
589                         {
590                             ptr->keyptrmap.insert(make_pair(temp->first, current->p));
591                             ptr->keyptrmap.insert(current->keyptrmap.begin(), current->keyptrmap.end());
592                             delete current;
593                             stackforback.top().first->keyptrmap.erase(temp);
594 
595                             if (stackforback.top().first == root)
596                             {
597                                 if (stackforback.top().first->keyptrmap.size() == 0)
598                                 {
599                                     current = stackforback.top().first;
600                                     stackforback.pop();
601                                 }
602                                 else
603                                 {
604                                     return root;
605                                 }
606                             }
607                             else
608                             {
609                                 if (stackforback.top().first->keyptrmap.size() >= (M + 1) / 2 - 1)
610                                 {
611                                     return root;
612                                 }
613                                 else
614                                 {
615                                     current = stackforback.top().first;
616                                     stackforback.pop();
617                                 }
618                             }
619                         }
620                     }
621                 }
622             }
623         }
624     }
625 }
626 
627 int main()
628 {
629     vector<int> seq{ 2, 7, 5, 19, 10, 18, 16, 12, 11, 15, 13, 14, 21, 29, 25, 20, 22, 28, 23, 26 };
630     BTreeNode<int> *root = nullptr;
631     for (vector<int>::const_iterator p = seq.cbegin(); p != seq.cend(); ++p)
632     {
633         cout << "插入节点" << *p << endl;
634         root = InsertBTree(root, *p);
635         cout << endl;
636         if (isBTree(root) == true)
637         {
638             cout << "当前树是B树";
639             cout << endl;
640         }
641         else
642         {
643             cerr << "错误当前树不是B树!" << endl;
644             exit(0);
645         }
646     }
647     cout << endl;
648     for (vector<int>::const_iterator p = seq.cbegin(); p != seq.cend(); ++p)
649     {
650         cout << "删除节点" << *p << endl;
651         root = DelBTree(root, *p);
652         if (root != nullptr)
653         {
654             if (isBTree(root) == true)
655             {
656                 cout << "当前树是B树";
657                 cout << endl;
658             }
659             else
660             {
661                 cerr << "错误当前树不是B树!" << endl;
662                 exit(0);
663             }
664         }
665         else
666             cout << "NULL";
667         cout << endl;
668     }
669     return 0;
670 }

运行结果：