Рубрики

Level Order Преемник узла в двоичном дереве

По заданному двоичному дереву и узлу в двоичном дереве найдите преемника Levelorder данного узла. То есть узел, который появляется после данного узла в порядке обхода уровня дерева.

Примечание . Задача состоит не только в печати данных узла, вы должны вернуть весь узел из дерева.

Примеры :

Consider the following binary tree
              20            
           /      \         
          10       26       
         /  \     /   \     
       4     18  24    27   
            /  \
           14   19
          /  \
         13  15

Levelorder traversal of given tree is:
20, 10, 26, 4, 18, 24, 27, 14, 19, 13, 15

Input : 24
Output : 27

Input : 4
Output : 18

Подход :

  1. Проверьте, является ли корень NULL, то есть дерево пусто. Если true, то вернуть NULL.
  2. Проверьте, является ли данный узел корневым. Если правда:
    • Проверьте, существует ли левый потомок root, если true, верните левого потомка root.
    • Иначе, проверьте, существует ли правильный ребенок, верните его.
    • Если корень является единственным узлом. Вернуть NULL.
  3. В противном случае выполните обход уровня порядка на дереве с помощью очереди.
  4. На каждом шаге обхода порядка уровня проверяйте, совпадает ли текущий узел с данным узлом.
  5. Если True, прекратите обход дальше и верните элемент в верхней части очереди, который будет следующим узлом в обходе порядка уровней.

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

C ++

// Программа CPP для поиска Levelorder
// наследник данного узла в
// Двоичное дерево

  
#include <bits/stdc++.h>

using namespace std;

  
// Tree Node

struct Node {

    struct Node *left, *right;

    int value;

};

  
// Сервисная функция для создания
// новый узел с заданным значением

struct Node* newNode(int value)

{

    Node* temp = new Node;

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

    temp->value = value;

  

    return temp;

}

  
// Функция поиска преемника уровня порядка
// данного узла в двоичном дереве
Node* levelOrderSuccessor(Node* root, Node* key)
{

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

    if (root == NULL)

        return NULL;

  

    // Если корень равен ключу

    if (root == key) {

  

        // Если левый ребенок существует, он будет

        // Преемник

        if (root->left)

            return root->left;

  

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

        // Преемник

        else if (root->right)

            return root->right;

        else

            return NULL; // Нет преемника

    }

  

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

    // обход заказа

    queue<Node*> q;

  

    // ставим в корень

    q.push(root);

  

    while (!q.empty()) {

        Node* nd = q.front();

        q.pop();

  

        if (nd->left != NULL) {

            q.push(nd->left);

        }

  

        if (nd->right != NULL) {

            q.push(nd->right);

        }

  

        if (nd == key)

            break;

    }

  

    return q.front();

}

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

int main()

{

    struct Node* root = newNode(20);

    root->left = newNode(10);

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

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

    root->right = newNode(26);

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

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

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

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

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

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

  

    struct Node* key = root->right->left; // узел 24

  

    struct Node* res = levelOrderSuccessor(root, key);

  

    if (res)

        cout << "LevelOrder successor of "

             << key->value << " is " << res->value;

    else

        cout << "LevelOrder successor of "

             << key->value << " is "  << "NULL";

  

    return 0;

}

Джава

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

import java.util.*;

class GfG {

  
// Tree Node

static class Node { 

    Node left, right; 

    int value; 

}

  
// Сервисная функция для создания
// новый узел с заданным значением

static Node newNode(int value) 

    Node temp = new Node(); 

    temp.left = null;

    temp.right = null

    temp.value = value; 

  

    return temp; 

  
// Функция поиска преемника уровня порядка
// данного узла в двоичном дереве

static Node levelOrderSuccessor(Node root, Node key) 

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

    if (root == null

        return null

  

    // Если корень равен ключу

    if (root == key) { 

  

        // Если левый ребенок существует, он будет

        // Преемник

        if (root.left != null

            return root.left; 

  

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

        // Преемник

        else if (root.right != null

            return root.right; 

        else

            return null; // Нет преемника

    

  

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

    // обход заказа

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

  

    // ставим в корень

    q.add(root); 

  

    while (!q.isEmpty()) { 

        Node nd = q.peek(); 

        q.remove(); 

  

        if (nd.left != null) { 

            q.add(nd.left); 

        

  

        if (nd.right != null) { 

            q.add(nd.right); 

        

  

        if (nd == key) 

            break

    

  

    return q.peek(); 

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

public static void main(String[] args) 

    Node root = newNode(20); 

    root.left = newNode(10); 

    root.left.left = newNode(4); 

    root.left.right = newNode(18); 

    root.right = newNode(26); 

    root.right.left = newNode(24); 

    root.right.right = newNode(27); 

    root.left.right.left = newNode(14); 

    root.left.right.left.left = newNode(13); 

    root.left.right.left.right = newNode(15); 

    root.left.right.right = newNode(19); 

  

    Node key = root.right.left; // узел 24

  
Node res = levelOrderSuccessor(root, key); 

  

    if (res != null

        System.out.println("LevelOrder successor of " 

                        +key.value + " is " + res.value); 

    else

        System.out.println("LevelOrder successor of " 

                            +key.value + " is NULL"); 

  
}

Python 3

# Python3 программа для поиска уровня
# заказ преемника данного узла
# в двоичном дереве

  
# Определение узла

class Node:

      

    def __init__(self, value):

        self.left = None

        self.right = None

        self.value = value

  
# Функция для поиска уровня
# Заказ наследника данного
# Узел в двоичном дереве

def levelOrderSuccessor(root, key):

      

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

    if root == None:

        return None

      

    # Если корень равен ключу

    elif root == key:

          

        # Если левый ребенок существует, он будет

        # быть преемником PostOrder

        if root.left:

            return root.left

              

        # В противном случае, если правильный ребенок существует, это

        # будет преемником PostOrder

        elif root.right:

            return root.right

          

        # Нет преемника

        else:

            return None

              

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

    # уровень порядка обхода

    q = [] 

  

    # Enqueue Root

    q.append(root) 

  

    while len(q) != 0

        nd = q.pop(0

  

        if nd.left != None

            q.append(nd.left)

  

        if nd.right != None

            q.append(nd.right)

      

        if nd == key: 

            break

  

    return q[0]

  
Код водителя

if __name__ == "__main__"

  

    root = Node(20)

    root.left = Node(10)

    root.left.left = Node(4

    root.left.right = Node(18

    root.right = Node(26)

    root.right.left = Node(24

    root.right.right = Node(27

    root.left.right.left = Node(14

    root.left.right.left.left = Node(13

    root.left.right.left.right = Node(15)

    root.left.right.right = Node(19)

  

    key = root.right.left # узел 24

  

    res = levelOrderSuccessor(root, key) 

  

    if res: 

        print("LevelOrder successor of " + 

                 str(key.value) + " is " + 

                 str(res.value)) 

      

    else:

        print("LevelOrder successor of " +

              str(key.value) + " is NULL"

  
# Этот код добавлен
# от Rituraj Jain

C #

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

using System;

using System.Collections.Generic;

  

class GfG 

{

  
// Tree Node

public class Node

    public Node left, right; 

    public int value; 

}

  
// Сервисная функция для создания
// новый узел с заданным значением

static Node newNode(int value) 

    Node temp = new Node(); 

    temp.left = null;

    temp.right = null

    temp.value = value; 

  

    return temp; 

  
// Функция поиска преемника уровня порядка
// данного узла в двоичном дереве

static Node levelOrderSuccessor(Node root, Node key) 

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

    if (root == null

        return null

  

    // Если корень равен ключу

    if (root == key) 

    

  

        // Если левый ребенок существует, он будет

        // Преемник

        if (root.left != null

            return root.left; 

  

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

        // Преемник

        else if (root.right != null

            return root.right; 

        else

            return null; // Нет преемника

    

  

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

    // обход заказа

    LinkedList<Node> q = new LinkedList<Node> (); 

  

    // ставим в корень

    q.AddLast(root); 

  

    while (q.Count != 0) 

    

        Node nd = q.First.Value; 

        q.RemoveFirst(); 

  

        if (nd.left != null)

        

            q.AddLast(nd.left); 

        

  

        if (nd.right != null

        

            q.AddLast(nd.right); 

        

  

        if (nd == key) 

            break

    

  

    return q.First.Value; 

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

public static void Main(String[] args) 

    Node root = newNode(20); 

    root.left = newNode(10); 

    root.left.left = newNode(4); 

    root.left.right = newNode(18); 

    root.right = newNode(26); 

    root.right.left = newNode(24); 

    root.right.right = newNode(27); 

    root.left.right.left = newNode(14); 

    root.left.right.left.left = newNode(13); 

    root.left.right.left.right = newNode(15); 

    root.left.right.right = newNode(19); 

  

    Node key = root.right.left; // узел 24

  

    Node res = levelOrderSuccessor(root, key); 

  

    if (res != null

        Console.WriteLine("LevelOrder successor of "

                        +key.value + " is " + res.value); 

    else

        Console.WriteLine("LevelOrder successor of "

                            +key.value + " is NULL"); 

  
}
}

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

Выход:

LevelOrder successor of 24 is 27

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

Level Order Преемник узла в двоичном дереве

0.00 (0%) 0 votes