我试图递归地做它......父整数变量就像我一样,符合公式,2*i +1
for leftChild
's和 2*i +2
为右边。
void BST::insert(const data &aData)
{
if ( items[Parent].empty )
{
items[Parent].theData = aData;
items[Parent].empty = false;
}
else if ( aData < items[Parent].theData )
{
Parent = 2 * Parent + 1;
if ( Parent >= maxSize ) this->reallocate();
this->insert(aData);
}
else
{
Parent = (2 * rightChild++)+ 2;
if ( Parent >= maxSize ) this->reallocate();
this->insert(aData);
}
}
当插入小于原始父级的项目时,它工作正常...... 但是当我发现更大的东西时,一切都搞砸了 :x
void BST::reallocate()
{
item *new_array = new item[maxSize*2];
for ( int array_index = 0; array_index < maxSize; array_index++ )
{
if ( ! items[array_index].empty )
{
new_array[array_index].theData = items[array_index].theData;
}
}
maxSize *= 2;
delete [] items;
items = NULL;
items = new_array;
}
这是我的 ctor,所以没有人比我更困惑了:
BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0),
leftChild(0), rightChild(0)
{
items->empty = true;
maxSize = capacity;
}
private:
int size; // size of the ever growing/expanding tree :)
int Parent;
int maxSize;
int leftChild;
int rightChild;
struct item
{
bool empty;
data theData;
};
item *items; // The tree array
上面的插入功能实际上是我能得到的最好的..
R
/ \
/ \
/ \
L X
/ \ / \
J V K T <--The only out of place node.
/ \ \
/ NULL \
G /
P
插入时:R, L, J, G, X, K, V, P, T
按此顺序
最佳答案
我怀疑你的问题出在这条线上:
Parent = (2 * rightChild++)+ 2;
为什么在这里使用 rightChild 而不是 (2 * Parent) + 2
?
为了让事情更清楚,你可能想在你的类中添加一些简单的内联函数来计算左/右 child 和 parent 的索引,给定一个索引:
inline int getLeftChildIndex(int nodeNdx) { return (nodeNdx * 2) + 1; }
inline int getRightChildIndex(int nodeNdx) { ... }
inline int getParentIndex(int nodeNdx) { ... }
您可能还想考虑使用类 search()
或 find()
方法(我假设它有一个)来确定在哪里插入新的节点。搜索函数应返回现有节点的索引(由您决定如何处理重复值的插入)或应插入新值的位置的索引。
关于c++ - 数组 BST 的插入排序如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1752900/