Рубрики

Найти следующий правый узел данного ключа

По заданному двоичному дереву и ключу в двоичном дереве найдите узел справа от заданного ключа. Если на правой стороне нет узла, верните NULL. Ожидаемая сложность по времени составляет O (n), где n — количество узлов в данном двоичном дереве.

Например, рассмотрим следующее двоичное дерево. Выход для 2 — 6, выход для 4 — 5. Выход для 10, 6 и 5 — NULL.

                  10
               /      \
          2         6
           /   \         \ 
     8      4          5

Решение: Идея состоит в том, чтобы сделать обход уровня заданного двоичного дерева. Когда мы находим данный ключ, мы просто проверяем, находится ли следующий узел в обходе уровня на том же уровне, если да, мы возвращаем следующий узел, в противном случае возвращаем NULL.

C ++

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

using namespace std;

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

struct node

{

    struct node *left, *right;

    int key;

};

  
// Метод, чтобы найти следующее право данного ключа k, он возвращает NULL, если k
// отсутствует в дереве или k является самым правым узлом его уровня

node* nextRight(node *root, int k)

{

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

    if (root == NULL)

        return 0;

  

    // Создаем пустую очередь для прохождения уровня заказа

    queue<node *> qn; // Очередь для хранения адресов узлов

    queue<int> ql;   // Очередь для хранения уровней узлов

  

    int level = 0;  // Инициализируем уровень как 0

  

    // ставим в очередь Root и его уровень

    qn.push(root);

    ql.push(level);

  

    // Стандартный цикл BFS

    while (qn.size())

    {

        // удаляем узел из qn и его уровень из ql

        node *node = qn.front();

        level = ql.front();

        qn.pop();

        ql.pop();

  

        // Если у удаленного узла есть заданный ключ k

        if (node->key == k)

        {

            // Если в очереди больше нет элементов или данный узел

            // самый правый узел своего уровня, затем возвращаем NULL

            if (ql.size() == 0 || ql.front() != level)

               return NULL;

  

            // Иначе вернем следующий узел из очереди узлов

            return qn.front();

        }

  

        // Стандартные шаги BFS: поставить в очередь дочерние элементы этого узла

        if (node->left != NULL)

        {

            qn.push(node->left);

            ql.push(level+1);

        }

        if (node->right != NULL)

        {

            qn.push(node->right);

            ql.push(level+1);

        }

    }

  

    // Мы достигаем здесь, если данный ключ x не существует в дереве

    return NULL;

}

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

node* newNode(int key)

{

    node *temp = new node;

    temp->key = key;

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

    return temp;

}

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

void test(node *root, int k)

{

    node *nr = nextRight(root, k);

    if (nr != NULL)

      cout << "Next Right of " << k << " is " << nr->key << endl;

    else

      cout << "No next right node found for " << k << endl;

}

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

int main()

{

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

    node *root = newNode(10);

    root->left = newNode(2);

    root->right = newNode(6);

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

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

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

  

    test(root, 10);

    test(root, 2);

    test(root, 6);

    test(root, 5);

    test(root, 8);

    test(root, 4);

    return 0;

}

Джава

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

   

import java.util.LinkedList;

import java.util.Queue;

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Метод, чтобы найти следующее право данного ключа k, он возвращает NULL, если k

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

    Node nextRight(Node first, int k) 

    {

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

        if (first == null)

            return null;

   

        // Создаем пустую очередь для прохождения уровня заказа

        // Очередь для хранения адресов узлов

        Queue<Node> qn = new LinkedList<Node>(); 

          

        // Очередь для хранения уровней узлов

        Queue<Integer> ql = new LinkedList<Integer>();   

   

        int level = 0// Инициализируем уровень как 0

   

        // ставим в очередь Root и его уровень

        qn.add(first);

        ql.add(level);

   

        // Стандартный цикл BFS

        while (qn.size() != 0

        {

            // удаляем узел из qn и его уровень из ql

            Node node = qn.peek();

            level = ql.peek();

            qn.remove();

            ql.remove();

   

            // Если у удаленного узла есть заданный ключ k

            if (node.data == k) 

            {

                // Если в очереди больше нет элементов или данный узел

                // самый правый узел своего уровня, затем возвращаем NULL

                if (ql.size() == 0 || ql.peek() != level)

                    return null;

   

                // Иначе вернем следующий узел из очереди узлов

                return qn.peek();

            }

   

            // Стандартные шаги BFS: поставить в очередь дочерние элементы этого узла

            if (node.left != null

            {

                qn.add(node.left);

                ql.add(level + 1);

            }

            if (node.right != null

            {

                qn.add(node.right);

                ql.add(level + 1);

            }

        }

   

        // Мы достигаем здесь, если данный ключ x не существует в дереве

        return null;

    }

   

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

    void test(Node node, int k) 

    {

        Node nr = nextRight(root, k);

        if (nr != null)

            System.out.println("Next Right of " + k + " is " + nr.data);

        else

            System.out.println("No next right node found for " + k);

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

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

   

        tree.test(tree.root, 10);

        tree.test(tree.root, 2);

        tree.test(tree.root, 6);

        tree.test(tree.root, 5);

        tree.test(tree.root, 8);

        tree.test(tree.root, 4);

   

    }

}

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

питон

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

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

class Node:

      

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

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

      
# Метод, чтобы найти следующее право данного ключа k, он возвращает
# Нет, если k отсутствует в дереве или k является самым правым
# узел его уровня

def nextRight(root, k):

  

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

    if root is None:

        return 0 

  

    # Создать пустую очередь для прохождения порядка уровней

    qn =  [] # Очередь для хранения адресов узлов

    q1 = [] # Очередь для хранения уровней узлов

  

    level = 0

  

    # Ставить корень в очередь и его уровень

    qn.append(root)

    q1.append(level)

  

    # Стандартный цикл BFS

    while(len(qn) > 0):

  

        # Удаление узла из qn и его уровня из q1

        node = qn.pop(0)

        level = q1.pop(0)

  

        # Если у удаленного узла есть заданный ключ k

        if node.key == k :

  

            # Если в очереди или задании больше нет элементов

            # узел - самый правый узел своего уровня,

            # затем вернуть None

            if (len(q1) == 0 or q1[0] != level):

                return None

  

            # В противном случае вернуть следующий узел из очереди узлов

            return qn[0]

  

        # Стандартные шаги BFS: поставить в очередь дочерние элементы этого узла

        if node.left is not None:

            qn.append(node.left)

            q1.append(level+1)

  

        if node.right is not None:

            qn.append(node.right)

            q1.append(level+1)

  

    # Мы достигаем здесь, если данный ключ х не существует в дереве

    return None

  

def test(root, k):

    nr = nextRight(root, k)

    if nr is not None:

        print "Next Right of " + str(k) + " is " + str(nr.key)

    else:

        print "No next right node found for " + str(k)

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

root = Node(10)

root.left = Node(2)

root.right = Node(6)

root.right.right = Node(5)

root.left.left = Node(8)

root.left.right = Node(4)

  

test(root, 10)

test(root, 2)

test(root, 6)

test(root, 5)

test(root, 8)

test(root, 4)

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

C #

// C # программа для поиска следующего справа от заданного ключа

using System;

using System.Collections.Generic;

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

public class Node 

    public int data; 

    public Node left, right; 

  

    public Node(int item) 

    

        data = item; 

        left = right = null

    

  

public class BinaryTree 

    Node root; 

  

    // Метод, чтобы найти следующий справа от данного

    // клавиша k возвращает NULL, если k

    // отсутствует в дереве или k является

    // самый правый узел его уровня

    Node nextRight(Node first, int k) 

    

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

        if (first == null

            return null

  

        // Создать пустую очередь для

        // уровень заказа tarversal

        // Очередь для хранения адресов узлов

        Queue<Node> qn = new Queue<Node>(); 

          

        // Очередь для хранения уровней узлов

        Queue<int> ql = new Queue<int>(); 

  

        int level = 0; // Инициализируем уровень как 0

  

        // ставим в очередь Root и его уровень

        qn.Enqueue(first); 

        ql.Enqueue(level); 

  

        // Стандартный цикл BFS

        while (qn.Count != 0) 

        

            // снимаем узел с узла

            // qn и его уровень от ql

            Node node = qn.Peek(); 

            level = ql.Peek(); 

            qn.Dequeue(); 

            ql.Dequeue(); 

  

            // Если у удаленного узла есть заданный ключ k

            if (node.data == k) 

            

                // если больше нет товаров

                // в очереди или заданном узле

                // самый правый узел его

                // уровень, затем возвращаем NULL

                if (ql.Count == 0 || ql.Peek() != level) 

                    return null

  

                // Иначе вернемся дальше

                // узел из очереди узлов

                return qn.Peek(); 

            

  

            // Стандартные шаги BFS: enqueue

            // дети этого узла

            if (node.left != null

            

                qn.Enqueue(node.left); 

                ql.Enqueue(level + 1); 

            

            if (node.right != null

            

                qn.Enqueue(node.right); 

                ql.Enqueue(level + 1); 

            

        

  

        // Мы достигаем здесь, если дано

        // ключ x не существует в дереве

        return null

    

  

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

    void test(Node node, int k) 

    

        Node nr = nextRight(root, k); 

        if (nr != null

            Console.WriteLine("Next Right of "

                        k + " is " + nr.data); 

        else

            Console.WriteLine("No next right node found for " + k); 

    

  

    // Код драйвера

    public static void Main(String []args) 

    

        BinaryTree tree = new BinaryTree(); 

        tree.root = new Node(10); 

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

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

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

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

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

  

        tree.test(tree.root, 10); 

        tree.test(tree.root, 2); 

        tree.test(tree.root, 6); 

        tree.test(tree.root, 5); 

        tree.test(tree.root, 8); 

        tree.test(tree.root, 4); 

    

  
// Этот код был добавлен
// от 29AjayKumar


Выход:

No next right node found for 10
Next Right of 2 is 6
No next right node found for 6
No next right node found for 5
Next Right of 8 is 4
Next Right of 4 is 5

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

Упражнение: Напишите функцию для поиска левого узла данного узла. Если на левой стороне нет узла, верните NULL.

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

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

Найти следующий правый узел данного ключа

0.00 (0%) 0 votes