基于数组的二叉搜索树C ++ [英] Array Based Binary Search Tree C++
问题描述
直到我需要realloacte，我的树类似：
R
/
A
\
F
\
/
B
\
C
\
T
递归。但是，我注意到我需要回到根，R....试图这样做...
void BST :: insert（const data& aData）
{
item * y = NULL; //算法调用NULL赋值..
item * x = new item（）;
//如何初始化左右？
//没有结构项的嵌套复制ctor？
if（items-> empty）
{
items = new item（）;
items-> empty = false;
items-> theData = aData; //获取数据。
++ size;
}
else if（size == maxSize）this-> reallocate（）;
else
{
if（aData< items-> theData）
{
x [x-> LEFT] .theData = aData;
x-> LEFT = x-> LEFT + 1;
this-> insert（items-> theData）;
}
else if（items-> theData< aData）
{
x [x-> RIGHT] .theData = aData;
x-> RIGHT = x-> RIGHT + 1;
this-> insert（item-> theData）;
}
else this-> insert（items-> theData）;
}
这是我的BST类的private部分中的items数组的结构对象文件：
...
private：
int size; //不断增长/扩展的树的大小:)
int maxSize;
struct item
{
bool empty;
int LEFT;
int RIGHT;
数据theData;
};
item * items; //树数组
item * oldRoot;
int root_index; //根的索引
Im也重载赋值运算符...我不知道该说什么。这个很难（硬。我看过这么多的例子和在线讲座;以及算法....
所请求的relloaction方法：
void BST :: reallocate（）
{
item * new_array = new item [size * 2];
for（int array_index = 0; array_index< size; array_index ++）
{
new_array [array_index] .theData = items [array_index] .theData;
new_array [array_index] .empty = false;
}
size * = 2;
delete [] items;
items = NULL;
items = new_array;
}
将二叉树实现为数组，其中根位于索引0，在索引 i 处的元素 LEFT 将在2i + 1处找到， RIGHT 将在2i + 2找到。您不需要有LEFT和RIGHT作为您的结构的一部分。
它必须
结构项目
{
int index;
data theData;
};
在结构中存储左索引和右索引 NOT 。此外，您不需要跟踪根索引。它总是0.有关二叉树的 wiki文章。搜索存储二叉树的方法字符串。
此实现允许根据需要轻松地向下和向上遍历树。
Im trying to build an array based, "Binary Search Tree" by following the algorithm at:
Up until I need to realloacte, my tree resembles:
R
/
A
\
F
\
L
/
B
\
C
\
T
Recursively. However, im notice that I need to get back to the root, "R"....Trying to do that now..
void BST::insert(const data& aData)
{
item *y = NULL; // Algorithm calls for NULL assignment..
item *x = new item();
// How do i Init LEFT and RIGHT?
// With no nested copy ctor for struct item?
if ( items->empty )
{
items = new item();
items->empty = false;
items->theData = aData; // Get the data.
++size;
}
else if ( size == maxSize ) this->reallocate();
else
{
if ( aData < items->theData )
{
x[x->LEFT].theData = aData;
x->LEFT = x->LEFT + 1;
this->insert(items->theData);
}
else if ( items->theData < aData )
{
x[x->RIGHT].theData = aData;
x->RIGHT = x->RIGHT + 1;
this->insert(items->theData);
}
else this->insert(items->theData);
}
Here is my struct for the items array in the private section of the BST class object file: ...
private:
int size; // size of the ever growing/expanding tree :)
int maxSize;
struct item
{
bool empty;
int LEFT;
int RIGHT;
data theData;
};
item *items; // The tree array
item *oldRoot;
int root_index; // index for the root(s)
Hmm. Im also overloading the assignment operator...I dont know what to say. Its hard. I've looked at so many examples and lectures online; as well as algorithms....
The relloaction method as requested:
void BST::reallocate()
{
item *new_array = new item[size*2];
for ( int array_index = 0; array_index < size; array_index++ )
{
new_array[array_index].theData = items[array_index].theData;
new_array[array_index].empty = false;
}
size *= 2;
delete [] items;
items = NULL;
items = new_array;
}
There is well established way to implement binary tree as array, which says that root is sitting at index 0, LEFT of element at index i will be found at 2i + 1 and RIGHT will be found at 2i + 2. You do not need to have LEFT and RIGHT as part of your structure.
it has to be
struct item
{
int index;
data theData;
};
Do NOT store left index and right index in your structure. Also you don't need to keep track of root index. It is always 0. Check out wiki article on binary trees. Search for "Methods for storing binary trees" string. This implementation allows easy traversal down and up the tree if needed.
这篇关于基于数组的二叉搜索树C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
