Рубрики

Подсчитать половину узлов в двоичном дереве (итеративное и рекурсивное)

Учитывая бинарное дерево, как вы считаете все половинные узлы (у которых есть только один дочерний элемент) без использования рекурсии? Листья примечания не должны быть затронуты, поскольку они имеют обоих детей как NULL.

Input : Root of below tree

Output : 3
Nodes 7, 5 and 9 are half nodes as one of 
their child is Null. So count of half nodes
in the above tree is 3

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

1) Create an empty Queue Node and push root node to Queue.
2) Do following while nodeQeue is not empty.
   a) Pop an item from Queue and process it.
      a.1) If it is half node then increment count++.
   b) Push left child of popped item to Queue, if available.
   c) Push right child of popped item to Queue, if available.

Ниже приведена реализация этой идеи.

C ++

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

using namespace std;

  
// Узел бинарного дерева имеет данные, указатель налево
// дочерний элемент и указатель на правый дочерний элемент

struct Node

{

    int data;

    struct Node* left, *right;

};

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

unsigned int gethalfCount(struct Node* node)

{

    // Если дерево пусто

    if (!node)

        return 0;

  

    int count = 0; // Инициализируем количество половин узлов

  

    // Делаем прохождение порядка уровня, начиная с корня

    queue<Node *> q;

    q.push(node);

    while (!q.empty())

    {

        struct Node *temp = q.front();

        q.pop();

  

        if (!temp->left && temp->right ||

            temp->left && !temp->right)

            count++;

  

        if (temp->left != NULL)

            q.push(temp->left);

        if (temp->right != NULL)

            q.push(temp->right);

    }

    return count;

}

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

   Узел с данными данными и NULL слева

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

struct Node* newNode(int data)

{

    struct Node* node = new Node;

    node->data = data;

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

    return (node);

}

  
// Драйвер программы

int main(void)

{

    / * 2

     / /

    7 5

    / /

     6 9

    ///

    1 11 4

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

    приведенный выше пример * /

  

    struct Node *root = newNode(2);

    root->left     = newNode(7);

    root->right     = newNode(5);

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

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

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

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

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

  

    cout << gethalfCount(root);

  

    return 0;

}

Джава

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

import java.util.Queue;

import java.util.LinkedList;

  
// Класс для представления узла дерева

class Node

{

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = null;

        right = null;

    }

}

  
// Класс для подсчета половины узлов дерева

class BinaryTree

{

  

    Node root;

  

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

    двоичное дерево * /

    int gethalfCount()

    {

        // Если дерево пусто

        if (root==null)

            return 0;

  

        // Делаем прохождение порядка уровня, начиная с корня

        Queue<Node> queue = new LinkedList<Node>();

        queue.add(root);

  

        int count=0; // Инициализируем количество половин узлов

        while (!queue.isEmpty())

        {

  

            Node temp = queue.poll();

            if (temp.left!=null && temp.right==null ||

                temp.left==null && temp.right!=null)

                count++;

  

            // ставим в очередь левого ребенка

            if (temp.left != null)

                queue.add(temp.left);

  

            // ставим в очередь правого ребенка

            if (temp.right != null)

                queue.add(temp.right);

        }

        return count;

    }

  

    public static void main(String args[])

    {

        / * 2

          / /

        7 5

        / /

        6 9

        ///

        1 11 4

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

        приведенный выше пример * /

        BinaryTree tree_level = new BinaryTree();

        tree_level.root = new Node(2);

        tree_level.root.left = new Node(7);

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

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

        tree_level.root.left.right.left = new Node(1);

        tree_level.root.left.right.right = new Node(11);

        tree_level.root.right.right = new Node(9);

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

  

        System.out.println(tree_level.gethalfCount());

  

    }

}

питон

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

  
# Структура узла

class Node:

  

    # Сервисная функция для создания нового узла

    def __init__(self ,key):

        self.data = key

        self.left = None

        self.right = None

  
# Итеративный метод для подсчета половины узлов двоичного дерева

def gethalfCount(root):

  

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

    if root is None:

        return 0

  

    # Создать пустую очередь для прохождения порядка уровней

    queue = []

  

    # Поставить в очередь Root и инициализировать счет

    queue.append(root)

  

    count = 0 #initialize count для половины узлов

    while(len(queue) > 0):

  

        node = queue.pop(0)

  

        # если это половина узла, то счетчик приращений

        if node.left is not None and node.right is None or node.left is None and node.right is not None:

            count = count+1

  

        # Поставить в очередь левого ребенка

        if node.left is not None:

            queue.append(node.left)

  

        # Поставить в очередь правильного ребенка

        if node.right is not None:

            queue.append(node.right)

  

    return count

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

  

root = Node(2)

root.left = Node(7)

root.right = Node(5)

root.left.right = Node(6)

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

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

root.right.right = Node(9)

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

  

  

print "%d" %(gethalfCount(root))

C #

// C # программа для подсчета половины узлов в двоичном дереве
// используя итеративный подход

using System;

using System.Collections.Generic; 

  
// Класс для представления узла дерева

public class Node 

    public int data; 

    public Node left, right; 

  

    public Node(int item) 

    

        data = item; 

        left = null

        right = null

    

  
// Класс для подсчета половины узлов дерева

public class BinaryTree 

  

    Node root; 

  

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

    двоичное дерево * /

    int gethalfCount() 

    

        // Если дерево пусто

        if (root == null

            return 0; 

  

        // Делаем прохождение порядка уровня, начиная с корня

        Queue<Node> queue = new Queue<Node>(); 

        queue.Enqueue(root); 

  

        int count = 0; // Инициализируем количество половин узлов

        while (queue.Count != 0) 

        

  

            Node temp = queue.Dequeue(); 

            if (temp.left != null && temp.right == null || 

                temp.left == null && temp.right != null

                count++; 

  

            // ставим в очередь левого ребенка

            if (temp.left != null

                queue.Enqueue(temp.left); 

  

            // ставим в очередь правого ребенка

            if (temp.right != null

                queue.Enqueue(temp.right); 

        

        return count; 

    

  

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

    public static void Main() 

    

        / * 2

        / /

        7 5

        / /

        6 9

        ///

        1 11 4

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

        приведенный выше пример * /

        BinaryTree tree_level = new BinaryTree(); 

        tree_level.root = new Node(2); 

        tree_level.root.left = new Node(7); 

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

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

        tree_level.root.left.right.left = new Node(1); 

        tree_level.root.left.right.right = new Node(11); 

        tree_level.root.right.right = new Node(9); 

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

  

        Console.WriteLine(tree_level.gethalfCount()); 

    

  
// Этот код предоставлен Rajput-Ji


Выход:

 3

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

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

C ++

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

using namespace std;

  
// Узел бинарного дерева имеет данные, указатель налево
// дочерний элемент и указатель на правый дочерний элемент

struct Node

{

    int data;

    struct Node* left, *right;

};

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

unsigned int gethalfCount(struct Node* root)

{

    if (root == NULL)

       return 0;

  

    int res = 0;

    if  ((root->left == NULL && root->right != NULL) ||

         (root->left != NULL && root->right == NULL))

       res++;

  

    res += (gethalfCount(root->left) + gethalfCount(root->right));

    return res;

}

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

   Узел с данными данными и NULL слева

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

struct Node* newNode(int data)

{

    struct Node* node = new Node;

    node->data = data;

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

    return (node);

}

  
// Драйвер программы

int main(void)

{

    / * 2

     / /

    7 5

    / /

     6 9

    ///

    1 11 4

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

    приведенный выше пример * /

  

    struct Node *root = newNode(2);

    root->left     = newNode(7);

    root->right     = newNode(5);

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

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

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

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

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

  

    cout << gethalfCount(root);

  

    return 0;

}

Джава

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

import java.util.*;

class GfG {

  
// Узел бинарного дерева имеет данные, указатель налево
// дочерний элемент и указатель на правый дочерний элемент

static class Node 

    int data; 

    Node left, right; 

}

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

static int gethalfCount(Node root) 

    if (root == null

    return 0

  

    int res = 0

    if ((root.left == null && root.right != null) ||

        (root.left != null && root.right == null)) 

    res++; 

  

    res += (gethalfCount(root.left) 

            + gethalfCount(root.right)); 

    return res; 

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

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = null;

    node.right = null

    return (node); 

  
// Драйвер программы

public static void main(String[] args) 

    / * 2

    / /

    7 5

    / /

    6 9

    ///

    1 11 4

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

    приведенный выше пример * /

  

    Node root = newNode(2); 

    root.left = newNode(7); 

    root.right = newNode(5); 

    root.left.right = newNode(6); 

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

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

    root.right.right = newNode(9); 

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

  

    System.out.println(gethalfCount(root)); 

  
}

C #

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

using System;

  

class GfG 

{

  

    // Узел бинарного дерева имеет данные, указатель налево

    // дочерний элемент и указатель на правый дочерний элемент

    public class Node 

    

        public int data; 

        public Node left, right; 

    }

  

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

    // двоичное дерево

    static int gethalfCount(Node root) 

    

        if (root == null

        return 0; 

  

        int res = 0; 

        if ((root.left == null && root.right != null) ||

            (root.left != null && root.right == null)) 

        res++; 

  

        res += (gethalfCount(root.left) 

                + gethalfCount(root.right)); 

        return res; 

    

  

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

    Узел с данными данными и NULL слева

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

    static Node newNode(int data) 

    

        Node node = new Node(); 

        node.data = data; 

        node.left = null;

        node.right = null

        return (node); 

    

  

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

    public static void Main() 

    

        / * 2

        / /

        7 5

        / /

        6 9

        ///

        1 11 4

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

        приведенный выше пример * /

  

        Node root = newNode(2); 

        root.left = newNode(7); 

        root.right = newNode(5); 

        root.left.right = newNode(6); 

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

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

        root.right.right = newNode(9); 

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

  

        Console.WriteLine(gethalfCount(root)); 

    }

}

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


Выход :

3

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

Похожие статьи:

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

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

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

Подсчитать половину узлов в двоичном дереве (итеративное и рекурсивное)

0.00 (0%) 0 votes