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)

Solutions

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 7 months ago

Next > < Previous

Related Solutions

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

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

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 an implementation of the set class, with associated iterators using a binary search tree. Add...

Write an implementation of the set class, with associated iterators using a binary search tree. Add to each node a link to the parent node. (C++)

PYTHON CODING Create a method for a Binary Search tree that finds the lowest common ancestor...

PYTHON CODING Create a method for a Binary Search tree that finds the lowest common ancestor of two nodes in a tree (nodesLCA). The two nodes are input by the user identified by their values. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.Illustrate the performance of the nodesLCA method. For the BST of datalist excute the method on following pairs: (500, 271), (21, 203) and (53 , 991)...

PYTHON CODING Create a method for a Binary Search tree that finds the lowest common ancestor...

PYTHON CODING Create a method for a Binary Search tree that finds the lowest common ancestor of two nodes in a tree (nodesLCA). The two nodes are input by the user identified by their values. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose. Illustrate the performance of the nodesLCA method. For the BST of datalist excute the method on following pairs: (500, 271), (21, 203) and (53 ,...

PYTHON CODING Create a method for the Binary Search Tree (deleteNode) that deletes a specified node...

PYTHON CODING Create a method for the Binary Search Tree (deleteNode) that deletes a specified node identified by its value, and rearranges the descendants of the deleted node to ensure the resulting Tree meets the requirements of a Binary Search Tree. a) Discuss and justify your approach to address each possible case. b) Is the new tree (with the deleted node removed) unique? Discuss your answer. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or...

PYTHON CODING Create a method for the Binary Search Tree (deleteNode) that deletes a specified node...

Subjects