Data structures in python tree

Python Tree Data Structure | Tree in Python

Learn tree in Python- data structure, programs with code examples. Know more about Python tree, how to create it and traverse using pre and post order.

What is a tree in Python?

Trees are non-linear data structures representing nodes connected by edges. Each tree consists of a root or main node known as the Parent node and the left node and right node as Child nodes. It is used for searching and data organization.

Does Python have Tree?

No, Python does not have any trees built-in. On the other hand, you can easily construct by subclassing a Node type from list and writing the traversal methods. We will discuss this later in the article.

Introduction to Python Tree

A binary tree node contains the following components- Data, Left Child, Right Child. The important terms related to a binary tree are:

1. Node – The simplest unit of a binary tree.
2. Root – It is the topmost element. There is mostly one root in a binary tree.
3. Parent – It is the node that is one level upward of the node.
4. Child – They are the nodes that are one level downward of the node.
5. Leaf – Leaves of a binary tree are the nodes that have no children.
6. Level – It is the generation of the node.

For example, a root has level 0, the children of the root node is at level 1 and the grandchildren of the root node is at level 2.

How Tree is implemented in Python? Tree program in Python

To implement and create a tree in Python, we first create a Node class that will represent a single node. The node class will have 3 variables- the left child, the second variable data containing the value for that node and the right child.

class Node: def __init__(self, data): self.left = None self.right = None self.data = data

root = Node(10) root.left = Node(34) root.right = Node(89) root.right.left = Node(45) root.right.right = Node(50)

As a result, the output tree looks like this:

If you create an object of class Node, the __init__ constructor is called, and all the variables inside that constructor will get initialized. The root holds the root node of the tree has a value of 10. We insert the left child with the value 34 and the right child with the value 89. As it is a binary tree, every node can contain a maximum of two nodes. Further, we insert two more nodes to the tree as in 45 and 50. They are the children for node 89.

Note: We can insert any number of nodes we want inside a tree, depending upon the type of tree being created.

How to print tree elements | Traverse a Tree in Python

Since we have created a tree, so we need to traverse the tree to print the tree elements. Traversing means visiting every node in a tree. Every node in a tree is visited three times. There are three types of traversals in a binary tree: in-order traversal, pre-order traversal, and post-order traversal.

In-order Traversal

In this case, we first visit the left child and perform recursion, then we visit the same node for the second time to print that node. It is further followed by the parent node, then followed by recursion on the right child.
The given tree is:

 10 / \ 34 89 / \ / \ 20 45 56 54

def inorder(node): if node: inorder(node.left) print(node.data) inorder(node.right)

As a result, the output is:
20 34 45 10 56 89 54

Pre-order Traversal

In this case, while traversing a python tree, we see the root node for the first time and print it. It is then followed by recursion on the left and the right child.
The given tree is:

 10 / \ 34 89 / \ / \ 20 45 56 54

def preorder(node): if node: print(node.data) preorder(node.left) preorder(node.right)

As a result, the output is:
10 34 20 45 89 56 54

Post-order Traversal

In this case, while traversing a tree, we do recursion on the left node and the right node. Then we come to the root node to print it.
The given tree is:

 10 / \ 34 89 / \ / \ 20 45 56 54

def postorder(node): if node: postorder(node.left) postorder(node.right) print(node.data)

As a result, the output is:
20 45 34 56 54 89 10

Using the Insert Method

To use the insert method in the same node class, we add an insert class to it. This insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Further, the PrintTree class prints the tree.
Example:

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() root = Node(30) root.insert(15) root.insert(40) root.insert(35) root.insert(12) root.insert(20) root.PrintTree()

As a result, the output is:
12 15 20 30 35 40

Conclusion & Practical Application

Using trees in Python can be fun, as we saw in the above examples. These are widely used in different software and applications. A strong grip on this topic can be very beneficial for interview purposes and give you an extra edge. After understanding the principles of a tree, practice some problem sets to test your knowledge of trees in python.

Like this article? Follow us on Facebook and LinkedIn.

Источник

Tree Data Structure in Python

Python is a very rich language in terms of features and data structures. It has a lot of inbuilt data structures like Python dictionary, list, tuple, set, frozenset, etc. Apart from that, we can also create our own custom data structures using Classes. In this article, we will learn about Binary tree data structure in Python and will try to implement it using an example.

What is a Tree Data Structure?

A Python tree is a data structure in which data items are connected using references in a hierarchical manner in the form of edges and nodes. Each tree consists of a root node from which we can access the elements of the tree. Starting from the root node, each node contains zero or more nodes connected to it as children.

A simple binary tree can be depicted as seen in the following figure.

Parts of a Tree Data structure

A tree consists of a root node, leaf nodes, and internal nodes. Each node is connected to its child via a reference, which is called an edge.

Root Node: The root node is the topmost node of a tree. It is always the first node created while creating the tree and we can access each element of the tree starting from the root node. In the above example, the node containing element 50 is the root node.

Parent Node: The parent of any node is the node that references the current node. In the above example, 50 is the parent of 20 and 45, and 20 is the parent of 11, 46, and 15. Similarly, 45 is the parent of 30 and 78.

Child Node: Child nodes of a parent node are the nodes at which the parent node is pointing using the references. In the example above, 20 and 45 are children of 50. The nodes 11, 46, and 15 are children of 20 and 30 and 78 are children of 45.

Edge: The reference through which a parent node is connected to a child node is called an edge. In the above example, each arrow that connects any two nodes is an edge.

Leaf Node: These are those nodes in the tree that have no children. In the above example, 11, 46, 15, 30, and 78 are leaf nodes.

Internal Nodes: Internal Nodes are the nodes that have at least one child. In the above example, 50, 20, and 45 are internal nodes.

What is a Binary Tree in Python?

A binary tree is a tree data structure in which each node can have a maximum of 2 children. It means that each node in a binary tree can have either one, or two or no children. Each node in a binary tree contains data and references to its children. Both the children are named as the left child and the right child according to their position.

The structure of a node in a binary tree is shown in the following figure.

We can define a Tree node of the structure shown above in Python using classes as follows.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None

Here, the constructor of the Tree node takes the data value as input, creates an object of BinaryTreeNode type and initializes the data field equal to the given input, and initializes the references to the children to None. The children can be assigned to the nodes later.

An example of a binary tree is shown in the figure below.

We can implement the above binary tree in Python as follows.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild = None node1 = BinaryTreeNode(50) node2 = BinaryTreeNode(20) node3 = BinaryTreeNode(45) node4 = BinaryTreeNode(11) node5 = BinaryTreeNode(15) node6 = BinaryTreeNode(30) node7 = BinaryTreeNode(78) node1.leftChild = node2 node1.rightChild = node3 node2.leftChild = node4 node2.rightChild = node5 node3.leftChild = node6 node3.rightChild = node7 print("Root Node is:") print(node1.data) print("left child of the node is:") print(node1.leftChild.data) print("right child of the node is:") print(node1.rightChild.data) print("Node is:") print(node2.data) print("left child of the node is:") print(node2.leftChild.data) print("right child of the node is:") print(node2.rightChild.data) print("Node is:") print(node3.data) print("left child of the node is:") print(node3.leftChild.data) print("right child of the node is:") print(node3.rightChild.data) print("Node is:") print(node4.data) print("left child of the node is:") print(node4.leftChild) print("right child of the node is:") print(node4.rightChild) print("Node is:") print(node5.data) print("left child of the node is:") print(node5.leftChild) print("right child of the node is:") print(node5.rightChild) print("Node is:") print(node6.data) print("left child of the node is:") print(node6.leftChild) print("right child of the node is:") print(node6.rightChild) print("Node is:") print(node7.data) print("left child of the node is:") print(node7.leftChild) print("right child of the node is:") print(node7.rightChild) 

Root Node is: 50 left child of the node is: 20 right child of the node is: 45 Node is: 20 left child of the node is: 11 right child of the node is: 15 Node is: 45 left child of the node is: 30 right child of the node is: 78 Node is: 11 left child of the node is: None right child of the node is: None Node is: 15 left child of the node is: None right child of the node is: None Node is: 30 left child of the node is: None right child of the node is: None Node is: 78 left child of the node is: None right child of the node is: None

How to Traverse a Binary Tree in Python?

We use different tree traversal algorithms to traverse a binary tree in Python. To understand the traversal algorithms, you need to understand the concept of recursion in Python.

You can read the implementation of all these tree traversal algorithms in Python using the following links.

Different Operations on A Binary Tree in Python

Binary trees are a complex data structure and operations on binary trees can also be complex. Hence, we use a special type of binary tree called a binary search tree to implement a binary tree in Python. We can add elements to a binary search tree, search for an element, update an element, and delete an element from a binary tree. You can learn how to add an element and search for an element in a binary search tree in this article on binary search trees in Python.

Conclusion

In this article, we have discussed tree data structure and binary tree data structure in Python. To learn more about data structures in Python, you can read this article on linked list in Python. You might also like this article on Python continue vs break statements.

I hope you enjoyed reading this article. Stay tuned for more informative articles.

Источник