Рубрики

Ближайший лист к данному узлу в двоичном дереве

По заданному двоичному дереву и узлу x в нем найдите расстояние от ближайшего листа до x в двоичном дереве. Если данный узел сам является листом, то расстояние равно 0.

Примеры:

Input: Root of below tree
       And x = pointer to node 13
          10
       /     \
     12       13
             /     
           14      
Output 1
Distance 1. Closest leaf is 14.


Input: Root of below tree
       And x = pointer to node 13
          10
       /     \
     12       13
           /     \
         14       15    
        /   \     /  \
       21   22   23   24
       /\   /\   /\   /\
      1 2  3 4  5 6  7  8

Output 2
Closest leaf is 12 through 10.

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

C ++

/ * Найти ближайший лист к данному узлу x в дереве * /
#include<bits/stdc++.h>

using namespace std;

  
// Узел дерева

struct Node

{

    int key;

    struct Node* left, *right;

};

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

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

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

    return (temp);

}

  
// Эта функция находит ближайший к корню лист. Это расстояние
// хранится в * minDist.

void findLeafDown(Node *root, int lev, int *minDist)

{

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

    if (root == NULL)

        return ;

  

    // Если это листовой узел, то проверяем, ближе ли он

    // чем ближе всего

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

    {

        if (lev < (*minDist))

            *minDist = lev;

        return;

    }

  

    // Повтор для левого и правого поддеревьев

    findLeafDown(root->left, lev+1, minDist);

    findLeafDown(root->right, lev+1, minDist);

}

  
// Эта функция находит, если есть более близкий лист к x через
// родительский узел.

int findThroughParent(Node * root, Node *x, int *minDist)

{

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

    if (root == NULL) return -1;

    if (root == x) return 0;

  

    // Поиск x в левом поддереве корня

    int l = findThroughParent(root->left, x,  minDist);

  

    // Если у левого поддерева есть x

    if (l != -1)

    {

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

        findLeafDown(root->right, l+2, minDist);

        return l+1;

    }

  

    // Поиск x в правом поддереве корня

    int r = findThroughParent(root->right, x, minDist);

  

    // Если правое поддерево имеет х

    if (r != -1)

    {

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

        findLeafDown(root->left, r+2, minDist);

        return r+1;

    }

  

    return -1;

}

  
// Возвращает минимальное расстояние листа от заданного узла x

int minimumDistance(Node *root, Node *x)

{

    // Инициализировать результат (минимальное расстояние от листа)

    int minDist = INT_MAX;

  

    // Находим ближайший лист до х

    findLeafDown(x, 0, &minDist);

  

    // Посмотрим, есть ли ближе родитель

    findThroughParent(root, x, &minDist);

  

    return minDist;

}

  
// Драйвер программы

int main ()

{

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

    Node *root  = newNode(1);

    root->left  = newNode(12);

    root->right = newNode(13);

  

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

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

  

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

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

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

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

  

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

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

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

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

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

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

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

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

  

    Node *x = root->right;

  

    cout << "The closest leaf to the node with value "

         << x->key << " is at a distance of "

         << minimumDistance(root, x) << endl;

  

    return 0;

}

Джава

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

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

class Node 

{

    int key;

    Node left, right;

   

    public Node(int key) 

    {

        this.key = key;

        left = right = null;

    }

}

   

class Distance 

{

    int minDis = Integer.MAX_VALUE;

}

   

class BinaryTree 

{

    Node root;

   

    // Эта функция находит ближайший к корню лист. Это расстояние

    // хранится в * minDist.

    void findLeafDown(Node root, int lev, Distance minDist) 

    {

           

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

        if (root == null

            return;

   

        // Если это листовой узел, то проверяем, ближе ли он

        // чем ближе всего

        if (root.left == null && root.right == null

        {

            if (lev < (minDist.minDis)) 

                minDist.minDis = lev;

               

            return;

        }

   

        // Повтор для левого и правого поддеревьев

        findLeafDown(root.left, lev + 1, minDist);

        findLeafDown(root.right, lev + 1, minDist);

    }

   

    // Эта функция находит, если есть более близкий лист к x через

    // родительский узел.

    int findThroughParent(Node root, Node x, Distance minDist) 

    {

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

        if (root == null

            return -1;

           

        if (root == x) 

            return 0;

           

        // Поиск x в левом поддереве корня

        int l = findThroughParent(root.left, x, minDist);

   

        // Если у левого поддерева есть x

        if (l != -1

        {    

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

            findLeafDown(root.right, l + 2, minDist);

            return l + 1;

        }

   

        // Поиск x в правом поддереве корня

        int r = findThroughParent(root.right, x, minDist);

   

        // Если правое поддерево имеет х

        if (r != -1

        {

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

            findLeafDown(root.left, r + 2, minDist);

            return r + 1;

        }

   

        return -1;

    }

   

    // Возвращает минимальное расстояние листа от заданного узла x

    int minimumDistance(Node root, Node x) 

    {

        // Инициализировать результат (минимальное расстояние от листа)

        Distance d = new Distance();

   

        // Находим ближайший лист до х

        findLeafDown(x, 0, d);

   

        // Посмотрим, есть ли ближе родитель

        findThroughParent(root, x, d);

   

        return d.minDis;

    }

   

    // Драйвер программы

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

           

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

        tree.root = new Node(1);

        tree.root.left = new Node(12);

        tree.root.right = new Node(13);

   

        tree.root.right.left = new Node(14);

        tree.root.right.right = new Node(15);

   

        tree.root.right.left.left = new Node(21);

        tree.root.right.left.right = new Node(22);

        tree.root.right.right.left = new Node(23);

        tree.root.right.right.right = new Node(24);

   

        tree.root.right.left.left.left = new Node(1);

        tree.root.right.left.left.right = new Node(2);

        tree.root.right.left.right.left = new Node(3);

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

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

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

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

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

   

        Node x = tree.root.right;

   

        System.out.println("The closest leaf to node with value "

                + x.key + " is at a distance of "

                + tree.minimumDistance(tree.root, x));

    }

}

   
// Этот код был добавлен mayank_24

python3

# Найти ближайший лист к данному
# узел x в дереве

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

class newNode:

    def __init__(self, key):

        self.key = key 

        self.left = self.right = None

      
# Эта функция находит ближайший лист к
# root. Это расстояние хранится в * minDist.

def findLeafDown(root, lev, minDist):

      

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

    if (root == None): 

        return

  

    # Если это листовой узел, то проверьте,

    # он ближе, чем самый близкий

    if (root.left == None and 

        root.right == None):

        if (lev < (minDist[0])): 

            minDist[0] = lev 

        return

  

    # Повтор для левого и правого поддеревьев

    findLeafDown(root.left, lev + 1, minDist) 

    findLeafDown(root.right, lev + 1, minDist)

  
# Эта функция находит, если есть
# ближе к x через родительский узел.

def findThroughParent(root, x, minDist):

      

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

    if (root == None):

        return -1

    if (root == x):

        return 0

  

    # Поиск х в левом поддереве корня

    l = findThroughParent(root.left, x, 

                               minDist) 

  

    # Если у левого поддерева есть x

    if (l != -1):

          

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

        findLeafDown(root.right, l + 2, minDist) 

        return l + 1

  

    # Поиск х в правом поддереве корня

    r = findThroughParent(root.right, x, minDist) 

  

    # Если правильное поддерево имеет х

    if (r != -1):

          

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

        findLeafDown(root.left, r + 2, minDist) 

        return r + 1

  

    return -1

  
# Возвращает минимальное расстояние листа
# из данного узла x

def minimumDistance(root, x):

      

    # Инициализировать результат (минимум

    # расстояние от листа)

    minDist = [999999999999]

  

    # Найти ближайший лист до х

    findLeafDown(x, 0, minDist) 

  

    # Посмотрим, есть ли ближе лист

    # через родителя

    findThroughParent(root, x, minDist) 

  

    return minDist[0]

  
Код водителя

if __name__ == '__main__':

      

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

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

    root = newNode(1

    root.left = newNode(12

    root.right = newNode(13

  

    root.right.left = newNode(14

    root.right.right = newNode(15

  

    root.right.left.left = newNode(21

    root.right.left.right = newNode(22

    root.right.right.left = newNode(23

    root.right.right.right = newNode(24

  

    root.right.left.left.left = newNode(1

    root.right.left.left.right = newNode(2

    root.right.left.right.left = newNode(3

    root.right.left.right.right = newNode(4

    root.right.right.left.left = newNode(5

    root.right.right.left.right = newNode(6

    root.right.right.right.left = newNode(7

    root.right.right.right.right = newNode(8

  

    x = root.right 

  

    print("The closest leaf to the node with value",

           x.key, "is at a distance of"

           minimumDistance(root, x))

  
# Этот код предоставлен PranchalK

C #

using System;

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

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

public class Node

{

    public int key;

    public Node left, right;

  

    public Node(int key)

    {

        this.key = key;

        left = right = null;

    }

}

  

public class Distance

{

    public int minDis = int.MaxValue;

}

  

public class BinaryTree

{

    public Node root;

  

    // Эта функция находит ближайший к корню лист. Это расстояние

    // хранится в * minDist.

    public virtual void findLeafDown(Node root, int lev, Distance minDist)

    {

  

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

        if (root == null)

        {

            return;

        }

  

        // Если это листовой узел, то проверяем, ближе ли он

        // чем ближе всего

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

        {

            if (lev < (minDist.minDis))

            {

                minDist.minDis = lev;

            }

  

            return;

        }

  

        // Повтор для левого и правого поддеревьев

        findLeafDown(root.left, lev + 1, minDist);

        findLeafDown(root.right, lev + 1, minDist);

    }

  

    // Эта функция находит, если есть более близкий лист к x через

    // родительский узел.

    public virtual int findThroughParent(Node root, Node x, Distance minDist)

    {

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

        if (root == null)

        {

            return -1;

        }

  

        if (root == x)

        {

            return 0;

        }

  

        // Поиск x в левом поддереве корня

        int l = findThroughParent(root.left, x, minDist);

  

        // Если у левого поддерева есть x

        if (l != -1)

        {

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

            findLeafDown(root.right, l + 2, minDist);

            return l + 1;

        }

  

        // Поиск x в правом поддереве корня

        int r = findThroughParent(root.right, x, minDist);

  

        // Если правое поддерево имеет х

        if (r != -1)

        {

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

            findLeafDown(root.left, r + 2, minDist);

            return r + 1;

        }

  

        return -1;

    }

  

    // Возвращает минимальное расстояние листа от заданного узла x

    public virtual int minimumDistance(Node root, Node x)

    {

        // Инициализировать результат (минимальное расстояние от листа)

        Distance d = new Distance();

  

        // Находим ближайший лист до х

        findLeafDown(x, 0, d);

  

        // Посмотрим, есть ли ближе родитель

        findThroughParent(root, x, d);

  

        return d.minDis;

    }

  

    // Драйвер программы

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

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

        tree.root = new Node(1);

        tree.root.left = new Node(12);

        tree.root.right = new Node(13);

  

        tree.root.right.left = new Node(14);

        tree.root.right.right = new Node(15);

  

        tree.root.right.left.left = new Node(21);

        tree.root.right.left.right = new Node(22);

        tree.root.right.right.left = new Node(23);

        tree.root.right.right.right = new Node(24);

  

        tree.root.right.left.left.left = new Node(1);

        tree.root.right.left.left.right = new Node(2);

        tree.root.right.left.right.left = new Node(3);

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

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

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

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

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

  

        Node x = tree.root.right;

  

        Console.WriteLine("The closest leaf to node with value " + x.key + " is at a distance of " + tree.minimumDistance(tree.root, x));

    }

}

  

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


Выход:

The closest leaf to the node with value 13 is at a distance of 2

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

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

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

Ближайший лист к данному узлу в двоичном дереве

0.00 (0%) 0 votes