输出3阶B
问题 C: 输出3阶B-树的构造过程
题目描述
给定n个正整数，请构造3阶B-树，输出构造过程
输入格式
第一行为正整数n（n<20)
第二行是空格分割的n个不重复的正整数
输出格式
输出构造过程。
采用深度优先遍历的方法，从B树的根节点（第0层）开始输出所有节点。每个节点的输出包括空格和关键字两部分。针对每个节点，首先根据节点所在的层数level，输出level*4个空格，然后用空格隔开输出这个节点的所有关键字，最后换行。
输入样例
12
45 32 16 77 94 38 44 21 39 68 33 26
输出样例
====insert a key:45
45
==================
====insert a key:32
32 45
==================
====insert a key:16
32 16 45
==================
====insert a key:77
32 16 45 77
==================
====insert a key:94
32 77 16 45 94
==================
====insert a key:38
32 77 16 38 45 94
==================
====insert a key:44
44 32 16 38 77 45 94
==================
====insert a key:21
44 32 16 21 38 77 45 94
==================
====insert a key:39
44 32 16 21 38 39 77 45 94
==================
====insert a key:68
44 32 16 21 38 39 77 45 68 94
==================
====insert a key:33
44 32 38 16 21 33 39 77 45 68 94
==================
====insert a key:26
32 44 21 16 26 38 33 39 77 45 68 94
==================
代码填空题（空：DFS，PrintBTree，findNodeToInsertKey）
ssn:我发现我一直输出不对劲是因为有点时候就糊涂了，忘了孩子数比关键词数要多一个，debug一晚上，转天早上才幡然醒悟，终于Ac了。
#include <queue>
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
#define MAXSIZE 4// B树结点的结构体定义
struct BTreeNode{int n; // 关键字个数bool isLeaf; //是否叶结点int keys[MAXSIZE]; // 有序关键字序列BTreeNode* children[MAXSIZE]; // 子结点集合BTreeNode* parent; // 父结点int level; // 层数，用于层次遍历
};
typedef BTreeNode* bt;// 初始化节点，确保每个数据都有初始值
BTreeNode* getInitNode(){bt node = new BTreeNode();node->isLeaf = true;node->n = 0;node->parent = nullptr;for(int i=0;i<MAXSIZE;i++){node->children[i] = nullptr;node->keys[i] = 0;}node->level = 0;return node;
}// B树结构体定义
struct BTree{BTreeNode* root; // B树的根结点int degree; // B树的维数
};// 深度优先遍历B树
void DFS(const BTreeNode* root){for(int i=0;i<root->level;i++){cout<<" ";}for(int i=0;i<root->n;i++){cout<<root->keys[i]<<" ";}cout<<endl;for(int i=0;i<=root->n;i++){if(root->children[i]!=nullptr)DFS(root->children[i]);}
}// 先用层次遍历的思想求每个节点的层数，再用深度优先遍历的方法输出BTree
void PrintBTree(BTree& B){B.root->level=0;queue<bt> Q;Q.push(B.root);while(!Q.empty()){bt node=Q.front();Q.pop();for(int i=0;i<=node->n;i++){if(node->children[i]!=nullptr){node->children[i]->level = node->level+1;Q.push(node->children[i]);}}}DFS(B.root);
}// 查找插入关键字key的节点
BTreeNode* findNodeToInsertKey( BTreeNode* root, int key){if(root->isLeaf){return root;}else{if(key < root->keys[0]){if(root->children[0]->isLeaf)return root->children[0];else{return findNodeToInsertKey(root->children[0],key);}} else{int i;for(i=1; i < root->n; i++){if(key < root->keys[i]){if(root->children[i]->isLeaf)return root->children[i];else{return findNodeToInsertKey(root->children[i],key);}} }if(i==root->n){if(root->children[root->n]->isLeaf)return root->children[root->n];else{return findNodeToInsertKey(root->children[root->n],key);}} } }
}// 在节点中插入关键字，并返回关键字在keys数组中的下标，用于更新字节点下标
// 可能在叶节点插入，也有可能在非叶节点插入（分裂操作）
int InsertKeyToNode(BTreeNode*& node, int key){// 关键字按照升序排列int index = node->n;while(index >= 1 && node->keys[index-1] > key){node->keys[index] = node->keys[index-1];node->children[index+1] = node->children[index];index--;}node->keys[index] = key;node->n++;return index;
}// 分裂操作：将节点一分为二
void SplitNode(BTree& B, BTreeNode*& node){BTreeNode* temp = node;BTreeNode* node1 = getInitNode();BTreeNode* node2 = getInitNode();node1->n = node2->n = 1;node1->isLeaf = node2->isLeaf = node->isLeaf;// 新构造的2个节点，父子指针node1->keys[0] = (node->keys[0]);node1->children[0] = node->children[0];node1->children[1] = node->children[1];if(node1->children[0] != nullptr) node1->children[0]->parent = node1;if(node1->children[1] != nullptr) node1->children[1]->parent = node1;node2->keys[0] = (node->keys[2]);node2->children[0] = node->children[2];node2->children[1] = node->children[3];if(node2->children[0] != nullptr) node2->children[0]->parent = node2;if(node2->children[1] != nullptr) node2->children[1]->parent = node2;BTreeNode* parent = node->parent;if(parent == nullptr){// 父节点是空节点，表示是在根结点分裂parent = getInitNode();parent->isLeaf = false;parent->n = 1;parent->keys[0] = node->keys[1];parent->children[0] = node1;parent->children[1] = node2;node1->parent = node2->parent = parent;B.root = parent;}else{//在父节点中插入一个新关键词，更新子节点指针int index = InsertKeyToNode(parent, node->keys[1]);parent->children[index] = node1;parent->children[index+1] = node2;node1->parent = node2->parent = parent;if(parent->n == B.degree){// 继续分裂SplitNode(B, parent);}}delete temp;
}// 在B-树中插入关键字key
void Insert(BTree& B, int key){if(B.root == nullptr){B.root = getInitNode();B.root->keys[0] = key;B.root->n = 1;}else{BTreeNode* node = findNodeToInsertKey(B.root, key);InsertKeyToNode(node, key);if(node->n == B.degree){SplitNode(B, node);}}
}int main(){
// freopen("/config/workspace/answer/test.in", "r", stdin);BTree B;B.degree = 3;B.root = nullptr;int n; cin >> n;for(int i=0;i<n;i++){int t; cin >> t;cout << "====insert a key:" << t << endl;Insert(B, t);PrintBTree(B);cout << "==================" << endl;}return 0;
}
更多推荐
输出3阶B
发布评论