Рубрики

Распечатать ключи BST в заданном диапазоне

Даны два значения k1 и k2 (где k1 <k2) и корневой указатель на дерево двоичного поиска. Выведите все ключи дерева в диапазоне от k1 до k2. т.е. выведите все x так, чтобы k1 <= x <= k2 и x был ключом данного BST. Распечатайте все ключи в порядке возрастания.

Например, если k1 = 10 и k2 = 22, то ваша функция должна вывести 12, 20 и 22.

Идея состоит в том, чтобы использовать обход по порядку, поскольку обход по BST дает ключи в отсортированном порядке.

Алгоритм:
1) Если значение ключа root больше k1, то рекурсивно вызвать в левое поддерево.
2) Если значение ключа root находится в диапазоне, выведите ключ root.
3) Если значение ключа root меньше, чем k2, то рекурсивно вызывается правое поддерево.

Реализация:

C ++

// C ++ программа для печати BST в заданном диапазоне
#include<bits/stdc++.h>

using namespace std; 

  
/ * Древовидная структура * /

class node 

    public:

    int data; 

    node *left; 

    node *right; 

}; 

  
/ * Функции печатают все клавиши
который в заданном диапазоне [k1..k2].

    Функция предполагает, что k1 <k2 * /

void Print(node *root, int k1, int k2) 

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

    if ( NULL == root ) 

        return

      

    / * Так как желаемый o / p отсортирован,

        рекурсировать для левого поддерева

        Если root-> data больше чем k1,

        только тогда мы можем получить ключи o / p

        в левом поддереве * /

    if ( k1 < root->data ) 

        Print(root->left, k1, k2); 

      

    / * если данные root находятся в диапазоне,

    затем печатает данные root * /

    if ( k1 <= root->data && k2 >= root->data ) 

        cout<<root->data<<" "

      

    / * Если root-> data меньше k2,

        только тогда мы можем получить ключи o / p

        в правом поддереве * /

    if ( k2 > root->data ) 

        Print(root->right, k1, k2); 

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

node* newNode(int data) 

    node *temp = new node(); 

    temp->data = data; 

    temp->left = NULL; 

    temp->right = NULL; 

      

    return temp; 

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

int main() 

    node *root = new node(); 

    int k1 = 10, k2 = 25; 

      

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

    на рисунке выше * /

    root = newNode(20); 

    root->left = newNode(8); 

    root->right = newNode(22); 

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

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

      

    Print(root, k1, k2); 

    return 0; 

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

С

#include<stdio.h>

  
/ * Древовидная структура * /

struct node

{

  int data;

  struct node *left;

  struct node *right;

};

  
/ * Функции печатают все клавиши, которые находятся в заданном диапазоне [k1..k2].

    Функция предполагает, что k1 <k2 * /

void Print(struct node *root, int k1, int k2)

{

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

   if ( NULL == root )

      return;

  

   / * Так как желаемый o / p отсортирован, сначала вернемся к левому поддереву

      Если root-> data больше чем k1, то только мы можем получить ключи o / p

      в левом поддереве * /

   if ( k1 < root->data )

     Print(root->left, k1, k2);

  

   / * если данные root находятся в диапазоне, то печатаются данные root * /

   if ( k1 <= root->data && k2 >= root->data )

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

  

  / * Если root-> data меньше, чем k2, то только мы можем получить ключи o / p

      в правом поддереве * /

   if ( k2 > root->data )

     Print(root->right, k1, k2);

}

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

struct node* newNode(int data)

{

  struct node *temp = new struct node;

  temp->data = data;

  temp->left = NULL;

  temp->right = NULL;

  

  return temp;

}

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

int main()

{

  struct node *root = new struct node;

  int k1 = 10, k2 = 25;

  

  / * Построение дерева приведено на рисунке выше * /

  root = newNode(20);

  root->left = newNode(8);

  root->right = newNode(22);

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

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

  

  Print(root, k1, k2);

  

  getchar();

  return 0;

}

Джава

// Java-программа для печати BST в заданном диапазоне

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class BinaryTree {

      

    static Node root;

      

    / * Функции печатают все клавиши, которые находятся в заданном диапазоне [k1..k2].

     Функция предполагает, что k1 <k2 * /

    void Print(Node node, int k1, int k2) {

          

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

        if (node == null) {

            return;

        }

  

        / * Так как желаемый o / p отсортирован, сначала вернемся к левому поддереву

         Если root-> data больше чем k1, то только мы можем получить ключи o / p

         в левом поддереве * /

        if (k1 < node.data) {

            Print(node.left, k1, k2);

        }

  

        / * если данные root находятся в диапазоне, то печатаются данные root * /

        if (k1 <= node.data && k2 >= node.data) {

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

        }

  

        / * Если root-> data меньше, чем k2, то только мы можем получить ключи o / p

         в правом поддереве * /

        if (k2 > node.data) {

            Print(node.right, k1, k2);

        }

    }

      

  

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();

        int k1 = 10, k2 = 25;

        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.Print(root, k1, k2);

    }

}

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

питон

# Программа Python для поиска ключей BST в заданном диапазоне

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Функция печатает все клавиши в диапазоне gicven
# [k1..k2]. Предполагается, что k1 <k2

def Print(root, k1, k2):

      

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

    if root is None:

        return 

  

    # Так как желаемый o / p отсортирован, рекурсивно для левого

    # поддерево первое. Если root.data больше, чем k1, то

    # только мы можем получить o / p ключи в левом поддереве

    if k1 < root.data :

        Print(root.left, k1, k2)

  

    # Если данные root находятся в диапазоне, то печатаются данные root

    if k1 <= root.data and k2 >= root.data:

        print root.data,

  

    # Если root.data меньше, чем k2, то только мы можем получить

    # o / p ключи в правом поддереве

    if k2 > root.data:

        Print(root.right, k1, k2)

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

k1 = 10 ; k2 = 25 ;

root = Node(20)

root.left = Node(8)

root.right = Node(22)

root.left.left = Node(4)

root.left.right = Node(12)

  

Print(root, k1, k2)

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

C #

using System;

  
// C # программа для печати BST в заданном диапазоне

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

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinaryTree

{

  

    public static Node root;

  

    / * Функции печатают все клавиши, которые находятся в заданном диапазоне [k1..k2].

     Функция предполагает, что k1 <k2 * /

    public virtual void Print(Node node, int k1, int k2)

    {

  

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

        if (node == null)

        {

            return;

        }

  

        / * Так как желаемый o / p отсортирован, сначала вернемся к левому поддереву

         Если root-> data больше чем k1, то только мы можем получить ключи o / p

         в левом поддереве * /

        if (k1 < node.data)

        {

            Print(node.left, k1, k2);

        }

  

        / * если данные root находятся в диапазоне, то печатаются данные root * /

        if (k1 <= node.data && k2 >= node.data)

        {

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

        }

  

        / * Если root-> data меньше, чем k2, то только мы можем получить ключи o / p

         в правом поддереве * /

        if (k2 > node.data)

        {

            Print(node.right, k1, k2);

        }

    }

  

  

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        int k1 = 10, k2 = 25;

        BinaryTree.root = new Node(20);

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

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

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

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

  

        tree.Print(root, k1, k2);

    }

}

  

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


Выход:

12 20 22

Сложность времени: O (n), где n — общее количество ключей в дереве.

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

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

Распечатать ключи BST в заданном диапазоне

0.00 (0%) 0 votes