c++treemultiway-tree

Is this how I should be understanding what a multiway tree is?

I am currently about to implement a multi-way tree in c++, but I am still not sure about what exactly they are. I have read a few documentations, but I am still confused because of the lack of pictures or visualization provided.

Lets say I want a 3 way tree, according to online web notes it means each node can have at most 3-1 = 2 elements and each node can have at most 3 children. Below I have drawn some trees that I am not sure if they are 3-way trees, can someone please verify I am understanding this correctly? Thank you!

Also, if I have a 2 way tree, does that mean I have a binary tree as well? O.o? enter image description here

Solution

  • My understanding of a multi-way tree is the number of subtrees that can be traversed from a single node.

               +---+  
           | D |
           +---+  
             ^  
             |  
             |  
+---+     +------+     +---+  
| A | <-- | Root | --> | B |  
+---+     +------+     +---+
             |  
             |  
             V
           +---+  
           | C |  
           +---+

    The diagram above shows a multi-way tree because the root has more than 1 child.

    Usually 2 children per node (except leaf nodes) indicates binary trees.
    There are many different kinds of binary trees.

    See also B-Tree and B*Trees.

    Edit 1:
    Another view:

     +------------------------+  
 |          Root          +
 +------------------------+  
  |       |       |       |  
  V       V       V       V  
+---+   +---+   +---+   +---+  
| A |   | B |   | C |   | D |  
+---+   +---+   +---+   +---+