代码之家  ›  专栏  ›  技术社区  ›  Fate Kyougo

球拍:二叉树的最大高度

  •  1
  • Fate Kyougo  · 技术社区  · 11 年前

    我正在尝试在球拍中创建一个代码,它可以在二元搜索树中找到从根到叶的最大距离。

    我已经在C++中看到过这一点,但我很难将其转换为球拍。 我已经计算了一棵树中的所有节点,但还没有单独计算路径。

    有什么建议吗?我已经看到了模板和所有这些,但仍然没有设法使一个工作。

    这是我迄今为止所尝试的

     (define-struct node (left right))
    
     (define (maxdepth tree)
        (cond 
              [(null? tree) 0]
              [ (> (size (node-left tree)) (size (node-right tree)))
                       (maxdepth (node-left tree))]
    [else (maxdepth (node-right tree))]))
    
    
      (define (size tree)
          (if (null? tree) 0
             (+ 1 (size (node-left tree)) (size (node-right tree)))))
    
    1 回复  |  直到 8 年前
        1
  •  3
  •   Óscar López    11 年前

    我们只需要一个函数- maxdepth ,我们只需要找到 max 每个子树的高度加上当前节点的高度:

    (define (maxdepth tree)
      (cond 
        [(null? tree) 0]
        [else (+ 1 (max (maxdepth (node-left  tree))
                        (maxdepth (node-right tree))))]))