Рубрики

Получить максимальный левый узел в двоичном дереве

Для данного дерева задача состоит в том, чтобы найти максимум в единственном левом узле двоичного дерева.

Примеры:

Input : 
           7
         /    \
        6       5
       / \     / \
      4  3     2  1 
Output :
6

Input :
            1
         /    \
        2       3
       /       / \
      4       5   6
        \    /  \ 
         7  8   9 
Output :
8

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

C ++

// Программа CPP для печати максимального элемента
// в левом узле.
#include <bits/stdc++.h>

using namespace std;

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

struct Node {

    int data;

    struct Node *left, *right;

};

  
// Получить максимум левого элемента, используя
// обход обхода

int maxOfLeftElement(Node* root)

{

    int res = INT_MIN;

    if (root == NULL)

        return res;

  

    if (root->left != NULL)

        res = root->left->data;

  

    // Вернуть максимум три значения

    // 1) Рекурсивный максимум в левом поддереве

    // 2) Значение в левом узле

    // 3) Рекурсивный максимум в правом поддереве

    return max({ maxOfLeftElement(root->left),

                 res,

                 maxOfLeftElement(root->right) });

}

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

Node* newNode(int data)

{

    Node* temp = new Node;

    temp->data = data;

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

    return temp;

}

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

int main()

{

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

    Node* root = newNode(7);

    root->left = newNode(6);

    root->right = newNode(5);

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

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

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

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

  

    / * 7

         / /

        6 5

       / / / /

      4 3 2 1 * /

    cout << maxOfLeftElement(root);

    return 0;

}

Джава

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

import java.util.*;

class GfG {

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

static class Node { 

    int data; 

    Node left, right; 

}

  
// Получить максимум левого элемента, используя
// обход обхода

static int maxOfLeftElement(Node root) 

    int res = Integer.MIN_VALUE; 

    if (root == null

        return res; 

  

    if (root.left != null

        res = root.left.data; 

  

    // Вернуть максимум три значения

    // 1) Рекурсивный максимум в левом поддереве

    // 2) Значение в левом узле

    // 3) Рекурсивный максимум в правом поддереве

    return Math.max(maxOfLeftElement(root.left),

       Math.max(res, maxOfLeftElement(root.right))); 

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

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.left = null;

    temp.right = null

    return temp; 

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

public static void main(String[] args) 

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

    Node root = newNode(7); 

    root.left = newNode(6); 

    root.right = newNode(5); 

    root.left.left = newNode(4); 

    root.left.right = newNode(3); 

    root.right.left = newNode(2); 

    root.right.right = newNode(1); 

  

    / * 7

        / /

        6 5

    / / / /

    4 3 2 1 * /

    System.out.println(maxOfLeftElement(root)); 

}

python3

# Программа Python для элемента prmaximum
# в левом узле.

  
# Утилита класса для создания
# новый узел дерева

class newNode:

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

      
# Получить максимум левого элемента, используя
# Inorder обход

def maxOfLeftElement(root):

    res = -999999999999

    if (root == None):

        return res 

  

    if (root.left != None): 

        res = root.left.data 

  

    # Вернуть максимум три значения

    # 1) Рекурсивный максимум в левом поддереве

    # 2) Значение в левом узле

    # 3) Рекурсивный максимум в правом поддереве

    return max({ maxOfLeftElement(root.left), res,

                 maxOfLeftElement(root.right) })

  
Код водителя

if __name__ == '__main__':

  

    # Давайте создадим двоичное дерево, показанное

    # на диаграмме выше

    root = newNode(7

    root.left = newNode(6

    root.right = newNode(5

    root.left.left = newNode(4

    root.left.right = newNode(3

    root.right.left = newNode(2

    root.right.right = newNode(1

  

    № 7

    # / /

    № 6 5

    # / / / /

    # 4 3 2 1

    print(maxOfLeftElement(root))

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

C #

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

using System;

  

class GfG 

{

  

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

    class Node 

    

        public int data; 

        public Node left, right; 

    }

  

    // Получить максимум левого элемента, используя

    // обход обхода

    static int maxOfLeftElement(Node root) 

    

        int res = int.MinValue; 

        if (root == null

            return res; 

  

        if (root.left != null

            res = root.left.data; 

  

        // Вернуть максимум три значения

        // 1) Рекурсивный максимум в левом поддереве

        // 2) Значение в левом узле

        // 3) Рекурсивный максимум в правом поддереве

        return Math.Max(maxOfLeftElement(root.left),

        Math.Max(res, maxOfLeftElement(root.right))); 

    

  

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

    static Node newNode(int data) 

    

        Node temp = new Node(); 

        temp.data = data; 

        temp.left = null;

        temp.right = null

        return temp; 

    

  

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

    public static void Main(String[] args) 

    

        // Давайте создадим бинарное дерево

        // показано на диаграмме выше

        Node root = newNode(7); 

        root.left = newNode(6); 

        root.right = newNode(5); 

        root.left.left = newNode(4); 

        root.left.right = newNode(3); 

        root.right.left = newNode(2); 

        root.right.right = newNode(1); 

  

        / * 7

            / /

            6 5

        / / / /

        4 3 2 1 * /

        Console.WriteLine(maxOfLeftElement(root)); 

    }

}

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

Выход:

6

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

Получить максимальный левый узел в двоичном дереве

0.00 (0%) 0 votes