Рубрики

Найти расстояние между двумя узлами двоичного дерева

Найти расстояние между двумя ключами в двоичном дереве, родительские указатели не указываются. Расстояние между двумя узлами — это минимальное количество ребер, которые необходимо пройти, чтобы достичь одного узла от другого.

Расстояние между двумя узлами может быть получено с точки зрения наименьшего общего предка . Ниже приводится формула.

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) 
'n1' and 'n2' are the two given keys
'root' is root of given Binary Tree.
'lca' is lowest common ancestor of n1 and n2
Dist(n1, n2) is the distance between n1 and n2.

Ниже приводится реализация вышеуказанного подхода. Реализация принята из последнего кода, предоставленного в Lowest Common Ancestor Post .

C ++

/ * C ++ программа для поиска расстояния между n1 и n2, используя

   один обход * /

#include <iostream>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    struct Node *left, *right;

    int key;

};

  
// Сервисная функция для создания нового дерева Node

Node* newNode(int key)

{

    Node *temp = new Node;

    temp->key = key;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Возвращает уровень ключа k, если он присутствует в дереве,
// в противном случае возвращает -1

int findLevel(Node *root, int k, int level)

{

    // Базовый вариант

    if (root == NULL)

        return -1;

  

    // если ключ присутствует в корне или в левом поддереве

    // или правое поддерево, возвращаем true;

    if (root->key == k)

        return level;

  

    int l = findLevel(root->left, k, level+1);

    return (l != -1)? l : findLevel(root->right, k, level+1);

}

  
// Эта функция возвращает указатель на LCA двух данных
// значения n1 и n2. Он также устанавливает d1, d2 и dist, если
// один ключ не является предком другого
// d1 -> сохранить расстояние n1 от корня
// d2 -> сохранить расстояние n2 от корня
// lvl -> Уровень (или расстояние от корня) текущего узла
// dist -> Для сохранения расстояния между n1 и n2

Node *findDistUtil(Node* root, int n1, int n2, int &d1, 

                            int &d2, int &dist, int lvl)

{

    // Базовый вариант

    if (root == NULL) return NULL;

  

    // Если n1 или n2 совпадает с ключом root, сообщить

    // присутствие, возвращая root (обратите внимание, что если ключ

    // предок другого, тогда ключ предка становится LCA

    if (root->key == n1)

    {

         d1 = lvl;

         return root;

    }

    if (root->key == n2)

    {

         d2 = lvl;

         return root;

    }

  

    // ищем n1 и n2 в левом и правом поддеревьях

    Node *left_lca  = findDistUtil(root->left, n1, n2, 

                                   d1, d2, dist, lvl+1);

    Node *right_lca = findDistUtil(root->right, n1, n2,

                                   d1, d2, dist, lvl+1);

  

    // Если оба вышеуказанных вызова возвращают значение, отличное от NULL, то

    // один ключ присутствует в поддереве, а другой -

    // присутствует в другом. Таким образом, этот узел является LCA

    if (left_lca && right_lca)

    {

        dist = d1 + d2 - 2*lvl;

        return root;

    }

  

    // В противном случае проверяем левое поддерево или правое поддерево

    // это LCA

    return (left_lca != NULL)? left_lca: right_lca;

}

  
// Основная функция, которая возвращает расстояние между n1
// и n2. Эта функция возвращает -1, если либо n1, либо n2
// отсутствует в двоичном дереве.

int findDistance(Node *root, int n1, int n2)

{

    // Инициализируем d1 (расстояние n1 от корня), d2

    // (расстояние n2 от корня) и dist (расстояние

    // между n1 и n2)

    int d1 = -1, d2 = -1, dist;

    Node *lca = findDistUtil(root, n1, n2, d1, d2,

                                          dist, 1);

  

    // Если оба n1 и n2 присутствовали в двоичном

    // Дерево, вернуть dist

    if (d1 != -1 && d2 != -1)

        return dist;

  

    // Если n1 является предком n2, рассмотрим n1 как root

    // и найти уровень n2 в поддереве с корнем n1

    if (d1 != -1)

    {

        dist = findLevel(lca, n2, 0);

        return dist;

    }

  

    // Если n2 является предком n1, считать n2 корнем

    // и найти уровень n1 в поддереве с корнем n2

    if (d2 != -1)

    {

        dist = findLevel(lca, n1, 0);

        return dist;

    }

  

    return -1;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Давайте создадим двоичное дерево, заданное в

    // приведенный выше пример

    Node * root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

    root->right->left->right = newNode(8);

    cout << "Dist(4, 5) = " << findDistance(root, 4, 5);

    cout << "nDist(4, 6) = " << findDistance(root, 4, 6);

    cout << "nDist(3, 4) = " << findDistance(root, 3, 4);

    cout << "nDist(2, 4) = " << findDistance(root, 2, 4);

    cout << "nDist(8, 5) = " << findDistance(root, 8, 5);

    return 0;

}

Джава

/ * Java-программа для определения расстояния между n1 и n2

 используя один обход * /

public class DistanceBetweenTwoKey 

{

    // (Модератору) в c ++ решение этой переменной

    // объявляются как указатели, следовательно, в них вносятся изменения

    // отражается во всей программе

      

    // Глобальная статическая переменная

    static int d1 = -1;

    static int d2 = -1;

    static int dist = 0;

      

    // Узел двоичного дерева

    static class Node{

        Node left, right;

        int key;

          

        // конструктор

        Node(int key){

            this.key = key;

            left = null;

            right = null;

        }

    }

      

    // Возвращает уровень ключа k, если он присутствует в дереве,

     // в противном случае возвращает -1

    static int findLevel(Node root, int k, int level)

    {

        // Базовый вариант

        if (root == null)

            return -1;

          

        // Если ключ присутствует в корне, или в левом поддереве или в правом поддереве,

        // возвращаем истину;

        if (root.key == k)

            return level;

              

        int l = findLevel(root.left, k, level + 1);

        return (l != -1)? l : findLevel(root.right, k, level + 1);

    }

      

    // Эта функция возвращает указатель на LCA двух заданных значений n1 и n2.

    // Он также устанавливает d1, d2 и dist, если один ключ не является предком другого

    // d1 -> сохранить расстояние n1 от корня

    // d2 -> сохранить расстояние n2 от корня

    // lvl -> Уровень (или расстояние от корня) текущего узла

    // dist -> Для сохранения расстояния между n1 и n2

    static Node findDistUtil(Node root, int n1, int n2, int lvl){

          

        // Базовый вариант

        if (root == null)

            return null;

          

        // Если n1 или n2 совпадает с ключом root, сообщить

        // присутствие, возвращая root (обратите внимание, что если ключ

        // предок другого, тогда ключ предка становится LCA

        if (root.key == n1){

            d1 = lvl;

            return root;

        }

        if (root.key == n2)

        {

            d2 = lvl;

            return root;

        }

          

        // ищем n1 и n2 в левом и правом поддеревьях

        Node left_lca = findDistUtil(root.left, n1, n2,  lvl + 1);

        Node right_lca = findDistUtil(root.right, n1, n2,  lvl + 1);

          

        // Если оба вышеуказанных вызова возвращают значение, отличное от NULL, то один ключ

        // присутствует в одном поддереве, а другое - в другом,

        // Итак, этот узел - LCA

        if (left_lca != null && right_lca != null)

        {

            dist = (d1 + d2) - 2*lvl;

            return root;

        }

          

        // В противном случае проверяем, является ли левое поддерево или правое поддерево LCA

        return (left_lca != null)? left_lca : right_lca;    

    }

      

    // Основная функция, которая возвращает расстояние между n1 и n2

    // Эта функция возвращает -1, если в n1 или n2 нет

    // Двоичное дерево.

    static int findDistance(Node root, int n1, int n2){

         d1 = -1;

         d2 = -1;

         dist = 0;

        Node lca = findDistUtil(root, n1, n2, 1);

          

        // Если в двоичном дереве присутствуют как n1, так и n2, вернуть dist

        if (d1 != -1 && d2 != -1)

            return dist;

          

        // Если n1 является предком n2, рассмотрим n1 как root и найдем уровень

        // из n2 в поддереве с корнем из n1

        if (d1 != -1)

        {

            dist = findLevel(lca, n2, 0);

            return dist;

        }

          

        // Если n2 является предком n1, рассмотрим n2 как root и найдем уровень

        // из n1 в поддереве с корнем из n2

        if (d2 != -1)

        {

            dist = findLevel(lca, n1, 0);

            return dist;

        }

          

        return -1;

    }

      

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) {

          

        // Давайте создадим двоичное дерево, приведенное в примере выше

        Node  root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

        root.left.left = new Node(4);

        root.left.right = new Node(5);

        root.right.left = new Node(6);

        root.right.right = new Node(7);

        root.right.left.right = new Node(8);

         

        System.out.println("Dist(4, 5) = "+findDistance(root, 4, 5));

        System.out.println("Dist(4, 6) = "+findDistance(root, 4, 6));

        System.out.println("Dist(3, 4) = "+findDistance(root, 3, 4));

        System.out.println("Dist(2, 4) = "+findDistance(root, 2, 4));

        System.out.println("Dist(8, 5) = " +findDistance(root, 8, 5));

          

    }

}
// Этот код предоставлен Sumit Ghosh

питон

# Программа Python, чтобы найти расстояние между
# n1 и n2, используя один обход

  

class Node:

    def __init__(self, data):

        self.data = data

        self.right = None

        self.left = None

  

def pathToNode(root, path, k):

  

    # обработка базового случая

    if root is None:

        return False

  

     # добавить значение узла в путь

    path.append(root.data)

   

    # Посмотрим, совпадает ли k с данными root

    if root.data == k :

        return True

   

    # Проверьте, найден ли k слева или справа

    # поддерево

    if ((root.left != None and pathToNode(root.left, path, k)) or

            (root.right!= None and pathToNode(root.right, path, k))):

        return True

   

    # Если отсутствует в поддереве с корнем root,

    # удалить root из path и вернуть False

    path.pop()

    return False

  

def distance(root, data1, data2):

    if root:

        # путь к хранилищу, соответствующий узлу: data1

        path1 = []

        pathToNode(root, path1, data1)

  

        # путь к хранилищу, соответствующий узлу: data2

        path2 = []

        pathToNode(root, path2, data2)

  

        # перебрать пути, чтобы найти

        # общая длина пути

        i=0

        while i<len(path1) and i<len(path2):

            # убирайся, как только путь отличается

            # или длина любого пути исчерпана

            if path1[i] != path2[i]:

                break

            i = i+1

  

        # получить длину пути, вычтя

        # длина пересекающегося пути (или до LCA)

        return (len(path1)+len(path2)-2*i)

    else:

        return 0

  
# Код драйвера для проверки вышеуказанных функций

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.right.right= Node(7)

root.right.left = Node(6)

root.left.right = Node(5)

root.right.left.right = Node(8)

  

dist = distance(root, 4, 5)

print "Distance between node {} & {}: {}".format(4, 5, dist) 

  

dist = distance(root, 4, 6)

print "Distance between node {} & {}: {}".format(4, 6, dist) 

  

dist = distance(root, 3, 4)

print "Distance between node {} & {}: {}".format(3, 4, dist) 

  

dist = distance(root, 2, 4)

print "Distance between node {} & {}: {}".format(2, 4, dist) 

  

dist = distance(root, 8, 5)

print "Distance between node {} & {}: {}".format(8, 5, dist) 

  
# Эта программа предоставлена Aartee

C #

// AC # Программа для поиска расстояния между
// n1 и n2, используя один обход

using System;

  

class GFG

{
// (Модератору) в решении C ++ эти
// переменные объявляются как указатели
// внесенные в них изменения отражаются на всей программе

  
// Глобальная статическая переменная

public static int d1 = -1;

public static int d2 = -1;

public static int dist = 0;

  
// Узел двоичного дерева

public class Node

{

    public Node left, right;

    public int key;

  

    // конструктор

    public Node(int key)

    {

        this.key = key;

        left = null;

        right = null;

    }

}

  
// Возвращает уровень ключа k, если он присутствует
// в дереве, иначе возвращает -1

public static int findLevel(Node root, int k,

                                   int level)

{

    // Базовый вариант

    if (root == null)

    {

        return -1;

    }

  

    // Если ключ присутствует в корне или слева

    // поддерево или правое поддерево, возвращаем true;

    if (root.key == k)

    {

        return level;

    }

  

    int l = findLevel(root.left, k, level + 1);

    return (l != -1)? l : findLevel(root.right, k, 

                                        level + 1);

}

  
// Эта функция возвращает указатель на LCA
// два заданных значения n1 и n2. Это также устанавливает
// d1, d2 и dist, если один ключ не является предком другого
// d1 -> сохранить расстояние n1 от корня
// d2 -> сохранить расстояние n2 от корня
// lvl -> Уровень (или расстояние от корня) текущего узла
// dist -> Для сохранения расстояния между n1 и n2

public static Node findDistUtil(Node root, int n1, 

                                   int n2, int lvl)

{

  

    // Базовый вариант

    if (root == null)

    {

        return null;

    }

  

    // Если n1 или n2 совпадают с root

    // ключ, сообщить о присутствии, вернувшись

    // root (Обратите внимание, что если ключ является предком

    // другой, тогда ключ предка становится LCA

    if (root.key == n1)

    {

        d1 = lvl;

        return root;

    }

    if (root.key == n2)

    {

        d2 = lvl;

        return root;

    }

  

    // ищем n1 и n2 в левом и правом поддеревьях

    Node left_lca = findDistUtil(root.left, n1, 

                                   n2, lvl + 1);

    Node right_lca = findDistUtil(root.right, n1, 

                                     n2, lvl + 1);

  

    // Если оба вышеуказанных вызова возвращают значение, отличное от NULL,

    // тогда один ключ присутствует в одном поддереве и

    // другое присутствует в другом, так что этот узел является LCA

    if (left_lca != null && right_lca != null)

    {

        dist = (d1 + d2) - 2 * lvl;

        return root;

    }

  

    // В противном случае проверяем, осталось ли поддерево

    // или правое поддерево - LCA

    return (left_lca != null)? left_lca : right_lca;

}

  
// Основная функция, которая возвращает расстояние
// между n1 и n2. Эта функция возвращает -1
// если n1 или n2 отсутствуют в
// Двоичное дерево.

public static int findDistance(Node root, int n1, int n2)

{

    d1 = -1;

    d2 = -1;

    dist = 0;

    Node lca = findDistUtil(root, n1, n2, 1);

  

    // Если присутствовали оба n1 и n2

    // в двоичном дереве вернуть dist

    if (d1 != -1 && d2 != -1)

    {

        return dist;

    }

  

    // Если n1 является предком n2, рассмотрим

    // n1 как root и найти уровень

    // из n2 в поддереве с корнем из n1

    if (d1 != -1)

    {

        dist = findLevel(lca, n2, 0);

        return dist;

    }

  

    // Если n2 является предком n1, рассмотрим

    // n2 как root и найти уровень

    // из n1 в поддереве с корнем из n2

    if (d2 != -1)

    {

        dist = findLevel(lca, n1, 0);

        return dist;

    }

  

    return -1;

}

  
// Код драйвера

public static void Main(string[] args)

{

  

    // Давайте создадим данное двоичное дерево

    // в приведенном выше примере

    Node root = new Node(1);

    root.left = new Node(2);

    root.right = new Node(3);

    root.left.left = new Node(4);

    root.left.right = new Node(5);

    root.right.left = new Node(6);

    root.right.right = new Node(7);

    root.right.left.right = new Node(8);

  

    Console.WriteLine("Dist(4, 5) = "

                       findDistance(root, 4, 5));

    Console.WriteLine("Dist(4, 6) = "

                       findDistance(root, 4, 6));

    Console.WriteLine("Dist(3, 4) = "

                       findDistance(root, 3, 4));

    Console.WriteLine("Dist(2, 4) = "

                       findDistance(root, 2, 4));

    Console.WriteLine("Dist(8, 5) = "

                       findDistance(root, 8, 5));

}
}

  
// Этот код предоставлен Shrikant13


Выход:

Dist(4, 5) = 2
Dist(4, 6) = 4
Dist(3, 4) = 3
Dist(2, 4) = 1
Dist(8, 5) = 5

Сложность времени: временная сложность вышеупомянутого решения составляет O (n), так как метод выполняет один обход дерева.

Спасибо Атул Сингх за предоставление первоначального решения для этого поста.

Лучшее решение:
Сначала мы находим LCA из двух узлов. Затем мы находим расстояние от LCA до двух узлов.

C ++

/ * C ++ Программа для поиска расстояния между n1 и n2

   используя один обход * /

#include <iostream>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    struct Node *left, *right;

    int key;

};

  
// Сервисная функция для создания нового дерева Node

Node* newNode(int key)

{

    Node *temp = new Node;

    temp->key = key;

    temp->left = temp->right = NULL;

    return temp;

}

Node* LCA(Node * root, int n1,int n2)

{

    // Ваш код здесь

    if (root == NULL)

       return root;

    if (root->key == n1 || root->key == n2)

       return root;

  

    Node* left = LCA(root->left, n1, n2);

    Node* right = LCA(root->right, n1, n2);

  

    if (left != NULL && right != NULL)

         return root;

    if (left != NULL)

        return LCA(root->left, n1, n2);

  

    return LCA(root->right, n1, n2);

}

  
// Возвращает уровень ключа k, если он присутствует в
// дерево, иначе возвращает -1

int findLevel(Node *root, int k, int level)

{

    if(root == NULL) return -1;

    if(root->key == k) return level;

  

    int left = findLevel(root->left, k, level+1);

    if (left == -1)

       return findLevel(root->right, k, level+1);

    return left;

}

  

int findDistance(Node* root, int a, int b)

{

    // Ваш код здесь

    Node* lca = LCA(root, a , b);

  

    int d1 = findLevel(lca, a, 0);

    int d2 = findLevel(lca, b, 0);

  

    return d1 + d2;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Давайте создадим двоичное дерево, заданное в

    // приведенный выше пример

    Node * root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

    root->right->left->right = newNode(8);

    cout << "Dist(4, 5) = " << findDistance(root, 4, 5);

    cout << "\nDist(4, 6) = " << findDistance(root, 4, 6);

    cout << "\nDist(3, 4) = " << findDistance(root, 3, 4);

    cout << "\nDist(2, 4) = " << findDistance(root, 2, 4);

    cout << "\nDist(8, 5) = " << findDistance(root, 8, 5);

    return 0;

}

Джава

/ * Java-программа для поиска расстояния между n1 и n2

   используя один обход * /

public class GFG {

  

    public static class Node {

        int value;

        Node left;

        Node right;

  

        public Node(int value) {

            this.value = value;

        }

    }

  

    public static Node LCA(Node root, int n1, int n2) 

    {

        if (root == null)

            return root;

        if (root.value == n1 || root.value == n2)

            return root;

  

        Node left = LCA(root.left, n1, n2);

        Node right = LCA(root.right, n1, n2);

  

        if (left != null && right != null)

            return root;

        if (left != null)

            return LCA(root.left, n1, n2);

        else

            return LCA(root.right, n1, n2);

    }

  

    // Возвращает уровень ключа k, если он присутствует в

    // дерево, иначе возвращает -1

    public static int findLevel(Node root, int a, int level)

    {

        if (root == null)

            return -1;

        if (root.value == a)

            return level;

        int left = findLevel(root.left, a, level + 1);

        if (left == -1)

            return findLevel(root.right, a, level + 1);

        return left;

    }

  

    public static int findDistance(Node root, int a, int b)

    {

        Node lca = LCA(root, a, b);

  

        int d1 = findLevel(lca, a, 0);

        int d2 = findLevel(lca, b, 0);

  

        return d1 + d2;

    }

      

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) {

          

        // Давайте создадим двоичное дерево, заданное в

        // приведенный выше пример

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

        root.left.left = new Node(4);

        root.left.right = new Node(5);

        root.right.left = new Node(6);

        root.right.right = new Node(7);

        root.right.left.right = new Node(8);

        System.out.println("Dist(4, 5) = " 

                             + findDistance(root, 4, 5));

                               

        System.out.println("Dist(4, 6) = " 

                             + findDistance(root, 4, 6));

                               

        System.out.println("Dist(3, 4) = " 

                             + findDistance(root, 3, 4));

                               

        System.out.println("Dist(2, 4) = " 

                             + findDistance(root, 2, 4));

                               

        System.out.println("Dist(8, 5) = "

                             + findDistance(root, 8, 5));

  

    }

}

  
// Этот код предоставлен Шринивасаном Джаяраманом.

python3

«»»
Программа Python, чтобы найти расстояние между n1
и n2 в двоичном дереве
«»»
# двоичный узел дерева

class Node:

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = self.right = None

  

  
# Эта функция возвращает указатель на LCA
# два заданных значения n1 и n2.

def LCA(root, n1, n2):

      

    # Базовый вариант

    if root is None:

        return None

  

    # Если n1 или n2 совпадают с root

    # ключ, сообщить о присутствии, вернувшись

    # root

    if root.data == n1 or root.data == n2:

        return root

  

    # Ищите ключи в левом и правом поддеревьях

    left = LCA(root.left, n1, n2)

    right = LCA(root.right, n1, n2)

  

    if left is not None and right is not None:

        return root

  

    # В противном случае проверьте, осталось ли поддерево или

    # правильное поддерево LCA

    if left:

        return left

    else:

        return right

  

  
# функция для определения расстояния до любого узла
# от корня

def findLevel(root, data, d, level):

      

    # Базовый случай, когда дерево пусто

    if root is None:

        return

  

    # Узел найден, затем добавьте уровень

    # значение для отображения и возврата

    if root.data == data:

        d.append(level)

        return

  

    findLevel(root.left, data, d, level + 1)

    findLevel(root.right, data, d, level + 1)

  
# функция, чтобы найти расстояние между двумя
# узлы в двоичном дереве

def findDistance(root, n1, n2):

      

    lca = LCA(root, n1, n2)

      

    # хранить расстояние n1 от lca

    d1 = [] 

      

    # хранить расстояние n2 от lca

    d2 = [] 

  

    # если существует

    if lca:

          

        # расстояние n1 от lca

        findLevel(lca, n1, d1, 0

          

        # расстояние n2 от lca

        findLevel(lca, n2, d2, 0

        return d1[0] + d2[0]

    else:

        return -1

  

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.left = Node(6)

root.right.right = Node(7)

root.right.left.right = Node(8)

  

print("Dist(4,5) = ", findDistance(root, 4, 5))

print("Dist(4,6) = ", findDistance(root, 4, 6))

print("Dist(3,4) = ", findDistance(root, 3, 4))

print("Dist(2,4) = ", findDistance(root, 2, 4))

print("Dist(8,5) = ", findDistance(root, 8, 5))

  
# Эта статья предоставлена Шветой Сингх.

C #

using System;

  
/ * C # Программа для поиска расстояния между n1 и n2

   используя один обход * /

public class GFG

{

  

    public class Node

    {

        public int value;

        public Node left;

        public Node right;

  

        public Node(int value)

        {

            this.value = value;

        }

    }

  

    public static Node LCA(Node root, int n1, int n2)

    {

        if (root == null)

        {

            return root;

        }

        if (root.value == n1 || root.value == n2)

        {

            return root;

        }

  

        Node left = LCA(root.left, n1, n2);

        Node right = LCA(root.right, n1, n2);

  

        if (left != null && right != null)

        {

            return root;

        }

        if (left != null)

        {

            return LCA(root.left, n1, n2);

        }

        else

        {

            return LCA(root.right, n1, n2);

        }

    }

  

    // Возвращает уровень ключа k, если он присутствует в

    // дерево, иначе возвращает -1

    public static int findLevel(Node root, int a, int level)

    {

        if (root == null)

        {

            return -1;

        }

        if (root.value == a)

        {

            return level;

        }

        int left = findLevel(root.left, a, level + 1);

        if (left == -1)

        {

            return findLevel(root.right, a, level + 1);

        }

        return left;

    }

  

    public static int findDistance(Node root, int a, int b)

    {

        Node lca = LCA(root, a, b);

  

        int d1 = findLevel(lca, a, 0);

        int d2 = findLevel(lca, b, 0);

  

        return d1 + d2;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(string[] args)

    {

  

        // Давайте создадим двоичное дерево, заданное в

        // приведенный выше пример

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

        root.left.left = new Node(4);

        root.left.right = new Node(5);

        root.right.left = new Node(6);

        root.right.right = new Node(7);

        root.right.left.right = new Node(8);

        Console.WriteLine("Dist(4, 5) = " + findDistance(root, 4, 5));

  

        Console.WriteLine("Dist(4, 6) = " + findDistance(root, 4, 6));

  

        Console.WriteLine("Dist(3, 4) = " + findDistance(root, 3, 4));

  

        Console.WriteLine("Dist(2, 4) = " + findDistance(root, 2, 4));

  

        Console.WriteLine("Dist(8, 5) = " + findDistance(root, 8, 5));

  

    }

}

  

  // Этот код предоставлен Shrikant13


Выход :

Dist(4, 5) = 2
Dist(4, 6) = 4
Dist(3, 4) = 3
Dist(2, 4) = 1
Dist(8, 5) = 5

Спасибо NILMADHAB MONDAL за предложение этого решения.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти расстояние между двумя узлами двоичного дерева

0.00 (0%) 0 votes