Получить следующий узел в PreOrder Traversal без вызова из цикла - PullRequest
Новая
       2

Получить следующий узел в PreOrder Traversal без вызова из цикла

0 голосов
/ 03 апреля 2020

Я знаю, что написать код для обхода бинарного дерева по предварительному заказу просто. Мое требование заключается в том, что я хочу получить следующий узел из любого случайного узла из списка, пройденного по предварительному заказу. Примечание. Следующий узел должен выбираться по требованию, а не обязательно с foreach l oop на стороне вызывающего. Предпочтительно этот метод Next должен быть методом расширения и должен вызываться на данном узле.

Я думаю использовать какой-то «yield» для поддержания состояния, но мое ограничение заключается в том, что сигнатура этого метода расширения I не может изменить. Он должен строго возвращать объект Node и НЕ IEnumerable. 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = new Node(1,
                new Node(2, null, null),
                new Node(3, null, null));

            // I know I can do a preorder and get Next node one by one in a loop
            var list = new List<Node>();
            PreOrder(r, list);
            foreach (var item in list)
            {
                Console.WriteLine(item.data);
            }

            // But I want to call it in following way. Note I can call Next on any random node of the tree.
            var next = r.Next();
            Console.WriteLine(next.data);

            next = next.Next();
            Console.WriteLine(next.data);

            next = next.Next();
            Console.WriteLine(next.data);
        }
        static void PreOrder(Node node, List<Node> list)
        {
            if (node == null) return;
            list.Add(node);
            PreOrder(node.left, list);
            PreOrder(node.right, list);
        }
    }
    public class Node
    {
        public Node left;
        public Node right;
        public int data;

        public Node(int d, Node l, Node r)
        {
            data = d;
            left = l;
            right = r;
        }
    }
    public static class NodeExtensions
    {
        public static Node Next(this Node node)
        {
            // I want to implement this
        }
    }
}
...