CODEWITHSUNDEEP
schemeracket
user2113651
user2113651

Reputation: 153

binary trees searching inside

Can anyone tell me what I need to do here?

(define (count-values abst v)
  (cond [(empty? abst) 0]
        [else (+ (cond [(equal? v (bae-fn abst)) 1]
                       (else 0))
                 (count-values .... v)
                 (count-values .... v ))]))

I basically need a function that counts the amount of symbols v inside a binary tree

(define bae
  (make-bae '+
            (make-bae '* (make-bae '+ 4 1)
                      (make-bae '+ 5 2))
            (make-bae '- 6 3)))
(count-values bae '+) => 3

because there are 3 '+ in bae

Upvotes: 0

Views: 114

Answers (2)

GoZoner
GoZoner

Reputation: 70135

If you define your data structure recursively, then a recursive count algorithm will naturally arise:

;; Utils
(define (list-ref-at n)
  (lambda (l) (list-ref l n)))
(define (eq-to x)
  (lambda (y) (eq? x y)))

;; Data Type    
(define (make-bae op arg1 arg2)
  `(BAE ,op, arg1, arg2))
(define (bae? thing) 
  (and (list? thing) (eq? 'BAE (car thing)) (= 4 (length thing))))
(define bae-op   (list-ref-at 1))
(define bae-arg1 (list-ref-at 2))
(define bae-arg2 (list-ref-at 3))

;; Walk
(define (bae-walk func bae)  ;; 'pre-ish order'
  (if (not (bae? bae))
      (func bae)
      (begin
        (func (bae-op bae))
        (bae-walk func (bae-arg1 bae))
        (bae-walk func (bae-arg2 bae)))))

;; Count
(define (bae-count-if pred bae)
  (let ((count 0))
    (bae-walk (lambda (x) 
                 (if (pred x) 
                     (set! count (+ 1 count))))
              bae)
     count))

(define (bae-count-if-plus bae)
  (bae-count-if (eq-to '+) bae))

> bae
(BAE + (BAE * (BAE + 4 1) (BAE + 5 2)) (BAE - 6 3))

> (bae-count-if-plus bae)
3

;; Find
(define (bae-find-if pred bae)
  (call/cc (lambda (exit)
             (bae-walk (lambda (x)
                         (if (pred x) (exit #t)))
                       bae)
             #f)))

Upvotes: 0

Óscar López
Óscar López

Reputation: 235994

You need to:

  1. Post the definition of the tree - I'm guessing bae is a struct - don't assume we know your code, post all the relevant information as part of the question
  2. Make sure that the code you post works at least in part - for instance, the (define bae ...) part won't work even if you provided the definition of bae, because of a naming conflict
  3. Follow the recipe for traversing a binary tree, I bet it's right in the text book

The general idea for the solution goes like this, without taking a look at the actual implementation of the code you've done so far is the only help I can give you:

  1. If the tree is empty, then return 0
  2. If the current element's value equals the searched value, add 1; otherwise add 0
  3. Either way, add the value to the result of recursively traversing the left and right subtrees

Upvotes: 1

Related Questions