Рубрики

Предшественник уровня порядка узла в двоичном дереве

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

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

Примеры :

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 : 19
Output : 14

Input : 4
Output : 26

Подход :

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

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

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* levelOrderPredecessor(Node* root, Node* key)
{

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

    if (root == NULL)

        return NULL;

  

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

    if (root == key) {

  

        // Предшественника нет

        // корневой узел

        return NULL;

    }

  

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

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

    queue<Node*> q;

  

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

    q.push(root);

  

    // Временный узел для отслеживания

    // последний узел

    Node* prev = NULL;

  

    while (!q.empty()) {

        Node* nd = q.front();

        q.pop();

  

        if (nd == key)

            break;

        else

            prev = nd;

  

        if (nd->left != NULL) {

            q.push(nd->left);

        }

  

        if (nd->right != NULL) {

            q.push(nd->right);

        }

    }

  

    return prev;

}

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

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->left->right->right;

  

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

  

    if (res)

        cout << "LevelOrder Predecessor of " << key->value

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

    else

        cout << "LevelOrder Predecessor 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 levelOrderPredecessor(Node root, Node key) 

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

    if (root == null

        return null

  

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

    if (root == key) { 

  

        // Предшественника нет

        // корневой узел

        return null

    

  

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

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

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

  

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

    q.add(root); 

  

    // Временный узел для отслеживания

    // последний узел

    Node prev = null

  

    while (!q.isEmpty()) { 

        Node nd = q.peek(); 

        q.remove(); 

  

        if (nd == key) 

            break

        else

            prev = nd; 

  

        if (nd.left != null) { 

            q.add(nd.left); 

        

  

        if (nd.right != null) { 

            q.add(nd.right); 

        

    

  

    return prev; 

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

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.left.right.right; 

  

    Node res = levelOrderPredecessor(root, key); 

  

    if (res != null

        System.out.println("LevelOrder Predecessor of " + key.value + " is " + res.value); 

    else

        System.out.println("LevelOrder Predecessor of " + key.value+ " is null"); 

  
}

python3

"" "Программа Python3 для поиска порядка уровней
Предшественник данного узла в
Двоичное дерево "" "

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

class newNode: 

  

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

    def __init__(self, data): 

        self.value = data 

        self.left = None

        self.right = self.parent = None

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

def levelOrderPredecessor(root, key) :

  

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

    if (root == None) :

        return None

  

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

    if (root == key):

          

        # Нет предшественника

        # корневой узел

        return None

      

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

    # обход заказа

    q = [] 

  

    # Enqueue Root

    q.append(root) 

  

    # Временный узел для отслеживания

    № последнего узла

    prev = None

  

    while (len(q)):

        nd = q[0

        q.pop(0

  

        if (nd == key) :

            break

        else:

            prev = nd 

  

        if (nd.left != None):

            q.append(nd.left) 

          

        if (nd.right != None): 

            q.append(nd.right) 

    return prev

  
Код водителя

if __name__ == '__main__':

  

    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

  

    key = root.left.right.right 

  

    res = levelOrderPredecessor(root, key) 

  

    if (res) :

        print("LevelOrder Predecessor of"

               key.value, "is", res.value)

    else:

        print("LevelOrder Predecessor of",

                  key.value, "is", "None")

  
# Этот код предоставлен
# SHUBHAMSINGH10

C #

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

using System;

using System.Collections.Generic;

  

class GfG

  

    // Tree Node

    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 levelOrderPredecessor(Node root, Node key) 

    

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

        if (root == null

            return null

  

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

        if (root == key) 

        

  

            // Предшественника нет

            // корневой узел

            return null

        

  

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

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

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

  

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

        q.Enqueue(root); 

  

        // Временный узел для отслеживания

        // последний узел

        Node prev = null

  

        while (q.Count!=0) 

        

            Node nd = q.Peek(); 

            q.Dequeue(); 

  

            if (nd == key) 

                break

            else

                prev = nd; 

  

            if (nd.left != null

            

                q.Enqueue(nd.left); 

            

  

            if (nd.right != null

            

                q.Enqueue(nd.right); 

            

        

  

        return prev; 

    

  

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

    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.left.right.right; 

  

        Node res = levelOrderPredecessor(root, key); 

  

        if (res != null

            Console.WriteLine("LevelOrder Predecessor of " +

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

        else

            Console.WriteLine("LevelOrder Predecessor of " +

                                key.value+ " is null"); 

    }

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

Выход:

LevelOrder Predecessor of 19 is 14

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

Предшественник уровня порядка узла в двоичном дереве

0.00 (0%) 0 votes