Рубрики

Печать левого вида двоичного дерева

Дано Бинарное Дерево, выведите на экран вид слева. Вид слева двоичного дерева — это набор узлов, видимых при посещении дерева с левой стороны.

Примеры:

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

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

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

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

C ++

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

using namespace std;

  

class node {

public:

    int data;

    node *left, *right;

};

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

node* newNode(int item)

{

    node* temp = new node();

    temp->data = item;

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

    return temp;

}

  
// Рекурсивная функция для печати левого представления двоичного дерева.

void leftViewUtil(node* root, int level, int* max_level)

{

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

    if (root == NULL)

        return;

  

    // Если это первый узел его уровня

    if (*max_level < level) {

        cout << root->data << "\t";

        *max_level = level;

    }

  

    // Повтор для левого и правого поддеревьев

    leftViewUtil(root->left, level + 1, max_level);

    leftViewUtil(root->right, level + 1, max_level);

}

  
// Обёртка над leftViewUtil ()

void leftView(node* root)

{

    int max_level = 0;

    leftViewUtil(root, 1, &max_level);

}

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

int main()

{

    node* root = newNode(12);

    root->left = newNode(10);

    root->right = newNode(30);

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

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

  

    leftView(root);

  

    return 0;

}

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

С

// C программа для печати левого вида двоичного дерева
#include <stdio.h>
#include <stdlib.h>

  

struct node {

    int data;

    struct node *left, *right;

};

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

struct node* newNode(int item)

{

    struct node* temp = (struct node*)malloc(sizeof(struct node));

    temp->data = item;

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

    return temp;

}

  
// Рекурсивная функция для печати левого представления двоичного дерева.

void leftViewUtil(struct node* root, int level, int* max_level)

{

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

    if (root == NULL)

        return;

  

    // Если это первый узел его уровня

    if (*max_level < level) {

        printf("%d\t", root->data);

        *max_level = level;

    }

  

    // Повтор для левого и правого поддеревьев

    leftViewUtil(root->left, level + 1, max_level);

    leftViewUtil(root->right, level + 1, max_level);

}

  
// Обёртка над leftViewUtil ()

void leftView(struct node* root)

{

    int max_level = 0;

    leftViewUtil(root, 1, &max_level);

}

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

int main()

{

    struct node* root = newNode(12);

    root->left = newNode(10);

    root->right = newNode(30);

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

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

  

    leftView(root);

  

    return 0;

}

Джава

// Java-программа для печати левого представления двоичного дерева

  
/ * Класс, содержащий левого и правого потомка текущего
значение узла и ключа * /

class Node {

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  
/ * Класс для печати левого вида * /

class BinaryTree {

    Node root;

    static int max_level = 0;

  

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

    void leftViewUtil(Node node, int level)

    {

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

        if (node == null)

            return;

  

        // Если это первый узел его уровня

        if (max_level < level) {

            System.out.print(" " + node.data);

            max_level = level;

        }

  

        // Повтор для левого и правого поддеревьев

        leftViewUtil(node.left, level + 1);

        leftViewUtil(node.right, level + 1);

    }

  

    // Обёртка над leftViewUtil ()

    void leftView()

    {

        leftViewUtil(root, 1);

    }

  

    / * тестирование на примере узлов * /

    public static void main(String args[])

    {

        / * создание бинарного дерева и ввод узлов * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(12);

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

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

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

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

  

        tree.leftView();

    }

}

питон

# Программа Python для печати левого вида двоичного дерева

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  

  
# Рекурсивная функция притна левого вида двоичного дерева

def leftViewUtil(root, level, max_level):

      

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

    if root is None:

        return

  

    # Если это первый узел своего уровня

    if (max_level[0] < level):

        print "% d\t" %(root.data),

        max_level[0] = level

  

    # Повтор для левого и правого поддерева

    leftViewUtil(root.left, level + 1, max_level)

    leftViewUtil(root.right, level + 1, max_level)

  

  
# Обёртка над leftViewUtil ()

def leftView(root):

    max_level = [0]

    leftViewUtil(root, 1, max_level)

  

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

root = Node(12)

root.left = Node(10)

root.right = Node(20)

root.right.left = Node(25)

root.right.right = Node(40)

  
leftView(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

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

  
/ * Класс, содержащий левого и правого потомка текущего
значение узла и ключа * /

public class Node {

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  
/ * Класс для печати левого вида * /

public class BinaryTree {

    public Node root;

    public static int max_level = 0;

  

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

    public virtual void leftViewUtil(Node node, int level)

    {

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

        if (node == null) {

            return;

        }

  

        // Если это первый узел его уровня

        if (max_level < level) {

            Console.Write(" " + node.data);

            max_level = level;

        }

  

        // Повтор для левого и правого поддеревьев

        leftViewUtil(node.left, level + 1);

        leftViewUtil(node.right, level + 1);

    }

  

    // Обёртка над leftViewUtil ()

    public virtual void leftView()

    {

        leftViewUtil(root, 1);

    }

  

    / * тестирование на примере узлов * /

    public static void Main(string[] args)

    {

        / * создание бинарного дерева и ввод узлов * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(12);

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

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

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

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

  

        tree.leftView();

    }

}

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


Выход:

12      10      25

Сложность времени: функция выполняет простой обход дерева, поэтому сложность равна O (n).
Вспомогательное пространство: O (n), из-за стекового пространства во время рекурсивного вызова.

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

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

Печать левого вида двоичного дерева

0.00 (0%) 0 votes