a) Based on the binary tree implementation from the Python program below write a recursive method that...

a) Based on the binary tree implementation from the Python program below write a recursive method that calculates the number of leaf nodes in the tree.

class Binaertre:
    def __init__(self, datatobjekt):
        self.data = datatobjekt
        self.forelder = None
        self.venstre_barn = None
        self.hoyre_barn = None

    @property
    def venstre_barn(self):
        return self.__venstre_barn

    @venstre_barn.setter
    def venstre_barn(self, node):
        self.__venstre_barn = node
        if node is not None:
            node.forelder = self

    @property
    def hoyre_barn(self):
        return self.__hoyre_barn

    @hoyre_barn.setter
    def hoyre_barn(self, node):
        self.__hoyre_barn = node
        if node is not None:
            node.forelder = self

    def er_bladnode(self):
        if self.venstre_barn is None and self.hoyre_barn is None:
            return True
        return False

    def rekursiv_preorder_utskrift(self, nivaa=0):
        for i in range(nivaa):
            print("\t", end="")
        print(self.data)
        if self.venstre_barn is not None:
            self.venstre_barn.rekursiv_preorder_utskrift(nivaa+1)
        if self.hoyre_barn is not None:
            self.hoyre_barn.rekursiv_preorder_utskrift(nivaa+1)

    def rekursiv_postorder_utregning(self):
        if self.er_bladnode():
            return float(self.data)
        venstre_verdi = self.venstre_barn.rekursiv_postorder_utregning()
        hoyre_verdi = self.hoyre_barn.rekursiv_postorder_utregning()
        if self.data == "+":
            return venstre_verdi + hoyre_verdi
        if self.data == "*":
            return venstre_verdi * hoyre_verdi
        if self.data == "**":
            return venstre_verdi ** hoyre_verdi
        if self.data == "-":
            return venstre_verdi + hoyre_verdi
        if self.data == "/":
            return venstre_verdi / hoyre_verdi
        raise ValueError(f"Ukjent operator: {self.data}")

    def rekursiv_inorder_formelutskrift(self):
        if self.er_bladnode():
            print(self.data, end="")
        else:
            print("(", end="")
            self.venstre_barn.rekursiv_inorder_formelutskrift()
            print(f" {self.data} ", end="")
            self.hoyre_barn.rekursiv_inorder_formelutskrift()
            print(")", end="")

    def __iter__(self):
        return BinaertrePostorderIterator(self)

class BinaertrePostorderIterator:
    def __init__(self, treet):
        self.treet = treet
        self.stabel = []
        self.stabel.append((treet, 0))

    def __next__(self):
        while len(self.stabel) > 0:
            element = self.stabel.pop()
            if element[0].er_bladnode():
                return element[0].data
            if element[1] == 0:
                self.stabel.append((element[0], 1))
                if element[0].venstre_barn is not None:
                    self.stabel.append((element[0].venstre_barn, 0))
            if element[1] == 1:
                self.stabel.append((element[0], 2))
                if element[0].hoyre_barn is not None:
                    self.stabel.append((element[0].hoyre_barn, 0))
            if element[1] == 2:
                return element[0].data
        raise StopIteration

    def __iter__(self):
        return self

if __name__ == "__main__":
    rot = Binaertre("+")
    v_barn_1 = Binaertre("**")
    rot.venstre_barn = v_barn_1
    v_v_barn = Binaertre("5")
    v_h_barn = Binaertre("2")
    v_barn_1.venstre_barn = v_v_barn
    v_barn_1.hoyre_barn = v_h_barn
    h_barn_1 = Binaertre("+")
    rot.hoyre_barn = h_barn_1
    h_v_barn = Binaertre("*")
    h_v_barn.venstre_barn = Binaertre("2")
    h_v_barn.hoyre_barn = Binaertre("3")
    h_barn_1.venstre_barn = h_v_barn
    h_h_barn = Binaertre("*")
    h_barn_1.hoyre_barn = h_h_barn
    h_h_barn.venstre_barn = Binaertre("7")
    h_h_h_barn = Binaertre("+")
    h_h_barn.hoyre_barn = h_h_h_barn
    h_h_h_barn.venstre_barn = Binaertre("9")
    h_h_h_barn.hoyre_barn = Binaertre("5")
    rot.rekursiv_preorder_utskrift()
    print(rot.rekursiv_postorder_utregning())
    rot.rekursiv_inorder_formelutskrift()
    print()
    print("\n Iterativ iteratortest")
    for element in rot:
        print(element)

Expert Solution

class Binaertre:
    def __init__(self, datatobjekt):
        self.data = datatobjekt
        self.forelder = None
        self.venstre_barn = None
        self.hoyre_barn = None

    @property
    def venstre_barn(self):
        return self.__venstre_barn

    @venstre_barn.setter
    def venstre_barn(self, node):
        self.__venstre_barn = node
        if node is not None:
            node.forelder = self

    @property
    def hoyre_barn(self):
        return self.__hoyre_barn

    @hoyre_barn.setter
    def hoyre_barn(self, node):
        self.__hoyre_barn = node
        if node is not None:
            node.forelder = self

    def er_bladnode(self):
        if self.venstre_barn is None and self.hoyre_barn is None:
            return True
        return False

    def rekursiv_preorder_utskrift(self, nivaa=0):
        for i in range(nivaa):
            print("\t", end="")
        print(self.data)
        if self.venstre_barn is not None:
            self.venstre_barn.rekursiv_preorder_utskrift(nivaa+1)
        if self.hoyre_barn is not None:
            self.hoyre_barn.rekursiv_preorder_utskrift(nivaa+1)

    def rekursiv_postorder_utregning(self):
        if self.er_bladnode():
            return float(self.data)
        venstre_verdi = self.venstre_barn.rekursiv_postorder_utregning()
        hoyre_verdi = self.hoyre_barn.rekursiv_postorder_utregning()
        if self.data == "+":
            return venstre_verdi + hoyre_verdi
        if self.data == "*":
            return venstre_verdi * hoyre_verdi
        if self.data == "**":
            return venstre_verdi ** hoyre_verdi
        if self.data == "-":
            return venstre_verdi + hoyre_verdi
        if self.data == "/":
            return venstre_verdi / hoyre_verdi
        raise ValueError(f"Ukjent operator: {self.data}")

    def rekursiv_inorder_formelutskrift(self):
        if self.er_bladnode():
            print(self.data, end="")
        else:
            print("(", end="")
            self.venstre_barn.rekursiv_inorder_formelutskrift()
            print(f" {self.data} ", end="")
            self.hoyre_barn.rekursiv_inorder_formelutskrift()
            print(")", end="")

    def __iter__(self):
        return BinaertrePostorderIterator(self)

    def leaf_count(self):
        # Check if left and right subtrees are None, if they are return 1 as current node is leaf
        if(self.hoyre_barn == None and self.venstre_barn == None):
            return 1
        
        ans = 0
        # Else recursively call for left and right subtrees after checking if they are not None.
        if(self.hoyre_barn != None):
            ans += self.hoyre_barn.leaf_count()
        if(self.venstre_barn != None):
            ans += self.venstre_barn.leaf_count()
        
        return ans

class BinaertrePostorderIterator:
    def __init__(self, treet):
        self.treet = treet
        self.stabel = []
        self.stabel.append((treet, 0))

    def __next__(self):
        while len(self.stabel) > 0:
            element = self.stabel.pop()
            if element[0].er_bladnode():
                return element[0].data
            if element[1] == 0:
                self.stabel.append((element[0], 1))
                if element[0].venstre_barn is not None:
                    self.stabel.append((element[0].venstre_barn, 0))
            if element[1] == 1:
                self.stabel.append((element[0], 2))
                if element[0].hoyre_barn is not None:
                    self.stabel.append((element[0].hoyre_barn, 0))
            if element[1] == 2:
                return element[0].data
        raise StopIteration

    def __iter__(self):
        return self

if __name__ == "__main__":
    rot = Binaertre("+")
    v_barn_1 = Binaertre("**")
    rot.venstre_barn = v_barn_1
    v_v_barn = Binaertre("5")
    v_h_barn = Binaertre("2")
    v_barn_1.venstre_barn = v_v_barn
    v_barn_1.hoyre_barn = v_h_barn
    h_barn_1 = Binaertre("+")
    rot.hoyre_barn = h_barn_1
    h_v_barn = Binaertre("*")
    h_v_barn.venstre_barn = Binaertre("2")
    h_v_barn.hoyre_barn = Binaertre("3")
    h_barn_1.venstre_barn = h_v_barn
    h_h_barn = Binaertre("*")
    h_barn_1.hoyre_barn = h_h_barn
    h_h_barn.venstre_barn = Binaertre("7")
    h_h_h_barn = Binaertre("+")
    h_h_barn.hoyre_barn = h_h_h_barn
    h_h_h_barn.venstre_barn = Binaertre("9")
    h_h_h_barn.hoyre_barn = Binaertre("5")
    rot.rekursiv_preorder_utskrift()
    print(rot.rekursiv_postorder_utregning())
    rot.rekursiv_inorder_formelutskrift()
    print()
    print("\n Iterativ iteratortest")
    for element in rot:
        print(element)

Added leaf_count() method, added the comments in english as I dont know Danish :)

I would love to resolve any queries in the comments. Please consider dropping an upvote to help out a struggling college kid :)

Happy Coding !!

venereology answered 1 year ago

(Binary Tree): Write a recursive implementation of the function, singleParent, that returns the number of the...

(Binary Tree): Write a recursive implementation of the function, singleParent, that returns the number of the nodes in a binary tree that have only one child. Convert it to an iterative version. in C++

Write a method for binary tree in Python that can determine whether a binary tree is...

Write a method for binary tree in Python that can determine whether a binary tree is a binary search tree or not. The input should be a binary tree. The output should be true or false. True= binary tree meets the criteria to be a binary search tree. False= does not meet the criteria to be a binary search tree.

Please make an Array-based implementation of a Binary Tree in Python based on the given file...

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."""...

Write a recursive implementation of insertion sort. Draw a tree of recursive calls for your prototype...

Write a recursive implementation of insertion sort. Draw a tree of recursive calls for your prototype random dataset and compare its big-O efficiency to that of iterative insertion sort. Run your prototype datasets (best, worst, random) from homework 1 and compare the results to the ones for iterative insertion sort. Which version is better? Make sure to present the results in the table form used in homework 1. Include the data for both iterative and recursive versions.

Implement a recursive program to draw a binary tree so that the root appears at the...

Implement a recursive program to draw a binary tree so that the root appears at the center of the page, the root of the left subtree is at the center of the left half of the page, etc. Alternative formulation: implement a recursive preorder binary tree traversal so that, when each node is displayed on the page, if the node is a left child it is shown to the left of the node displayed above it, and if it is...

Create an array-based implementation of a binary tree. (WRITE IN JAVA) DON'T FORGET TO INCLUDE PSEUDOCODE...

Create an array-based implementation of a binary tree. (WRITE IN JAVA) DON'T FORGET TO INCLUDE PSEUDOCODE AND UML DIAGRAM

PYTHON CODING Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary...

PYTHON CODING Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary Search Tree in ascending or deceasing order. The order type is an input to the method and can be "ascending" or "descending". The ascending input would return the node values of the tree beginning with the smallest and ending with the largest, descending returns the opposite. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify...

Write a non recursive method to insert into an AVL tree in Java

PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary...

PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary Tree Node structure class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None class BSTree(): def __init__(self, rootdata): self.root = Node(rootdata) def insert(self, data, cur_node): if data < cur_node.data: if cur_node.left == None: cur_node.left = Node(data) else: self.insert(data, cur_node.left) elif data > cur_node.data: if cur_node.right == None: cur_node.right = Node(data) else:...

Write a recursive method to implement Binary Search of a sorted integer array. Signature of method...

Write a recursive method to implement Binary Search of a sorted integer array. Signature of method could be public int BinarySearch(int target, int low, int high)

Question