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)