Рубрики

Высота бинарного дерева, учитывая только четные уровни

Найдите высоту бинарного дерева, учитывая, что только узлы на четных уровнях считаются действительными конечными узлами.
Высота бинарного дерева — это количество ребер между корнем дерева и его самым дальним листом. Но что, если мы внесем поворот и изменим определение листового узла. Давайте определим действительный конечный узел как узел, который не имеет дочерних элементов и находится на четном уровне (рассматривая корневой узел как узел нечетного уровня).

Вывод: высота дерева 4

Решение: Подход к этой проблеме немного отличается от обычного подхода к определению высоты. На шаге возврата мы проверяем, является ли узел действительным корневым узлом или нет. Если это верно, верните 1, иначе мы вернем 0. Теперь в рекурсивном шаге — если левое и правое поддерево оба дают 0, текущий узел тоже возвращает 0, потому что в этом случае нет пути от текущего узла. к действительному конечному узлу. Но если хотя бы одно из значений, возвращаемых потомками, не равно нулю, это означает, что листовой узел на этом пути является допустимым листовым узлом, и, следовательно, этот путь может внести вклад в конечный результат, поэтому мы возвращаем max значений вернул + 1 для текущего узла.

C ++

/ * Программа для определения высоты дерева с учетом

   уходит только ровный уровень. * /

#include <bits/stdc++.h>

using namespace std;

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

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

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

};

  

int heightOfTreeUtil(Node* root, bool isEven)

{

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

    if (!root)

        return 0;

  

    if (!root->left && !root->right) {

        if (isEven)

            return 1;

        else

            return 0;

    }

  

    / * left сохраняет результат левого поддерева,

      и right сохраняет результат правильного поддерева * /

    int left = heightOfTreeUtil(root->left, !isEven);

    int right = heightOfTreeUtil(root->right, !isEven);

  

    / * Если слева и справа возвращается 0, это означает

      нет правильного пути до конечного узла * /

    if (left == 0 && right == 0)

        return 0;

  

    return (1 + max(left, right));

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct Node* newNode(int data)

{

    struct Node* node = 

              (struct Node*)malloc(sizeof(struct Node));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

  

    return (node);

}

  

int heightOfTree(Node* root)

{

    return heightOfTreeUtil(root, false);

}

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

int main()

{

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

    struct Node* root = newNode(1);

  

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

    cout << "Height of tree is " << heightOfTree(root);

    return 0;

}

Джава

/ * Java-программа для определения высоты дерева с учетом
уходит только ровный уровень. * /

class GfG {

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

static class Node { 

    int data; 

    Node left; 

 Node right; 

}

  

static int heightOfTreeUtil(Node root, boolean isEven) 

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

    if (root == null

        return 0

  

    if (root.left == null && root.right == null) { 

        if (isEven == true

            return 1

        else

            return 0

    

  

    / * left сохраняет результат левого поддерева,

    и right сохраняет результат правильного поддерева * /

    int left = heightOfTreeUtil(root.left, !isEven); 

    int right = heightOfTreeUtil(root.right, !isEven); 

  

    / * Если слева и справа возвращается 0, это означает

    нет правильного пути до конечного узла * /

    if (left == 0 && right == 0

        return 0

  

    return (1 + Math.max(left, right)); 

  
/ * Вспомогательная функция, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = null

    node.right = null

  

    return (node); 

  

static int heightOfTree(Node root) 

    return heightOfTreeUtil(root, false); 

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

public static void main(String[] args) 

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

    Node root = newNode(1); 

  

    root.left = newNode(2); 

    root.right = newNode(3); 

    root.left.left = newNode(4); 

    root.left.right = newNode(5); 

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

    System.out.println("Height of tree is " + heightOfTree(root)); 

}

python3

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

  
# Вспомогательный класс, который выделяет новый узел с
# даны данные и нет левого и правого указателей.

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  

def heightOfTreeUtil(root, isEven):

      

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

    if (not root): 

        return 0

  

    if (not root.left and not root.right): 

        if (isEven): 

            return 1

        else:

            return 0

  

    # left хранит результат левого поддерева,

    # и right хранит результат правильного поддерева

    left = heightOfTreeUtil(root.left, not isEven) 

    right = heightOfTreeUtil(root.right, not isEven) 

  

    # Если и левый, и правый возвращают 0, это означает

    # нет верного пути до конечного узла

    if (left == 0 and right == 0):

        return 0

  

    return (1 + max(left, right))

  

def heightOfTree(root):

    return heightOfTreeUtil(root, False)

  
Код водителя

if __name__ == '__main__'

      

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

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

    root = newNode(1

  

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(4

    root.left.right = newNode(5

    root.left.right.left = newNode(6

    print("Height of tree is",

           heightOfTree(root))

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

C #

/ * C # Программа для определения высоты дерева с учетом
уходит только ровный уровень. * /

using System;

  

class GfG

  

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

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

    class Node

    

        public int data; 

        public Node left; 

        public Node right; 

    

  

    static int heightOfTreeUtil(Node root,

                               bool isEven) 

    

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

        if (root == null

            return 0; 

  

        if (root.left == null && 

            root.right == null)

        

            if (isEven == true

                return 1; 

            else

                return 0; 

        

  

        / * left сохраняет результат левого поддерева,

        и right сохраняет результат правильного поддерева * /

        int left = heightOfTreeUtil(root.left, !isEven); 

        int right = heightOfTreeUtil(root.right, !isEven); 

  

        / * Если слева и справа возвращается 0, это означает

        нет правильного пути до конечного узла * /

        if (left == 0 && right == 0) 

            return 0; 

  

        return (1 + Math.Max(left, right)); 

    

  

    / * Вспомогательная функция, которая выделяет новый узел с

    данные даны и NULL левый и правый указатели. * /

    static Node newNode(int data) 

    

        Node node = new Node(); 

        node.data = data; 

        node.left = null

        node.right = null

  

        return (node); 

    

  

    static int heightOfTree(Node root) 

    

        return heightOfTreeUtil(root, false); 

    

  

    / * Код водителя * /

    public static void Main(String[] args) 

    

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

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

        Node root = newNode(1); 

  

        root.left = newNode(2); 

        root.right = newNode(3); 

        root.left.left = newNode(4); 

        root.left.right = newNode(5); 

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

        Console.WriteLine("Height of tree is " +

                            heightOfTree(root)); 

    

  
/ * Этот код предоставлен Rajput-Ji * /


Выход:

Height of tree is 4

Сложность времени: O (n), где n — количество узлов в данном двоичном дереве.

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

Высота бинарного дерева, учитывая только четные уровни

0.00 (0%) 0 votes