本文属于原创，转载请注明来源。
在上一篇博文中，详细介绍了2-3树的操作（具体地址：），那么对于更多教科书上更为普遍的2-3-4树，在这里也给出 树的定义、节点的定义、插入、查找、删除和遍历等操作的源代码实现。
关于2-3-4树的文字定义，网上很多，可自行百度，这里不再重复论述。但看了很多博文，关于插入等操作的实现较多，基本上没有实现删除操作的。因此本博文给出完整版的2-3-4树的插入、删除、查找及遍历等源代码。
另，2-3-4树代码的实现，与2-3树非常类似，故关于代码的分析，请参考2-3树（）的介绍，这里仅给出简要说明。
如果节点允许的最大元素数量超过3个，非叶子节点最大孩子数量超过4个，就成了多叉树，后续有机会分享一下一个关于8叉树的实现。
本代码由dart语言实现，关于dart，一门类似Java、JavaScript的语言，也是现在比较流行的flutter的后台语言，有兴趣的同学可以去dart官网了解：
https://dart.dev
闲话少说，上代码。
1 // 树的定义 2-3-4树 2 class QuaternaryTree> { 3 QuaterNode _root; 4 int _elementsCount; 5 6 factory QuaternaryTree.of(Iterable > elements) { 7 var tree = QuaternaryTree (); 8 for (var e in elements) tree.insert(e); 9 return tree; 10 } 11 12 QuaternaryTree() : _elementsCount = 0; 13 14 int get elementsCount => _elementsCount; 15 QuaterNode get root => _root; 16 17 // 计算树高 18 int get height { 19 var h = 0, c = root; 20 while (c != null) { 21 h++; 22 c = c.isNotLeaf ? c.branches[0] : null; 23 } 24 return h; 25 } 26 27 bool get isEmpty => _root == null; 28 29 bool contains(E value) => find(value) != null; 30 31 // 查找树中是否存在某个值 32 // 若找到，返回包含此值的树节点，否则返回null 33 QuaterNode find(E value) { 34 var c = root; 35 while (c != null) { 36 var i = 0; 37 while (i < c.size && c.items[i].compareTo(value) < 0) i++; 38 if (i < c.size && c.items[i] == value) break; 39 c = c.isNotLeaf ? c.branches[i] : null; 40 } 41 return c; 42 } 43 44 // 插入新的值，如果值已经存在，则不做任何操作 45 // 插入始终在叶子节点进行 46 void insert(E value) { 47 var c = root, i = 0; 48 while (c != null) { 49 i = 0; 50 while (i < c.size && c.items[i].compareTo(value) < 0) i++; 51 if (i < c.size && c.items[i] == value) return; 52 if (c.isLeaf) break; 53 c = c.branches[i]; 54 } 55 if (c != null) { 56 c.items.insert(i, value); 57 58 // 判断插入后是否需要修复 59 if (c.isOverflow) _fixAfterIns(c); 60 } else { 61 _root = QuaterNode([value]); 62 } 63 _elementsCount++; 64 } 65 66 // 删除指定值 67 bool delete(E value) { 68 // 首先查找该值 69 var d = find(value); 70 // 若不存在，直接返回 71 if (d == null) return false; 72 73 // 查找该值在节点中的索引顺序 74 var i = d.find(value); 75 76 // 如果节点不是叶子节点，则用后继节点的值替代该值 77 // 这样删除操作将转移为删除叶子节点的值 78 if (d.isNotLeaf) { 79 var s = _successor(d.branches[i + 1]); 80 d.items[i] = s.items[0]; 81 d = s; 82 i = 0; 83 } 84 d.items.removeAt(i); 85 _elementsCount--; 86 87 // 根据2-3-4树的定义，节点不能为空，因此判断删除后是否需要修复 88 if (d.items.isEmpty) _fixAfterDel(d); 89 return true; 90 } 91 92 // 遍历树 93 void traverse(void func(List items)) { 94 if (!isEmpty) _traverse(_root, func); 95 } 96 97 // 插入修复 98 // 注意，插入修复时，采用节点分裂的形式进行修复； 99 // 分裂出来的新的父节点需要被上层节点吸收（如果存在上层节点的话）100 void _fixAfterIns(QuaterNode c) {101 while (c != null && c.isOverflow) {102 var t = _split(c);103 c = t.parent != null ? _absorb(t) : null;104 }105 }106 107 // 节点分裂，由于分裂->吸收，可能会递归分裂；108 // 因此需要注意根节点的更新判断以及子节点的处理；109 QuaterNode _split(QuaterNode c) {110 var mid = c.size ~/ 2,111 l = QuaterNode._internal(c.items.sublist(0, mid)),112 nc = QuaterNode._internal(c.items.sublist(mid, mid + 1)),113 r = QuaterNode._internal(c.items.sublist(mid + 1));114 nc.branches.addAll([l, r]);115 l.parent = r.parent = nc;116 117 nc.parent = c.parent;118 if (c.parent != null) {119 var i = 0;120 while (c.parent.branches[i] != c) i++;121 c.parent.branches[i] = nc;122 } else {123 _root = nc;124 }125 if (c.isNotLeaf) {126 l.branches127 ..addAll(c.branches.getRange(0, mid + 1))128 ..forEach((b) => b.parent = l);129 r.branches130 ..addAll(c.branches.getRange(mid + 1, c.branches.length))131 ..forEach((b) => b.parent = r);132 }133 return nc;134 }135 136 // 上层节点吸收新分裂出来的节点，以保持树的平衡137 QuaterNode _absorb(QuaterNode c) {138 var i = 0, p = c.parent;139 while (p.branches[i] != c) i++;140 p.items.insertAll(i, c.items);141 p.branches.replaceRange(i, i + 1, c.branches);142 c.branches.forEach((b) => b.parent = p);143 return p;144 }145 146 // 查找后继节点147 QuaterNode _successor(QuaterNode p) {148 while (p.isNotLeaf) p = p.branches[0];149 return p;150 }151 152 // 删除修复153 void _fixAfterDel(QuaterNode d) {154 if (d == root) {155 _root = null;156 } else {157 var ct = 0;158 while (d.size < (1 << ct + 1) - 1 && d.parent != null) {159 // 塌缩父节点160 _collapse(d.parent);161 d = d.parent;162 ct++;163 }164 165 // 如果塌缩到了树的根，则树高减1166 // if (d.size < (1 << ct + 1) - 1) ct--;167 if (d == root) ct--;168 169 // 修剪多余的值170 var rest = _prune(d, (1 << ct + 1) - 1);171 172 // 重新展开173 _expand(d, ct);174 175 // 将刚才修剪掉的多余的值重新插入树176 for (var e in rest) insert(e);177 }178 }179 180 // 树的塌缩函数，注意递归塌缩181 void _collapse(QuaterNode p) {182 if (p.isLeaf) return;183 for (var i = p.branches.length - 1; i >= 0; i--) {184 _collapse(p.branches[i]);185 p.items.insertAll(i, p.branches[i].items);186 }187 p.branches.clear();188 }189 190 // 修剪，保留满足展开为满二叉树的最小数量的值191 List _prune(QuaterNode d, int least) {192 var t = d.size ~/ least, rest = [];193 if (t < 2) {194 rest.addAll(d.items.getRange(least, d.size));195 d.items.removeRange(least, d.size);196 } else {197 // 跳跃修剪，以保证二次插入时分裂的次数较少198 var list = [];199 for (var i = 0; i < d.size; i++) {200 if (i % t == 0 && list.length < least)201 list.add(d.items[i]);202 else203 rest.add(d.items[i]);204 }205 d.items = list;206 }207 _elementsCount -= rest.length;208 return rest;209 }210 211 // 递归展开修剪后的节点，ct代表展开的层数或高度212 void _expand(QuaterNode p, int ct) {213 if (ct == 0) return;214 p = _split(p);215 for (var b in p.branches) _expand(b, ct - 1);216 }217 218 void _traverse(QuaterNode r, void f(List items)) {219 f(r.items);220 for (var b in r.branches) _traverse(b, f);221 }222 }223 224 class QuaterNode > {225 static final int capacity = 3;226 List items;227 List > branches;228 QuaterNode parent;229 230 factory QuaterNode(List elements) {231 if (elements.length > capacity) throw StateError('too many elements.');232 return QuaterNode._internal(elements);233 }234 235 QuaterNode._internal(List elements)236 : items = [],237 branches = [] {238 items.addAll(elements);239 }240 241 int get size => items.length;242 bool get isOverflow => size > capacity;243 bool get isLeaf => branches.isEmpty;244 bool get isNotLeaf => !isLeaf;245 246 bool contains(E value) => items.contains(value);247 int find(E value) => items.indexOf(value);248 249 String toString() => items.toString();250 }
-end-