/** * test if an item is in a subtree. * x is item to search for. * t is the node that roots the subtree. */ boolcontains( const Comparable & x, BinaryNode *t )const{ if( t == nullptr ) returnfalse; //找不到 elseif( x < t->element ) returncontains( x, t->left ); //查找值小于当前节点，往左子树找 elseif( t->element < x ) returncontains( x, t->right ); //查找值大于当前节点，往右子树找 elsereturntrue; // Match 找到 }
查找最小值
使用递归进行查找：
/** * find the smallest item in a subtree t. * Return node containing the smallest item. **/ BinaryNode * findMin( BinaryNode *t )const{ if( t == nullptr ) returnnullptr; // root is empty 加这一行判断主要是t可能不是整棵树的根，而是某颗子树的根 //比方说：只有一个节点的树：如果我们是从根的做儿子开始找，那么就需要这一行代码进行判断 if( t->left == nullptr ) return t; //left child is empty returnfindMin( t->left ); }
插入
讨论情况：
如果找到，不执行任何操作。
如果找不到，插入新节点。
使用递归进行插入：
/** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ voidinsert( const Comparable & x, BinaryNode * & t ){ //注意这里t的传递方式是传递引用，不然这棵树就断了 if( t == nullptr ) t = new BinaryNode{ x, nullptr, nullptr }; //不存在，插入新节点 elseif( x < t->element ) insert( x, t->left ); //插入值比当前节点小，往左子树插入 elseif( t->element < x ) insert( x, t->right ); //插入值比当前节点大，往右子树插入 else ; // Duplicate; do nothing 已经存在这个节点，不执行操作 }
二叉搜索树的形状取决于元素插入的顺序。
删除
讨论情况：
如果该节点没有儿子，直接删除即可
如果有一个儿子，则由替换为儿子。
如果有两个儿子，则由右子树中的最小元素进行替换。
/** * remove from a subtree. Textbook page 140 * x is the item to remove. t is the node that roots the subtree. * Set the new root of the subtree. */ voidremove( const Comparable & x, BinaryNode * & t ){ if( t == nullptr ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left ); elseif( t->element < x ) remove( x, t->right ); elseif( t->left != nullptr && t->right != nullptr ){// Two children t->element = findMin( t->right )->element; remove( t->element, t->right ); } else{ BinaryNode *oldNode = t; t = ( t->left != nullptr ) ? t->left : t->right; delete oldNode; } }
//Node declaration for AVL trees structAvlNode{ Comparable element; AvlNode *left; AvlNode *right; int height; //keep the height. You can keep balance factor AvlNode(const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0) : element{ ele }, left{ lt }, right{ rt }, height{ h } { } };
/** * Return the height of node t or -1 if nullptr. */ intheight( AvlNode *t )const{ return t == nullptr ? -1 : t->height; } staticconstint IMBALANCE = 1;
/** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ voidinsert( const Comparable & x, AvlNode * & t ){ if( t == nullptr ) t = new AvlNode{ x, nullptr, nullptr }; elseif( x < t->element ) insert( x, t->left ); elseif( t->element < x ) insert( x, t->right ); balance( t ); }
// Assume t is balanced or within one of being balanced voidbalance( AvlNode * & t ){ if( t == nullptr ) return; if( height(t->left) - height(t->right) > IMBALANCE ) if( height( t->left->left ) >= height( t->left->right ) ) rotateWithLeftChild( t ); else doubleWithLeftChild( t ); else if( height( t->right ) - height( t->left ) > IMBALANCE ) if( height( t->right->right ) >= height( t->right->left ) ) rotateWithRightChild( t ); else doubleWithRightChild( t ); t->height = max( height( t->left ), height( t->right ) ) + 1; //注意需要更新高度 }
/** * Rotate binary tree node with left child. * For AVL trees, this is a single rotation for case 1. * Update heights, then set new root. */ voidrotateWithLeftChild( AvlNode * & k2 ){ //注意传递的是引用 AvlNode *k1 = k2->left; //获取左儿子 k2->left = k1->right; //右挂左 k1->right = k2; //拎左 k2->height = max( height( k2->left ), height( k2->right ) ) + 1; //更新高度 k1->height = max( height( k1->left ), k2->height ) + 1; //更新高度 k2 = k1; //更换当前的节点，非常重要，这样才真正完成了“拎左” }
/** * Double rotate binary tree node: first left child * with its right child; then node k3 with new left child. * For AVL trees, this is a double rotation for case 3. * Update heights, then set new root. */ voiddoubleWithLeftChild( AvlNode * & k3 ){ rotateWithRightChild( k3->left ); rotateWithLeftChild( k3 ); }
Find(ElementType K, Btree T){ B = T; while (B is not a leaf){ find the Pi in node B that points to the proper subtree that K will be in; B = Pi; } /* Now we’re at a leaf */ if key K is the jth key in leaf B, use the jth record pointer to find the associated record; else/* K is not in leaf B */ report failure; }
B 树中的节点包含有多个键。假设需要查找的是\(k\)，那么从根节点开始，从上到下递归的遍历树。在每一层上，搜索的范围被减小到包含了搜索值的子树中。子树值的范围被它的父节点的键确定。因为是从根节点开始的二分法查找，所以查找一个键的代码如下：
BTreeNode *BTreeNode::search(int k){ // 找到第一个大于等于待查找键 k 的键 int i = 0; while (i < n && k > keys[i]) i++;
// 如果找到的第一个键等于 k , 返回节点指针 if (keys[i] == k) returnthis;
// 如果没有找到键 k 且当前节点为叶子节点则返回NULL if (leaf == true) returnNULL;
// 递归 return C[i]->search(k); }
遍历
B
树的中序遍历与二叉搜索树的中序遍历也很相似，从最左边的孩子节点开始，递归地打印最左边的孩子节点，然后对剩余的孩子和键重复相同的过程。最后，递归打印最右边的孩子节点。
遍历的代码如下：
voidBTreeNode::traverse(){ // 有 n 个键和 n+1 个孩子 // 遍历 n 个键和前 n 个孩子 int i; for (i = 0; i < n; i++) { // 如果当前节点不是叶子节点, 在打印 key[i] 之前, // 先遍历以 C[i] 为根的子树. if (leaf == false) C[i]->traverse(); cout << " " << keys[i]; }
// 打印以最后一个孩子为根的子树 if (leaf == false) C[i]->traverse(); }
先贴一份GPT的实现代码
#include<iostream> usingnamespace std;
constint T = 3; // B树的最小度
// B树节点定义 classBTreeNode { public: int keys[2 * T - 1]; // 节点中的关键字 BTreeNode* children[2 * T]; // 子节点 int n; // 当前存储的关键字数 bool leaf; // 是否为叶子节点
BTreeNode(bool _leaf);
voidtraverse(); // 遍历节点
BTreeNode* search(int k); // 搜索关键字
intfindKey(int k); // 查找关键字在节点中的索引
voidinsertNonFull(int k); // 在非满节点中插入
voidsplitChild(int i, BTreeNode* y); // 分裂子节点
voidremove(int k); // 从子树中删除关键字
voidremoveFromLeaf(int idx); // 从叶子节点中删除
voidremoveFromNonLeaf(int idx); // 从非叶子节点中删除
intgetPred(int idx); // 获取前驱关键字
intgetSucc(int idx); // 获取后继关键字
voidfill(int idx); // 填补缺少的子节点
voidborrowFromPrev(int idx); // 从前一个子节点借一个关键字
voidborrowFromNext(int idx); // 从后一个子节点借一个关键字
voidmerge(int idx); // 合并两个子节点
friendclassBTree; };
classBTree { public: BTreeNode* root; // 根节点
BTree() { root = nullptr; }
voidtraverse(){ if (root != nullptr) root->traverse(); }
