A tree is yet another data structure that is used to represent hierarchical data. A tree is an abstract data type in computer science that depicts a hierarchical tree structure with a set of connected nodes. Except for the root node, which has no parent, each node in the tree can have numerous children (depending on the type of tree). However, each node must have precisely one parent. Because of these restrictions, there are no cycles or “loops” (no node may be its own ancestor), and each child can be viewed as the root node of its own subtree, making recursion a suitable tree traversal strategy. Many trees, unlike linear data structures, cannot be represented by a single straight line connecting neighboring nodes.
Example of Tree Data Structure
Suppose I f we want to depict the computer and its components in a hierarchical manner, we can do so as follows:
Key Points of Tree Data Structure.
- Each node contains data as well as a link or reference to other nodes known as children.
- Because it does not store data in a sequential order, a tree data structure is a non-linear data structure. Because the elements in a Tree are organized at multiple levels, it is a hierarchical structure.
- A tree data structure is defined as a collection of objects or entities known as nodes that are linked together to represent or simulate hierarchy.
- The topmost node is known as root.
Coding Of Tree in Python
Now lets start step wise step to code a tree data structure using python. first we create the structure of Tree Node
Class of Tree Node
Here we create the structure of Tree Node which consists of three things.
- Data – This variable is used to store the value in the node.
- Children – This is a type of list which stores all the references of it child nodes.
- Parent – This is used to store the reference of the parent of current node. If the current node in root node then it stores None.
class TreeNode:
def __init__(self,data) :
self.data = data
self.children = []
self.parent = None
Add Child
The below function is used to add a child to its parent. Here the self is a reference to parent and we add the parent of current node. In next line we just add that child to is parent.
def addChild(self,child):
child.parent = self
self.children.append(child)
Printing the Tree
Here we are creating a function to print the tree. We have used 2 functions here first is getLevel and the second is showTree. Using getLevel function we just get the level of the node by traversing to its parent.
The showTree is a recursive function that is used to print the tree. We pass the root node here and call its children recursively to print the data.
def getLevel(self):
level = 0
p = self.parent
while p:
level +=1
p = p.parent
return level
def showTree(self):
spaces = " "*self.getLevel()*2
prefix = spaces + "|--"if self.parent else ""
print(prefix ,self.data)
if self.children:
for child in self.children:
child.showTree()
The Main Function
Here comes the main function which is used to build ree and call other functions of class
def build_product_tree():
root = TreeNode("Computer")
hardware = TreeNode("Hardware")
hardware.addChild(TreeNode("Moniter"))
hardware.addChild(TreeNode("Keyboard"))
hardware.addChild(TreeNode("Mouse"))
hardware.addChild(TreeNode("CPU"))
software = TreeNode("Software")
software.addChild(TreeNode("System Software"))
software.addChild(TreeNode("Application Software"))
software.addChild(TreeNode("Utility Software"))
root.addChild(hardware)
root.addChild(software)
return root
if __name__ == '__main__':
root = build_product_tree()
root.showTree()
Full Python Code of Tree Data Structure
class TreeNode:
def __init__(self,data) :
self.data = data
self.children = []
self.parent = None
def addChild(self,child):
child.parent = self
self.children.append(child)
def getLevel(self):
level = 0
p = self.parent
while p:
level +=1
p = p.parent
return level
def showTree(self):
spaces = " "*self.getLevel()*2
prefix = spaces + "|--"if self.parent else ""
print(prefix ,self.data)
if self.children:
for child in self.children:
child.showTree()
def build_product_tree():
root = TreeNode("Computer")
hardware = TreeNode("Hardware")
hardware.addChild(TreeNode("Moniter"))
hardware.addChild(TreeNode("Keyboard"))
hardware.addChild(TreeNode("Mouse"))
hardware.addChild(TreeNode("CPU"))
software = TreeNode("Software")
software.addChild(TreeNode("System Software"))
software.addChild(TreeNode("Application Software"))
software.addChild(TreeNode("Utility Software"))
root.addChild(hardware)
root.addChild(software)
return root
if __name__ == '__main__':
root = build_product_tree()
root.showTree()
Click here for GitHub code
Output of above code
