Рубрики

Найти максимальное количество повторяющихся узлов в бинарном дереве поиска

Бинарное дерево поиска, Структуры данных

По заданному бинарному дереву поиска (BST) с дубликатами найдите узел (наиболее часто встречающийся элемент) в данном BST. Если BST содержит два или более таких узлов, выведите любой из них.

Примечание. Мы не можем использовать дополнительное пространство. (Предположим, что неявное пространство стека, возникшее из-за рекурсии, не учитывается)

Предположим, что BST определяется следующим образом:

  • Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу узла.
  • Правое поддерево узла содержит только узлы с ключами, которые больше или равны ключу узла.
  • Левое и правое поддеревья также должны быть деревьями двоичного поиска.

Примеры:

Input :   Given BST is

                    6
                 /    \
                5       7
              /   \    /  \
             4     5  7    7
Output : 7 

Input :  Given BST is
 
                    10
                 /    \
                5       12
              /   \    /  \
             5     6  12    16
Output : 5 or 12 
We can print any of the two value 5 or 12.

Подходить:

Чтобы найти узел, нам нужно найти обход Inorder BST, потому что его обход Inorder будет в отсортированном порядке.

Итак, идея состоит в том, чтобы сделать рекурсивный обход Inorder и отслеживать предыдущий узел. Если текущее значение узла равно предыдущему значению, мы можем увеличить текущий счет, и если текущий счет становится больше, чем максимальный счет, замените элемент.

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

C ++

/ * C ++ программа для поиска медианы BST в O (n)

   время и O (1) пространство * /

  
#include <iostream>

using namespace std;

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

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

  

struct Node {

    int val;

    struct Node *left, *right;

};

  

struct Node* newNode(int data)

{

    struct Node* temp = new Node;

    temp->val = data;

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

    return temp;

}

  
// cur для хранения текущего значения значения
// и mx для максимального количества элементов, которые обозначены узлом

  

int cur = 1, mx = 0;

int node;

struct Node* previous = NULL;

  
// Находим обход по BST

void inorder(struct Node* root)

{

    // Если root равен NULL, вернуть

    if (root == NULL) {

        return;

    }

    inorder(root->left);

    if (previous != NULL) {

        // Если предыдущее значение равно текущему

        // затем увеличиваем количество

        if (root->val == previous->val) {

            cur++;

        }

        // Иначе инициализировать счет на 1

        else {

            cur = 1;

        }

    }

    // Если текущее значение больше максимального

    // затем обновляем значение mx

    if (cur > mx) {

        mx = cur;

        node = root->val;

    }

    // Сделать текущий узел как предыдущий

    previous = root;

    inorder(root->right);

}

  
// Вспомогательная функция

int findnode(struct Node* root)

{

    inorder(root);

    return node;

}

int main()

{

    / * Давайте создадим следующий BST

                   6

                 / /

                5 7

              / / / /

             4 5 7 7

    * /

  

    struct Node* root = newNode(6);

    root->left = newNode(5);

    root->right = newNode(7);

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

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

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

    root->right->right = newNode(7);

  

    cout << "Node of BST is " << findnode(root) << '\n';

    return 0;

}

Джава

/ * Java-программа для поиска медианы BST
в O (n) времени и O (1) пространстве * /

class GFG

{

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

static class Node

{

    int val;

    Node left, right;

};

  

static Node newNode(int data)

{

    Node temp = new Node();

    temp.val = data;

    temp.left = temp.right = null;

    return temp;

}

  
// cur для сохранения текущего счета
// значения и mx для максимального количества
// элемента, который обозначен узлом

static int cur = 1, mx = 0;

static int node;

static Node previous = null;

  
// Находим обход по BST

static void inorder(Node root)

{

    // Если root имеет значение null, вернуть

    if (root == null) 

    {

        return;

    }

    inorder(root.left);

    if (previous != null) 

    {

          

        // Если предыдущее значение равно

        // текущее значение затем увеличить счет

        if (root.val == previous.val) 

        {

            cur++;

        }

          

        // Иначе инициализировать счет на 1

        else 

        {

            cur = 1;

        }

    }

      

    // Если текущее значение больше чем

    // максимальное количество, затем обновляем значение mx

    if (cur > mx) 

    {

        mx = cur;

        node = root.val;

    }

      

    // Сделать текущий узел как предыдущий

    previous = root;

    inorder(root.right);

}

  
// Вспомогательная функция

static int findnode(Node root)

{

    inorder(root);

    return node;

}

  
// Java-код

public static void main(String args[])

{

    / * Давайте создадим следующий BST

                6

                / /

                5 7

            / / / /

            4 5 7 7

    * /

    Node root = newNode(6);

    root.left = newNode(5);

    root.right = newNode(7);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right.left = newNode(7);

    root.right.right = newNode(7);

  

    System.out.println("Node of BST is " + 

                          findnode(root));

}
}

  
// Этот код предоставлен Арнабом Кунду

C #

/ * C # программа для поиска медианы BST
в O (n) времени и O (1) пространстве * /

using System;

      

class GFG

{

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

public class Node

{

    public int val;

    public Node left, right;

};

  

static Node newNode(int data)

{

    Node temp = new Node();

    temp.val = data;

    temp.left = temp.right = null;

    return temp;

}

  
// cur для сохранения текущего счета
// значения и mx для максимального количества
// элемента, который обозначен узлом

static int cur = 1, mx = 0;

static int node;

static Node previous = null;

  
// Находим обход по BST

static void inorder(Node root)

{

    // Если root имеет значение null, вернуть

    if (root == null) 

    {

        return;

    }

    inorder(root.left);

    if (previous != null) 

    {

          

        // Если предыдущее значение равно

        // текущее значение затем увеличить счет

        if (root.val == previous.val) 

        {

            cur++;

        }

          

        // Иначе инициализировать счет на 1

        else

        {

            cur = 1;

        }

    }

      

    // Если текущее значение больше чем

    // максимальное количество, затем обновляем значение mx

    if (cur > mx) 

    {

        mx = cur;

        node = root.val;

    }

      

    // Сделать текущий узел как предыдущий

    previous = root;

    inorder(root.right);

}

  
// Вспомогательная функция

static int findnode(Node root)

{

    inorder(root);

    return node;

}

  
// Код диска

public static void Main(String []args)

{

    / * Давайте создадим следующий BST

                6

                / /

                5 7

            / / / /

            4 5 7 7

    * /

    Node root = newNode(6);

    root.left = newNode(5);

    root.right = newNode(7);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right.left = newNode(7);

    root.right.right = newNode(7);

  

    Console.WriteLine("Node of BST is " + 

                         findnode(root));

}
}

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

Выход:

node of BST is 7

Сложность времени:

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

Найти максимальное количество повторяющихся узлов в бинарном дереве поиска

0.00 (0%) 0 votes