Guest User

Untitled

a guest
Jan 14th, 2020
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # coding: utf-8
  2. # Prosta implementacja drzewa binarnego w oparciu o dodatkowa klase Node
  3. # Nie ma zaimplementowanego wstawwiania -  to jest zalezna od zastosowan
  4. # Prosze samemu uzupelnic te implemetacje o inne operacje na drzewie
  5. # Michal Baczynski (AiSD wyklad)
  6.  
  7. #importujemy plik z naszą klasa kolejki FIFO (np. opartej na liscie dowiazanej)
  8. import FIFO_queue_ver_04_linked_list_poprawne
  9.  
  10. # dla ułatienia odwolania się do naszej kolejki tworzymy alias
  11. Kolejka = FIFO_queue_ver_04_linked_list_poprawne.Queue
  12.  
  13. class Node:
  14.     """Klasa Node - do pamietania pojedynczego wezla w drzewie"""
  15.     def __init__(self, dane=None, left=None, right=None):
  16.         # konstruktor
  17.         # pole "dane" bedzie zawieralo nasze dane np. liczby, napisy lub inne rekordy badz klasy
  18.         # left_node bedzie wskazywalo na lewy wezel
  19.         # right_node bedzie wskazywalo na prawy wezel
  20.         self.dane = dane
  21.         self.left_node  = left
  22.         self.right_node = right
  23.  
  24. class binaryTree:
  25.     """Klasa drzewo binarne - istotna dana jest tylko korzen"""
  26.     def __init__(self):
  27.         self.korzen = None
  28.  
  29.     def _inorder(self,drzewo):
  30.         #Wypisywanie drzewa w sposob inorder - procedura wewnetrzna
  31.         if drzewo is not None:
  32.             self._inorder(drzewo.left_node)
  33.             print(drzewo.dane)
  34.             self._inorder(drzewo.right_node)
  35.  
  36.     def inorder(self):
  37.         #Wypisywanie w porzadku inorder dla korzenia - procedura zeewnetrzna
  38.         self._inorder(self.korzen)
  39.  
  40.  
  41.     def _postorder(self,drzewo):
  42.         # Wypisywanie w porzadku postorder dla korzenia - procedura wewnetrzna
  43.         if drzewo is not None:
  44.             self._postorder(drzewo.left_node)
  45.             self._postorder(drzewo.right_node)
  46.             print(drzewo.dane)
  47.  
  48.     def postorder(self):
  49.         #Wypisywanie w porzadku postorder dla korzenia - procedura zeewnetrzna
  50.         self._postorder(self.korzen)
  51.  
  52.  
  53.     def _breadthFirst(self,drzewo):
  54.         # Wypisywanie metoda przeszukiwania wszerz - procedura wewnetrzna
  55.         # korzystamy z kolejki FIFO (nieistotne jak zaimplementowanej!)
  56.         q = Kolejka()
  57.         # wkladamy do naszej kolejki FIFO korzen
  58.         q.enqueue(drzewo)
  59.  
  60.         # odwiedzamy kazdy wezel w drzewie
  61.         while not q.isEmpty():
  62.             # wypisujemy i usuwamy to co jest na poczatku kolejki
  63.             node = q.first()
  64.             q.dequeue()
  65.             print(node.dane)
  66.             # i dodajemy dzieci tego wezla do kolejki o ile nie sa puste (czyli "Nonami")
  67.             if node.left_node is not None:
  68.                 q.enqueue(node.left_node)
  69.             if node.right_node is not None:
  70.                 q.enqueue(node.right_node)
  71.  
  72.     def breadthFirst(self):
  73.         # Wypisywanie metoda przeszukiwania wszerz - procedura zewnetrzna
  74.         self._breadthFirst(self.korzen)
  75.        
  76.     def _breadthFirst222(self,drzewo):
  77.         # Wypisywanie metoda przeszukiwania wszerz - procedura wewnetrzna
  78.         # korzystamy z kolejki FIFO (nieistotne jak zaimplementowanej!)
  79.         q = Stack()
  80.         # wkladamy do naszej kolejki FIFO korzen
  81.         q.push(drzewo)
  82.  
  83.         # odwiedzamy kazdy wezel w drzewie
  84.         while not q.isEmpty():
  85.             # wypisujemy i usuwamy to co jest na poczatku kolejki
  86.             node = q.top()
  87.             q.pop()
  88.             print(node.dane)
  89.             # i dodajemy dzieci tego wezla do kolejki o ile nie sa puste (czyli "Nonami")
  90.             if node.left_node is not None:
  91.                 q.push(node.left_node)
  92.             if node.right_node is not None:
  93.                 q.push(node.right_node)
  94.  
  95.     def breadthFirst222(self):
  96.         # Wypisywanie metoda przeszukiwania wszerz - procedura zewnetrzna
  97.         self._breadthFirst222(self.korzen)
  98.  
  99.     def _height(self,drzewo):
  100.         if drzewo is None:
  101.             return -1
  102.         return max(self._height(drzewo.left_node),self._height(drzewo.right_node))+1
  103.  
  104.     def height(self):
  105.         return self._height(self.korzen)
  106.    
  107.     def _waga(self, drzewo):
  108.         if drzewo is None:
  109.             return 0
  110.         suma = self._waga(drzewo.left_node) + self._waga(drzewo.right_node) + 1
  111.         return suma
  112.    
  113.     def waga(self):
  114.         return self._waga(self.korzen)
  115.    
  116.     def _level0(self, drzewo):
  117.         """PROCEDURA WEWNETRZNA"""        
  118.         if drzewo is None:
  119.             return 0
  120.         elif (drzewo.left_node is None and drzewo.right_node is None):
  121.             return 1
  122.         else:
  123.             return self._level0(drzewo.left_node) + self._level0(drzewo.right_node)
  124.        
  125.     def level0(self):
  126.         """PROCEDURA ZEWNETRZNA"""
  127.         return self._level0(self.korzen)
  128.    
  129.     def _level2(self, drzewo):
  130.         """PROCEDURA WEWNETRZNA"""        
  131.         if (drzewo.left_node is None and drzewo.right_node is not None):
  132.             return 1 + self._level2(drzewo.left_node) + self.level2(drzewo.right_node)
  133.         else:
  134.             return 0
  135.        
  136.     def level2(self):
  137.         """PROCEDURA ZEWNETRZNA"""
  138.         return self._level2(self.korzen)
  139.        
  140.        
  141.        
  142.    
  143.    
  144.        
  145.            
  146.    
  147.                    
  148.  
  149. # Przykladowe drzewo
  150. r1 = binaryTree()
  151. r1.korzen = Node("T")
  152. r1.korzen.left_node =Node("X")
  153. r1.korzen.left_node.left_node =Node("B")
  154. r1.korzen.left_node.right_node=Node("G")
  155. r1.korzen.left_node.right_node.left_node=Node("Z")
  156. r1.korzen.right_node =Node("C")
  157. r1.korzen.right_node.left_node =Node("J")
  158. r1.korzen.right_node.right_node =Node("R")
  159. r1.korzen.right_node.right_node.left_node =Node("K")
  160. r1.korzen.right_node.right_node.left_node.left_node =Node("A")
  161. r1.korzen.right_node.right_node.right_node=Node("M")
  162.  
  163. print("Porzadek Inorder")
  164. r1.inorder()
  165.  
  166. print("Porzadek Postorder")
  167. r1.postorder()
  168.  
  169. print("Przeszukiwanie wszerz")
  170. r1.breadthFirst()
  171.  
  172. print("Przeszukiwanie wszerz222")
  173. r1.breadthFirst222()
RAW Paste Data