# Implementation of Binary Tree (Supplementary)

### This implementation of binary tree includes binary tree traversal in order, in order and after order, as well as binary tree traversal in order, including the height of the binary tree, leaf nodes and inverted binary tree.

The sequence traversal of binary tree is still to use Python's built-in deque to realize a queue. According to the nature of FIFO, the root node of binary tree is put into the queue to determine whether the queue is empty or not. If it is not empty, an element is popped up and the value of the element is printed. If the element has a left child, the left child is put into the queue, and if there is a right child, the left child is put into the queue. Team entry

### Code:

```  1 from collections import deque
2
3
4 class Queue:  # With built-in deque We can quickly achieve one Queue
5     def __init__(self):
6         self._elem = deque()
7
8     def append(self, value):
9         return self._elem.append(value)
10
11     def pop(self):
12         return self._elem.popleft()
13
14     def empty(self):
15         return len(self._elem) == 0
16
17
18 class BTree(object):
19     def __init__(self, data=None, left=None, right=None):
20         self.data = data
21         self.left = left
22         self.right = right
23
24     def preorder(self):
25         if self.data is not None:
26             print(self.data, end=',')
27         if self.left is not None:
28             self.left.preorder()
29         if self.right is not None:
30             self.right.preorder()
31
32     def midorder(self):
33         if self.left is not None:
34             self.left.midorder()
35         if self.data is not None:
36             print(self.data, end=',')
37         if self.right is not None:
38             self.right.midorder()
39
40     def postorder(self):
41         if self.left is not None:
42             self.left.postorder()
43         if self.right is not None:
44             self.right.postorder()
45         if self.data is not None:
46             print(self.data, end=',')
47
48     def levelorder(self):
49
50         # Return the left child of a node
51         def LChild_Of_Node(node):
52             return node.left if node.left is not None else None
53
54         # Right child returning to a node
55         def RChild_Of_Node(node):
56             return node.right if node.right is not None else None
57
58         # Sequence traversal list
59         level_order = []
60         # Whether to add data in the root node
61         if self.data is not None:
62             level_order.append([self])
63
64         # Height of Binary Tree
65         height = self.height()
66         if height >= 1:
67             # Operate on Layer 2 and subsequent Layers, stay level_order Add nodes instead of data
68             for _ in range(2, height + 1):
69                 level = []  # Nodes in this layer
70                 for node in level_order[-1]:
71                     # If the left child is not empty, add the left child
72                     if LChild_Of_Node(node):
73                         level.append(LChild_Of_Node(node))
74                     # If the right child is not empty, add the right child
75                     if RChild_Of_Node(node):
76                         level.append(RChild_Of_Node(node))
77                 # If the layer is not empty, add the layer
78                 if level:
79                     level_order.append(level)
80
81             # Extract data from each layer
82             for i in range(0, height):  # Layer number
83                 for index in range(len(level_order[i])):
84                     level_order[i][index] = level_order[i][index].data
85
86         return level_order
87
88     def height(self):
89         if self.data is None:
90             return 0
91         elif self.left is None and self.right is None:
92             return 1
93         elif self.left is None and self.right is not None:
94             return 1 + self.left.height()
95         elif self.left is not None and self.right is None:
96             return 1 + self.left.height()
97         else:
98             return 1 + max(self.left.height(), self.right.height())
99
100     def leaves(self):
101         if self.data is None:
102             return None
103         elif self.left is None and self.right is None:
104             print(self.data, end=',')
105         elif self.left is None and self.right is not None:
106             self.right.leaves()
107         elif self.left is not None and self.right is None:
108             self.left.leaves()
109         else:
110             self.left.leaves()
111             self.right.leaves()
112
113     # Inverse Binary Tree
114     def reverse(self):
115         if self.data is not None:
116             if self.left and self.right:
117                 self.left, self.right = self.right, self.left
118                 self.left.reverse()
119                 self.right.reverse()
120
121     # @staticmethod
122     # def layer_trav(subtree):
123     #     cur_nodes = [subtree]  # current layer nodes
124     #     next_nodes = []
125     #     while cur_nodes or next_nodes:
126     #         for node in cur_nodes:
127     #             print(node.data, end=',')
128     #             if node.left:
129     #                 next_nodes.append(node.left)
130     #             if node.right:
131     #                 next_nodes.append(node.right)
132     #         cur_nodes = next_nodes  # Continue traversing the next layer
133     #         next_nodes = []
134
135     @staticmethod
136     def layer_trav(subtree):
137         q = Queue()
138         q.append(subtree)
139         while not q.empty():
140             node = q.pop()
141             print(node.data, end=',')
142             if node.left:
143                 q.append(node.left)
144             if node.right:
145                 q.append(node.right)
146
147
148 if __name__ == '__main__':
149     right_tree = BTree(6)
150     right_tree.left = BTree(2)
151     right_tree.right = BTree(4)
152
153     left_tree = BTree(5)
154     left_tree.left = BTree(1)
155     left_tree.right = BTree(3)
156
157     tree = BTree(11)
158     tree.left = left_tree
159     tree.right = right_tree
160
161     left_tree = BTree(7)
162     left_tree.left = BTree(3)
163     left_tree.right = BTree(4)
164
165     right_tree = tree  # Add new variables
166     tree = BTree(18)
167     tree.left = left_tree
168     tree.right = right_tree
169     tree.root = tree
170
171     print('The precedent traversal is:')
172     tree.preorder()
173     print('\n')
174
175     print('Subsequent traversal is:')
176     tree.postorder()
177     print('\n')
178
179     print('The middle order traversal is:')
180     tree.midorder()
181     print('\n')
182
183     print('Sequence traversal is:')
184     level_order = tree.levelorder()
185     tree.layer_trav(tree)
186     print('\n')
187     print(level_order)
188
189     print('The leaf node is:')
190     tree.leaves()
191     print('\n')
192
193     print('The height of the tree is:')
194     print(tree.height())
195     print('\n')
196
197     print('Inverse Binary Tree')
198     tree.reverse()
199     print('Preorder traversal')
200     tree.preorder()
201     print('\n')
202     print('level traversal')
203     tree.layer_trav(tree)```

Keywords: Python

Added by Randomizer on Wed, 09 Oct 2019 06:19:12 +0300