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

Question

Я новичок в эликсире, и у меня есть вопрос, что я в стеке

двоичное дерево

Реализация функции sum/1, которая принимает двоичное дерево и возвращаетсумма всех значений в дереве.Дерево представляется следующим образом:

 @type tree :: {:node, integer(), tree(), tree()} | nil

Answer 1

Попробуйте это.

@type tree :: {:node, integer(), tree(), tree()} | nil

def sum(nil), do: 0

def sum({:node, int, l, r}) do

  int + sum(l) + sum(r)

end

Answer 2

Пример обхода дерева по глубине в эликсире, который принимает функцию, которая должна быть выполнена на каждом узле, приведен в https://gist.github.com/kipcole9/43f9551e3c579a7d33e8daed10359c2c

По существу, задача разбита на две части:

1. Рекурсивно пройтись по дереву

2. Применить данную функцию, чтобы воздействовать на значение текущего узла, результат выполнения функции в левой ветви и результат выполнения функциина правой ветке

   defmodule Treewalk do
     @type tree :: {:node, integer(), tree(), tree()} | nil
   
     def depth({:node, value, nil, nil}, _fun) do
       value
     end
   
     def depth({:node, value, nil, right}, fun) do
       fun.(value, depth(right, fun), nil)
     end
   
     def depth({:node, value, left, nil}, fun) do
       fun.(value, depth(left, fun), nil)
     end
   
     def depth({:node, value, left, right}, fun) do
       fun.(value, depth(left, fun), depth(right, fun))
     end
   
     # The function to be run on each
     # node of the tree which is passed
     # the current value, the result of
     # running the funciton on the left
     # branch and the result of running
     # the function on the right branch
     def adder(a, b, nil) do
       a + b
     end
   
     def adder(a, b, c) do
       a + b + c
     end
   
     # Test tess
     def tree do
       {:node,
         1,
         {:node, 2,
           {:node, 4, nil, nil},
           nil
         },
         {:node, 3,
           nil,
           {:node, 4, nil, nil}
         }
       }
     end
   
     def sum(tree) do
       depth(tree, &adder/3)
     end
   
     # run a test, returns 14
     def test do
       depth(tree(), &adder/3)
     end
   end