Рубрики

Итеративный обход по порядку N-арного дерева

Деревья, Стек

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

Примеры:

Input:
     1
   / | \
  3  2  4
 / \
5   6
Output: [5, 6, 3, 2, 4, 1]

Input:
   1
  / \
 2   3
Output: [2, 3, 1]

Подходить:

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

Псевдокод:

  • Начните с корня.
  • Повторите все шаги ниже, пока ни root! = Null ИЛИ стек не будет пустым.
    1. Если root! = Null, тогда протолкните корень, и это индекс в стек и будет продолжаться в направлении левого узла.
    2. Вытащите элемент из стека и распечатайте его.
    3. Извлечь все элементы из стека, пока стек не будет пустым && popped узел является последним потомком
      это родитель.
    4. Назначьте корень следующим дочерним элементам вершины стека.

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

Джава

    // Класс узла

    static class Node {

        public int val;

        public List<Node> children = new ArrayList<Node>();

      

        // Конструктор по умолчанию

        public Node() {}

      

        public Node(int _val)

        {

            val = _val;

        }

      

        public Node(int _val, List<Node> _children)

        {

            val = _val;

            children = _children;

        }

    };

      

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

    // в стек

    static class Pair {

        public Node node;

        public int childrenIndex;

        public Pair(Node _node, int _childrenIndex)

        {

            node = _node;

            childrenIndex = _childrenIndex;

        }

    }

      

    // Мы будем сохранять начальный индекс как 0,

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

    // обрабатываем большинство левых детей

    int currentRootIndex = 0;

    Stack<Pair> stack = new Stack<Pair>();

    ArrayList<Integer> postorderTraversal = 

                        new ArrayList<Integer>();

      

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

    public ArrayList<Integer> postorder(Node root)

    {

        while (root != null || !stack.isEmpty()) {

            if (root != null) {

                  

                // толкаем корень и его индекс

                // в стек

                stack.push(new Pair(root, currentRootIndex));

                currentRootIndex = 0;

      

                // Если у пользователя root нет детей,

                // означает, что мы уже находимся слева

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

                if (root.children.size() >= 1) {

                    root = root.children.get(0);

                }

                else {

                    root = null;

                }

                continue;

            }

      

            // Мы вытолкнем вершину стека и

            // добавить его в наш ответ

            Pair temp = stack.pop();

            postorderTraversal.add(temp.node.val);

      

            // Неоднократно мы будем поп все

            // элементы из стека до выскочил

            // элемент является последним потомком вершины

            // стек

            while (!stack.isEmpty() && temp.childrenIndex == 

                    stack.peek().node.children.size() - 1) {

                temp = stack.pop();

                  

                postorderTraversal.add(temp.node.val);

            }

      

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

            // корень для следующих потомков вершины

            // стекового узла

            if (!stack.isEmpty()) {

                root = stack.peek().node.children.get(

                                        temp.childrenIndex + 1);

                currentRootIndex = temp.childrenIndex + 1;

            }

        }

      

        return postorderTraversal;

    }

      

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

    public static void main(String[] args)

    {

        GFG solution = new GFG();

        Node root = new Node(1);

      

        root.children.add(new Node(3));

        root.children.add(new Node(2));

        root.children.add(new Node(4));

      

        root.children.get(0).children.add(new Node(5));

        root.children.get(0).children.add(new Node(6));

      

        System.out.println(solution.postorder(root));

    }

}

C #

// C # Программа для итеративного обхода по порядку N-арного дерева

using System;

using System.Collections.Generic;

  

class GFG

{

    // Класс узла

    public class Node 

    {

        public int val;

        public List<Node> children = new List<Node>();

      

        // Конструктор по умолчанию

        public Node() {}

      

        public Node(int _val)

        {

            val = _val;

        }

      

        public Node(int _val, List<Node> _children)

        {

            val = _val;

            children = _children;

        }

    };

      

    // Вспомогательный класс to.Push узел и его индекс

    // в стек

    class Pair 

    {

        public Node node;

        public int childrenIndex;

        public Pair(Node _node, int _childrenIndex)

        {

            node = _node;

            childrenIndex = _childrenIndex;

        }

    }

      

    // Мы будем сохранять начальный индекс как 0,

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

    // обрабатываем большинство левых детей

    int currentRootIndex = 0;

    Stack<Pair> stack = new Stack<Pair>();

    List<int> postorderTraversal = 

                        new List<int>();

      

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

    public List<int> postorder(Node root)

    {

        while (root != null || stack.Count != 0) 

        {

            if (root != null)

            {

                  

                // толкаем корень и его индекс

                // в стек

                stack.Push(new Pair(root, currentRootIndex));

                currentRootIndex = 0;

      

                // Если у пользователя root нет детей,

                // означает, что мы уже находимся слева

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

                if (root.children.Count >= 1) 

                {

                    root = root.children[0];

                }

                else

                {

                    root = null;

                }

                continue;

            }

      

            // Мы будем. Поп вершина стека и

            //.Добавить это к нашему ответу

            Pair temp = stack.Pop();

            postorderTraversal.Add(temp.node.val);

      

            // Повторно мы будем. Поп все

            // элементы из стека

            // элемент является последним потомком вершины

            // стек

            while (stack.Count != 0 && temp.childrenIndex == 

                    stack.Peek().node.children.Count - 1) 

            {

                temp = stack.Pop();

                  

                postorderTraversal.Add(temp.node.val);

            }

      

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

            // корень для следующих потомков вершины

            // стекового узла

            if (stack.Count != 0)

            {

                root = stack.Peek().node.children[temp.childrenIndex + 1];

                currentRootIndex = temp.childrenIndex + 1;

            }

        }

      

        return postorderTraversal;

    }

      

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

    public static void Main(String[] args)

    {

        GFG solution = new GFG();

        Node root = new Node(1);

      

        root.children.Add(new Node(3));

        root.children.Add(new Node(2));

        root.children.Add(new Node(4));

      

        root.children[0].children.Add(new Node(5));

        root.children[0].children.Add(new Node(6));

        Console.Write("[");

        List<int> temp = solution.postorder(root);

        int size = temp.Count;

        int count = 0;

        foreach(int v in temp)

        {

            Console.Write(v);

            count++;

            if(count < size)

                Console.Write(", ");

        }

        Console.Write("]");

    }

}

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

Выход:

[5, 6, 3, 2, 4, 1]

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

Итеративный обход по порядку N-арного дерева

0.00 (0%) 0 votes