Рубрики

Печать путей от корня к листу без использования рекурсии

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

        6
     /    \
    3      5
  /   \     \
 2     5     4
     /   \
    7     4

There are 4 leaves, hence 4 root to leaf paths -
  6->3->2              
  6->3->5->7
  6->3->5->4
  6->5>4

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Мы можем обходить дерево итеративно (мы использовали итеративный предзаказ ). Вопрос в том, как расширить обход для вывода корневых путей в конечные. Идея состоит в том, чтобы сохранить карту для хранения родительских указателей узлов двоичного дерева. Теперь, когда мы сталкиваемся с листовым узлом при выполнении итеративного обхода предварительного заказа, мы можем легко распечатать путь от корня к листу, используя родительский указатель. Ниже приведена реализация этой идеи.

C ++

// C ++ программа для печати корня к листу пути БЕЗ
// используя рекурсию
#include <bits/stdc++.h>

using namespace std;

  
/ * Бинарное дерево * /

struct Node

{

    int data;

    struct Node *left, *right;

};

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

   с данными данными и NULL влево и вправо

   указатели. * /

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

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

    return node;

}

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

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

void printTopToBottomPath(Node* curr,

                         map<Node*, Node*> parent)

{

    stack<Node*> stk;

  

    // начинаем с конечного узла и продолжаем нажимать

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

    while (curr)

    {

        stk.push(curr);

        curr = parent[curr];

    }

  

    // Запускаем выталкивающие узлы из стека и печатаем их

    while (!stk.empty())

    {

        curr = stk.top();

        stk.pop();

        cout << curr->data << " ";

    }

    cout << endl;

}

  
/ * Итерационная функция для обхода предзаказа

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

   без использования рекурсии * /

void printRootToLeaf(Node* root)

{

    // Угловой корпус

    if (root == NULL)

        return;

  

    // Создаем пустой стек и помещаем в него корень

    stack<Node*> nodeStack;

    nodeStack.push(root);

  

    // Создать карту для хранения родительских указателей двоичного файла

    // узлы дерева

    map<Node*, Node*> parent;

  

    // родитель root равен NULL

    parent[root] = NULL;

  

    / * Поп все предметы по одному. Следуйте за

       каждый сованный предмет

        а) выдвинуть своего правого потомка и установить его родителя

           указатель

        б) толкнуть своего левого потомка и установить его родителя

           указатель

       Обратите внимание, что правый ребенок толкается первым, так что

       слева обрабатывается первым * /

    while (!nodeStack.empty())

    {

        // выталкиваем верхний элемент из стека

        Node* current = nodeStack.top();

        nodeStack.pop();

  

        // Если обнаружен листовой узел, выведите Top To

        // Нижний путь

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

            printTopToBottomPath(current, parent);

  

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

        // укладывать. Также установите родительский указатель в

        // карта

        if (current->right)

        {

            parent[current->right] = current;

            nodeStack.push(current->right);

        }

        if (current->left)

        {

            parent[current->left] = current;

            nodeStack.push(current->left);

        }

    }

}

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

int main()

{

    / * Построенное двоичное дерево

         10

        / /

       8 2

      ///

     3 5 2 * /

    Node* root = newNode(10);

    root->left = newNode(8);

    root->right = newNode(2);

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

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

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

  

    printRootToLeaf(root);

  

    return 0;

}

Джава

// Java-программа для печати корня к листу пути БЕЗ
// используя рекурсию

import java.util.Stack;

import java.util.HashMap;

public class PrintPath {

  

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

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

    public static void printTopToBottomPath(Node curr, HashMap<Node,Node> parent) 

    

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

    

        // начинаем с конечного узла и продолжаем нажимать

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

        while (curr!=null

        

            stk.push(curr); 

            curr = parent.get(curr); 

        

    

        // Запускаем выталкивающие узлы из стека и печатаем их

        while (!stk.isEmpty()) 

        

            curr = stk.pop(); 

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

        

        System.out.println();

    

  

  

    / * Итерационная функция для обхода предзаказа

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

    без использования рекурсии * /

    public static void printRootToLeaf(Node root) 

    

        // Угловой корпус

        if (root == null

            return

    

        // Создаем пустой стек и помещаем в него корень

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

        nodeStack.push(root); 

    

        // Создать карту для хранения родительских указателей двоичного файла

        // узлы дерева

        HashMap<Node,Node> parent=new HashMap<>();

    

        // родитель root равен NULL

        parent.put(root,null); 

    

        / * Поп все предметы по одному. Следуйте за

        каждый сованный предмет

            а) выдвинуть своего правого потомка и установить его родителя

            указатель

            б) толкнуть своего левого потомка и установить его родителя

            указатель

        Обратите внимание, что правый ребенок толкается первым, так что

        слева обрабатывается первым * /

        while (!nodeStack.isEmpty()) 

        

            // выталкиваем верхний элемент из стека

            Node current = nodeStack.pop(); 

    

            // Если обнаружен листовой узел, выведите Top To

            // Нижний путь

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

                printTopToBottomPath(current, parent); 

    

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

            // укладывать. Также установите родительский указатель в

            // карта

            if (current.right!=null

            

                parent.put(current.right,current);

                nodeStack.push(current.right); 

            

            if (current.left!=null

            

                parent.put(current.left,current);

                nodeStack.push(current.left); 

            

        

    

  

  

    public static void main(String args[]) {

        Node root=new Node(10);

        root.left = new Node(8); 

        root.right = new Node(2); 

        root.left.left = new Node(3); 

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

        root.right.left = new Node(2); 

        printRootToLeaf(root); 

    }

}

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

class Node 

    int data; 

    Node left, right; 

    Node(int data)

    {

        left=right=null;

        this.data=data;

    }

}; 
// Этот код предоставлен Гауравом Тивари

python3

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

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

class newNode:

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

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

def printTopToBottomPath(curr, parent):

    stk = [] 

  

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

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

    while (curr):

        stk.append(curr) 

        curr = parent[curr]

  

    # Начало выталкивания узлов из стека

    # и распечатать их

    while len(stk) != 0:

        curr = stk[-1

        stk.pop(-1

        print(curr.data, end = " ")

    print()

  
# Итеративная функция для предварительного заказа
# обход двоичного дерева и печать
# путь от корня к листу без использования рекурсии

def printRootToLeaf(root):

      

    # Угловой чехол

    if (root == None): 

        return

  

    # Создать пустой стек и

    # добавить к нему корень

    nodeStack = []

    nodeStack.append(root) 

  

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

    # указатели узлов двоичного дерева

    parent = {}

  

    # родитель root отсутствует

    parent[root] = None

  

    # Поп все предметы по одному. Делать следующее

    # за каждый найденный предмет

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

    # родительский указатель

    # б) добавить своего левого потомка и установить его

    # родительский указатель

    # Обратите внимание, что правильный ребенок добавляется первым

    # так что левый обрабатывается первым

    while len(nodeStack) != 0:

          

        # Вытолкнуть верхний элемент из стека

        current = nodeStack[-1]

        nodeStack.pop(-1

  

        # Если обнаружен листовой узел, выведите

        Путь сверху вниз

        if (not (current.left) and

            not (current.right)): 

            printTopToBottomPath(current, parent) 

  

        # добавить справа и слева от детей

        # выскочил узел в стек. Также установите их

        # родительский указатель на карте

        if (current.right):

            parent[current.right] = current 

            nodeStack.append(current.right)

        if (current.left):

            parent[current.left] = current 

            nodeStack.append(current.left)

  
Код водителя

if __name__ == '__main__':

      

    # Построенное двоичное дерево

    № 10

    # / /

    № 8 2

    # / / /

    # 3 5 2

    root = newNode(10

    root.left = newNode(8

    root.right = newNode(2

    root.left.left = newNode(3

    root.left.right = newNode(5

    root.right.left = newNode(2

  

    printRootToLeaf(root)

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

C #

// C # программа для печати корня к листу пути БЕЗ
// используя рекурсию

using System;

using System.Collections.Generic;

  

public class PrintPath 

{

  

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

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

    public static void printTopToBottomPath(Node curr, 

                        Dictionary<Node,Node> parent) 

    

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

      

        // начинаем с конечного узла и продолжаем нажимать

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

        while (curr != null

        

            stk.Push(curr); 

            curr = parent[curr]; 

        

      

        // Запускаем выталкивающие узлы из стека и печатаем их

        while (stk.Count != 0) 

        

            curr = stk.Pop(); 

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

        

        Console.WriteLine();

    

  

  

    / * Итерационная функция для обхода предзаказа

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

    без использования рекурсии * /

    public static void printRootToLeaf(Node root) 

    

        // Угловой корпус

        if (root == null

            return

      

        // Создаем пустой стек и помещаем в него корень

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

        nodeStack.Push(root); 

      

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

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

        Dictionary<Node,Node> parent = new Dictionary<Node,Node>();

      

        // родитель root равен NULL

        parent.Add(root, null); 

      

        / * Поп все предметы по одному. Следуйте за

        каждый сованный предмет

            а) выдвинуть своего правого потомка и установить его родителя

            указатель

            б) толкнуть своего левого потомка и установить его родителя

            указатель

        Обратите внимание, что правый ребенок толкается первым, так что

        слева обрабатывается первым * /

        while (nodeStack.Count != 0) 

        

            // выталкиваем верхний элемент из стека

            Node current = nodeStack.Pop(); 

      

            // Если обнаружен листовой узел, выведите Top To

            // Нижний путь

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

                printTopToBottomPath(current, parent); 

      

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

            // укладывать. Также установите родительский указатель в

            // карта

            if (current.right != null

            

                parent.Add(current.right,current);

                nodeStack.Push(current.right); 

            

            if (current.left != null

            

                parent.Add(current.left,current);

                nodeStack.Push(current.left); 

            

        

    

  

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

    public static void Main(String []args) 

    {

        Node root = new Node(10);

        root.left = new Node(8); 

        root.right = new Node(2); 

        root.left.left = new Node(3); 

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

        root.right.left = new Node(2); 

        printRootToLeaf(root); 

    }

}

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

public class Node 

    public int data; 

    public Node left, right; 

    public Node(int data)

    {

        left = right = null;

        this.data = data;

    }

};

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


Выход :

10 8 3 
10 8 5 
10 2 2 

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

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

Печать путей от корня к листу без использования рекурсии

0.00 (0%) 0 votes