Рубрики

Вывести все узлы в двоичном дереве с K листьями

Деревья

Для заданного двоичного дерева и целочисленного значения K задача состоит в том, чтобы найти все узлы в данном двоичном дереве, имеющие K листьев в поддереве с корнями в них.


Примеры :

// For above binary tree
Input : k = 2
Output: {3}
// here node 3 have k = 2 leaves

Input : k = 1
Output: {6}
// here node 6 have k = 1 leave

Здесь любой узел, имеющий K листьев, означает, что сумма листьев в левом поддереве и в правом поддереве должна быть равна K. Поэтому для решения этой проблемы мы используем обход дерева Postorder. Сначала мы вычисляем листья в левом поддереве, затем в правом поддереве и, если сумма равна K, то выводим текущий узел. В каждом рекурсивном вызове мы возвращаем сумму предков левого поддерева и правого поддерева.

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

C ++

// C ++ программа для подсчета всех узлов, имеющих k листьев
// в поддереве с ними
#include<bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data ;

    struct Node * left, * right ;

};

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

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

struct Node * newNode(int data)

{

    struct Node * node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

  
// Функция для печати всех узлов, имеющих k листьев

int kLeaves(struct Node *ptr,int k)

{

    // Базовые условия: нет листьев

    if (ptr == NULL)

        return 0;

  

    // если узел лист

    if (ptr->left == NULL && ptr->right == NULL)

        return 1;

  

    // всего листьев в поддереве с этим корнем

    // узел

    int total = kLeaves(ptr->left, k) +

                kLeaves(ptr->right, k);

  

    // Распечатать этот узел, если итог равен k

    if (k == total)

        cout << ptr->data << " ";

  

    return total;

}

  
// Драйвер программы для запуска дела

int main()

{

    struct Node *root = newNode(1);

    root->left        = newNode(2);

    root->right       = newNode(4);

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

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

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

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

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

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

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

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

  

    kLeaves(root, 2);

  

    return 0;

}

Джава

// Java-программа для подсчета всех узлов, имеющих k листьев
// в поддереве с ними

class GfG {

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

static class Node 

{ 

    int data ; 

    Node left, right ;

    Node(int data)

    {

        this.data = data;

    }

    Node()

    {

          

    }

}

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

static Node newNode(int data) 

{ 

    Node node = new Node(); 

    node.data = data; 

    node.left = null;

    node.right = null; 

    return (node); 

} 

  
// Функция для печати всех узлов, имеющих k листьев

static int kLeaves(Node ptr,int k) 

{ 

    // Базовые условия: нет листьев

    if (ptr == null) 

        return 0; 

  

    // если узел лист

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

        return 1; 

  

    // всего листьев в поддереве с этим корнем

    // узел

    int total = kLeaves(ptr.left, k) + kLeaves(ptr.right, k); 

  

    // Распечатать этот узел, если итог равен k

    if (k == total) 

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

  

    return total; 

} 

  
// Драйвер программы для запуска дела

public static void main(String[] args) 

{ 

    Node root = newNode(1); 

    root.left     = newNode(2); 

    root.right     = newNode(4); 

    root.left.left = newNode(5); 

    root.left.right = newNode(6); 

    root.left.left.left = newNode(9); 

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

    root.right.right = newNode(8); 

    root.right.left = newNode(7); 

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

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

  

    kLeaves(root, 2); 

  
} 
} 

python3

# Python3 программа для подсчета всех узлов
# наличие k листьев в поддереве с их корнями

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

class newNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Функция для печати всех узлов, имеющих k листьев

def kLeaves(ptr, k):

  

    # Базовые условия: нет листьев

    if (ptr == None):

        return 0

  

    # если узел лист

    if (ptr.left == None and 

        ptr.right == None):

        return 1

  

    # всего листьев в поддереве с этим

    # узел

    total = kLeaves(ptr.left, k) + \

            kLeaves(ptr.right, k)

  

    # Prthis узел, если общее число равно k

    if (k == total):

        print(ptr.data, end = " ")

  

    return total 

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

root = newNode(1) 

root.left = newNode(2) 

root.right = newNode(4) 

root.left.left = newNode(5) 

root.left.right = newNode(6) 

root.left.left.left = newNode(9) 

root.left.left.right = newNode(10) 

root.right.right = newNode(8) 

root.right.left = newNode(7) 

root.right.left.left = newNode(11) 

root.right.left.right = newNode(12) 

  

kLeaves(root, 2) 

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

C #

// C # программа для подсчета всех узлов, имеющих k листьев
// в поддереве с ними

using System;

      

class GfG 

{

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

public class Node 

{ 

    public int data ; 

    public Node left, right ;

    public Node(int data)

    {

        this.data = data;

    }

    public Node()

    {

          

    }

}

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

static Node newNode(int data) 

{ 

    Node node = new Node(); 

    node.data = data; 

    node.left = null;

    node.right = null; 

    return (node); 

} 

  
// Функция для печати всех узлов, имеющих k листьев

static int kLeaves(Node ptr,int k) 

{ 

    // Базовые условия: нет листьев

    if (ptr == null) 

        return 0; 

  

    // если узел лист

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

        return 1; 

  

    // всего листьев в поддереве с этим корнем

    // узел

    int total = kLeaves(ptr.left, k) + kLeaves(ptr.right, k); 

  

    // Распечатать этот узел, если итог равен k

    if (k == total) 

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

  

    return total; 

} 

  
// Драйвер программы для запуска дела

public static void Main(String[] args) 

{ 

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(4); 

    root.left.left = newNode(5); 

    root.left.right = newNode(6); 

    root.left.left.left = newNode(9); 

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

    root.right.right = newNode(8); 

    root.right.left = newNode(7); 

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

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

  

    kLeaves(root, 2); 

  
} 
}

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


Выход:

5 7

Временная сложность: O (n)

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Вывести все узлы в двоичном дереве с K листьями

0.00 (0%) 0 votes