9.İkili_Ağaclar_Tapşırıqlar_və_Həllər.md

İkili ağaclar - tapşırıqlar və həllər

Bu fəsildə ikili ağaclarla bağlı tapşırıq və onların həllərinə nəzər yetirəcik. İlk öncə tapşırığın izahını daha sonra da kod parçasını göstərəcəyik.

Tapşırıq - 1

Şərt:

İkili ağacda maximum elementi tapın.

Həlli:

Bir üsulumuz bu ola bilər ki, ilk öncə sol altağacda maximum elementi tapaq, daha sonra sol altağacda maximum elementi tapaq və onu root elementlə müqayisə edək. Gördüyünüz kimi, bu işi rekursiv üsulla həll edə bilərik.

Qeyd: bütün kodlara baxmaq üçün fesil9_problems_solutions.py

Kod nümunəmiz:

    def find_max_recursive(self, node):
        if not node:
            return self.max_data

        if node.get_data() > self.max_data:
            self.max_data = node.get_data()
        
        self.find_max_recursive(node.left)
        self.find_max_recursive(node.right)

        return self.max_data

Bizim nümunə ağacımız üçün yuxarıdakı kod 14 qaytaracaq:

tree = BinaryTree()
    arr = [8, 3, 1, 6, 4, 7, 10, 14, 13]
    for i in arr:
        tree.create_tree(i)
    
    print(tree.find_max_recursive(tree.root))

Tapşırıq - 2

Şərt:

Rekursiyadan istifadə etmədən ağacdakı maximum elementi tapın.

Həlli:

Level Order Traversal metodundan(bax 8-ci fəsilə) istifadə etməklə, hər səviyyədə(level) elementləri Növbədən silərkən müqayisə apararaq, maximum elementi aşkarlaya bilərik.

Kod nümunəmiz:

    def find_max_level_order_traversal(self, node):
        if node is not None:
            q = Queue()
            q.put(node) # root node-u daxil edirik.

            while not q.empty():
                node = q.get() # Dequeue FIFO
                # növbədən çıxartdıqdan sonra müqayisə edirik.
                if node.get_data() > self.max_data:
                    self.max_data = node.get_data()

                if node.left is not None:
                    q.put(node.left)

                if node.right is not None:
                    q.put(node.right)
        
        return self.max_data

Tapşırıq - 3

Şərt:

Ikili ağacda verilmiş data-lı node-un olub-olmamasını yoxlamaq və yaxud ağacda element axtarmaq.

Həlli:

İlk ağıla gələn təbii üsul, root-dan başlamaq, öncə sol altağacda, daha sonra da sağ altağacda verilmiş elementi axtarmaqdır.

Rekursiv kod nümunəmiz:

    def find_data_recursive(self, node, data):
        if node is None:
            return 0

        if node.get_data() == data:
            return 1
        elif data < node.get_data(): 
            return self.find_data_recursive(node.left, data)    
        else:
            return self.find_data_recursive(node.right, data)

Kodumuzu sınayaq:

    tree = BinaryTree()
    arr = [8, 3, 1, 6, 4, 7, 10, 14, 13]
    for i in arr:
        tree.create_tree(i)
    print("find_max_recursive() -> ", end='')
    print(tree.find_max_recursive(tree.root))
    print("find_max_level_order_traversal() -> ", end='')
    print(tree.find_max_level_order_traversal(tree.root))
    print("find_data_recursive() search 88 -> ", end='')
    print(tree.find_data_recursive(tree.root, 88))
    print("find_data_recursive() search 14 -> ", end='')
    print(tree.find_data_recursive(tree.root, 14))

Nəticə:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1

Tapşırıq - 4

Şərt:

Yuxarıdakı axtarışı iterativ üsulla edin.

Həlli:

Bu zaman ağıla gələn üsul budur ki, Level Order Traversal-dan istifadə edərək, hər level-də axtarış edək, yoxlayaq ki, verilmiş(axtarılan) data hansı node-dadır.

Kod nümunəmiz:

    def find_data_level_order_traversal(self, node, data):
        if node is not None:
            q = Queue()
            q.put(node) # root node-u daxil edirik.

            while not q.empty():
                node = q.get() # Dequeue FIFO
                # növbədən çıxartdıqdan sonra yoxlayırıq.
                if node.get_data() == data:
                    return 1
                if node.left is not None:
                    q.put(node.left)

                if node.right is not None:
                    q.put(node.right)
        # 0 qayıdırsa, deməli data Ağacda yoxdur.            
        return 0

Nəticə:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1

Tapşırıq - 5

Şərt:

İkili ağaca element daxil etməyin üsulunu yazın.

Həll:

Bu məqsədlə yenidən, Level Order Traversal üsulundan istifadə edə bilərik. Belə ki, hər level(səviyyə)-də sağ və ya sol node-u olmayan node-u aşkarlayaraq, ora daxil edə bilərik.

Kod nümunəmiz:

    def insert_in_binary_using_tree_level_order(self, node, data):
        new_node = Node(data)
        if node is None:
            node = new_node # Ağac boşdursa, yeni node-u root node edirik.
            return node
        
        q = Queue()
        q.put(node) # Root node-u növbəyə daxil edirik.

        while not q.empty():
            node = q.get() # Dequeue FIFO
            # növbədən çıxartdıqdan sonra yoxlayırıq.
            if node.get_data() == data:
                return "Already in tree"
            if node.left is not None:
                q.put(node.left)
            else:
                # Əgər hal-hazırkı node-un datasından kiçikdirsə
                if new_node.get_data() < node.get_data():
                    node.left = new_node
                    return "Inserted as left node"

            if node.right is not None:
                q.put(node.right)
            else:
                # Əgər hal-hazırkı node-un datasından böyükdürsə
                if new_node.get_data() > node.get_data():
                    node.right = new_node
                    return "Inserted as right node"

Tapşırıq - 6

Şərt:

Ağacın ölçüsünü(elementlərinin sayını, node-ların sayını) tapın.

Həlli:

Rekursiv olaraq sağ və sol altağacları ziyarət etmək lazımdır. Son nəticənin də üstünə 1 gəlmək lazımdır(root node-u).

    def find_tree_size_recursive(self, node):
        if node is None:
            return 0
        
        return self.find_tree_size_recursive(node.left) + self.find_tree_size_recursive(node.right) + 1

Tapşırıq - 7

Şərt:

Ağacın ölçüsünü iterativ üsulla tapın(yuxarıdakı məsələni).

Həlli:

Yenə də Level Order Traversal edərək hər səviyyədəki node sayını hesablayırıq.

    def find_tree_size_iterative(self, node):
        if node is None:
            return 0
        
        q = Queue()
        q.put(node) # Root node-u növbəyə daxil edirik.
        count = 0

        while not q.empty():
            node = q.get()
            count = count + 1
            if node.left is not None:
                q.put(node.left)
            if node.right is not None:
                q.put(node.right)

        return count

Nəticə:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1
insert_in_binary_using_tree_level_order(tree.root, 21) -> Inserted as right node
find_tree_size_recursive() -> 10
find_tree_size_iterative() -> 10

Tapşırıq - 8

Şərt:

Level Order Traversal-ın elementləri əks(reverse) ardıcıllıqla çap edən növünü yazın.

Həlli:

Adi qaydada etdiyimiz Level Order Traversal zamanı, bir də köməkçi list-dən istifadə etsək, hər dəfə Queue-dən çıxartdığımız node-u həmin listə yığsaq son nəticədə bizdə Stack əmələ gələcək. Yəni faktiki olaraq, ən son gələni ən birinci çıxarda biləcəyik(LİFO). Bunu list-dən pop() edərək əldə edirik. Aşağıdakı kod parçasına diqqət yetirək:

def level_order_traversal_in_reverse(self, node):
        if node is None:
            return 0
        
        q = Queue()
        s = [] # LIFO üçün istifadə edəcəyimiz list
        q.put(node) # root node-u daxil edirik.

        while not q.empty():
            node = q.get() # Dequeue FIFO
            s.append(node.get_data()) # LIFO

            if node.left is not None:
                q.put(node.left)

            if node.right is not None:
                q.put(node.right)
        
        while(s):
            print(s.pop(), end=' ')

Nəticəmizdən də göründüyü kimi ağacın elementlərini tərsinə olaraq çıxara bildik:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1
insert_in_binary_using_tree_level_order(tree.root, 21) -> Inserted as right node
find_tree_size_recursive() -> 10
find_tree_size_iterative() -> 10
level_order_traversal_in_reverse() -> 13 7 4 21 14 6 1 10 3 8

Tapşırıq - 9

Şərt:

Ağacı silmək üçün alqoritm düşünün.

Həlli:

Ağacı silmək üçün, bütün node-ları ziyarət etməli və bir-bir silməliyik. Təbii ki, parent node-u silməzdən əvvəl onun child node-larını silməliyik. Belə olan halda hansı metod bizə uyğundur? İnOrder, PreOrder, PostOrder yoxsa Level Order Traversal? Keçmiş fəsildən xatırladığımız kimi, PostOrder qət etmə zamanı root node-lar ən sonda ziyarət olunur, dolayısı ilə biz bu üsuldan istifadə etməklə ilk öncə child node-ları daha sonra da parent node-ları silə bilərik.

Aşağıdakı kod nümunəsi bu işi görəcək:

def delete_binary_tree(self, node):
        if node is None:
            return
        
        self.delete_binary_tree(node.left)
        self.delete_binary_tree(node.right)
        node.data = None
        node.left = None
        node.right = None
        self.root = None

Nəticə:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1
insert_in_binary_using_tree_level_order(tree.root, 21) -> Inserted as right node
find_tree_size_recursive() -> 10
find_tree_size_iterative() -> 10
level_order_traversal_in_reverse() -> 13 7 4 21 14 6 1 10 3 8
delete_binary_tree() ->
find_tree_size_recursive() -> 0
find_tree_size_iterative() -> 0

Tapşırıq - 10

Şərt:

Ağacın hündürlüyünü(height or depth) tapan alqoritmi qurun.

Həlli:

Bu məqsədlə, rekursiv olaraq sol altağacın, daha sonra sağ altağacın hündürlüyünü hesablaya bilərik. Daha sonra bu hündürlüklərdən ən böyüyünü(maksimum) götürüb üzərinə 1 gəlmək lazımdır. Aşağıdakı kod parçası rekursiv olaraq, bu işi görür:

    def max_depth_recursive(self, node):
        if node is None:
            return 0
        return max(self.max_depth_recursive(node.left), self.max_depth_recursive(node.right)) + 1

Tapşırıq - 11

Şərt:

Yuxarıdakı tapşırığı iterativ üsulla həll edin.

Həlli:

Level Order Traversal üsulundan istifadə etməklə, hər səviyyədə depth dəyişənini artırmaqla ən sonda ağacın ümumi hündürlüyünü tapmış oluruq:

    def max_depth_iterative(self, node):
        if node is None:
            return 0
        q_list = []
        q_list.append([node, 1])
        while q_list:
            node, depth = q_list.pop() # Buna Python-da unpacking deyilir.
            if node.left is not None: 
                q_list.append([node.left, depth + 1]) # Əgər sol node varsa, onu listə əlavə et və depth-i artır.
            if node.right is not None:
                q_list.append([node.right, depth + 1]) # Əgər sağ node varsa, onu listə əlavə et və depth-i artır.
        
        return depth

Kod nəticəmiz:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1
insert_in_binary_using_tree_level_order(tree.root, 21) -> Inserted as right node
find_tree_size_recursive() -> 10
find_tree_size_iterative() -> 10
level_order_traversal_in_reverse() -> 13 7 4 21 14 6 1 10 3 8
max_depth_recursive() -> 4
max_depth_iterative() -> 4

Tapşırıq - 12

Şərt:

Ağacın ən dərin node-unu tapmaq üçün alqoritm qurun.

Həlli:

Yenidən Level Order Traversal etməklə ən sonda Növbədən(Queue) çıxarılan node-un data-sını geri qaytara bilərik.

    def deepest_node(self, node):
        if node is None:
            return 0

        q = Queue()
        q.put(node)

        while not q.empty():
            node = q.get()
            if node.left is not None:
                q.put(node.left)
            if node.right is not None:
                q.put(node.right)
        
        return node.get_data()

Tapşırıq - 13

Şərt:

Ağacda leaf node-ların sayını tapın.

Həlli:

Xatırlayaq ki, lead node elə bir node-a deyilir ki, onun xələfi(ardıcılı, övladı) olmasın. Yəni, onun sağ və sol node-ları None(NULL) olsun. Level Order Traversal üsulundan istifadə etməklə, Növbədən çıxarılan hər node-un sağ və solunun None olub olmadığını yoxlaya bilərik. Əgər bu şərt doğru olsa deməli elə bu node leaf node-dur.

def number_of_leafs_iterative(self, node):
        
        if node is None:
            return 0

        q = Queue()
        q.put(node)
        count = 0 # sayğac

        while not q.empty():
            node = q.get()
            if (node.left is None) and (node.right is None):
                count = count + 1
            else:
                if node.left is not None:
                    q.put(node.left)
                if node.right is not None:
                    q.put(node.right)
        
        return count

Nəticə:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1
insert_in_binary_using_tree_level_order(tree.root, 21) -> Inserted as right node
find_tree_size_recursive() -> 10
find_tree_size_iterative() -> 10
level_order_traversal_in_reverse() -> 13 7 4 21 14 6 1 10 3 8
max_depth_recursive() -> 4
max_depth_iterative() -> 4
deepest_node() -> 13
number_of_leafs_iterative() -> 4

Tapşırıq - 14

Şərt:

Ağacda full node-ların sayını tapın. Qeyd edək ki, full node həm sol, həm də sağ node-ları var olan node-a deyilir. Yəni, sağ və sol node-ları None(NULL) olmayan node-ların sayını tapmaq lazımdır.

Həlli:

Yuxarıdakı tapşırıqda leaf node tapdığımız kodda sayğacın şərtini dəyişməklə nəticə əldə edə bilərik.

    def number_of_full_nodes_iterative(self, node):
        
        if node is None:
            return 0

        q = Queue()
        q.put(node)
        count = 0 # sayğac

        while not q.empty():
            node = q.get()
            if (node.left is not None) and (node.right is not None):
                count = count + 1
            else:
                if node.left is not None:
                    q.put(node.left)
                if node.right is not None:
                    q.put(node.right)
        
        return count

Tapşırıq - 15

Şərt:

Ağacda olan yarım node-ların(half nodes) sayını tapın. Qeyd edək ki, yarım node elə bir node-a deyilir ki, onun ya sağ ya da sol node-u olsun. Yəni sağ ya sol node-lardan biri None(NULL) olsun.

Həlli:

Yenidən yuxarıdakı kodumuzda sayğac şərtini dəyişirik:

    def number_of_half_nodes_iterative(self, node):
        if node is None:
            return 0

        q = Queue()
        q.put(node)
        count = 0 # sayğac

        while not q.empty():
            node = q.get()
            if (node.left is None and node.right is not None) or \
               (node.right is None and node.left is not None):
                count = count + 1
            else:
                if node.left is not None:
                    q.put(node.left)
                if node.right is not None:
                    q.put(node.right)
        
        return count

Nəticələrimiz:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1
insert_in_binary_using_tree_level_order(tree.root, 21) -> Inserted as right node
find_tree_size_recursive() -> 10
find_tree_size_iterative() -> 10
level_order_traversal_in_reverse() -> 13 7 4 21 14 6 1 10 3 8
max_depth_recursive() -> 4
max_depth_iterative() -> 4
deepest_node() -> 13
number_of_leafs_iterative() -> 4
number_of_full_nodes_iterative() -> 1
number_of_half_nodes_iterative() -> 2

Tapşırıq - 16

Şərt:

Verilmiş iki Ağacın bir-birinə struktur olaraq bərabərliyini yoxlayın.

Həlli:

• Əgər hər iki ağac boşdursa(yəni None-dursa), o zaman True qaytarın.
• Əgər hər iki ağac doludursa, o zaman sağ və sol altağacların strukturlarını rekursiv olaraq yoxlamaq lazımdır.

Kodumuz:

def check_tree_structures_to_be_same(self, node1, node2):
        # Əgər ağacların nə sol nə də sağ altağacları qalıbsa və data-lar da bərabərdirsə o zaman True qaytarırır.
        if (not node1.left) and \
           (not node1.right) and \
           (not node2.left) and \
           (not node2.right) and node1.data == node2.data:
           return True
        # Aşağıda isə görürük ki, iki ağac bir-biri ilə fərqlənir   
        if (node1.data != node2.data) or (node1.left and not node2.left) or \
           (not node1.left and node2.left) or (node1.right and not node2.right) or \
           (not node1.right and node2.right):
           return False

        left = self.check_tree_structures_to_be_same(node1.left, node2.left) if node1.left and node2.left else True
        right = self.check_tree_structures_to_be_same(node1.right, node2.right) if node1.right and node2.right else True
        
        return left and right

Test etmək üçün eyni strukturda ikinci ağacı yaradırıq daha sonra əvvəlki ağacda olduğu kimi, 21 daxil edirik:

    tree2 = BinaryTreeExercises()
    arr2 = [8, 3, 1, 6, 4, 7, 10, 14, 13]
    for i in arr2:
        tree2.create_tree(i)
    print("insert_in_binary_using_tree_level_order(tree2.root, 21) -> ", end='')
    print(tree.insert_in_binary_using_tree_level_order(tree2.root, 21))
    print("check_tree_structures_to_be_same(tree.root, tree2.root) -> ", end='')
    print(tree.check_tree_structures_to_be_same(tree.root, tree2.root))

Bu zaman True qayıdacaq. Lakin əlavə olaraq ikinci ağaca 88 daxil etsək bu zaman artıq struktur fərqlənəcək və False qayıdacaq:

    print("insert_in_binary_using_tree_level_order(tree2.root, 88) -> ", end='')
    print(tree.insert_in_binary_using_tree_level_order(tree2.root, 88))
    print("check_tree_structures_to_be_same(tree.root, tree2.root) -> ", end='')
    print(tree.check_tree_structures_to_be_same(tree.root, tree2.root))

Nəticə:

$ python3 fesil9_problems_solutions.py
find_max_recursive() -> 14
find_max_level_order_traversal() -> 14
find_data_recursive() search 88 -> 0
find_data_recursive() search 14 -> 1
find_data_level_order_traversal() search 88 -> 0
find_data_level_order_traversal() search 14 -> 1
insert_in_binary_using_tree_level_order(tree.root, 21) -> Inserted as right node
find_tree_size_recursive() -> 10
find_tree_size_iterative() -> 10
level_order_traversal_in_reverse() -> 13 7 4 21 14 6 1 10 3 8
max_depth_recursive() -> 4
max_depth_iterative() -> 4
deepest_node() -> 13
number_of_leafs_iterative() -> 4
number_of_full_nodes_iterative() -> 1
number_of_half_nodes_iterative() -> 2
insert_in_binary_using_tree_level_order(tree2.root, 21) -> Inserted as right node
check_tree_structures_to_be_same(tree.root, tree2.root) -> True
insert_in_binary_using_tree_level_order(tree2.root, 21) -> Inserted as right node
check_tree_structures_to_be_same(tree.root, tree2.root) -> False

Tapşırıq - 17

Şərt:

Ağacın diametrini tapan kodu yazın. Qeyd edək ki,ağacın diametri iki node arasında ən uzun məsafəyə bərabərdir.

Həlli:

İlk öncə sol daha sonra sağ altağacın hündürlüyünü(maximum dərinliyini) tapmaq lazımdır. Bunu biz artıq 10-cu tapşırıqda etmişik. Daha sonra sol altağacın diametrini daha sonra da sağ altağacın diametrini tapmaq lazımdır. Son nəticədə isə bunların arasından maksimumu qaytarmaq lazımdır. Aşağıdakı kod bunu edir:

Mənbə: diameter-of-a-binary-tree

    def diameter_of_tree(self, node):
        if node is None:
            return 0
    
        # sol və sağ altağacların hündürlüyünü tapırıq.
        lheight = self.max_depth_recursive(node.left)
        rheight = self.max_depth_recursive(node.right)
    
        # sol və sağ altağacların diametrlərini tapırıq.
        ldiameter = self.diameter_of_tree(node.left)
        rdiameter = self.diameter_of_tree(node.right)
    
        # Ağac üçün max dəyəri qaytarmalıyı.
        # sol və sağ altağacın diametrləri arasından maksimumu tapırıq.
        # sol və sağ altağacın hündürlüklərini cəmləyib üzərinə 1 gəlirik.
        # Yuxarıdakı ikisində maksimumu tapırıq.
        return max(lheight + rheight + 1, max(ldiameter, rdiameter))