Рубрики

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

Имея двоичное дерево и ключ, напишите функцию, которая возвращает уровень ключа.

Например, рассмотрим следующее дерево. Если клавиша ввода — 3, то ваша функция должна вернуть 1. Если клавиша ввода равна 4, то ваша функция должна возвращать 3. А для клавиши, которой нет в клавише, ваша функция должна возвращать 0.

Идея состоит в том, чтобы начать с корня и уровня как 1. Если ключ совпадает с данными корня, вернуть уровень. Иначе рекурсивно вызовите левое и правое поддеревья с уровнем как уровень + 1.

C ++

// C ++ программа для получения уровня
// узел в двоичном дереве
#include<bits/stdc++.h>

using namespace std;

  
/ * Древовидная структура * /

struct node

{

    int data;

    struct node *left;

    struct node *right;

};

  
/ * Вспомогательная функция для getLevel ().
Возвращает уровень данных, если данные
присутствует в дереве, в противном случае возвращает 0. * /

int getLevelUtil(struct node *node, 

                 int data, int level)

{

    if (node == NULL)

        return 0;

  

    if (node -> data == data)

        return level;

  

    int downlevel = getLevelUtil(node -> left, 

                                 data, level + 1);

    if (downlevel != 0)

        return downlevel;

  

    downlevel = getLevelUtil(node->right, 

                             data, level + 1);

    return downlevel;

}

  
/ * Возвращает уровень заданного значения данных * /

int getLevel(struct node *node, int data)

{

    return getLevelUtil(node, data, 1);

}

  
/ * Утилита для создания
новый узел двоичного дерева * /

struct node* newNode(int data)

{

    struct node *temp = new struct node;

    temp -> data = data;

    temp -> left = NULL;

    temp -> right = NULL;

  

    return temp;

}

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

int main()

{

    struct node *root = new struct node;

    int x;

  

    / * Построение дерева дано в

    приведенная выше цифра *

    root = newNode(3);

    root->left = newNode(2);

    root->right = newNode(5);

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

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

  

    for (x = 1; x <= 5; x++)

    {

        int level = getLevel(root, x);

        if (level)

            cout << "Level of "<< x << " is "

                 << getLevel(root, x) << endl;

        else

            cout << x << "is not present in tree"

                      << endl;

    }

  

    getchar();

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

#include<stdio.h>
// C программа для получения уровня узла в двоичном дереве
/ * Древовидная структура * /

struct node

{

    int data;

    struct node *left;

    struct node *right;

};

  
/ * Вспомогательная функция для getLevel (). Возвращает уровень данных, если данные

   присутствует в дереве, в противном случае возвращает 0. * /

int getLevelUtil(struct node *node, int data, int level)

{

    if (node == NULL)

        return 0;

  

    if (node->data == data)

        return level;

  

    int downlevel = getLevelUtil(node->left, data, level+1);

    if (downlevel != 0)

        return downlevel;

  

    downlevel = getLevelUtil(node->right, data, level+1);

    return downlevel;

}

  
/ * Возвращает уровень заданного значения данных * /

int getLevel(struct node *node, int data)

{

    return getLevelUtil(node,data,1);

}

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

struct node* newNode(int data)

{

    struct node *temp = new struct node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

  

    return temp;

}

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

int main()

{

    struct node *root = new struct node;

    int x;

  

    / * Построение дерева приведено на рисунке выше * /

    root = newNode(3);

    root->left = newNode(2);

    root->right = newNode(5);

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

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

  

    for (x = 1; x <=5; x++)

    {

      int level = getLevel(root, x);

      if (level)

        printf(" Level of %d is %d\n", x, getLevel(root, x));

      else

        printf(" %d is not present in tree \n", x);

  

    }

  

    getchar();

    return 0;

}

Джава

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

class Node 

{

    int data;

    Node left, right;

   

    public Node(int d) 

    {

        data = d;

        left = right = null;

    }

}

   

class BinaryTree 

{

   

    Node root;

   

    / * Вспомогательная функция для getLevel (). Возвращает уровень данных

    если данные присутствуют в дереве, в противном случае возвращает 0. * /

    int getLevelUtil(Node node, int data, int level) 

    {

        if (node == null)

            return 0;

   

        if (node.data == data)

            return level;

   

        int downlevel = getLevelUtil(node.left, data, level + 1);

        if (downlevel != 0)

            return downlevel;

   

        downlevel = getLevelUtil(node.right, data, level + 1);

        return downlevel;

    }

   

    / * Возвращает уровень заданного значения данных * /

    int getLevel(Node node, int data) 

    {

        return getLevelUtil(node, data, 1);

    }

   

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

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

   

        / * Построение дерева приведено на рисунке выше * /

        tree.root = new Node(3);

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

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

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

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

        for (int x = 1; x <= 5; x++) 

        {

            int level = tree.getLevel(tree.root, x);

            if (level != 0)

                System.out.println("Level of " + x + " is "

                        + tree.getLevel(tree.root, x));

            else

                System.out.println(x + " is not present in tree");

        }

    }

}

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

python3

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

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

class newNode: 

  

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

    def __init__(self, data): 

        self.data = data

        self.left = None

        self.right = None

  
# Вспомогательная функция для getLevel (). Это
# возвращает уровень данных, если данные
# присутствует в дереве, в противном случае возвращает 0

def getLevelUtil(node, data, level):

    if (node == None):

        return 0

  

    if (node.data == data) :

        return level 

  

    downlevel = getLevelUtil(node.left,

                             data, level + 1

    if (downlevel != 0) :

        return downlevel 

  

    downlevel = getLevelUtil(node.right, 

                             data, level + 1

    return downlevel 

  
# Возвращает уровень заданного значения данных

def getLevel(node, data) :

  

    return getLevelUtil(node, data, 1

  
Код водителя

if __name__ == '__main__':

      

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

    # на рисунке выше

    root = newNode(3

    root.left = newNode(2

    root.right = newNode(5

    root.left.left = newNode(1

    root.left.right = newNode(4)

    for x in range(1, 6):

        level = getLevel(root, x)

        if (level) :

            print("Level of", x, 

                  "is", getLevel(root, x))

        else:

            print(x, "is not present in tree"

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

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

using System;

  
/ * Древовидная структура * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinaryTree

{

  

    public Node root;

  

    / * Вспомогательная функция для getLevel (). Возвращает уровень данных

    если данные присутствуют в дереве, в противном случае возвращает 0. * /

    public virtual int getLevelUtil(Node node, int data, int level)

    {

        if (node == null)

        {

            return 0;

        }

  

        if (node.data == data)

        {

            return level;

        }

  

        int downlevel = getLevelUtil(node.left, data, level + 1);

        if (downlevel != 0)

        {

            return downlevel;

        }

  

        downlevel = getLevelUtil(node.right, data, level + 1);

        return downlevel;

    }

  

    / * Возвращает уровень заданного значения данных * /

    public virtual int getLevel(Node node, int data)

    {

        return getLevelUtil(node, data, 1);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / * Построение дерева приведено на рисунке выше * /

        tree.root = new Node(3);

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

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

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

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

        for (int x = 1; x <= 5; x++)

        {

            int level = tree.getLevel(tree.root, x);

            if (level != 0)

            {

                Console.WriteLine("Level of " + x + " is " + tree.getLevel(tree.root, x));

            }

            else

            {

                Console.WriteLine(x + " is not present in tree");

            }

        }

    }

}

  

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


Выход:

 Level of 1 is 3
 Level of 2 is 2
 Level of 3 is 1
 Level of 4 is 3
 Level of 5 is 2

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

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

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

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

0.00 (0%) 0 votes