This is a Python program to count the number of non-leaf nodes in a tree.
The program creates a tree and counts the number of non-leaf nodes in the tree.
1. Create a class Tree with instance variables key and children.
2. Define methods set_root, add, count_nonleaf_nodes 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 count_nonleaf_nodes counts the number of non-leaf nodes and returns it.
Here is the source code of a Python program to count the number of non-leaf nodes in 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 count_nonleaf_nodes(self): nonleaf_count = 0 if self.children != []: nonleaf_count = 1 for child in self.children: nonleaf_count = nonleaf_count + child.count_nonleaf_nodes() return nonleaf_count tree = None print('Menu (this assumes no duplicate keys)') print('add <data> at root') print('add <data> below <data>') print('count') 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 == 'count': if tree is None: print('Tree is empty.') else: count = tree.count_nonleaf_nodes() print('Number of nonleaf nodes: {}'.format(count)) 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 count_nonleaf_nodes is called on the tree to calculate the number of non-leaf nodes in the tree.
Case 1: Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> count quit What would you like to do? add 1 at root What would you like to do? count Number of nonleaf nodes: 0 What would you like to do? add 2 below 1 What would you like to do? add 3 below 1 What would you like to do? count Number of nonleaf nodes: 1 What would you like to do? add 4 below 2 What would you like to do? count Number of nonleaf nodes: 2 What would you like to do? add 5 below 4 What would you like to do? count Number of nonleaf nodes: 3 What would you like to do? quit Case 2: Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> count 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 3 What would you like to do? add 5 below 4 What would you like to do? count Number of nonleaf nodes: 4 What would you like to do? add 6 below 4 What would you like to do? count Number of nonleaf nodes: 4 What would you like to do? add 7 below 6 What would you like to do? count Number of nonleaf nodes: 5 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
