Подсчет узлов в двух разных поддеревах в clojure

Question

Очень новый для Clojure, и у меня нет подсказки, как это сделать, мне нужно пересечь двоякое дерево поиска до конца и подсчитать количество узлов в 2 разностных поддеревях, как этот вопрос

https://uva.onlinejudge.org/external/116/11615.pdf

Спасибо за любую помощь на всех, просто нужно толчок, чтобы начать

(defn familytree [tree i x] 
    (cond 
    (= (first(tree) i)) 
     (count (zip/children)) 

    (= (first(tree) x)) 
     (count (zip/children)) 

    :else 
     (familytree (rest tree)x i) 
    )) 

Входные данные (def test1 '[ 1 [ 2 [ 4 [8 9 ] 5 [ 10 11 ]] 3 [ 6 [ 12 13 ] 7 [ 14 15 ]]]])

Answer 1

Cameron

Начните с принятием решения, которые Clojure настойчивого типа данных вы будете хранить информацию в только что решили:.

• Взгляните на Clojure zippers.
• Посмотрите на Clojure walk
• Как вы знаете о рекурсии, в зависимости от того, насколько велика дерево это, вы можете предпочесть отказаться от Somethings как молния для прямой прямой рекурсии. В этом случае могут применяться for, loop и reduce.

Обновлено

Вот мое понимание требований:

1. Входное дерево будет в векторном/вложенной векторной структуры
2. Каждый вектор в дереве имеет «узел идентификатор '(в вашем случае номер)
3. Требовать функцию, которая подсчитывает дочерние элементы для узла, когда узел соответствует некоторым критериям
4. Должна быть возможность указать несколько узлов, для которых имеет значение, будет возвращено

Учитывая, что я решил использовать zipper как это разумно демонстрирует разрыв вниз логики для достижения целей требование. Я также абстрагировал аспекты, чтобы сделать так, чтобы предикат для подсчета детей мог измениться.

Вам нужно будет прочитать на clojure.zip (есть множество информации о интер-сети для этого.

Счетчик Теперь, когда ядро ​​обход накрыт (zippers) позволяет начать с функция подсчета в соответствии с требованиями:., независимо от того, как я приезжаю в узле Я хочу, чтобы сосчитать детей узла:

(defn count-children-at-node 
    "Takes a zipper location and counts 
    elements of it's chidren vector. Uses flatten on the 
    children to sequence all the elements for counting. 
    Returns a tuple identifiying the node and it's children count" 
    [loc] 
    (let [cnodes (zip/right loc)] 
    [:node (zip/node loc) 
    :count (if (nil? cnodes) ; test for no children 
       0 
       (count (flatten (zip/node cnodes))))])) 

The ломовой Здесь происходит обход. Он будет исчерпывающим, чтобы найти все возможные узлы, представляющие интерес. Подсчет будет также включен (см. Результаты ниже).Я также хочу, чтобы аккумулировать свои результаты и имеет гибкую функцию предиката для проверки для включения в результатах:

(defn find-nodes-to-count 
    "Accumulate results of performing a reduction function on a node in 
    the tree that matches the predicate criteria" 
    [acc predfn redfn loc] 
    (if (zip/end? loc) 
    acc 
    (if (predfn (zip/node loc)) 
     (recur (conj acc (redfn loc)) predfn redfn (zip/next loc)) 
     (recur acc predfn redfn (zip/next loc))))) 

обертка С моими основными встречными и обходных механизмами в месте, используйте легкую функцию обертывания для физических упражнений ядро:

(defn nodes-counter 
    "Takes a tree collection and variable number of node identifiers 
    and return an accumulation of tuples, each identifying the node and it's children 
    count" 
    [coll & nodevals] 
    (find-nodes-to-count 
    []         ; accumultator 
    #(contains? (into #{} nodevals) %) ; predicate function 
    count-children-at-node    ; reduction function 
    (zip/vector-zip coll)))    ; the tree collection 

Тест/Проверка некоторых примеров Repl вызова nodes-counter с вариациями идентификатора узла:

(def mytree [1 [2 [4 [8 9] 5 [ 10 11 ]] 3 [ 6 [ 12 13 ] 7 [ 14 15 ]]]]) 

(nodes-counter mytree 16) ; => [] 
(nodes-counter mytree 15) ; => [[:node 15 :count 0]] 
(nodes-counter mytree 2 4) ; => [[:node 2 :count 6] [:node 4 :count 2]] 
(nodes-counter mytree 4 2) ; => [[:node 2 :count 6] [:node 4 :count 2]]