1

I have a binary search tree, and I created a struct for the node that represents one element and the child to its left, yet, I cannot figure out the mechanism on how to check if it's a 2 node, with one element and two children or if it's 3 node, with two elements and three children. Would someone please give me a hint ?

This is my template class for the BNode

template<class E>
class BNode
{
    public:
        struct Entry
        {
            E value;
            BNode* left;
        };
        bool IsThree();

    private:
        bool _three;
        Entry _first, _second;
        BNode* _right;
};

template<class E>
bool BNode<E>::IsThree()
{
// 

}
interjay
  • 107,303
  • 21
  • 270
  • 254
Hoang Minh
  • 1,066
  • 2
  • 21
  • 40
  • 3
    A binary search tree with three children per node? – Kerrek SB Nov 14 '13 at 09:29
  • from my understanding, it's a 2-3 trees – Hoang Minh Nov 14 '13 at 09:30
  • 1
    Obviously (?) you need to check whether you have 2 or 3 non-NULL BNode pointers. I.e. check _first.left, _second.left and _right. – john Nov 14 '13 at 09:32
  • @KerrekSB: I looked it up, and I can't put in a new tag 2-3 tree in there unless I have at least 1500 reputations :( – Hoang Minh Nov 14 '13 at 09:33
  • What is `bool _three;`? Seems to me like it's supposed to indicate three children, no? – interjay Nov 14 '13 at 09:33
  • @john: but the 3-node can have only 2 children. It is not required to have all 3 children – Hoang Minh Nov 14 '13 at 09:35
  • @interjay: I variable _three is there to hold the return valued of the bool IsThree(). That way, you would know if that node has one element or two elements. – Hoang Minh Nov 14 '13 at 09:39
  • 1
    @HoangMinh Well, yes. If it has only two children then set one of the three pointers to NULL. That's the test. Do you understand pointers? Do you know what NULL is? It seems completely obvious that this is what you need to do. – john Nov 14 '13 at 09:56
  • @john: thanks, I got it now – Hoang Minh Nov 14 '13 at 20:48

0 Answers0