Survival of game engine and Earth depend on trees. Trees are used to maintain data in a structured and heirarchial way. One possible use case, among many, is to store transformations of game objects/entities in scene. Traversal will allow to get the transformation of an entity with respect to its parent’s transformation space.
A tree starts with a root node, the only node with no parent. Each node will contain a key (anything that needs to be encapsulated in a node and stored in the tree). The children of node can be stored in a doubly linked list. Nodes with no child are called leaf node. Nodes are connected by edges, basically representing a parent child relationship.
The entire structure is broken into two parts, TreeNode and Tree. The TreeNode class represents the node ( pretty evident ) and Tree class represents the entire heirarchy of the nodes. To setup the tree, the first child is stored in a node called child and the siblings can be accessed with nodes, named next or prev.
TreeNode class:
Here, data is the key and the other members are meant for maintenance of the node within a tree. Only for the root node the parent member will be NULL. next and prev are pointers to nodes linked to the first child. The first child, child, will always have its prev pointing to NULL, similarly the last node will have its next as NULL. These NULLs are similar to ‘\0’ at the end of the string, which tell us about the extremes. The TreeNode class need some functions which will allow us to populate its own heirarchy. So lets add them.
Forward declared the Tree class and made it a friend of TreeNode. Lets go one by one.
void AddSibling(TreeNode<T> * node)
Post creation of the first child, this function will allow us to add more children of the node. It will always be called on the first child node as it adds siblings.void AssignId()
Assigns a unique id to each node, called in the constructor. Many ways to get a unique id, simplest way, static counter, is adopted here. TreeNode()
This private empty constructor, only accessible to the friend Tree, will come in handy to create a dummy root node. This is completely implementation dependant.TreeNode(T * data)
Constructor allows to add the key (the data member)~TreeNode()
Deletes all the children of a given node along with the node.void AddChild(TreeNode<T> * child)
Add a child to the node.void DetachChild(TreeNode<T> * child)
Detaches a child from its current parent which makes root as it parent node.void DeleteChild(TreeNode<T> * child)
Delete a child from the tree.void SetParent(TreeNode<T> * parent)
Assign a parent to the child.
Now lets see the implementation of the above functionalities.
I guess nothing much to explain here.
If the child is not NULL, go and delete the sub heirarchy first. Iterate the children, reach the last one and start the deletion in the reverse order.
If the current node is not the first or last but its somewhere in between, then after deletion adjust next and prev pointers of the predecessor and successor node respectively.
If its the last node adjust the next of the predeccessor node.
Lastly make the prev and next pointer, of the current node, NULL.
If first child, represented by child pointer is NULL then make the node, the first child else add it as a sibling of the first child.
Add the new node as the last sibling.
Detaching a node from its current parent, makes the root node as its parent. The above mentioned behaviour is implementation dependant. If the node to be deleted is the first child and it has no siblings then make the relevant pointers, namely next and prev, NULL.
In case, the child has siblings, make the first sibling as the first child.
In case, the node is not the first child, the next and prev of the successor and predeccessor nodes respectively, need to be adjusted.
Deletion of the node will require an additional step of releasing the dynamic memory.
Detach the child from its current parent and then attach it to the new onc. Please note that the new child will always get added as the last child. This behaviour can be changed, already in my TODO list.
This is how the tree node structure looks like. Part-2, coming soon, will focus on the tree. I’m sure there is a lot of scope for improvement, do let me know in the comments.
