我正在尝试构建2-3树的构造函数。但我不知道该怎么处理。我们是从一开始就创建一个只有一个值和两个指针(左和中)的节点,还是创建一个包含两个值和三个指针(左、中、右)的节点?
这里是我的2-3节点类.
template<class E>
class BNode
{
public:
// I'm not sure if this is quite enough for the constructor
BNode() {_right == nullptr;};
typedef struct Entry
{
E value;
BNode<E>* _left;
// Constructor for the entry
Entry();
};
E fValue() {return _first.value;}
E sValue() {return _second.value;}
BNode<E>* fLeft() {return _first._left;}
BNode<E>* sLeft() {return _second._left;}
//check if the node is 2 or 3 pointers
bool IsThree()
{
if(_first._left != nullptr && _second._left != nullptr
&& _second._right != nullptr)
_three = true;
else
_three = false;
return _three;
}
Entry fEntry() {return _first;}
Entry sEntry() {return _second;}
BNode<E>* right() {return _right;}
private:
bool _three;
Entry _first, _second;
BNode<E>* _right;
};
template<class E>
BNode<E>::Entry::Entry()
{
_left = nullptr;
}发布于 2013-12-02 21:12:36
我认为你首先应该这样声明这棵树:
template<class E>
class BTree
{
public:
BTree();
~BTree();
class BNode
{
public:
// I'm not sure if this is quite enough for the constructor
BNode() {_right == nullptr;};
typedef struct Entry
{
E value;
BNode<E>* _left;
// Constructor for the entry
Entry();
};
E fValue() {return _first.value;}
E sValue() {return _second.value;}
BNode<E>* fLeft() {return _first._left;}
BNode<E>* sLeft() {return _second._left;}
//check if the node is 2 or 3 pointers
bool IsThree()
{
if(_first._left != nullptr && _second._left != nullptr
&& _second._right != nullptr)
_three = true;
else
_three = false;
return _three;
}
Entry fEntry() {return _first;}
Entry sEntry() {return _second;}
BNode<E>* right() {return _right;}
private:
bool _three;
Entry _first, _second;
BNode<E>* _right;
};
private:
BNode* root_;
};
template<class E>
BTree<E>::BNode<E>::Entry::Entry()
{
_left = nullptr;
}然后,BNode()应该包含叶上的一个或两个元素,而BTree()应该包含一个列表或/和一个包含对象列表的初始化程序列表(2或3个对象?)如果使用C++11,应该在每片叶子上构建树,从最向下的右叶的根开始,按照下面的图:tree
https://stackoverflow.com/questions/20336697
复制相似问题