# coding: utf-8
# Prosta implementacja drzewa binarnego w oparciu o dodatkowa klase Node
# Nie ma zaimplementowanego wstawwiania -  to jest zalezna od zastosowan
# Prosze samemu uzupelnic te implemetacje o inne operacje na drzewie
# Michal Baczynski (AiSD wyklad)

#importujemy plik z naszą klasa kolejki FIFO (np. opartej na liscie dowiazanej)
import FIFO_queue_ver_04_linked_list_poprawne

# dla ułatienia odwolania się do naszej kolejki tworzymy alias
Kolejka = FIFO_queue_ver_04_linked_list_poprawne.Queue

class Node:
    """Klasa Node - do pamietania pojedynczego wezla w drzewie"""
    def __init__(self, dane=None, left=None, right=None):
        # konstruktor
        # pole "dane" bedzie zawieralo nasze dane np. liczby, napisy lub inne rekordy badz klasy
        # left_node bedzie wskazywalo na lewy wezel
        # right_node bedzie wskazywalo na prawy wezel
        self.dane = dane
        self.left_node  = left
        self.right_node = right

class binaryTree:
    """Klasa drzewo binarne - istotna dana jest tylko korzen"""
    def __init__(self):
        self.korzen = None

    def _inorder(self,drzewo):
        #Wypisywanie drzewa w sposob inorder - procedura wewnetrzna
        if drzewo is not None:
            self._inorder(drzewo.left_node)
            print(drzewo.dane)
            self._inorder(drzewo.right_node)

    def inorder(self):
        #Wypisywanie w porzadku inorder dla korzenia - procedura zeewnetrzna
        self._inorder(self.korzen)


    def _postorder(self,drzewo):
        # Wypisywanie w porzadku postorder dla korzenia - procedura wewnetrzna
        if drzewo is not None:
            self._postorder(drzewo.left_node)
            self._postorder(drzewo.right_node)
            print(drzewo.dane)

    def postorder(self):
        #Wypisywanie w porzadku postorder dla korzenia - procedura zeewnetrzna
        self._postorder(self.korzen)


    def _breadthFirst(self,drzewo):
        # Wypisywanie metoda przeszukiwania wszerz - procedura wewnetrzna
        # korzystamy z kolejki FIFO (nieistotne jak zaimplementowanej!)
        q = Kolejka()
        # wkladamy do naszej kolejki FIFO korzen
        q.enqueue(drzewo)

        # odwiedzamy kazdy wezel w drzewie
        while not q.isEmpty():
            # wypisujemy i usuwamy to co jest na poczatku kolejki
            node = q.first()
            q.dequeue()
            print(node.dane)
            # i dodajemy dzieci tego wezla do kolejki o ile nie sa puste (czyli "Nonami")
            if node.left_node is not None:
                q.enqueue(node.left_node)
            if node.right_node is not None:
                q.enqueue(node.right_node)

    def breadthFirst(self):
        # Wypisywanie metoda przeszukiwania wszerz - procedura zewnetrzna
        self._breadthFirst(self.korzen)

    def _breadthFirst222(self,drzewo):
        # Wypisywanie metoda przeszukiwania wszerz - procedura wewnetrzna
        # korzystamy z kolejki FIFO (nieistotne jak zaimplementowanej!)
        q = Stack()
        # wkladamy do naszej kolejki FIFO korzen
        q.push(drzewo)

        # odwiedzamy kazdy wezel w drzewie
        while not q.isEmpty():
            # wypisujemy i usuwamy to co jest na poczatku kolejki
            node = q.top()
            q.pop()
            print(node.dane)
            # i dodajemy dzieci tego wezla do kolejki o ile nie sa puste (czyli "Nonami")
            if node.left_node is not None:
                q.push(node.left_node)
            if node.right_node is not None:
                q.push(node.right_node)

    def breadthFirst222(self):
        # Wypisywanie metoda przeszukiwania wszerz - procedura zewnetrzna
        self._breadthFirst222(self.korzen)

    def _height(self,drzewo):
        if drzewo is None:
            return -1
        return max(self._height(drzewo.left_node),self._height(drzewo.right_node))+1

    def height(self):
        return self._height(self.korzen)

    def _waga(self, drzewo):
        if drzewo is None:
            return 0
        suma = self._waga(drzewo.left_node) + self._waga(drzewo.right_node) + 1
        return suma

    def waga(self):
        return self._waga(self.korzen)

    def _level0(self, drzewo):
        """PROCEDURA WEWNETRZNA"""
        if drzewo is None:
            return 0
        elif (drzewo.left_node is None and drzewo.right_node is None):
            return 1
        else:
            return self._level0(drzewo.left_node) + self._level0(drzewo.right_node)

    def level0(self):
        """PROCEDURA ZEWNETRZNA"""
        return self._level0(self.korzen)

    def _level2(self, drzewo):
        """PROCEDURA WEWNETRZNA"""
        if (drzewo.left_node is None and drzewo.right_node is not None):
            return 1 + self._level2(drzewo.left_node) + self.level2(drzewo.right_node)
        else:
            return 0

    def level2(self):
        """PROCEDURA ZEWNETRZNA"""
        return self._level2(self.korzen)










# Przykladowe drzewo
r1 = binaryTree()
r1.korzen = Node("T")
r1.korzen.left_node =Node("X")
r1.korzen.left_node.left_node =Node("B")
r1.korzen.left_node.right_node=Node("G")
r1.korzen.left_node.right_node.left_node=Node("Z")
r1.korzen.right_node =Node("C")
r1.korzen.right_node.left_node =Node("J")
r1.korzen.right_node.right_node =Node("R")
r1.korzen.right_node.right_node.left_node =Node("K")
r1.korzen.right_node.right_node.left_node.left_node =Node("A")
r1.korzen.right_node.right_node.right_node=Node("M")

print("Porzadek Inorder")
r1.inorder()

print("Porzadek Postorder")
r1.postorder()

print("Przeszukiwanie wszerz")
r1.breadthFirst()

print("Przeszukiwanie wszerz222")
r1.breadthFirst222()