Рубрики

Вывести все узлы на расстоянии k от данного узла

Для заданного двоичного дерева, целевого узла в двоичном дереве и целочисленного значения k выведите все узлы, которые находятся на расстоянии k от заданного целевого узла. Нет родительских указателей доступны.

Consider the tree shown in diagram

Input: target = pointer to node with data 8.
root = pointer to node with data 20.
k = 2.
Output : 10 14 22

If target is 14 and k is 3, then output
should be “4 20”

Есть два типа узлов, которые необходимо учитывать.
1) Узлы в поддереве имеют корни с целевым узлом. Например, если целевым узлом является 8, а k равно 2, то такими узлами являются 10 и 14.
2) Другие узлы могут быть предком цели или узлом в каком-либо другом поддереве. Для целевого узла 8 и k равно 2, узел 22 входит в эту категорию.

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

Как найти узлы второго типа? Чтобы выходные узлы не лежали в поддереве с целевым узлом в качестве корня, мы должны пройти через всех предков. Для каждого предка мы находим его расстояние от целевого узла, пусть расстояние будет d, теперь мы переходим к другому поддереву (если цель была найдена в левом поддереве, тогда мы идем к правому поддереву и наоборот) предка и находим все узлы. на расстоянии кд от предка.

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

C ++

#include <iostream>

using namespace std;

  
// двоичный узел дерева

struct node

{

    int data;

    struct node *left, *right;

};

  
/ * Рекурсивная функция для печати всех узлов на расстоянии k в

   дерево (или поддерево) имеет корень с заданным корнем. Видеть */

void printkdistanceNodeDown(node *root, int k)

{

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

    if (root == NULL || k < 0)  return;

  

    // Если мы дойдем до дальнего узла, напечатаем его

    if (k==0)

    {

        cout << root->data << endl;

        return;

    }

  

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

    printkdistanceNodeDown(root->left, k-1);

    printkdistanceNodeDown(root->right, k-1);

}

  
// Печатает все узлы на расстоянии k от заданного целевого узла.
// k удаленных узлов могут быть вверх или вниз. Эта функция
// Возвращает расстояние корня от целевого узла, возвращает -1, если цель
// узел не присутствует в дереве с корнем root.

int printkdistanceNode(node* root, node* target , int k)

{

    // Базовый случай 1: если дерево пусто, вернуть -1

    if (root == NULL) return -1;

  

    // Если цель совпадает с root. Используйте нисходящую функцию

    // напечатать все узлы на расстоянии k в поддереве с корнем

    // цель или корень

    if (root == target)

    {

        printkdistanceNodeDown(root, k);

        return 0;

    }

  

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

    int dl = printkdistanceNode(root->left, target, k);

  

    // Проверяем, был ли найден целевой узел в левом поддереве

    if (dl != -1)

    {

         // Если корень находится на расстоянии k от цели, вывести корень

         // Обратите внимание, что dl - это расстояние левого потомка корня от цели

         if (dl + 1 == k)

            cout << root->data << endl;

  

         // В противном случае перейдем к правому поддереву и напечатаем все удаленные узлы k-dl-2

         // Обратите внимание, что правый дочерний элемент находится на расстоянии 2 ребер от левого дочернего элемента

         else

            printkdistanceNodeDown(root->right, k-dl-2);

  

         // Добавляем 1 к расстоянию и возвращаемое значение для родительских вызовов

         return 1 + dl;

    }

  

    // ЗЕРКАЛО ВЫШЕГО КОДА ДЛЯ ПРАВОЙ СУБДРИИ

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

    int dr = printkdistanceNode(root->right, target, k);

    if (dr != -1)

    {

         if (dr + 1 == k)

            cout << root->data << endl;

         else

            printkdistanceNodeDown(root->left, k-dr-2);

         return 1 + dr;

    }

  

    // Если цель не присутствовала ни в левом, ни в правом поддереве

    return -1;

}

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

node *newnode(int data)

{

    node *temp = new node;

    temp->data = data;

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

    return temp;

}

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

int main()

{

    / * Построим дерево, показанное на диаграмме выше * /

    node * root = newnode(20);

    root->left = newnode(8);

    root->right = newnode(22);

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

    root->left->right = newnode(12);

    root->left->right->left = newnode(10);

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

    node * target = root->left->right;

    printkdistanceNode(root, target, 2);

    return 0;

}

Джава

// Java-программа для печати всех узлов на расстоянии k от заданного узла

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

    / * Рекурсивная функция для печати всех узлов на расстоянии k в

       дерево (или поддерево) имеет корень с заданным корнем. * /

   

    void printkdistanceNodeDown(Node node, int k) 

    {

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

        if (node == null || k < 0)

            return;

   

        // Если мы дойдем до дальнего узла, напечатаем его

        if (k == 0

        {

            System.out.print(node.data);

            System.out.println("");

            return;

        }

   

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

        printkdistanceNodeDown(node.left, k - 1);

        printkdistanceNodeDown(node.right, k - 1);

    }

   

    // Печатает все узлы на расстоянии k от заданного целевого узла.

    // k удаленных узлов может быть вверх или вниз. Эта функция

    // Возвращает расстояние корня от целевого узла, возвращает -1

    // если целевой узел отсутствует в дереве с корнем root.

    int printkdistanceNode(Node node, Node target, int k) 

    {

        // Базовый случай 1: если дерево пусто, вернуть -1

        if (node == null)

            return -1;

   

        // Если цель совпадает с root. Используйте нисходящую функцию

        // напечатать все узлы на расстоянии k в поддереве с корнем

        // цель или корень

        if (node == target) 

        {

            printkdistanceNodeDown(node, k);

            return 0;

        }

   

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

        int dl = printkdistanceNode(node.left, target, k);

   

        // Проверяем, был ли найден целевой узел в левом поддереве

        if (dl != -1

        {

               

            // Если корень находится на расстоянии k от цели, вывести корень

            // Обратите внимание, что dl - это Расстояние левого потомка корня от

            // цель

            if (dl + 1 == k) 

            {

                System.out.print(node.data);

                System.out.println("");

            }

               

            // В противном случае перейдем к правому поддереву и напечатаем все удаленные узлы k-dl-2

            // Обратите внимание, что правый дочерний элемент находится на расстоянии 2 ребер от левого дочернего элемента

            else

                printkdistanceNodeDown(node.right, k - dl - 2);

   

            // Добавляем 1 к расстоянию и возвращаемое значение для родительских вызовов

            return 1 + dl;

        }

   

        // ЗЕРКАЛО ВЫШЕГО КОДА ДЛЯ ПРАВОЙ СУБДРИИ

        // Обратите внимание, что мы достигаем здесь только тогда, когда узел не был найден слева

        // поддерево

        int dr = printkdistanceNode(node.right, target, k);

        if (dr != -1

        {

            if (dr + 1 == k) 

            {

                System.out.print(node.data);

                System.out.println("");

            

            else 

                printkdistanceNodeDown(node.left, k - dr - 2);

            return 1 + dr;

        }

   

        // Если цель не присутствовала ни в левом, ни в правом поддереве

        return -1;

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

   

        / * Построим дерево, показанное на диаграмме выше * /

        tree.root = new Node(20);

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

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

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

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

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

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

        Node target = tree.root.left.right;

        tree.printkdistanceNode(tree.root, target, 2);

    }

}

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

питон

# Программа Python для печати узлов на расстоянии k от заданного узла

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

class Node:

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

      
# Рекурсивная функция для печати всех узлов на расстоянии k
# int дерево (или поддерево) с корнем из данного корня. Видеть

def printkDistanceNodeDown(root, k):

      

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

    if root is None or k< 0 :

        return 

      

    # Если мы дойдем до дальнего узла, распечатайте его

    if k == 0 :

        print root.data 

        return 

      

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

    printkDistanceNodeDown(root.left, k-1)

    printkDistanceNodeDown(root.right, k-1)

  

  
# Печатает все узлы на расстоянии k от заданного целевого узла
# K удаленных узлов может быть вверх или вниз. Эта функция
# возвращает расстояние корня от целевого узла, возвращает -1
# если целевой узел отсутствует в дереве с корнем root

def printkDistanceNode(root, target, k):

      

    # Базовый случай 1: если дерево пусто, вернуть -1

    if root is None:

        return -1

  

    # Если цель совпадает с root. Используйте нисходящую функцию

    # распечатать все узлы на расстоянии k в поддереве с корнем

    # цель или корень

    if root == target:

        printkDistanceNodeDown(root, k)

        return 0 

      

    # Recur для левого поддерева

    dl = printkDistanceNode(root.left, target, k)

      

    # Проверить, был ли найден целевой узел в левом поддереве

    if dl != -1:

          

        # Если корень находится на расстоянии k от цели, выведите корень

        # Примечание: dl - расстояние от левого потомка root

        # от цели

        if dl +1 == k :

            print root.data

      

        # Остальное перейдите к нужному поддереву и распечатайте все k-dl-2

        # дальние узлы

        # Примечание: правильный ребенок находится на расстоянии 2 ребер от

        # левый ребенок

        else:

            printkDistanceNodeDown(root.right, k-dl-2)

  

        # Добавить 1 к расстоянию и вернуть значение для

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

        return 1 + dl

  

    # ЗЕРКАЛО ВЫШЕГО КОДА ДЛЯ ПРАВОЙ СУБДРИИ

    # Обратите внимание, что мы достигаем здесь только тогда, когда узел не был найден

    # в левом поддереве

    dr = printkDistanceNode(root.right, target, k)

    if dr != -1:

        if (dr+1 == k):

            print root.data

        else:

            printkDistanceNodeDown(root.left, k-dr-2)

        return 1 + dr

  

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

    return -1

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

root = Node(20)

root.left = Node(8)

root.right = Node(22)

root.left.left = Node(4)

root.left.right = Node(12)

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

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

target = root.left.right

printkDistanceNode(root, target, 2)

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

C #

using System;

  
// C # программа для печати всех узлов на расстоянии k от заданного узла

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

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;

    / * Рекурсивная функция для печати всех узлов на расстоянии k в

       дерево (или поддерево) имеет корень с заданным корнем. * /

  

    public virtual void printkdistanceNodeDown(Node node, int k)

    {

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

        if (node == null || k < 0)

        {

            return;

        }

  

        // Если мы дойдем до дальнего узла, напечатаем его

        if (k == 0)

        {

            Console.Write(node.data);

            Console.WriteLine("");

            return;

        }

  

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

        printkdistanceNodeDown(node.left, k - 1);

        printkdistanceNodeDown(node.right, k - 1);

    }

  

    // Печатает все узлы на расстоянии k от заданного целевого узла.

    // k удаленных узлов может быть вверх или вниз. Эта функция

    // Возвращает расстояние корня от целевого узла, возвращает -1

    // если целевой узел отсутствует в дереве с корнем root.

    public virtual int printkdistanceNode(Node node, Node target, int k)

    {

        // Базовый случай 1: если дерево пусто, вернуть -1

        if (node == null)

        {

            return -1;

        }

  

        // Если цель совпадает с root. Используйте нисходящую функцию

        // напечатать все узлы на расстоянии k в поддереве с корнем

        // цель или корень

        if (node == target)

        {

            printkdistanceNodeDown(node, k);

            return 0;

        }

  

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

        int dl = printkdistanceNode(node.left, target, k);

  

        // Проверяем, был ли найден целевой узел в левом поддереве

        if (dl != -1)

        {

  

            // Если корень находится на расстоянии k от цели, вывести корень

            // Обратите внимание, что dl - это Расстояние левого потомка корня от

            // цель

            if (dl + 1 == k)

            {

                Console.Write(node.data);

                Console.WriteLine("");

            }

  

            // В противном случае перейдем к правому поддереву и напечатаем все удаленные узлы k-dl-2

            // Обратите внимание, что правый дочерний элемент находится на расстоянии 2 ребер от левого дочернего элемента

            else

            {

                printkdistanceNodeDown(node.right, k - dl - 2);

            }

  

            // Добавляем 1 к расстоянию и возвращаемое значение для родительских вызовов

            return 1 + dl;

        }

  

        // ЗЕРКАЛО ВЫШЕГО КОДА ДЛЯ ПРАВОЙ СУБДРИИ

        // Обратите внимание, что мы достигаем здесь только тогда, когда узел не был найден слева

        // поддерево

        int dr = printkdistanceNode(node.right, target, k);

        if (dr != -1)

        {

            if (dr + 1 == k)

            {

                Console.Write(node.data);

                Console.WriteLine("");

            }

            else

            {

                printkdistanceNodeDown(node.left, k - dr - 2);

            }

            return 1 + dr;

        }

  

        // Если цель не присутствовала ни в левом, ни в правом поддереве

        return -1;

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / * Построим дерево, показанное на диаграмме выше * /

        tree.root = new Node(20);

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

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

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

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

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

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

        Node target = tree.root.left.right;

        tree.printkdistanceNode(tree.root, target, 2);

    }

}

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


Выход:

4
20

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

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

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

Вывести все узлы на расстоянии k от данного узла

0.00 (0%) 0 votes