Рубрики

Найдите ближайший лист в бинарном дереве

По заданному двоичному дереву и ключу «k» найдите расстояние ближайшего листа от «k».

Примеры:

              A
            /    \    
           B       C
                 /   \  
                E     F   
               /       \
              G         H
             / \       /
            I   J     K

Closest leaf to 'H' is 'K', so distance is 1 for 'H'
Closest leaf to 'C' is 'B', so distance is 2 for 'C'
Closest leaf to 'E' is either 'I' or 'J', so distance is 2 for 'E' 
Closest leaf to 'B' is 'B' itself, so distance is 0 for 'B' 

Главное, на что следует обратить внимание, это то, что ближайший ключ может быть либо потомком данного ключа, либо может быть достигнут через одного из предков.
Идея состоит в том, чтобы пройти заданное дерево в предзаказе и отслеживать предков в массиве. Когда мы достигаем заданного ключа, мы оцениваем расстояние до ближайшего листа в поддереве с корнем данного ключа. Мы также пересекаем всех предков одного за другим и находим расстояние ближайшего листа в поддереве с корнем предка. Мы сравниваем все расстояния и возвращаем минимум.

Ниже приведена реализация вышеуказанного подхода.

C ++

// Программа на C ++ для поиска листа замыкания данного ключа в двоичном дереве
#include <iostream>
#include <climits>

using namespace std;

  
/ * Узел двоичного дерева имеет ключ, pocharer для левого и правого дочерних элементов * /

struct Node

{

    char key;

    struct Node* left, *right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с

   даны данные и NULL левого и правого pocharers. * /

Node *newNode(char k)

{

    Node *node = new Node;

    node->key = k;

    node->right = node->left = NULL;

    return node;

}

  
// Полезная функция для нахождения минимума x и y

int getMin(int x, int y)

{

    return (x < y)? x :y;

}

  
// Полезная функция для определения расстояния до ближайшего листа дерева
// корень под данным корнем

int closestDown(struct Node *root)

{

    // Базовые случаи

    if (root == NULL)

        return INT_MAX;

    if (root->left == NULL && root->right == NULL)

        return 0;

  

    // Возвращаем минимум левого и правого плюс один

    return 1 + getMin(closestDown(root->left), closestDown(root->right));

}

  
// Возвращает расстояние листа сгустка до заданного ключа 'k'. Массив
// предки используются для отслеживания предков текущего узла и
// 'index' используется для отслеживания индекса curremt в 'ancestors []'

int findClosestUtil(struct Node *root, char k, struct Node *ancestors[],

                                               int index)

{

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

    if (root == NULL)

        return INT_MAX;

  

    // Если ключ найден

    if (root->key == k)

    {

        // Находим лист клеста под поддеревом с корневым ключом

        int res = closestDown(root);

  

        // Обходим всех предков и обновляем результат, если есть родительский узел

        // дает меньшее расстояние

        for (int i = index-1; i>=0; i--)

            res = getMin(res, index - i + closestDown(ancestors[i]));

        return res;

    }

  

    // Если ключевой узел найден, сохранить текущий узел и повторить для левого и

    // правильные дети

    ancestors[index] = root;

    return getMin(findClosestUtil(root->left, k, ancestors, index+1),

                  findClosestUtil(root->right, k, ancestors, index+1));

  
}

  
// Основная функция, которая возвращает расстояние ближайшего ключа до «k». Это
// в основном использует рекурсивную функцию findClosestUtil () для поиска замыканий
// расстояние.

int findClosest(struct Node *root, char k)

{

    // Создать массив для хранения предков

    // Assumptiom: максимальная высота дерева 100

    struct Node *ancestors[100];

  

    return findClosestUtil(root, k, ancestors, 0);

}

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

int main()

{

    // Давайте построим BST, показанный на рисунке выше

    struct Node *root        = newNode('A');

    root->left               = newNode('B');

    root->right              = newNode('C');

    root->right->left        = newNode('E');

    root->right->right       = newNode('F');

    root->right->left->left  = newNode('G');

    root->right->left->left->left  = newNode('I');

    root->right->left->left->right = newNode('J');

    root->right->right->right      = newNode('H');

    root->right->right->right->left = newNode('K');

  

    char k = 'H';

    cout << "Distance of the closest key from " << k << " is "

         << findClosest(root, k) << endl;

    k = 'C';

    cout << "Distance of the closest key from " << k << " is "

         << findClosest(root, k) << endl;

    k = 'E';

    cout << "Distance of the closest key from " << k << " is "

         << findClosest(root, k) << endl;

    k = 'B';

    cout << "Distance of the closest key from " << k << " is "

         << findClosest(root, k) << endl;

  

    return 0;

}

Джава

// Java-программа для поиска ближайшего листа данного ключа в двоичном дереве

   
/ * Класс, содержащий левого и правого потомка текущего

   значение узла и ключа * /

class Node 

{

    int data;

    Node left, right;

   

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

       

    // Полезная функция для нахождения минимума x и y

    int getMin(int x, int y) 

    {

        return (x < y) ? x : y;

    }

   

    // Полезная функция для определения расстояния до ближайшего листа дерева

    // корень под данным корнем

    int closestDown(Node node) 

    {

        // Базовые случаи

        if (node == null)

            return Integer.MAX_VALUE;

        if (node.left == null && node.right == null)

            return 0;

   

        // Возвращаем минимум левого и правого плюс один

        return 1 + getMin(closestDown(node.left), closestDown(node.right));

    }

   

    // Возвращает расстояние листа сгустка до заданного ключа 'k'. Массив

    // предки используются для отслеживания предков текущего узла и

    // 'index' используется для отслеживания индекса curremt в 'ancestors []'

    int findClosestUtil(Node node, char k, Node ancestors[], int index) 

    {

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

        if (node == null)

            return Integer.MAX_VALUE;

   

        // Если ключ найден

        if (node.data == k) 

        {

            // Находим лист клеста под поддеревом с корневым ключом

            int res = closestDown(node);

   

            // Обходим всех предков и обновляем результат, если есть родительский узел

            // дает меньшее расстояние

            for (int i = index - 1; i >= 0; i--)

                res = getMin(res, index - i + closestDown(ancestors[i]));

            return res;

        }

   

        // Если ключевой узел найден, сохранить текущий узел и повторить для левого и

        // правильные дети

        ancestors[index] = node;

        return getMin(findClosestUtil(node.left, k, ancestors, index + 1),

                findClosestUtil(node.right, k, ancestors, index + 1));

   

    }

   

    // Основная функция, которая возвращает расстояние ближайшего ключа до «k». Это

    // в основном использует рекурсивную функцию findClosestUtil () для поиска замыканий

    // расстояние.

    int findClosest(Node node, char k) 

    {

        // Создать массив для хранения предков

        // Assumptiom: максимальная высота дерева 100

        Node ancestors[] = new Node[100];

   

        return findClosestUtil(node, k, ancestors, 0);

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node('A');

        tree.root.left = new Node('B');

        tree.root.right = new Node('C');

        tree.root.right.left = new Node('E');

        tree.root.right.right = new Node('F');

        tree.root.right.left.left = new Node('G');

        tree.root.right.left.left.left = new Node('I');

        tree.root.right.left.left.right = new Node('J');

        tree.root.right.right.right = new Node('H');

        tree.root.right.right.right.left = new Node('H');

   

        char k = 'H';

        System.out.println("Distance of the closest key from " + k + " is "

                            + tree.findClosest(tree.root, k));

        k = 'C';

        System.out.println("Distance of the closest key from " + k + " is "

                            + tree.findClosest(tree.root, k));

        k = 'E';

        System.out.println("Distance of the closest key from " + k + " is "

                            + tree.findClosest(tree.root, k));

        k = 'B';

        System.out.println("Distance of the closest key from " + k + " is "

                             + tree.findClosest(tree.root, k));

   

    }

}

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

питон

# Программа Python, чтобы найти ближайший лист
# данный ключ в двоичном дереве

  

INT_MAX = 2**32

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

class Node:

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

    def __init__(self ,key):

        self.key = key

        self.left  = None

        self.right = None

  

def closestDown(root):

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

    if root is None:

        return INT_MAX

    if root.left is None and root.right is None:

        return 0

      

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

    return 1 + min(closestDown(root.left),

                   closestDown(root.right))

  
# Возвращает адрес закрытия листа для данного ключа k
# Массив предков, который мы использовали, чтобы отслеживать предков
# текущего узла, а индекс используется для отслеживания
# текущий индекс в 'ancestors [i]'

def findClosestUtil(root, k, ancestors, index):

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

    if root is None:

        return INT_MAX

      

    # если ключ найден

    if root.key == k:

        # Найти ближайший лист под поддеревом

        # с данным ключом

        res = closestDown(root)

          

        # Пройдите через предков и обновите результат, если таковой имеется

        # родительский узел дает меньшее расстояние

        for i in reversed(range(0,index)):

            res = min(res, index-i+closestDown(ancestors[i]))

        return res

  

    # если ключевой узел найден, сохранить текущий узел и повторить для левого

    # и право детей

    ancestors[index] = root

    return min(

        findClosestUtil(root.left, k,ancestors, index+1),

        findClosestUtil(root.right, k, ancestors, index+1))

  
# Основная функция, которая возвращает расстояние клавиши clses до
# «ключ». В основном используется рекурсивная функция findClosestUtil ()
# найти близкое расстояние

def findClosest(root, k):

    # Создать массив для хранения предков

    # Предположение: максимальная высота дерева 100

    ancestors = [None for i in range(100)]

  

    return findClosestUtil(root, k, ancestors, 0)

  

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

root = Node('A')

root.left = Node('B')

root.right = Node('C');

root.right.left = Node('E');

root.right.right  = Node('F');

root.right.left.left = Node('G');

root.right.left.left.left  = Node('I');

root.right.left.left.right = Node('J');

root.right.right.right  = Node('H');

root.right.right.right.left = Node('K');

  

k = 'H';

print "Distance of the closest key from "+ k + " is",

print findClosest(root, k)

  

k = 'C'

print "Distance of the closest key from " + k + " is",

print findClosest(root, k)

  

k = 'E'

print "Distance of the closest key from " + k + " is",

print findClosest(root, k)

  

k = 'B'

print "Distance of the closest key from " + k + " is",

print findClosest(root, k)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// C # программа для поиска ближайшего листа данного ключа в двоичном дереве

  
/ * Класс, содержащий левого и правого потомка текущего

   значение узла и ключа * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    // Полезная функция для нахождения минимума x и y

    public virtual int getMin(int x, int y)

    {

        return (x < y) ? x : y;

    }

  

    // Полезная функция для определения расстояния до ближайшего листа дерева

    // корень под данным корнем

    public virtual int closestDown(Node node)

    {

        // Базовые случаи

        if (node == null)

        {

            return int.MaxValue;

        }

        if (node.left == null && node.right == null)

        {

            return 0;

        }

  

        // Возвращаем минимум левого и правого плюс один

        return 1 + getMin(closestDown(node.left), closestDown(node.right));

    }

  

    // Возвращает расстояние листа сгустка до заданного ключа 'k'. Массив

    // предки используются для отслеживания предков текущего узла и

    // 'index' используется для отслеживания индекса curremt в 'ancestors []'

    public virtual int findClosestUtil(Node node, char k, Node[] ancestors, int index)

    {

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

        if (node == null)

        {

            return int.MaxValue;

        }

  

        // Если ключ найден

        if ((char)node.data == k)

        {

            // Находим лист клеста под поддеревом с корневым ключом

            int res = closestDown(node);

  

            // Обходим всех предков и обновляем результат, если есть родительский узел

            // дает меньшее расстояние

            for (int i = index - 1; i >= 0; i--)

            {

                res = getMin(res, index - i + closestDown(ancestors[i]));

            }

            return res;

        }

  

        // Если ключевой узел найден, сохранить текущий узел и повторить для левого и

        // правильные дети

        ancestors[index] = node;

        return getMin(findClosestUtil(node.left, k, ancestors, index + 1), findClosestUtil(node.right, k, ancestors, index + 1));

  

    }

  

    // Основная функция, которая возвращает расстояние ближайшего ключа до «k». Это

    // в основном использует рекурсивную функцию findClosestUtil () для поиска замыканий

    // расстояние.

    public virtual int findClosest(Node node, char k)

    {

        // Создать массив для хранения предков

        // Assumptiom: максимальная высота дерева 100

        Node[] ancestors = new Node[100];

  

        return findClosestUtil(node, k, ancestors, 0);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node('A');

        tree.root.left = new Node('B');

        tree.root.right = new Node('C');

        tree.root.right.left = new Node('E');

        tree.root.right.right = new Node('F');

        tree.root.right.left.left = new Node('G');

        tree.root.right.left.left.left = new Node('I');

        tree.root.right.left.left.right = new Node('J');

        tree.root.right.right.right = new Node('H');

        tree.root.right.right.right.left = new Node('H');

  

        char k = 'H';

        Console.WriteLine("Distance of the closest key from " + k + " is " + tree.findClosest(tree.root, k));

        k = 'C';

        Console.WriteLine("Distance of the closest key from " + k + " is " + tree.findClosest(tree.root, k));

        k = 'E';

        Console.WriteLine("Distance of the closest key from " + k + " is " + tree.findClosest(tree.root, k));

        k = 'B';

        Console.WriteLine("Distance of the closest key from " + k + " is " + tree.findClosest(tree.root, k));

  

    }

}

  

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


Выход:

Distance of the closest key from H is 1
Distance of the closest key from C is 2
Distance of the closest key from E is 2
Distance of the closest key from B is 0 

Приведенный выше код может быть оптимизирован путем сохранения левой и правой информации также в массиве предков. Идея состоит в том, что если данный ключ находится в левом поддереве предков, то нет смысла вызывать closestDown (). Кроме того, цикл может, который пересекает массив предков, может быть оптимизирован, чтобы не пересекать предков, которые находятся на большем расстоянии, чем текущий результат.

Упражнение:
Расширьте вышеприведенное решение, чтобы напечатать не только расстояние, но и ключ ближайшего листа.

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

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

Найдите ближайший лист в бинарном дереве

0.00 (0%) 0 votes