ArrayBinaryTree is given below

class ArrayBinaryTree: """ Array based binary tree implementation, root starts 1 """ def __init__(self): self._data = [None] * 10 self._size = 0 # the number of nodes self._root = 1 # root starts index 1 def size(self): return self._size

def isEmpty(self): return self._size == 0 def root(self): return self._data[self._root]

def parent(self,idx): """return parentNone if there is not parent (root)""" return None if idx == 1 else self._data[int(idx/2)]

def children(self,idx): """ return a [left, right]""" return [self.left(idx),self.right(idx)]

def left(self,idx): #your code goes here to replace "pass" pass

def right(self,idx): #your code goes here to replace "pass" pass

def isInternal(self,idx): #your code goes here to replace "pass" pass

def isExternal(self,idx): #your code goes here to replace "pass" pass def setRoot(self,v): if self._data[cur] == None:#if the root does not exist print("The root node does not exist") return None self._data[cur] = v return cur

def setLeft(self,cur,v): """set the left node value.""" #your code goes here to replace "pass" #make sure to check whether the current, the child exist pass

def setRight(self,cur,v): """set the right node value.""" #your code goes here to replace "pass" #make sure to check whether the current, the child exist pass

def insertRoot(self, v): if not self._data[self._root] == None: print("The root node already exists") return None self._data[self._root] = v self._size += 1 return 1

def insertLeft(self,cur,v): """recursively insert to the left node. Increase the array size if needed.""" #your code goes here to replace "pass" #make sure to check whether the current, the child exist; if the child exist, recursively go left #also check the array space, expand it if needed using _resize method pass

def insertRight(self,cur,v): """insert to the right node. Increase the array size if needed.""" #your code goes here to replace "pass" #make sure to check whether the current, the child exist; if the child exist, recursively go right #also check the array space, expand it if needed using _resize method pass

def inOrder(self): """Print an inorder iteration of nodes in the tree.""" if not self.isEmpty(): for p in self._subtree_inorder(self.root()): print(p) def _subtree_inorder(self, p): """Generate an inorder iteration of nodes in subtree rooted at p.""" if self.left(p) is not None: # if left child exists, traverse its subtree for other in self._subtree_inorder(self.left(p)): yield other yield p # visit p between its subtrees if self.right(p) is not None: # if right child exists, traverse its subtree for other in self._subtree_inorder(self.right(p)): yield other def preOrder(self): """Print a preorder of nodes in the tree.""" if not self.isEmpty(): for p in self._subtree_preorder(self.root()): # start recursion print(p)

def _subtree_preorder(self, p): """Generate a preorder iteration of positions in subtree rooted at p.""" #your code goes here to replace "pass"

def postOrder(self): """Print a postorder of nodes in the tree.""" if not self.isEmpty(): for p in self._subtree_postorder(self.root()): # start recursion print(p)

def _subtree_postorder(self, p): """Generate a postorder iteration of node in subtree rooted at p.""" #your code goes here to replace "pass" def printTreeArray(self): print(self._data)

def _resize(self, cap): # we assume cap >= len(self) """Resize to a new list of capacity >= len(self).""" old = self._data # keep track of existing list self._data = [None] * cap # allocate list with new capacity for k in range(self._size): # only consider existing elements self._data[k] = old[k] # intentionally shift indices

if __name__ == '__main__': #testing code bt = ArrayBinaryTree() bt.insertRoot(1) bt.insertLeft(1,2) bt.insertRight(1,3) bt.insertLeft(1,4) bt.insertRight(2,5) bt.insertLeft(3,6) bt.insertRight(1,7) bt.printTreeArray() bt.inOrder() bt.postOrder() bt.preOrder()

2. (70 points) Implement the binary tree ADT into class ArrayBinaryTree using the array-based representation described in Section 8.3.2 of the textbook (pages 325-326). Assuming root is at index 1. For simplicity, assume your binary tree stores integers only. Include the following methods: left(), right(), is Internal(), is External() setLeft(v), setRight(v); these methods should not set the node value which does not exist. insertLeft(node, v): recursively insert a node to the left of the given node, i.e. if the current node has left child, insert to the left of the child, and so on. insertRight(node,v): recursively insert a node to the right of the given node, i.e. if the current node has right child, insert to the right of the child, and so on. preOrder() and postOrder(): print the sequence of the binary tree using an preorder, or postorder traversal, respectively. Download ArrayBinaryTree.py and complete these above methods. An example testing code is also provided in the file. You can test with more your own examples