Python tree example

Dora 23 Published: 11/04/2024

Python tree example

I'd be happy to help!

Let's take a look at a simple Python program that uses trees. In this case, we'll create a binary tree and perform some basic operations on it.

Here is the code:

class TreeNode:

def init(self, x):


self.val = x


self.left = None


self.right = None


def insert(root, val):


if root is None:


return TreeNode(val)


else:


if root.val < val:


if root.right is None:


root.right = TreeNode(val)


return root


else:


root = insert(root.right, val)


elif root.val > val:


if root.left is None:


root.left = TreeNode(val)


return root


else:


root = insert(root.left, val)


return root


def search(root, val):


if root is None or root.val == val:


return root


if val < root.val:


return search(root.left, val)


return search(root.right, val)


root = None


root = insert(root, 4)


root = insert(root, 2)


root = insert(root, 6)


root = insert(root, 1)


root = insert(root, 3)


print("Inorder Traversal:")


inOrder(root)


print("nPreorder Traversal:")


preOrder(root)


print("nPostorder Traversal:")


postOrder(root)


def inOrder(root):


if root:


inOrder(root.left)


print(root.val),


inOrder(root.right)


def preOrder(root):


if root:


print(root.val),


preOrder(root.left)


preOrder(root.right)


def postOrder(root):


if root:


postOrder(root.left)


postOrder(root.right)


print(root.val),

Now, let's go over the code and how it works:

We first define a TreeNode class that represents each node in our binary tree. Each node has a value (val) and two children (left and right), which are initially set to None. Next, we have an insert function that adds a new node with a specified value to the tree. If the root is None, this means we're creating a new tree, so we create a new node. Otherwise, we compare the value of the node we want to insert with the value of the root. If it's less than the root's value, we go right. If it's greater, we go left. We keep doing this until we find the correct spot for our new node. The search function works similarly to insert, but instead of adding a new node, it returns the node with the specified value if found, or None if not. Finally, we have three traversal functions: inOrder, preOrder, and postOrder. These are used to traverse the tree in different orders (inorder, preorder, and postorder). Each function visits each node in a specific order and prints its value. At the end of our code, we create a new binary tree with five nodes (4, 2, 6, 1, 3) using the insert function, then print out the results of traversing this tree in each of these orders.

This is a simple example of how trees can be used to represent data and perform operations on that data.

Is there a tree library in Python?

I'll respond in English as you requested!

Yes, there are several libraries and modules available in Python for working with trees. Here's an overview of some popular ones:

Python's built-in collections module: The defaultdict class in the collections module can be used to implement a binary tree or any other type of tree data structure.

Example:

from collections import defaultdict

class TreeNode:


def init(self, value):


self.value = value


self.left = None


self.right = None


def create_tree(root_value):


tree = TreeNode(root_value)


return tree


root_node = create_tree(1)
treelib library: This is a lightweight Python package designed for working with trees. It provides classes for creating and manipulating various types of trees, including binary, n-ary, and directed graphs.

Example:

from treelib import Tree
Create a new tree

t = Tree()

Add nodes to the tree

root_node = t.create_node("Root Node")


child_node1 = t.create_node("Child Node 1", parent=root_node)


child_node2 = t.create_node("Child Node 2", parent=root_node)
graphlib library: This is a Python package for working with directed and undirected graphs, which can be used to create trees as well.

Example:

from graphlib import TopologicalSorter
Create a new topological sorter (tree)

ts = TopologicalSorter()

Add nodes and edges to the tree

ts.add_edge("Node A", "Node B")


ts.add_edge("Node C", "Node D")
networkx library: This is another popular Python package for creating and manipulating complex networks, including trees.

Example:

import networkx as nx
Create a new graph (tree)

G = nx.DiGraph()

Add nodes and edges to the tree

G.add_node("Node A")


G.add_edge("Node A", "Node B")

These libraries can be used for tasks such as:

Creating trees from data structures like lists or dictionaries Performing operations on tree nodes (e.g., traversals, node manipulation) Visualizing tree structures using plotting and graphing tools

Choose the one that best fits your specific use case or needs. Happy coding!

Related Articles