Добавил 18 задание в деревьях

3 files changed, 171 insertions, 2 deletions

diff --git a/bin-trees/Makefile b/bin-trees/Makefile
index 3e3ce36..d4dffe5 100644
--- a/bin-trees/Makefile
+++ b/bin-trees/Makefile
@@ -11,8 +11,8 @@ test17: task17
 task18:
 	$(COMPILE) -o task.out task18.cpp
 test18: task18
-	@printf "\n" | ./task.out
-	@printf "Answer: \n"
+	@printf "10\n4 5 3 7 8 6 9 1 2 0\n2\n4\n" | ./task.out
+	@printf "Answer: 3\n"
 
 task19:
 	$(COMPILE) -o task.out task19.cpp
diff --git a/bin-trees/task18.cpp b/bin-trees/task18.cpp
new file mode 100644
index 0000000..e22c7ef
--- /dev/null
+++ b/bin-trees/task18.cpp
@@ -0,0 +1,104 @@
+#include <iostream>
+#include <string>
+
+#include "tree.h"
+
+using namespace std;
+
+// Функция вычисляет расстояние от узла b до узла a снизу вверх.
+// Если цикл достиг корня, то это означает, что либо узел b находится 
+// в другой ветке, либо он находится ниже узла a в этой же ветке.
+int length(tree *&a, tree *&b)
+{
+    tree *cur = b;
+    int count = 0;
+    while (cur != a)
+    {
+        if (cur->parent == NULL)
+        {
+            count = -1;
+            break;
+        }
+        else
+        {
+            cur = cur->parent;
+            count++;
+        }
+    }
+    return count;
+}
+
+int solve(tree *&a, tree *&b)
+{
+    int ab = length(a, b);
+    int ba = length(b, a);
+    return max(ab, ba);
+}
+
+void create(tree *&t, int n, tree *parent)
+{
+    if (n > 0)
+    {
+        int x;
+        cin >> x;
+        t = node(x);
+        t->parent = parent;
+        
+        int nl = n / 2;
+        int nr = n - nl - 1;
+
+        create(t->left, nl, t);
+        create(t->right, nr, t);
+    }
+}
+
+int main()
+{
+    int n;
+    cout << "Введите количество узлов: ";
+    cin >> n;
+    tree *t = new tree;
+    cout << "Введите содержимое узлов (желательно, уникальные):" << endl;
+    create(t, n, NULL);
+
+    print(t, log(n) / log(2));
+
+    tree *node_a = NULL;
+    {
+        cout << "Введите содержимое узла a: ";
+        int inf_a;
+        cin >> inf_a;
+
+        find(t, inf_a, node_a);
+
+        if (node_a == NULL)
+        {
+            cout << "Узел a не найден в дереве" << endl;
+            return 0;
+        }
+    }
+
+    tree *node_b = NULL;
+    {
+        cout << "Введите содержимое узла b: ";
+        int inf_b;
+        cin >> inf_b;
+
+        find(t, inf_b, node_b);
+
+        if (node_b == NULL)
+        {
+            cout << "Узел b не найден в дереве" << endl;
+            return 0;
+        }
+    }
+
+    int x = solve(node_a, node_b);
+    if (x < 0)
+        cout << "Заданные узлы находятся в разных ветках" << endl;
+    else if (x == 0)
+        cout << "Заданные узлы равны" << endl;
+    else
+        cout << "Длина пути от узла a до узла b равна " << x << endl;
+    return 0;
+}
diff --git a/bin-trees/tree.h b/bin-trees/tree.h
index 0fa61b1..95e380a 100644
--- a/bin-trees/tree.h
+++ b/bin-trees/tree.h
@@ -1,4 +1,9 @@
 #pragma once
+#include <iostream>
+#include <queue>
+#include <cmath>
+
+using namespace std;
 
 struct tree
 {
@@ -17,3 +22,63 @@ tree *node(int x)
     n->left = NULL;
     return n;
 }
+
+void find(tree *&tr, int x, tree *&res)
+{
+    if (tr)
+    {
+        if (tr->inf == x)
+        {
+            res = tr;
+        }
+        else
+        {
+            find(tr->left, x, res);
+            find(tr->right, x, res);
+        }
+    }
+}
+
+void print(tree *tr, int k)
+{
+    if (!tr) cout << "Empty tree" << endl;
+    else
+    {
+        queue<tree*> cur, next;
+        tree *r = tr;
+        cur.push(r);
+        int j = 0;
+        while (cur.size())
+        {
+            if (j == 0)
+            {
+                for (int i = 0; i < (int) pow(2.0, k) - 1; i++)
+                    cout << ' ';
+            }
+            tree *buf = cur.front();
+            cur.pop();
+            j++;
+            if (buf)
+            {
+                cout << buf->inf;
+                next.push(buf->left);
+                next.push(buf->right);
+                for (int i = 0; i < (int) pow(2.0, k + 1) - 1; i++)
+                    cout << ' ';
+            }
+            if (!buf)
+            {
+                for (int i = 0; i < (int) pow(2.0, k + 1) - 1; i++)
+                    cout << ' ';
+                cout << ' ';
+            }
+            if (cur.empty())
+            {
+                cout << endl;
+                swap(cur, next);
+                j = 0;
+                k--;
+            }
+        }
+    }
+}