Схема рекурсивного поиска дальнего левого узла дерева - PullRequest
Новая
       29

Схема рекурсивного поиска дальнего левого узла дерева

0 голосов
/ 14 февраля 2020

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

(define (far-left tree)
  (cond (null? (cadr tree))
        (car tree)
        (far-left (cdr tree))))

пример ввода, который дает много узлов, а не нужный: 

(display (far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))))

Ответы [ 2 ]

3 голосов
/ 14 февраля 2020

То, что вы называете «самым левым дочерним элементом первого узла», равно (cadr tree).
В вашей функции есть один (cadr tree), и это говорит о том, что первое условие всегда выполняется.
И это это то, что происходит. Форма

cond имеет вид 

(cond clause-1 clause-2 ...)

Каждый пункт в свою очередь имеет форму (condition value).

То есть 

(cond (condition-1 value-1)
      (condition-2 value-2)
      (condition-3 value-3)
      ...)

Если вы сопоставите это с вашей функцией, вы увидите, что

  • null? равно condition-1 и (cadr tree) равно value-1,
  • car равно condition-2 и tree равно value-2,
  • far-left равно condition-3 и (cdr tree) равно value-3.

С null? не #f, всегда выбирается первое предложение.

Правильная форма: 

(define (far-left tree)
    (cond
        ((null? (cadr tree)) (car tree))
        (else (far-left (cdr tree)))

Однако этот код по-прежнему не работает.
Исправление ошибок, оставленных как осуществление.

2 голосов
/ 14 февраля 2020

Определение данных : Tree

  • A Tree является либо Leaf, либо Node, где:
    • A Leaf является Number.
    • A Node - это непустой список под- Tree с.

Функция : far-left

  • Условие 1 : A Leaf в качестве ввода недопустимо, потому что мы должны найти «крайний левый» узел в любом дереве.
  • Условие 2 : если Node имеет Leaf в качестве самого левого (или first) элемента, то он это самый левый узел. Если самый левый элемент - это Tree, который не является Leaf, мы повторяем его. 
#lang typed/racket

(define-type Leaf Number)
(define-type Node (Pairof Tree (Listof Tree)))
(define-type Tree (U Leaf Node))

(: far-left (-> Tree Node))
(define (far-left tree)
  (cond [(number? tree) (error "Farthest left node of a leaf does not exist!")]
        [(cons? tree)   (if (number? (first tree)) tree (far-left (first tree)))]))

Тесты : 

(far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11)))
; =>  '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))

(far-left '((3 4 (6 7 (12 13))) 1  8 9 (10 11)))
; => '(3 4 (6 7 (12 13)))

(far-left '(((6 7 (12 13)) 3 4) 1  8 9 (10 11)))
; => '(6 7 (12 13))

(far-left '((((12 13) 6 7) 3 4) 1  8 9 (10 11)))
; => '(12 13)
...