SHARE
TWEET

Untitled

a guest Jan 14th, 2020 62 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top