Рубрики

Распечатайте узлы двоичного дерева, когда они станут листовым узлом

Дано бинарное дерево. Сначала выведите все листовые узлы, затем удалите все листовые узлы из дерева, а теперь напечатайте все вновь сформированные листовые узлы и продолжайте делать это, пока все узлы не будут удалены из дерева.

Примеры :

Input :  
              8
             / \
           3    10
          / \   / \
         1  6  14  4
        / \
       7   13

Output : 
4 6 7 13 14
1 10
3
8

Источник : Flipkart On Campus Recruitment

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

  1. Первоначально назначьте все узлы со значением 0.
  2. Теперь назначьте все узлы со значением как (максимальное значение обоих дочерних элементов) +1 .

Дерево перед DFS : временное значение ноль присваивается всем узлам.

Дерево после DFS : узлам присваивается значение (максимальное значение для обоих дочерних элементов) +1 .

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

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для печати узлов двоичного файла
// дерево, когда они становятся узлом листа

  
#include <bits/stdc++.h>

using namespace std;

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

struct Node {

    int data;

    int order;

    struct Node* left;

    struct Node* right;

};

  
// Utiltiy функция для выделения нового узла

struct Node* newNode(int data, int order)

{

    struct Node* node = new Node;

    node->data = data;

    node->order = order;

    node->left = NULL;

    node->right = NULL;

  

    return (node);

}

  
// Функция обхода дерева по порядку и
// присваиваем значения узлам

void Postorder(struct Node* node, vector<pair<int, int> >& v)

{

    if (node == NULL)

        return;

  

    / * первый рецидив на левом ребенке * /

    Postorder(node->left, v);

  

    / * теперь возвращаемся на правильного ребенка * /

    Postorder(node->right, v);

  

    // Если текущий узел является листовым, его порядок будет 1

    if (node->right == NULL && node->left == NULL) {

        node->order = 1;

  

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

        v.push_back(make_pair(node->order, node->data));

    }

    else {

        // в противном случае порядок будет:

        // max (left_child_order, right_child_order) + 1

        node->order = max((node->left)->order, (node->right)->order) + 1;

  

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

        v.push_back(make_pair(node->order, node->data));

    }

}

  
// Функция для печати листовых узлов в
// данный заказ

void printLeafNodes(int n, vector<pair<int, int> >& v)

{

    // Сортируем вектор по возрастанию

    // назначенные значения узла

    sort(v.begin(), v.end());

  

    for (int i = 0; i < n; i++) {

        if (v[i].first == v[i + 1].first)

            cout << v[i].second << " ";

  

        else

            cout << v[i].second << "\n";

    }

}

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

int main()

{

    struct Node* root = newNode(8, 0);

    root->left = newNode(3, 0);

    root->right = newNode(10, 0);

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

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

    root->right->left = newNode(14, 0);

    root->right->right = newNode(4, 0);

    root->left->left->left = newNode(7, 0);

    root->left->left->right = newNode(13, 0);

  

    int n = 9;

  

    vector<pair<int, int> > v;

  

    Postorder(root, v);

    printLeafNodes(n, v);

  

    return 0;

}

Джава

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

import java.util.*;

  

class GFG

{

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

static class Node

{

    int data;

    int order;

    Node left;

    Node right;

};

  

static class Pair

{

    int first,second;

      

    Pair(int a,int b)

    {

        first = a;

        second = b;

    }

}

  
// Utiltiy функция для выделения нового узла

static Node newNode(int data, int order)

{

    Node node = new Node();

    node.data = data;

    node.order = order;

    node.left = null;

    node.right = null;

  

    return (node);

}

static Vector<Pair> v = new Vector<Pair>();

  
// Функция обхода дерева по порядку и
// присваиваем значения узлам

static void Postorder(Node node)

{

    if (node == null)

        return;

  

    / * первый рецидив на левом ребенке * /

    Postorder(node.left);

  

    / * теперь возвращаемся на правильного ребенка * /

    Postorder(node.right);

  

    // Если текущий узел является листовым, его порядок будет 1

    if (node.right == null && node.left == null)

    {

        node.order = 1;

  

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

        v.add(new Pair(node.order, node.data));

    }

    else

    {

        // в противном случае порядок будет:

        // max (left_child_order, right_child_order) + 1

        node.order = Math.max((node.left).order, (node.right).order) + 1;

  

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

        v.add(new Pair(node.order, node.data));

    }

}

static class Sort implements Comparator<Pair> 

    // Используется для сортировки в порядке возрастания

    // номер рулона

    public int compare(Pair a, Pair b) 

    

        if(a.first != b.first)

        return (a.first - b.first);

        else

        return (a.second-b.second);

    

}

  
// Функция для печати листовых узлов в
// данный заказ

static void printLeafNodes(int n)

{

    // Сортируем вектор по возрастанию

    // назначенные значения узла

    Collections.sort(v,new Sort());

    for (int i = 0; i < v.size(); i++) 

    {

        if (i != v.size()-1 && v.get(i).first == v.get(i + 1).first)

            System.out.print( v.get(i).second + " ");

  

        else

            System.out.print( v.get(i).second + "\n");

    }

}

  

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

public static void main(String args[])

{

    Node root = newNode(8, 0);

    root.left = newNode(3, 0);

    root.right = newNode(10, 0);

    root.left.left = newNode(1, 0);

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

    root.right.left = newNode(14, 0);

    root.right.right = newNode(4, 0);

    root.left.left.left = newNode(7, 0);

    root.left.left.right = newNode(13, 0);

  

    int n = 9;

  

    Postorder(root);

    printLeafNodes(n);

}
}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 программа для печати узлов двоичного файла
# дерево, когда они становятся узлом листа

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

class newNode: 

      

    def __init__(self, data,order): 

        self.data = data 

        self.order=order

        self.left = None

        self.right = None

  
# Функция для обхода дерева по порядку и
# присваивание значений узлам

def Postorder(node,v):

    if (node == None):

        return

      

    "" "первый рецидив на левом ребенке" ""

    Postorder(node.left, v)

      

    "" "теперь возвращаемся на нужного ребенка" ""

    Postorder(node.right, v)

      

    # Если текущий узел является листовым узлом,

    # заказ будет 1

    if (node.right == None and 

        node.left == None):

        node.order = 1

          

        # составить пару назначенного значения и значения дерева

        v[0].append([node.order, node.data])

      

    else:

          

        # в противном случае порядок будет:

        # max (left_child_order, right_child_order) + 1

        node.order = max((node.left).order, 

                         (node.right).order) + 1

          

        # составить пару назначенного значения и значения дерева

        v[0].append([node.order, node.data])

          
# Функция для печати листовых узлов в
# данный заказ

def printLeafNodes(n, v):

      

    # Сортировать вектор по возрастанию

    # назначенные значения узла

    v=sorted(v[0])

    for i in range(n - 1):

        if (v[i][0]== v[i + 1][0]):

            print(v[i][1], end = " ")

        else:

            print(v[i][1])

    if (v[-1][0]== v[-2][0]):

            print(v[-1][1], end = " ")

    else:

        print(v[-1][1])

      
Код водителя

root = newNode(8, 0)

root.left = newNode(3, 0)

root.right = newNode(10, 0)

root.left.left = newNode(1, 0)

root.left.right = newNode(6, 0)

root.right.left = newNode(14, 0)

root.right.right = newNode(4, 0)

root.left.left.left = newNode(7, 0)

root.left.left.right = newNode(13, 0)

  

n = 9

v = [[] for i in range(1)]

  
Postorder(root, v)
printLeafNodes(n, v)

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

C #

// C # программа для печати узлов двоичного файла
// дерево, когда они становятся узлом листа

using System;

using System.Collections.Generic;

  

class GFG

{

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

public class Node

{

    public int data;

    public int order;

    public Node left;

    public Node right;

};

  

public class Pair

{

    public int first,second;

      

    public Pair(int a,int b)

    {

        first = a;

        second = b;

    }

}

  
// Utiltiy функция для выделения нового узла

static Node newNode(int data, int order)

{

    Node node = new Node();

    node.data = data;

    node.order = order;

    node.left = null;

    node.right = null;

  

    return (node);

}

  

static List<Pair> v = new List<Pair>();

  
// Функция для прохождения заказа
// дерево и присвоение значений узлам

static void Postorder(Node node)

{

    if (node == null)

        return;

  

    / * первый рецидив на левом ребенке * /

    Postorder(node.left);

  

    / * теперь возвращаемся на правильного ребенка * /

    Postorder(node.right);

  

    // Если текущий узел является листовым узлом,

    // порядок будет 1

    if (node.right == null && 

        node.left == null)

    {

        node.order = 1;

  

        // сделать пару назначенного значения

        // и значение дерева

        v.Add(new Pair(node.order, node.data));

    }

    else

    {

        // в противном случае порядок будет:

        // Max (left_child_order,

        // right_child_order) + 1

        node.order = Math.Max((node.left).order, 

                              (node.right).order) + 1;

  

        // сделать пару назначенного значения

        // и значение дерева

        v.Add(new Pair(node.order, node.data));

    }

}

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

public static int compare(Pair a, Pair b) 

    if(a.first != b.first)

        return (a.first - b.first);

    else

        return (a.second - b.second);

  
// Функция для печати листовых узлов в
// данный заказ

static void printLeafNodes(int n)

{

    // сортируем список по возрастанию

    // присвоенных значений узла

    v.Sort(compare);

    for (int i = 0; i < v.Count; i++) 

    {

        if (i != v.Count - 1 && 

            v[i].first == v[i + 1].first)

            Console.Write(v[i].second + " ");

  

        else

            Console.Write(v[i].second + "\n");

    }

}

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

public static void Main(String[] args)

{

    Node root = newNode(8, 0);

    root.left = newNode(3, 0);

    root.right = newNode(10, 0);

    root.left.left = newNode(1, 0);

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

    root.right.left = newNode(14, 0);

    root.right.right = newNode(4, 0);

    root.left.left.left = newNode(7, 0);

    root.left.left.right = newNode(13, 0);

  

    int n = 9;

  

    Postorder(root);

    printLeafNodes(n);

}
}

  
// Этот код добавлен
// Арнаб Кунду

Выход:

4 6 7 13 14
1 10
3
8

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

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

Распечатайте узлы двоичного дерева, когда они станут листовым узлом

0.00 (0%) 0 votes