__author__ ='Karolina'

#inicjowanie klasy wezel-Node
class Node(object):
    def __init__(self,klucz):
        self.lewySyn = None #do lewego dziecka
        self.prawySyn = None #do prawego dziecka
        self.klucz = klucz #klucz zapisany w węźle

    #wstawianie
    def insert(self, klucz):
        if klucz < self.klucz:
            if self.lewySyn is None:
                self.lewySyn = Node(klucz)
            else:
                self.lewySyn.insert(klucz)
        else:
            if self.prawySyn is None:
                self.prawySyn = Node(klucz)
            else:
                self.prawySyn.insert(klucz)


class BinaryTree(object):
    def __init__(self):
        self.root = None # root referencja do korzenia

    def insert(self, klucz):
        if self.root is None:
            self.root = Node(klucz)
        else:
            self.root.insert(klucz)

    #przechodzenie po drzewie
    #preOrder - wzdluzne-  najpierw odwiedzamy korzeń poddrzewa, a następnie przechodzimy kolejno lewe i prawe poddrzewo
    #inOrder - poprzeczne- najpierw przechodzimy lewe poddrzewo danego węzła, następnie odwiedzamy węzeł i na koniec przechodzimy prawe poddrzewo
    #postOrder - wsteczne- najpierw przechodzimy lewe poddrzewo, następnie prawe, a dopiero na końcu przetwarzamy węzeł
    def preOrderTreeWalk(self, root):
        if root is not None:
            print(root.klucz)
            if root.lewySyn is not None:
                self.preOrderTreeWalk(root.lewySyn)
            if root.prawySyn is not None:
                self.preOrderTreeWalk(root.prawySyn)

    def inOrderTreeWalk(self, root):
        if root is not None:
            if root.lewySyn is not None:
                self.inOrderTreeWalk(root.lewySyn)
            print(root.klucz)
            if root.prawySyn is not None:
                self.inOrderTreeWalk(root.prawySyn)

    def postOrderTreeWalk(self, root):
        if root.lewySyn is not None:
            self.preOrderTreeWalk(root.lewySyn)
        if root.prawySyn is not None:
            self.preOrderTreeWalk(root.prawySyn)
        print(root.klucz)



#dla każdego węzła wszystkie wartości znajdujące się w poddrzewie
#którego korzeniem jest jego prawy syn mają wartości większe niż on,
#a w poddrzewie którego korzeniem jest lewy syn mniejsze
    # przeszukiwanie
    def find(self, key):
        if Node is None:
            return None #nie znaleziono klucza
        if key < self.root.klucz:
            self.root = self.root.lewySyn
            return self.find(key)
        elif key > self.root.klucz:
            self.root = self.root.prawySyn
            return self.find(key)
        else: #gdy szukany klucz jest rowny kluczowi danego wezla
            return self.klucz


    def children_count(self):
        cnt = 0
        if self.lewySyn:
            cnt +=1
        if self.prawySyn:
            cnt+=1
        return cnt

    def remove(self, klucz, rodzic):
        if Node is not None:
            children_count = Node.children_count()
        # jezli wezel nie ma dzieci, usuwamy go
        if children_count == 0:
            if rodzic:
                if rodzic.lewySyn is Node:
                    rodzic.lewySyn = None
                else:
                    rodzic.prawySyn = None
                del Node  #kasujemy node
            else:
                self.klucz = None
#usuwany węzeł ma jednego syna: dany węzeł usuwamy,
#a jego syna podstawiamy w miejsce usuniętego węzła
        if children_count == 1:
            if Node.lewySyn:
                n = Node.lewySyn
            else:
                n = Node.prawySyn
            if rodzic:
                if rodzic.lewySyn is Node:
                    rodzic.lewySyn = n
                else:
                    rodzic.prawySyn = n
                del Node
            else:
                self.lewySyn = n.lewySyn
                self.prawySyn = n.prawySyn
                self.klucz = n.klucz
        else:
            #jesli wezel ma dwoch synow znajdz nastepce
            #usuwany węzeł ma dwóch synów:
            # po jego usunięciu wstawiamy w jego miejsce węzeł,
            # który jest jego następnikiem lub poprzednikiem
            #Następnik i poprzednik to odpowiednio najbardziej
            # lewy węzeł w prawym podrzewie, lub najbardziej prawy węzeł węzeł w prawym poddrzewie.
            rodzic = Node
            nastepca = Node.prawySyn
            while nastepca.lewySyn:
                rodzic = nastepca
                nastepca = nastepca.lewySyn
            #zamiana wezla nastepca
            Node.klucz = nastepca.klucz
            # nowe miejsca dla dzieci
            if rodzic.lewySyn == nastepca:
                rodzic.lewySyn = nastepca.prawySyn
            else:
                rodzic.prawySyn = nastepca.prawySyn


    # sprawdzenie czy wartosc jest w drzewie BST
    def sprawdz(self, klucz, rodzic = None):
        if klucz > self.lewySyn is None:
            if self.lewySyn is None:
                return None
            return self.lewySyn.sprawdz(klucz, self)

        elif klucz < self.klucz:
            if self.prawySyn is None:
                return None
            return self.prawySyn.sprawdz(klucz, self)

        else:
            return self, rodzic



tree = BinaryTree()
tree.insert(4)
tree.insert(3)
tree.insert(2)
tree.insert(1)
tree.insert(9)
tree.insert(12)
tree.insert(13)
tree.insert(5)
tree.insert(12)
tree.insert(54)
tree.insert(3)
print("\n")
tree.inOrderTreeWalk(tree.root)
print("\n")
tree.preOrderTreeWalk(tree.root)
print("\n")
tree.postOrderTreeWalk(tree.root)
print("\n")