Рубрики

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

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

Примеры:

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

{

    Node* node = new Node();

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

    node->data = key;

    return node;

}

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

void printLeafLeftToRight(Node* p)

{

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

    stack<Node*> s;

  

    while (1) {

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

        // это в стеке

        if (p) {

            s.push(p);

            p = p->left;

        }

  

        else {

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

            // цикла

            if (s.empty())

                break;

            else {

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

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

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

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

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

                    p = s.top();

                    s.pop();

  

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

                    if (p->left == NULL)

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

                }

  

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

                    p = s.top();

                    s.pop();

  

                    if (s.empty())

                        break;

                }

  

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

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

                if (!s.empty())

                    p = s.top()->right;

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

  

    printLeafLeftToRight(root);

  

    return 0;

}

Джава

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

import java.util.*;

class GfG 

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

static class Node 

    Node left; 

    Node right; 

    int data; 

}

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

static Node newNode(int key) 

    Node node = new Node(); 

    node.left = null;

    node.right = null

    node.data = key; 

    return node; 

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

static void printLeafLeftToRight(Node p) 

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

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

  

    while (true

    

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

        // это в стеке

        if (p != null

        

            s.push(p); 

            p = p.left; 

        

  

        else

        

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

            // цикла

            if (s.isEmpty()) 

                break

            else 

            

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

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

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

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

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

                

                    p = s.peek(); 

                    s.pop(); 

  

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

                    if (p.left == null

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

                

  

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

                

                    p = s.peek(); 

                    s.pop(); 

  

                    if (s.isEmpty()) 

                        break

                

  

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

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

                if (!s.isEmpty()) 

                    p = s.peek().right; 

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

  

    printLeafLeftToRight(root); 


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

python3

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

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

class newNode: 

      

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

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

def printLeafLeftToRight(p):

      

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

    s = []

    while (1):

          

        # Если p не None, нажмите

        # это в стеке

        if (p):

            s.insert(0, p)

            p = p.left

          

        else:

              

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

            № цикла

            if len(s) == 0:

                break

              

            else:

                  

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

                # правильное поддерево как None, затем вытолкнуть этот узел

                # и печатать узел только если он оставлен

                # поддерево также отсутствует

                if (s[0].right == None):

                    p = s[0]

                    s.pop(0)

                      

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

                    if (p.left == None):

                        print(p.data, end = " ")

                  

                while (p == s[0].right):

                    p = s[0]

                    s.pop(0)

                      

                    if len(s) == 0:

                        break

                  

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

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

                if len(s):

                    p = s[0].right

                  

                else:

                    p = None

  
Код водителя

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)

  
printLeafLeftToRight(root)

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

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 = null;

    node.right = null

    node.data = key; 

    return node; 

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

static void printLeafLeftToRight(Node p) 

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

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

  

    while (true

    

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

        // это в стеке

        if (p != null

        

            s.Push(p); 

            p = p.left; 

        

  

        else

        

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

            // цикла

            if (s.Count == 0) 

                break

            else

            

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

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

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

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

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

                

                    p = s.Peek(); 

                    s.Pop(); 

  

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

                    if (p.left == null

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

                

  

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

                

                    p = s.Peek(); 

                    s.Pop(); 

  

                    if (s.Count == 0) 

                        break

                

  

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

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

                if (s.Count != 0) 

                    p = s.Peek().right; 

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

  

    printLeafLeftToRight(root); 


}

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

Выход:

4 5 6 7

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

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

0.00 (0%) 0 votes