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

#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)

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