以下代码在树中插入一些节点并显示同一 B 树的中序和先序遍历。中序遍历似乎是正确的,因为节点是按升序排列的。前序遍历不对。您能否提供一些建议或帮助来纠正 preordertraverse() 函数?
class btree
{
int *keys;
int t;
btree **C;
int n;
bool leaf;
public:
btree(int _t, bool _leaf);
void inordertraverse();
void preordertraverse();
void insertnonfull(int k);
void splitchild(int i, btree *y);
void insert(int k);
btree(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;
keys = new int[2*t-1];
C = new btree *[2*t];
n = 0;
}
void btree::insert(int k)
{
if (root == NULL)
{
root = new btree(t, true);
root->keys[0] = k;
root->n = 1;
}
else
{
if (root->n == 2*t-1)
{
btree *s = new btree(t, false);
s->C[0] = root;
s->splitchild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertnonfull(k);
root = s;
}
else
root->insertnonfull(k);
}
}
void insertnonfull(int k)
{
int i = n-1;
if (leaf == true)
{
while (i >= 0 && keys[i] > k)
{
keys[i+1] = keys[i];
i--;
}
keys[i+1] = k;
n = n+1;
}
else
{
while (i >= 0 && keys[i] > k)
i--;
if (C[i+1]->n == 2*t-1)
{
splitchild(i+1, C[i+1]);
if (keys[i+1] < k)
i++;
}
C[i+1]->insertnonfull(k);
}
}
void splitchild(int i, btree *y)
{
btree *z = new btree(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t-1; j++)
z->keys[j] = y->keys[j+t];
if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->C[j] = y->C[j+t];
}
y->n = t - 1;
for (int j = n; j >= i+1; j--)
C[j+1] = C[j];
C[i+1] = z;
for (int j = n-1; j >= i; j--)
keys[j+1] = keys[j];
keys[i] = y->keys[t-1];
n = n + 1;
}
void intraverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->inotraverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->intraverse();
}
void pretraverse()
{
int i;
for (i = 0; i < n; i++)
{
cout << " " << keys[i];
if (leaf == false)
C[i]->pretraverse();
}
if (leaf == false)
C[i]->pretraverse();
}
int main()
{
btree t(3);
t.insert(1);
t.insert(2);
t.insert(4);
t.insert(7);
t.insert(5);
t.insert(8);
t.insert(10);
t.insert(11);
t.intraverse();
t.pretraverse();
return 0;
}
在前序遍历中,节点的键都在任何子键之前输出。然而,您的代码通过以下方法将父键与子键的输出混合在一起(我修复了缩进):
void btreenode::preordertraverse()
{
int i;
for (i = 0; i < n; i++)
{
cout << " " << keys[i];
if (leaf == false)
C[i]->preordertraverse();
}
if (leaf == false)
C[i]->preordertraverse();
}
输出应分为两个阶段:一阶段用于输出当前节点的键,一阶段用于递归地为子节点执行相同的操作:
void btreenode::preordertraverse()
{
for (int i = 0; i < n; i++)
cout << " " << keys[i];
if (!leaf)
for (int i = 0; i <= n; i++)
C[i]->preordertraverse();
}
现在示例的输出将是:
53 92 115 1 48 72 75 85 101 111 119 128 129 189 193
对应于这棵B树的形状: