Рубрики

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

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

Для приведенного выше двоичного дерева вывод будет таким, как показано ниже:

4 6 7 9 10

Идея сделать это похожа на алгоритм DFS . Ниже приведен пошаговый алгоритм для этого:

  1. Проверьте, является ли данный узел нулевым. Если ноль, вернитесь из функции.
  2. Проверьте, является ли это листовым узлом. Если узел является листовым, распечатайте его данные.
  3. Если на предыдущем шаге узел не является листовым узлом, проверьте, существуют ли левый и правый дочерние узлы узла. Если да, то вызовите функцию для левого и правого потомков узла рекурсивно.

Ниже приведена реализация C ++ вышеупомянутого подхода.

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

   направо */

#include <iostream>

using namespace std;

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

struct Node

{

    int data;

    struct Node *left, *right;

};

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

void printLeafNodes(Node *root)

{

    // если ноль ноль, возвращаем

    if (!root)

        return;

      

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

    if (!root->left && !root->right)

    {

        cout << root->data << " "

        return;

    }

  

    // если левый ребенок существует, проверить наличие листьев

    // рекурсивно

    if (root->left)

       printLeafNodes(root->left);

          

    // если правый ребенок существует, проверить наличие листьев

    // рекурсивно

    if (root->right)

       printLeafNodes(root->right);

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

Node* newNode(int data)

{

    Node *temp = new Node;

    temp->data = data;

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

    return temp;

}

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

int main()

{

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

    // вышеуказанная диаграмма

    Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

   

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

    printLeafNodes(root);

      

    return 0;

}

Выход:

4 6 7 9 10

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

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

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

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

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

0.00 (0%) 0 votes