Рубрики

Печать узлов на расстоянии k от корня

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

Например, в приведенном ниже дереве 4, 5 и 8 находятся на расстоянии 2 от корня.

            1
          /   \
        2      3
      /  \    /
    4     5  8 

Проблема может быть решена с помощью рекурсии. Спасибо Eldho за предложение решения.

C ++

#include<bits/stdc++.h> 
#include<iostream>

using namespace std;

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

class node 

    public:

    int data; 

    node* left; 

    node* right; 

      

    / * Конструктор, который выделяет новый узел с

    данные даны и NULL левый и правый указатели. * /

    node(int data)

    {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

    }

}; 

  

void printKDistant(node *root , int k) 

    if(root == NULL) 

        return

    if( k == 0 ) 

    

        cout << root->data << " "

        return

    

    else

    

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

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

    

  

  
/ * Код водителя * /

int main() 

  

    / * Построенное двоичное дерево

            1

            / /

        2 3

        ///

        4 5 8

    * /

    node *root = new node(1); 

    root->left = new node(2); 

    root->right = new node(3); 

    root->left->left = new node(4); 

    root->left->right = new node(5); 

    root->right->left = new node(8); 

      

    printKDistant(root, 2); 

    return 0; 

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

С

#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node

{

   int data;

   struct node* left;

   struct node* right;

};

  

void printKDistant(struct node *root , int k)    

{

   if(root == NULL) 

      return;

   if( k == 0 )

   {

      printf( "%d ", root->data );

      return ;

   }

   else

   {      

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

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

   }

}

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

   данные даны и NULL левый и правый указатели. * /

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  

  return(node);

}

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

int main()

{

  

  / * Построенное двоичное дерево

            1

          / /

        2 3

      ///

    4 5 8

  * /

  struct 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(8);  

  

  printKDistant(root, 2);

  

  getchar();

  return 0;

}

Джава

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

   
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    void printKDistant(Node node, int k) 

    {

        if (node == null)

            return;

        if (k == 0

        {

            System.out.print(node.data + " ");

            return;

        

        else 

        {

            printKDistant(node.left, k - 1);

            printKDistant(node.right, k - 1);

        }

    }

      

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

    public static void main(String args[]) {

        BinaryTree tree = new BinaryTree();

          

        / * Построенное двоичное дерево

                1

              / /

             2 3

            ///

           4 5 8

        * /

        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(8);

   

        tree.printKDistant(tree.root, 2);

    }

}

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

питон

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

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

class Node:

      

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  

def printKDistant(root, k):

      

    if root is None:

        return 

    if k == 0:

        print root.data,

    else:

        printKDistant(root.left, k-1)

        printKDistant(root.right, k-1)

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

   Построенное двоичное дерево

            1

          / /

        2 3

      ///

    4 5 8

«»»

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.left = Node(8)

  

printKDistant(root, 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;

  

    public virtual void printKDistant(Node node, int k)

    {

        if (node == null)

        {

            return;

        }

        if (k == 0)

        {

            Console.Write(node.data + " ");

            return;

        }

        else

        {

            printKDistant(node.left, k - 1);

            printKDistant(node.right, k - 1);

        }

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / * Построенное двоичное дерево

                1

              / /

             2 3

            ///

           4 5 8

        * /

        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(8);

  

        tree.printKDistant(tree.root, 2);

    }

}

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


Выход:

4 5 8 

Сложность времени: O (n), где n — количество узлов в данном двоичном дереве.

Пожалуйста, пишите комментарии, если вы обнаружите, что приведенный выше код / алгоритм неверен, или найдете лучшие способы решения той же проблемы.

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

Печать узлов на расстоянии k от корня

0.00 (0%) 0 votes