Рубрики

Распечатать правый вид двоичного дерева

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

Right view of following tree is 1 3 7 8

          1
       /     \
     2        3
   /   \     /  \
  4     5   6    7
                  \
                   8

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

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

C ++

// C ++ программа для печати правильного вида двоичного дерева
#include <iostream>

using namespace std;

  

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 rightViewUtil(struct Node *root, 

                   int level, int *max_level)

{

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

    if (root == NULL) return;

  

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

    if (*max_level < level)

    {

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

        *max_level = level;

    }

  

    // Повторяем сначала для правого поддерева,

    // затем оставляем поддерево

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

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

}

  
// Оболочка поверх rightViewUtil ()

void rightView(struct Node *root)

{

    int max_level = 0;

    rightViewUtil(root, 1, &max_level);

}

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

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->right->left = newNode(6);

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

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

  

    rightView(root);

  

    return 0;

}

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

С

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

  

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Утилита для создания нового узла Binary Tree

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 rightViewUtil(struct Node *root, int level, int *max_level)

{

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

    if (root==NULL)  return;

  

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

    if (*max_level < level)

    {

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

        *max_level = level;

    }

  

    // Повторяем сначала для правого поддерева, затем для левого поддерева

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

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

}

  
// Оболочка поверх rightViewUtil ()

void rightView(struct Node *root)

{

    int max_level = 0;

    rightViewUtil(root, 1, &max_level);

}

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

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->right->left = newNode(6);

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

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

  

    rightView(root);

  

    return 0;

}

Джава

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

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int item) {

        data = item;

        left = right = null;

    }

}

  
// класс для доступа к максимальному уровню по ссылке

class Max_level {

  

    int max_level;

}

  

class BinaryTree {

  

    Node root;

    Max_level max = new Max_level();

  

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

    void rightViewUtil(Node node, int level, Max_level max_level) {

  

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

        if (node == null

            return;

  

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

        if (max_level.max_level < level) {

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

            max_level.max_level = level;

        }

  

        // Повторяем сначала для правого поддерева, затем для левого поддерева

        rightViewUtil(node.right, level + 1, max_level);

        rightViewUtil(node.left, level + 1, max_level);

    }

  

    void rightView()

    {

        rightView(root);

    }

  

    // Оболочка поверх rightViewUtil ()

    void rightView(Node node) {

  

        rightViewUtil(node, 1, max);

    }

  

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

    public static void main(String args[]) {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

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

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

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

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

          

        tree.rightView();

  

        }

}

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

питон

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

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

class Node:

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

    def __init__(self, item):

        self.data = item

        self.left = None

        self.right = None

      
# Рекурсивная функция для печати правильного вида двоичного дерева
# использовал max_level в качестве списка ссылок .. только max_level [0]
# полезно для нас

def rightViewUtil(root, level, max_level):

      

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

    if root is None:

        return

      

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

    if (max_level[0] < level):

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

        max_level[0] = level

  

    # Повторить сначала для правого поддерева, затем для левого поддерева

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

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

  

def rightView(root):

    max_level = [0]

    rightViewUtil(root, 1, max_level)

  

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.left = Node(6)

root.right.right = Node(7)

root.right.left.right = Node(8)

  
rightView(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 Max_level

{

  

    public int max_level;

}

  

public class BinaryTree

{

  

    public Node root;

    public Max_level max = new Max_level();

  

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

    public virtual void rightViewUtil(Node node, int level,

                                        Max_level max_level)

    {

  

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

        if (node == null)

        {

            return;

        }

  

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

        if (max_level.max_level < level)

        {

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

            max_level.max_level = level;

        }

  

        // Повторяем сначала для правого поддерева, затем для левого поддерева

        rightViewUtil(node.right, level + 1, max_level);

        rightViewUtil(node.left, level + 1, max_level);

    }

  

    public virtual void rightView()

    {

        rightView(root);

    }

  

    // Оболочка поверх rightViewUtil ()

    public virtual void rightView(Node node)

    {

  

        rightViewUtil(node, 1, max);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

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

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

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

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

  

        tree.rightView();

  

    }

}

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

Выход:

1      3      7     8 

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

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

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

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

Распечатать правый вид двоичного дерева

0.00 (0%) 0 votes