Рубрики

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

Деревья

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

Здесь значение расстояния отличается от предыдущего поста . Здесь k расстояние от листа означает k уровней выше, чем узел листа. Например, если k больше высоты Binary Tree, то ничего не должно быть напечатано. Ожидаемая сложность по времени составляет O (n), где n — количество узлов в данном двоичном дереве.

Идея состоит в том, чтобы пройти через дерево. Продолжайте хранить всех предков, пока мы не достигнем листового узла. Когда мы достигаем листового узла, мы печатаем предка на расстоянии k. Нам также необходимо отслеживать узлы, которые уже напечатаны в качестве выходных данных. Для этого мы используем логический массив с посещением [].

C ++

/ * Программа для печати всех узлов, находящихся на расстоянии k от листа * /
#include <iostream>

using namespace std;

#define MAX_HEIGHT 10000

  

struct Node

{

    int key;

    Node *left, *right;

};

  
/ * утилита, которая выделяет новый узел с данным ключом * /

Node* newNode(int key)

{

    Node* node = new Node;

    node->key = key;

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

    return (node);

}

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

   путь [] -> Хранить предков узла

   visit [] -> Сохраняет значение true, если узел выводится как выходной. Узел может быть k

                 расстояние от многих листьев, мы хотим напечатать его один раз * /

void kDistantFromLeafUtil(Node* node, int path[], bool visited[],

                          int pathLen, int k)

{

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

    if (node==NULL) return;

  

    / * добавить этот узел к массиву путей * /

    path[pathLen] = node->key;

    visited[pathLen] = false;

    pathLen++;

  

    / * это лист, так что печатайте предка только на расстоянии k

       если предок еще не напечатан * /

    if (node->left == NULL && node->right == NULL &&

        pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)

    {

        cout << path[pathLen-k-1] << " ";

        visited[pathLen-k-1] = true;

        return;

    }

  

    / * Если не листовой узел, повторить для левого и правого поддеревьев * /

    kDistantFromLeafUtil(node->left, path, visited, pathLen, k);

    kDistantFromLeafUtil(node->right, path, visited, pathLen, k);

}

  
/ * Учитывая двоичное дерево и число k, выведите все узлы, которые k

   далекий от листа * /

void printKDistantfromLeaf(Node* node, int k)

{

    int path[MAX_HEIGHT];

    bool visited[MAX_HEIGHT] = {false};

    kDistantFromLeafUtil(node, path, visited, 0, k);

}

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

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 << "Nodes at distance 2 are: ";

    printKDistantfromLeaf(root, 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 от конечного узла

     путь [] -> Хранить предков узла

     visit [] -> Сохраняет значение true, если узел выводится как выходной. Узел может

     быть на расстоянии от многих листьев, мы хотим напечатать его один раз * /

    void kDistantFromLeafUtil(Node node, int path[], boolean visited[],

                              int pathLen, int k)

    {

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

        if (node == null)

            return;

   

        / * добавить этот узел к массиву путей * /

        path[pathLen] = node.data;

        visited[pathLen] = false;

        pathLen++;

   

        / * это лист, так что печатайте предка только на расстоянии k

         если предок еще не напечатан * /

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

           && pathLen - k - 1 >= 0 && visited[pathLen - k - 1] == false)

        {

            System.out.print(path[pathLen - k - 1] + " ");

            visited[pathLen - k - 1] = true;

            return;

        }

   

        / * Если не листовой узел, повторить для левого и правого поддеревьев * /

        kDistantFromLeafUtil(node.left, path, visited, pathLen, k);

        kDistantFromLeafUtil(node.right, path, visited, pathLen, k);

    }

   

    / * Учитывая двоичное дерево и число k, выведите все узлы, которые k

     далекий от листа * /

    void printKDistantfromLeaf(Node node, int k)

    {

        int path[] = new int[1000];

        boolean visited[] = new boolean[1000];

        kDistantFromLeafUtil(node, path, visited, 0, k);

    }

   

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

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

   

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

        tree.root = new Node(1);

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

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

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

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

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

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

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

   

        System.out.println(" Nodes at distance 2 are :");

        tree.printKDistantfromLeaf(tree.root, 2);

    }

}

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

python3

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

  
# утилита, которая выделяет новый узел с
# данный ключ

class newNode:

    def __init__(self, key):

        self.key = key 

        self.left = self.right = None

  
# Эта функция печатает все узлы, которые
# расстояние k от листового узла
# путь[] -. Хранить предков узла
# посетил [] -. Хранит истину, если узел
# печатается как вывод. Узел может быть k расстояние
# от многих листьев, мы хотим напечатать его один раз

def kDistantFromLeafUtil(node, path, visited, 

                                 pathLen, k):

      

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

    if (node == None):

        return

  

    # добавить этот узел в массив пути

    path[pathLen] = node.key 

    visited[pathLen] = False

    pathLen += 1

  

    # это лист, так что напечатайте предка в

    # расстояние k, только если предок

    # еще не напечатано

    if (node.left == None and node.right == None and 

                            pathLen - k - 1 >= 0 and 

                            visited[pathLen - k - 1] == False):

        print(path[pathLen - k - 1], end = " ") 

        visited[pathLen - k - 1] = True

        return

  

    # Если не листовой узел, повторить для левого

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

    kDistantFromLeafUtil(node.left, path, 

                         visited, pathLen, k)

    kDistantFromLeafUtil(node.right, path, 

                         visited, pathLen, k)

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

def printKDistantfromLeaf(node, k):

    global MAX_HEIGHT

    path = [None] * MAX_HEIGHT 

    visited = [False] * MAX_HEIGHT

    kDistantFromLeafUtil(node, path, visited, 0, k)

  
Код водителя

MAX_HEIGHT = 10000

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

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) 

  

print("Nodes at distance 2 are:", end = " ") 

printKDistantfromLeaf(root, 2)

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

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 от конечного узла

     путь [] -> Хранить предков узла

     visit [] -> Сохраняет значение true, если узел выводится как выходной. Узел может

     быть на расстоянии от многих листьев, мы хотим напечатать его один раз * /

    public virtual void kDistantFromLeafUtil(Node node, int[] path, bool[] visited, int pathLen, int k)

    {

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

        if (node == null)

        {

            return;

        }

  

        / * добавить этот узел к массиву путей * /

        path[pathLen] = node.data;

        visited[pathLen] = false;

        pathLen++;

  

        / * это лист, так что печатайте предка только на расстоянии k

         если предок еще не напечатан * /

        if (node.left == null && node.right == null && pathLen - k - 1 >= 0 && visited[pathLen - k - 1] == false)

        {

            Console.Write(path[pathLen - k - 1] + " ");

            visited[pathLen - k - 1] = true;

            return;

        }

  

        / * Если не листовой узел, повторить для левого и правого поддеревьев * /

        kDistantFromLeafUtil(node.left, path, visited, pathLen, k);

        kDistantFromLeafUtil(node.right, path, visited, pathLen, k);

    }

  

    / * Учитывая двоичное дерево и число k, выведите все узлы, которые k

     далекий от листа * /

    public virtual void printKDistantfromLeaf(Node node, int k)

    {

        int[] path = new int[1000];

        bool[] visited = new bool[1000];

        kDistantFromLeafUtil(node, path, visited, 0, k);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

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

        tree.root = new Node(1);

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

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

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

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

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

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

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

  

        Console.WriteLine(" Nodes at distance 2 are :");

        tree.printKDistantfromLeaf(tree.root, 2);

    }

}

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


Выход:

Nodes at distance 2 are: 1 3

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

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

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

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

0.00 (0%) 0 votes