Рубрики

Распечатать все листовые узлы двоичного дерева слева направо | Set-2 (итеративный подход)

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

Примеры:

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

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

Output :12 3 7 6 1

Мы уже обсуждали рекурсивный подход. Здесь мы решим проблему, используя два стека.

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

Затем мы начнем выталкивать второй стек и печатать все его элементы, пока стек не опустеет.

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

C ++

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

using namespace std;

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

struct Node {

    Node* left;

    Node* right;

    int data;

};

  
// Функция для создания нового
// Двоичный узел

Node* newNode(int data)

{

    Node* temp = new Node;

  

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

  

    return temp;

}

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

void PrintLeafLeftToRight(Node* root)

{

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

    stack<Node*> s1;

  

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

    stack<Node*> s2;

  

    // выдвигаем корневой узел

    s1.push(root);

  

    while (!s1.empty()) {

        Node* curr = s1.top();

        s1.pop();

  

        // Если у текущего узла есть левый потомок

        // вставляем его в первый стек

        if (curr->left)

            s1.push(curr->left);

  

        // Если текущий узел имеет правого потомка

        // вставляем его в первый стек

        if (curr->right)

            s1.push(curr->right);

  

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

        // вставить его во второй стек

        else if (!curr->left && !curr->right)

            s2.push(curr);

    }

  

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

    while (!s2.empty()) {

        cout << s2.top()->data << " ";

        s2.pop();

    }

}

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

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

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

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

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

  

    PrintLeafLeftToRight(root);

  

    return 0;

}

Джава

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

import java.util.*;

  

class GFG 

{

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

static class Node

{

    Node left;

    Node right;

    int data;

};

  
// Функция для создания нового
// Двоичный узел

static Node newNode(int data)

{

    Node temp = new Node();

  

    temp.data = data;

    temp.left = null;

    temp.right = null;

  

    return temp;

}

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

static void PrintLeafLeftToRight(Node root)

{

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

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

  

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

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

  

    // выдвигаем корневой узел

    s1.push(root);

  

    while (!s1.empty()) 

    {

        Node curr = s1.peek();

        s1.pop();

  

        // Если у текущего узла есть левый потомок

        // вставляем его в первый стек

        if (curr.left!=null)

            s1.push(curr.left);

  

        // Если текущий узел имеет правого потомка

        // вставляем его в первый стек

        if (curr.right!=null)

            s1.push(curr.right);

  

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

        // вставить его во второй стек

        else if (curr.left==null && curr.right==null)

            s2.push(curr);

    }

  

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

    while (!s2.empty()) 

    {

        System.out.print(s2.peek().data +" ");

        s2.pop();

    }

}

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

public static void main(String[] args)

{

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

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

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

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

  

    PrintLeafLeftToRight(root);

}
}

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

python3

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

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

class Node: 

      

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

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

def PrintLeafLeftToRight(root): 

  

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

    № дерева

    s1 = [] 

  

    # Стек для хранения всех

    # листовые узлы

    s2 = [] 

  

    # Нажмите на корневой узел

    s1.append(root) 

  

    while len(s1) != 0

        curr = s1.pop() 

  

        # Если у текущего узла есть левый потомок

        # поместите его в первый стек

        if curr.left:

            s1.append(curr.left) 

  

        # Если текущий узел имеет правильного потомка

        # поместите его в первый стек

        if curr.right: 

            s1.append(curr.right) 

  

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

        # толкнуть его на второй стек

        elif not curr.left and not curr.right: 

            s2.append(curr) 

      

    # Распечатать все листовые узлы

    while len(s2) != 0

        print(s2.pop().data, end = " ")

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

if __name__ == "__main__"

  

    root = Node(1

    root.left = Node(2

    root.right = Node(3

    root.left.left = Node(4

    root.right.left = Node(5

    root.right.right = Node(7

    root.left.left.left = Node(10

    root.left.left.right = Node(11

    root.right.right.left = Node(8

  

    PrintLeafLeftToRight(root) 

  
# Этот код добавлен
# от Rituraj Jain

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

{

    Node temp = new Node();

  

    temp.data = data;

    temp.left = null;

    temp.right = null;

  

    return temp;

}

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

static void PrintLeafLeftToRight(Node root)

{

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

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

  

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

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

  

    // выдвигаем корневой узел

    s1.Push(root);

  

    while (s1.Count != 0) 

    {

        Node curr = s1.Peek();

        s1.Pop();

  

        // Если у текущего узла есть левый потомок

        // вставляем его в первый стек

        if (curr.left != null)

            s1.Push(curr.left);

  

        // Если текущий узел имеет правого потомка

        // вставляем его в первый стек

        if (curr.right != null)

            s1.Push(curr.right);

  

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

        // вставить его во второй стек

        else if (curr.left == null && curr.right == null)

            s2.Push(curr);

    }

  

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

    while (s2.Count != 0) 

    {

        Console.Write(s2.Peek().data + " ");

        s2.Pop();

    }

}

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

public static void Main(String[] args)

{

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

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

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

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

  

    PrintLeafLeftToRight(root);

}
}

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

Выход:

10 11 5 8

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

Распечатать все листовые узлы двоичного дерева слева направо | Set-2 (итеративный подход)

0.00 (0%) 0 votes