Trees
In computer science, a tree is a hierarchical data structure that consists of nodes connected by edges. It is similar to a family tree, where the nodes represent individuals and the edges represent relationships between them.
Trees have various applications in computer science, such as representing hierarchical data, organizing data for efficient search operations, and implementing algorithms like binary search.
A tree is composed of nodes, where each node contains data and may have zero or more child nodes. The topmost node of a tree is called the root node.
Here's an example of creating and traversing a tree in Python:
1if __name__ == '__main__':
2 class Node:
3 def __init__(self, data):
4 self.data = data
5 self.left = None
6 self.right = None
7
8 # Create a tree
9 root = Node('A')
10 root.left = Node('B')
11 root.right = Node('C')
12 root.left.left = Node('D')
13 root.left.right = Node('E')
14 root.right.left = Node('F')
15 root.right.right = Node('G')
16
17 # Perform tree traversal
18 def pre_order(node):
19 if node:
20 print(node.data, end=' ')
21 pre_order(node.left)
22 pre_order(node.right)
23
24 print('Pre-order: ', end='')
25 pre_order(root)
26
27 def in_order(node):
28 if node:
29 in_order(node.left)
30 print(node.data, end=' ')
31 in_order(node.right)
32
33 print('
34In-order: ', end='')
35 in_order(root)
36
37 def post_order(node):
38 if node:
39 post_order(node.left)
40 post_order(node.right)
41 print(node.data, end=' ')
42
43 print('
44Post-order: ', end='')
45 post_order(root)In this example, we create a tree with nodes labeled from 'A' to 'G'. We then perform three types of tree traversals:
- Pre-order traversal: Visit the current node, then recursively visit the left subtree and the right subtree.
- In-order traversal: Recursively visit the left subtree, then visit the current node, and finally recursively visit the right subtree.
- Post-order traversal: Recursively visit the left subtree, then recursively visit the right subtree, and finally visit the current node.
The output of the code will be:
1Pre-order: A B D E C F G
2In-order: D B E A F C G
3Post-order: D E B F G C Axxxxxxxxxx post_order(root)if __name__ == '__main__': class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Create a tree root = Node('A') root.left = Node('B') root.right = Node('C') root.left.left = Node('D') root.left.right = Node('E') root.right.left = Node('F') root.right.right = Node('G') # Perform tree traversal def pre_order(node): if node: print(node.data, end=' ') pre_order(node.left) pre_order(node.right) print('Pre-order: ', end='') pre_order(root) def in_order(node): if node: in_order(node.left)