m-ary tree
(also known as k-ary tree or n-ary tree)
It is a rooted tree in which in which each node can have upto m children.
Let’s jump to implementation
We will be implementing it using pointer based method in which list of pointers (pointing to child node) will maintained in each node.
Note : Tree implementation in this article is for int, I will provide a separate article containing generic implementation.
For this, first we will create class node representing the each node of tree.
A node should contain :
- data
- pointer to parent node
- list of pointer to child nodes
As partial encapsulation will be maintained, it will also include
- data getter
- parent setter/getter
- getter for list of children
- children count getter and add child function for ease
- default parameter constructor with fist parameter to receive data and second parameter to receive address of parent node (which will be by default null for case of root node)
Below is code for class representing node in C++ :
Now let’s create a wrapper class for tree
It will contain :
- Pointer to root node
- Count of nodes
- count of Children(m)
- queue to handle adding nodes
- map for data-node mapping
- map for node-parent mapping
- constructor as well as destructor
- add function to add data
- function to show traversal logic
- additional functions supporting encapsulation and ease of working
Note : For explanatory purpose, first I will provide small snippets of code and at last I will provide a complete snippet.
Object Variables :
In the above snippet
- m → max number of child a node can have
- nodeCount → total number of nodes in tree
- root → entry point
- inputQueue → to handle sequence of nodes to which new nodes will be added
- dataNodeMapping → to get node object against data
- parent → to get parent of node
Constructor and Destructor :
Add Function :
- has one parameter that will receive data to be added to tree
- If data is already added to tree remaining process is skipped
- If it is tree is empty new node is created with no parent and it will assigned to root
- if node at front of inputQueue has m children pop operation will take place from inputQueue
- node at front of the inputQueue is the one to which new node is to be added
- data to node will be added using addChild method of m_ary_tree_node
Additional Functions :
Function for Depth First Search traversal output :
In the above snippet, dfs function acts as a seed function and _dfs function is the recursive function for depth first search traversal. It can also be considered as pre-order traversal. Just swapping line number 3 and 4 of above snippet will give post-order output.
Function for Breadth First Search traversal output :
In above the snippet a simple logic is used :
1. Push root to queue if it exists.
2. Do steps 3–6 if queue is not empty.
3. Process data (in our case print in console window) in top node of queue.
4. Push all children of top node to queue.
5. Pop from queue
6. Go to step 2
Usage :
In the above snippet, a tree is created in which each node could have upto 3 children.
