This is a Python program to display the nodes of a tree using BFS traversal.
The program creates a tree and presents a menu to the user to perform various operations including printing its BFS traversal.
1. Create a class Tree with instance variables key and children.
2. Define methods set_root, add, bfs and search.
3. The method set_root takes a key as argument and sets the instance variable key equal to it.
4. The method add appends a node to the list children.
5. The method search returns a node with a specified key.
6. The method bfs prints the BFS traversal of the tree. It uses a queue to do the traversal.
Here is the source code of a Python program to display the nodes of a tree using BFS traversal. The program output is shown below.
class Tree: def __init__(self, data=None): self.key = data self.children = [] def set_root(self, data): self.key = data def add(self, node): self.children.append(node) def search(self, key): if self.key == key: return self for child in self.children: temp = child.search(key) if temp is not None: return temp return None def bfs(self): queue = [self] while queue != []: popped = queue.pop(0) for child in popped.children: queue.append(child) print(popped.key, end=' ') tree = None print('Menu (this assumes no duplicate keys)') print('add <data> at root') print('add <data> below <data>') print('bfs') print('quit') while True: do = input('What would you like to do? ').split() operation = do[0].strip().lower() if operation == 'add': data = int(do[1]) new_node = Tree(data) suboperation = do[2].strip().lower() if suboperation == 'at': tree = new_node elif suboperation == 'below': position = do[3].strip().lower() key = int(position) ref_node = None if tree is not None: ref_node = tree.search(key) if ref_node is None: print('No such key.') continue ref_node.add(new_node) elif operation == 'bfs': if tree is None: print('Tree is empty.') else: print('BFS traversal: ', end='') tree.bfs() print() elif operation == 'quit': break
1. A variable is created to store the binary tree.
2. The user is presented with a menu to perform operations on the tree.
3. The corresponding methods are called to perform each operation.
4. The method bfs is called on the tree to print its breadth-first traversal.
Case 1: Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> bfs quit What would you like to do? add 1 at root What would you like to do? add 2 below 1 What would you like to do? bfs BFS traversal: 1 2 What would you like to do? add 3 below 1 What would you like to do? add 10 below 2 What would you like to do? add 12 below 2 What would you like to do? add 14 below 3 What would you like to do? add 7 below 14 What would you like to do? bfs BFS traversal: 1 2 3 10 12 14 7 What would you like to do? quit Case 2: Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> bfs quit What would you like to do? add 5 at root What would you like to do? add 7 below 5 What would you like to do? add 8 below 5 What would you like to do? add 4 below 7 What would you like to do? add 3 below 7 What would you like to do? add 1 below 8 What would you like to do? add 2 below 1 What would you like to do? bfs BFS traversal: 5 7 8 4 3 1 2 What would you like to do? quit
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.
- Apply for Python Internship
- Check Information Technology Books
- Practice Programming MCQs
- Apply for Programming Internship
- Check Python Books