Рекурсивный обход дерева почтовых заказов без создания новых узлов

Я хочу определить обобщенный хвостовой рекурсивный обход дерева, который работает для всех видов многоходовых деревьев. Это отлично работает с предварительным заказом и порядком уровней, но у меня возникают проблемы с реализацией обходов после заказа. Вот многоходовое дерево, с которым я работаю:

Желаемый заказ: EKFBCGHIJDA

Пока я не забочусь о хвостовой рекурсии, обход почтового заказа прост:

const postOrder = ([x, xs]) => {
  xs.forEach(postOrder);
  console.log(`${x}`);
};

const Node = (x, ...xs) => ([x, xs]);

const tree = Node("a",
  Node("b",
    Node("e"),
    Node("f",
      Node("k"))),
  Node("c"),
  Node("d",
    Node("g"),
    Node("h"),
    Node("i"),
    Node("j")));

postOrder(tree);

С другой стороны, хвостовой рекурсивный подход довольно громоздкий:

const postOrder = (p, q) => node => {
  const rec = ({[p]: x, [q]: forest}, stack) => {
      if (forest.length > 0) {
        const [node, ...forest_] = forest;
        stack.unshift(...forest_, Node(x));
        return rec(node, stack);
      }

      else {
        console.log(x);
        
        if (stack.length > 0) {
          const node = stack.shift();
          return rec(node, stack);
        }

        else return null;
      }
    };

  return rec(node, []);
};

const Node = (x, ...xs) => ([x, xs]);

const tree = Node("a",
  Node("b",
    Node("e"),
    Node("f",
      Node("k"))),
  Node("c"),
  Node("d",
    Node("g"),
    Node("h"),
    Node("i"),
    Node("j")));

postOrder(0, 1) (tree);

В частности, я хотел бы избежать создания новых узлов, чтобы я мог перемещаться по произвольным деревьям, ничего не зная об их конструкторах. Есть ли способ сделать это и по-прежнему оставаться хвостовой рекурсией?

Community 23.03.2018 источник

Ответы (2)

arrow_upward
2
arrow_downward

безопасен для стека

Мой первый ответ решает эту проблему, написав собственный протокол функционального итератора. По общему признанию, мне не терпелось поделиться этим подходом, поскольку я исследовал его в прошлом. Написание собственных структур данных — это действительно весело, и это может привести к творческим решениям вашей проблемы — и вам было бы скучно, если бы я сначала дал простые ответы, не так ли?

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const loop = (acc, [ node = Empty, ...nodes ], cont) =>
    isEmpty (node)
      ? cont (acc)
      : ???
  return loop (acc, [ node ], identity)
}

const postOrderValues = (node = Empty) =>
  postOrderFold ((acc, node) => [ ...acc, Node.value (node) ], [], node)

console.log (postOrderValues (tree))
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

Полное решение приведено ниже для других читателей...

const Node = (x, ...xs) =>
  [ x, xs ]

Node.value = ([ value, _ ]) =>
  value

Node.children = ([ _, children ]) =>
  children
  
const Empty =
  Symbol ()
  
const isEmpty = x =>
  x === Empty

const identity = x =>
  x

// tail recursive
const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const loop = (acc, [ node = Empty, ...nodes ], cont) =>
    isEmpty (node)
      ? cont (acc)
      : loop (acc, Node.children (node), nextAcc =>
          loop (f (nextAcc, node), nodes, cont))
  return loop (acc, [ node ], identity)
}

const postOrderValues = (node = Empty) =>
  postOrderFold ((acc, node) => [ ...acc, Node.value (node) ], [], node)

const tree =
  Node("a",
    Node("b",
      Node("e"),
      Node("f",
        Node("k"))),
    Node("c"),
    Node("d",
      Node("g"),
      Node("h"),
      Node("i"),
      Node("j")))
    
console.log (postOrderValues (tree))
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

взаимная рекурсия

Каким-то образом именно ваши вопросы позволяют мне рисовать мои самые вдохновенные работы. Вернувшись в свободное пространство с обходами дерева, я придумал такого рода псевдоприкладные типы суммы Now и Later.

Later не имеет правильного хвостового вызова, но я подумал, что решение было слишком изящным, чтобы не поделиться им

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const Now = node =>
    (acc, nodes) =>
      loop (f (acc, node), nodes)

  const Later = node =>
    (acc, nodes) =>
      loop (acc, [ ...Node.children (node) .map (Later), Now (node), ...nodes ])

  const loop = (acc, [ reducer = Empty, ...rest ]) =>
    isEmpty (reducer)
      ? acc
      : reducer (acc, rest)

  // return loop (acc, [ ...Node.children (node) .map (Later), Now (node) ])
  // or more simply ...
  return Later (node) (acc, [])
}

Демонстрация взаимной рекурсии

const Node = (x, ...xs) =>
  [ x, xs ]

Node.value = ([ value, _ ]) =>
  value

Node.children = ([ _, children ]) =>
  children
  
const Empty =
  Symbol ()
  
const isEmpty = x =>
  x === Empty

const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const Now = node =>
    (acc, nodes) =>
      loop (f (acc, node), nodes)
    
  const Later = node =>
    (acc, nodes) =>
      loop (acc, [ ...Node.children (node) .map (Later), Now (node), ...nodes ])
    
  const loop = (acc, [ reducer = Empty, ...rest ]) =>
    isEmpty (reducer)
      ? acc
      : reducer (acc, rest)
  
  // return loop (acc, [ ...Node.children (node) .map (Later), Now (node) ])
  // or more simply ...
  return Later (node) (acc, [])
}

const postOrderValues = (node = Empty) =>
  postOrderFold ((acc, node) => [ ...acc, Node.value (node) ], [], node)

const tree =
  Node("a",
    Node("b",
      Node("e"),
      Node("f",
        Node("k"))),
    Node("c"),
    Node("d",
      Node("g"),
      Node("h"),
      Node("i"),
      Node("j")))
    
console.log (postOrderValues (tree))
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

Mulan 25.03.2018

comment

Пару дней назад заболел чумой и сейчас не может обрабатывать информацию. Вы лучшие, спасибо! - ; 25.03.2018

arrow_upward
1
arrow_downward

Мы начинаем с написания Node.value и Node.children, которые получают два значения из вашего узла.

// -- Node -----------------------------------------------

const Node = (x, ...xs) =>
  [ x, xs ]

Node.value = ([ value, _ ]) =>
  value

Node.children = ([ _, children ]) =>
  children

Далее мы создаем универсальный тип Iterator. Этот имитирует собственное итерируемое поведение, только наши итераторы являются постоянными (неизменяемыми)

// -- Empty ----------------------------------------------

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

// -- Iterator -------------------------------------------

const Yield = (value = Empty, it = Iterator ()) =>
  isEmpty (value)
    ? { done: true }
    : { done: false, value, next: it.next }

const Iterator = (next = Yield) =>
  ({ next })

const Generator = function* (it = Iterator ())
{
  while (it = it.next ())
    if (it.done)
      break
    else
      yield it.value
}

Наконец, мы можем реализовать PostorderIterator

const PostorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : Node.children (node)
            .reduceRight ( (it, node) => PostorderIterator (node, it)
                         , PostorderIterator (node, backtrack, true)
                         )
            .next ())

И мы можем видеть, как это работает с вашим tree здесь

// -- Demo ---------------------------------------------

const tree =
  Node ("a",
    Node ("b",
      Node ("e"),
      Node ("f",
        Node ("k"))),
    Node ("c"),
    Node ("d",
      Node ("g"),
      Node ("h"),
      Node ("i"),
      Node ("j")));

const postOrderValues =
  Array.from (Generator (PostorderIterator (tree)), Node.value)

console.log (postOrderValues)
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

Демонстрация программы

// -- Node ----------------------------------------------

const Node = (x, ...xs) =>
  [ x, xs ]
  
Node.value = ([ value, _ ]) =>
  value
  
Node.children = ([ _, children ]) =>
  children

// -- Empty ---------------------------------------------

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

// -- Iterator ------------------------------------------

const Yield = (value = Empty, it = Iterator ()) =>
  isEmpty (value)
    ? { done: true }
    : { done: false, value, next: it.next }
    
const Iterator = (next = Yield) =>
  ({ next })
  
const Generator = function* (it = Iterator ())
{
  while (it = it.next ())
    if (it.done)
      break
    else
      yield it.value
}

const PostorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : Node.children (node)
            .reduceRight ( (it, node) => PostorderIterator (node, it)
                         , PostorderIterator (node, backtrack, true)
                         )
            .next ())
            
// -- Demo --------------------------------------------              

const tree =
  Node ("a",
    Node ("b",
      Node ("e"),
      Node ("f",
        Node ("k"))),
    Node ("c"),
    Node ("d",
      Node ("g"),
      Node ("h"),
      Node ("i"),
      Node ("j")));

const postOrderValues =
  Array.from (Generator (PostorderIterator (tree)), Node.value)
  
console.log (postOrderValues)
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

Вариативное поле children делает алгоритм немного более сложным по сравнению с типом Node, который имеет только поля left и right.

Упрощенная реализация этих итераторов упрощает их сравнение. Написание поддержки вариативных дочерних элементов в других итераторах оставляется читателю в качестве упражнения.

// -- Node ---------------------------------------------

const Node = (value, left = Empty, right = Empty) =>
  ({ value, left, right })

// -- Iterators ----------------------------------------

const PreorderIterator = (node = Empty, backtrack = Iterator ()) =>
  Iterator (() =>
    isEmpty (node)
      ? backtrack.next ()
      : Yield (node,
          PreorderIterator (node.left,
            PreorderIterator (node.right, backtrack))))

const InorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : InorderIterator (node.left,
            InorderIterator (node,
              InorderIterator (node.right, backtrack), true)) .next ())

const PostorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : PostorderIterator (node.left,
            PostorderIterator (node.right,
              PostorderIterator (node, backtrack, true))) .next ())

И очень особенный LevelorderIterator, просто потому, что я думаю, ты справишься

const LevelorderIterator = (node = Empty, queue = Queue ()) =>
  Iterator (() =>
    isEmpty (node)
      ? queue.isEmpty ()
        ? Yield ()
        : queue.pop ((x, q) =>
            LevelorderIterator (x, q) .next ())
      : Yield (node,
          LevelorderIterator (Empty,
            queue.push (node.left) .push (node.right))))

// -- Queue ---------------------------------------------

const Queue = (front = Empty, back = Empty) => ({
  isEmpty: () =>
    isEmpty (front),
  push: x =>
    front
      ? Queue (front, Pair (x, back))
      : Queue (Pair (x, front), back),
  pop: k =>
    front ? front.right ? k (front.left, Queue (front.right, back))
                        : k (front.left, Queue (List (back) .reverse () .pair, Empty))
          : k (undefined, undefined)
})

// -- List ----------------------------------------------

const List = (pair = Empty) => ({
  pair:
    pair,
  reverse: () =>
    List (List (pair) .foldl ((acc, x) => Pair (x, acc), Empty)),
  foldl: (f, acc) =>
    {  
      while (pair)
        (acc = f (acc, pair.left), pair = pair.right)
      return acc
    }
})

// -- Pair ----------------------------------------------
const Pair = (left, right) =>
  ({ left, right })

Перепроектирован? Виновный. Вы можете заменить интерфейсы выше только на примитивы JavaScript. Здесь мы обмениваем ленивый поток на нетерпеливый массив значений.

const postOrderValues = (node = Empty, backtrack = () => [], visit = false) =>
  () => visit
      ? [ node, ...backtrack () ]
      : isEmpty (node)
        ? backtrack ()
        : Node.children (node)
            .reduceRight ( (bt, node) => postOrderValues (node, bt)
                         , postOrderValues (node, backtrack, true)
                         )
            ()

postOrderValues (tree) () .map (Node.value)
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

Mulan 23.03.2018

comment

Это великая инженерия. Однако я не уверен, что дополнительная сложность итераторов/генераторов как синтаксически, так и с точки зрения потока управления того стоит (как вы знаете, безопасность стека без совокупной стоимости владения может быть достигнута с помощью батутов). Понятность и простота — свойства, которые также следует учитывать разработчику. Речь идет о правильном балансе. - ; 24.03.2018

Рекурсивный обход дерева почтовых заказов без создания новых узлов

Ответы (2)

Похожие вопросы