Question

Create a preorder iterator for the class binarytree from the Python program below.
class Binarytree:

    def __init__(self, DataObject):
        self.data = DataObject
        self.parents = None
        self.left_child = None
        self.right_child = None

    @property
    def left_child(self):
        return self.__left_child

    @left_child.setter
    def left_child(self, node):
        self.__left_child = node
        if node is not None:
            node.parents = self

    @property
    def right_child(self):
        return self.__right_child

    @right_child.setter
    def right_child(self, node):
        self.__right_child = node
        if node is not None:
            node.parents = self

    def is_leafNode(self):
        if self.left_child is None and self.right_child is None:
            return True
        return False

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

    def rekursive_preorder_calculation(self):
        if self.is_leafNode():
            return float(self.data)
        left_value = self.left_child.rekursive_preorder_calculation()
        right_value = self.right_child.rekursive_preorder_calculation()
        if self.data == "+":
            return left_value + right_value
        if self.data == "*":
            return left_value * right_value
        if self.data == "**":
            return left_value ** right_value
        if self.data == "-":
            return left_value + right_value
        if self.data == "/":
            return left_value / right_value
        raise ValueError(f"Ukjent operator: {self.data}")

    def rekursiv_inorder_formulaprint(self):
        if self.is_leafNode():
            print(self.data, end="")
        else:
            print("(", end="")
            self.left_child.rekursiv_inorder_formulaprint()
            print(f" {self.data} ", end="")
            self.right_child.rekursiv_inorder_formulaprint()
            print(")", end="")

    def __iter__(self):
        return BinarytreePostorderIterator(self)

class BinarytreePostorderIterator:
    def __init__(self, tree):
        self.tree = tree
        self.stabel = []
        self.stabel.append((tree, 0))

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

    def __iter__(self):
        return self


if __name__ == "__main__":
    rot = Binarytree("+")
    v_barn_1 = Binarytree("**")
    rot.left_child = v_barn_1
    v_v_barn = Binarytree("5")
    v_h_barn = Binarytree("2")
    v_barn_1.left_child = v_v_barn
    v_barn_1.right_child = v_h_barn
    h_barn_1 = Binarytree("+")
    rot.right_child = h_barn_1
    h_v_barn = Binarytree("*")
    h_v_barn.left_child = Binarytree("2")
    h_v_barn.right_child = Binarytree("3")
    h_barn_1.left_child = h_v_barn
    h_h_barn = Binarytree("*")
    h_barn_1.right_child = h_h_barn
    h_h_barn.left_child = Binarytree("7")
    h_h_h_barn = Binarytree("+")
    h_h_barn.right_child = h_h_h_barn
    h_h_h_barn.left_child = Binarytree("9")
    h_h_h_barn.right_child = Binarytree("5")
    rot.rekursive_preorder_print()
    print(rot.rekursive_preorder_calculation())
    rot.rekursiv_inorder_formulaprint()
    print()
    print("\n Iterativ iteratortest")
    for element in rot:
        print(element)

Answer 1

Preorder Traversal in any binary tree means that we'll go in the order Root -> Left -> right

It generally means that we'll go first at the root node, then the left child and finally to the right child.

Since we've been asked to make preorder iterator so we can make the same with the help of the class which is

BinaryTreePreOrderIterator.

class BinarytreePreorderIterator:

    def __init__(self, tree):

        self.tree = tree

        self.stabel = []

        self.stabel.append((tree, 0))

    def __next__(self):

        while len(self.stabel) > 0:

            element = self.stabel.pop()

            if element[0].is_leafNode():

                return element[0].data

            if element[1] == 0:

                return element[0].data

            if element[1] == 1:

                self.stabel.append((element[0], 1))

                if element[0].right_child is not None:

                    self.stabel.append((element[0].right_child, 0))

            if element[1] == 2:

                self.stabel.append((element[0], 2))

                if element[0].left_child is not None:

                    self.stabel.append((element[0].left_child, 0))

        raise StopIteration

    def __iter__(self):

        return self

This is our solution for the given problem as in postOrder the order is Left child -> right Child -> root and in preOrder it is Root -> Left child -> Right Child.

Please comment and let me know if you have any doubts.

Thank you.

Have a good day.