Рубрики

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

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

Примеры:

Input : 
       1
      /  \
     2    3
    / \  / \
   4   5 6  7
Output : 7 6 5 4

Input :
        1
       /  \
      2    3
     / \    \
    4   5    6
        /   / \
       7    8  9
Output : 9 8 7 4

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

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

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

C ++

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

  
#include <iostream>

using namespace std;

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

struct Node {

    int data;

    struct Node *left, *right;

};

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

Node* newNode(int data)

{

    Node* temp = new Node;

    temp->data = data;

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

    return temp;

}

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

void printLeafNodes(Node* root)

{

    // Если узел нулевой, вернуть

    if (!root)

        return;

  

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

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

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

        return;

    }

  

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

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

    if (root->right)

        printLeafNodes(root->right);

  

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

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

    if (root->left)

        printLeafNodes(root->left);

}

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

int main()

{

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

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

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

  

    printLeafNodes(root);

  

    return 0;

}

Джава

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

import java.util.*;

  

class GFG

{

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

static class Node 

    int data; 

    Node left, right; 

}; 

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

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.left = temp.right = null

    return temp; 

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

static void printLeafNodes(Node root) 

    // Если узел нулевой, вернуть

    if (root == null

        return

  

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

    if (root.left == null && root.right == null

    

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

        return

    

  

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

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

    if (root.right != null

        printLeafNodes(root.right); 

  

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

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

    if (root.left != null

        printLeafNodes(root.left); 

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

public static void main(String args[])

    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.left.left.left = newNode(8); 

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

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

  

    printLeafNodes(root); 


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

python3

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

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

class newNode: 

      

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

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

def printLeafNodes(root):

      

    # Если узел ноль, вернуть

    if root == None:

        return

      

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

    # распечатать свои данные

    if (root.left == None and 

        root.right == None):

        print(root.data, end = " ")

        return

      

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

    # проверяем лист рекурсивно

    if root.right:

        printLeafNodes(root.right)

      

    # Если левый ребенок существует,

    # проверяем лист рекурсивно

    if root.left:

        printLeafNodes(root.left)

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

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.left.left.left = newNode(8)

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

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

  
printLeafNodes(root)

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

C #

using System;

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

class GFG

{

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

public class Node

{

    public int data;

    public Node left, right;

}

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

public static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

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

public static void printLeafNodes(Node root)

{

    // Если узел нулевой, вернуть

    if (root == null)

    {

        return;

    }

  

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

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

    {

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

        return;

    }

  

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

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

    if (root.right != null)

    {

        printLeafNodes(root.right);

    }

  

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

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

    if (root.left != null)

    {

        printLeafNodes(root.left);

    }

}

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

public static void Main(string[] args)

{

    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.left.left.left = newNode(8);

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

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

  

    printLeafNodes(root);

}
}

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

Выход:

9 6 5 10

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

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

C ++

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

  
#include<bits/stdc++.h>

using namespace std; 

    
// Структура двоичного дерева

struct Node { 

    Node* left; 

    Node* right; 

    int data; 

}; 

    
// Функция для создания нового узла

Node* newNode(int key) 

    Node* node = new Node(); 

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

    node->data = key; 

    return node; 

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

void printLeafRightToLeft(Node* p) 

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

    stack<Node*> s; 

    

    while (1) { 

        // Если p не равно нулю, нажмите

        // это в стеке

        if (p) { 

            s.push(p); 

            p = p->right; 

        

    

        else

            // Если стек пуст, то выходи

            // цикла

            if (s.empty()) 

                break

            else

                // Если узел на вершине стека имеет

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

                // печатаем узел, только если он прав

                // поддерево также нулевое

                if (s.top()->left == NULL) { 

                    p = s.top(); 

                    s.pop(); 

    

                    // Распечатать листовой узел

                    if (p->right == NULL) 

                        printf("%d ", p->data); 

                

    

                while (p == s.top()->left) { 

                    p = s.top(); 

                    s.pop(); 

    

                    if (s.empty()) 

                        break

                

    

                // Если стек не пустой, тогда присваиваем p как

                // левый потомок верхнего узла стека

                if (!s.empty()) 

                    p = s.top()->left; 

                else

                    p = NULL; 

            

        

    

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

int main() 

    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); 

    

    printLeafRightToLeft(root); 

    

    return 0; 

}

Джава

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

import java.util.Stack;

  

class GFG

{

  

    // Структура двоичного дерева

    static class Node

    

        Node left; 

        Node right; 

        int data; 

    };

  

    // Функция для создания нового узла

    static Node newNode(int key) 

    

        Node node = new Node(); 

        node.left = node.right = null

        node.data = key; 

        return node; 

    

  

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

    // двоичного дерева, использующего один стек

    static void printLeafRightToLeft(Node p) 

    

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

        Stack<Node> s = new Stack<>(); 

  

        while (true

        

            // Если p не равно нулю, нажмите

            // это в стеке

            if (p != null

            

                s.push(p); 

                p = p.right; 

            

  

            else 

            

                // Если стек пуст, то выходи

                // цикла

                if (s.empty()) 

                    break

                else

                

                    // Если узел на вершине стека имеет

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

                    // печатаем узел, только если он прав

                    // поддерево также нулевое

                    if (s.peek().left == null

                    

                        p = s.peek(); 

                        s.pop(); 

  

                        // Распечатать листовой узел

                        if (p.right == null

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

                    

  

                    while (p == s.peek().left) 

                    

                        p = s.peek(); 

                        s.pop(); 

  

                        if (s.empty()) 

                            break

                    

  

                    // Если стек не пустой, тогда присваиваем p как

                    // левый потомок верхнего узла стека

                    if (!s.empty()) 

                        p = s.peek().left; 

                    else

                        p = null

                

            

        

    

  

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

    public static void main(String[] args)

    {

        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); 

  

        printLeafRightToLeft(root); 

  

    }

}

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

C #

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

using System;

using System.Collections.Generic;

  

class GFG

{

  

    // Структура двоичного дерева

    public class Node

    

        public Node left; 

        public Node right; 

        public int data; 

    };

  

    // Функция для создания нового узла

    static Node newNode(int key) 

    

        Node node = new Node(); 

        node.left = node.right = null

        node.data = key; 

        return node; 

    

  

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

    // двоичного дерева, использующего один стек

    static void printLeafRightToLeft(Node p) 

    

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

        Stack<Node> s = new Stack<Node>(); 

  

        while (true

        

            // Если p не равно нулю, нажмите

            // это в стеке

            if (p != null

            

                s.Push(p); 

                p = p.right; 

            

  

            else

            

                // Если стек пуст, то выходи

                // цикла

                if (s.Count == 0) 

                    break

                else

                

                    // Если узел на вершине стека имеет

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

                    // печатаем узел, только если он прав

                    // поддерево также нулевое

                    if (s.Peek().left == null

                    

                        p = s.Peek(); 

                        s.Pop(); 

  

                        // Распечатать листовой узел

                        if (p.right == null

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

                    

  

                    while (p == s.Peek().left) 

                    

                        p = s.Peek(); 

                        s.Pop(); 

  

                        if (s.Count == 0) 

                            break

                    

  

                    // Если стек не пустой, тогда присваиваем p как

                    // левый потомок верхнего узла стека

                    if (s.Count != 0) 

                        p = s.Peek().left; 

                    else

                        p = null

                

            

        

    

  

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

    public static void Main(String[] args)

    {

        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); 

  

        printLeafRightToLeft(root); 

    }

}

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

Выход:

7 6 5 4

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

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

0.00 (0%) 0 votes