首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >2-3树和如何构建构造函数

2-3树和如何构建构造函数
EN

Stack Overflow用户
提问于 2013-12-02 19:56:51
回答 1查看 294关注 0票数 0

我正在尝试构建2-3树的构造函数。但我不知道该怎么处理。我们是从一开始就创建一个只有一个值和两个指针(左和中)的节点,还是创建一个包含两个值和三个指针(左、中、右)的节点?

这里是我的2-3节点类.

代码语言:javascript
复制
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;
}
EN

回答 1

Stack Overflow用户

发布于 2013-12-02 21:12:36

我认为你首先应该这样声明这棵树:

代码语言:javascript
复制
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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/20336697

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档