Question

Please make an Array-based implementation of a Binary Tree in Python based on the given file below. Make sure to keep the Abstract Data File of the starter code below when building the Array-based implementation.

Python Starter Code Given Below:

class ArrayBinaryTree(BinaryTree):
    """Linked representation of a binary tree structure."""

    # -------------------------- nested _Node class --------------------------
    class _Node:

        def __init__(self, element, parent=None, left=None, right=None):

    # -------------------------- nested Position class --------------------------
    class Position(BinaryTree.Position):
        """An abstraction representing the location of a single element."""

        def __init__(self, container, node):

        def element(self):

        def __eq__(self, other):

    # ------------------------------- utility methods -------------------------------
    def _validate(self, p):
        """Return associated node, if position is valid."""

    def _make_position(self, node):
        """Return Position instance for given node (or None if no node)."""

    # -------------------------- binary tree constructor --------------------------
    def __init__(self):
        """Create an initially empty binary tree."""

    # -------------------------- public accessors --------------------------
    def __len__(self):
        """Return the total number of elements in the tree."""

    def root(self):
        """Return the root Position of the tree (or None if tree is empty)."""

    def parent(self, p):
        """Return the Position of p's parent (or None if p is root)."""

    def left(self, p):
        """Return the Position of p's left child (or None if no left child)."""

    def right(self, p):
        """Return the Position of p's right child (or None if no right child)."""

    def num_children(self, p):
        """Return the number of children of Position p."""

    # -------------------------- nonpublic mutators --------------------------
    def _add_root(self, e):
        """Place element e at the root of an empty tree and return new Position."""

    def _add_left(self, p, e):
        """Create anew left child for Position p, storing element e."""

    def _add_right(self, p, e):
        """Create a new right child for Position p, storing element e. Return the Position of new node. Raise ValueError if Position p is invalid or p already has a right child.
        """

    def _replace(self, p, e):
        """Replace the element at position p with e, and return old element."""

    def _delete(self, p):
        """Delete the node at Position p, and replace it with its child, if any.  Return the element that had been stored at Position p.Raise ValueError if Position p is invalid or p has two children.
        """

    def _attach(self, p, t1, t2):
        """Attach trees t1 and t2, respectively, as the left and right subtrees of the external Position p. As a side effect, set t1 and t2 to empty.
        Raise TypeError if trees t1 and t2 do not match type of this tree. Raise ValueError if Position p is invalid or not external.
        """

Answer 1

For this answer there is theory part and implementation part

and here is implementation part..

tree = [None] * 10

def root(key):
if tree[0] != None:
print("Can't add root")
else:
tree[0] = key


def left_son(key, parent):
if tree[parent] == None:
print("Child cannot set", (parent * 2) + 1, ", no parent found")
else:
tree[(parent * 2) + 1] = key


def right_son(key, parent):
if tree[parent] == None:
print("Child cannot set", (parent * 2) + 2, ", no parent found")
else:
tree[(parent * 2) + 2] = key


def print_tree():
for i in range(10):
if tree[i] != None:
print(tree[i], end="")
else:
print("-", end="")
print()

root('A')
right_son('C', 0)
left_son('D', 1)
right_son('E', 1)
right_son('F', 2)
print_tree()