# coding: cp852
#PY_3
#VER_FORMAT: "v(M\d3)_(S\d3)_(C\d8)\.(R\d3)" !_DO+R

####################################\#
#
# TREE - Klasa obsˆugi drzewa binarnego.
# AUTO_ver: v000_000_00000000.001
# basE\:[25J18]        date[25J18]
# hist:[???]
#                 KEyS_T
#
####################################//#

#.  
#-v000_000_00000000.001    [25J18]: START

import os,sys

from lib_v001_000 import *
from glob     import *

VERSION = "v000_000_00000000.001"  # AUTO_ver
DATE = "25J18"


#=======================================================================================[ T_Btree ]=======
class T_Btree:
  '''Klasa obsˆugi drewa binarnego.''' 
  _VAL=None									# Pole danych (warto˜ci).
  _count=0									# Krotno˜† warto˜ci.
  _L=None									# Odsyˆacz lewy.
  _R=None                                                                       # Odsyˆacz prawy.

#---============================[ __init__ ]==========================================[]
  def __init__(self,V):
    '''Inicjacja z warto˜ci¥ V.'''
    self._VAL=V									# Zapami©tuje waro˜†.
    self._count=1								# Pierwszy raz.
    self._R=None								# Nie ma prawej gaˆ©zi.
    self._L=None                                                                # Nie ma lewej gaˆ©zi.

#------------------------------------ MODI -------------------------------------------
#---============================[ add ]==========================================[]
  def add(self,V):
    '''Do drzewa dodaje elemeent w ten spos¢b, ze wart˜ci mniejsze od warto˜ci w we«le dodaje w lewej gaˆ©zi , wi©ksze w prawej, 
    a r¢wne zwi©kszaj¥ krotno˜†.'''
    if V==self._VAL:								# Taka sama warto˜c jak zapisana.
      self._count+=1								# Zwi©ksza krotno˜†.
    elif V<self._VAL:								# Warto˜† jest mniejsza od warto˜ci w w©«le.
      if self._L:								# istnieje lewa gaˆ¥«.
        self._L.add(V)								# Dodaje V do niej.
      else:									# Nie istnieje.
        self._L=T_Btree(V)							# Tworzy j¥ przez stworzenie w©zˆa  z V.
    else:									# V>VAL.
      if self._R:								# istnieje prawa gaˆ¥«.
        self._R.add(V)								# Dodaje V do niej.
      else:									# Nie istnieje.
        self._R=T_Btree(V)							# Tworzy j¥ przez stworzenie w©zˆa  z V.

#------------------------------------ DIAG -------------------------------------------
#---============================[ LEN ]==========================================[]
  def LEN(self,L=1):
    '''Zwraca gˆeboko˜† drzewa - odlegˆo˜† od korzenia do koäca najdˆu¾szej gaˆ©zi. L sˆu¾y do przekazywania aktualnej gˆ©boko˜ci.'''
    RES=L									#  W©zeˆ ma tak¥ gˆ©boko˜†, z jaka go wywoˆano.
    if self._L:									# Ma lewe poddrzewo.
      RES=max(RES,self._L.LEN(L+1))                                                 # Ustala czy jego gˆ©boko˜† jest wieksza od aktualnej.
    if self._R:                                                                 # Ma prawe poddrzewo.
      RES=max(RES,self._R.LEN(L+1))                                                 # Ustala czy jego gˆ©boko˜† jest wieksza od aktualnej.
    return RES									# Zwraca gˆ©boko˜†.

#------------------------------------ SHOW-------------------------------------------
#---============================[ SHOW ]==========================================[]
  def SHOW(self,DIR='L.R'):
    '''Wypisuje w©zˆy drzewa w kolejno˜ci DIR L-left, .-this, R- right.'''
    for d in DIR:
      if d=='L'and self._L:
        self._L.SHOW(DIR)
      elif d=='R'and self._R:
        self._R.SHOW(DIR)
      elif d=='.':
        for i in range(self._count):
          print(f'{self._VAL},',end='')



#---============================[ __name__ ]==========================================[]
if __name__=="__main__":
  S=[17, 23, 43, 1, 44, 2, 3 , 5,19,50,3,3,8]
  S=[1,2, 3 , 5,3,3,8,17,19, 23, 43,  44, 50]
  T=T_Btree(S.pop(0))
  for s in S:
    T.add(s)
  print(T.LEN())
  T.SHOW()
  print()
  print('-'*100)
  T.SHOW('R.L')
  print()
  print('-'*100)