This is a Python program to perform depth-first post-order traversal on a tree.
The program creates a tree and presents a menu to the user to perform operations on the tree including post-order traversal.
1. Create a class Tree with instance variables key and children.
2. Define methods set_root, add, postorder 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 postorder displays a DFS post-order traversal of the tree.
Here is the source code of a Python program to perform depth-first post-order traversal on a tree. 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 postorder(self): for child in self.children: child.postorder() print(self.key, end=' ') tree = None print('Menu (this assumes no duplicate keys)') print('add <data> at root') print('add <data> below <data>') print('dfs') 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 == 'dfs': print('Post-order traversal: ', end='') tree.postorder() 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 postorder is called on the tree to display a DFS post-order traversal.
Case 1: Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> dfs 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? add 3 below 2 What would you like to do? add 4 below 2 What would you like to do? add 5 below 1 What would you like to do? add 6 below 1 What would you like to do? dfs Post-order traversal: 3 4 2 5 6 1 What would you like to do? quit Case 2: Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> dfs quit What would you like to do? add 3 at root What would you like to do? add 5 below 3 What would you like to do? add 2 below 3 What would you like to do? add 1 below 5 What would you like to do? add 6 below 5 What would you like to do? dfs Post-order traversal: 1 6 5 2 3 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.
