Quyidagi vazifalarni bajaruvchi dastur tuzing

9

Binar daraxt

Inglizcha-o‘zbekcha lug‘at binar daraxt ko‘rinishida berilgan. har bir tugun inglzcha va unga mos o‘zbekcha so‘zni hamda ushbu so‘zga murojaatlar sonini saqlab turadi. Dastlab daraxtda so‘zlar ingliz alifbosi tartibida shakllantiriladi. Ushbu lug‘atni qayta ishlash jarayonida har bir so‘zga murojaatlar soni qayd qilib boriladi. Quyidagi vazifalarni bajaruvchi dastur tuzing: 1. Lug‘atga yangi so‘z va unga murojaatlar sonini hisoblash maydonini kiritish; 2. Mavjud so‘zlar daraxtini va kiritilgan yangi so‘zlar daraxtini chiqarish; 3. Yangi so‘z kiritilganda uning lug‘atda mavjud ekanligini aniqlash. Agar mavjud bo‘lmasa lug‘atga qo‘shib qo‘yish.

class Node:

def __init__(self, eng, uzb, num_refs=0, new_word=False):
self.eng = eng
self.uzb = uzb
self.num_refs = num_refs
self.new_word = new_word
self.left = None
self.right = None

class BinarySearchTree:

def __init__(self):
self.root = None

def insert(self, eng, uzb, new_word=False):

new_node = Node(eng, uzb, new_word=new_word)
if self.root is None:
self.root = new_node
else:
current = self.root
while True:
if eng < current.eng:
if current.left is None:
current.left = new_node
break
else:
current = current.left
elif eng > current.eng:
if current.right is None:
current.right = new_node
break
else:
current = current.right
else:
current.num_refs += 1
break

def search(self, eng):

current = self.root
while current is not None:
if eng < current.eng:
current = current.left
elif eng > current.eng:
current = current.right
else:
return current
return None

def extract_existing_words(self):

existing_words_tree = BinarySearchTree()
self._extract_existing_words_helper(self.root, existing_words_tree)
return existing_words_tree

def _extract_existing_words_helper(self, node, tree):

if node is not None:
if not node.new_word:
tree.insert(node.eng, node.uzb, node.num_refs)
self._extract_existing_words_helper(node.left, tree)
self._extract_existing_words_helper(node.right, tree)

def extract_new_words(self):

new_words_tree = BinarySearchTree()
self._extract_new_words_helper(self.root, new_words_tree)
return new_words_tree

def _extract_new_words_helper(self, node, tree):

if node is not None:
if node.new_word:
tree.insert(node.eng, node.uzb, node.num_refs)
self._extract_new_words_helper(node.left, tree)
self._extract_new_words_helper(node.right, tree)