В Haskell как мне вернуть количество узлов в двоичном дереве?

Question

Определите для дерева двоичного типа дерева функцию, которая возвращает количество узлов. Я придумал эту функцию, но она не запускается.

Ошибка: за пределами области действия: конструктор данных "Узел"

numberOfNodes :: Tree -> Int
numberOfNodes Null = 0
numberOfNodes (Node _ st1 st2) = 1 + max (st1)(st2)

Answer 1

Первая проблема заключается в том, что вам не хватает определения того, что такое дерево.

Обычно мы говорим, что это либо узел со значением плюс два поддерева, либо он пустой.

Далее, наше рекурсивное определение количества узлов в (непустом) дереве должно быть:

number of nodes in left subtree + number of nodes in right subtree + 1

Вот полное определение:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
numberOfNodes :: Tree x -> Int
numberOfNodes Empty = 0
numberOfNodes (Node _ st1 st2) = 1 + numberOfNodes(st1) + numberOfNodes(st2)

(Обратите внимание, что мы реализуем класс типов Show, чтобы мы могли печатать дерево)

Если мы определим двоичное дерево с 3 узлами, посмотрите, как оно работает:

myTree :: Tree Int
myTree =
   Node 0
      (Node 1 Empty Empty)
      (Node 2 Empty Empty)

> numberOfNodes myTree => 3

Live Demo

Answer 2

Ошибка указывает, что вы не создали конструктор данных Node. Возможно, вы создали конструктор данных Tree, например:

data Tree a = Null | <s>Tree</s> a (Tree a) (Tree a)

с использованием Tree в качестве конструктора данных не является неправильным . Но вам нужно решить, каким будет имя, и использовать этот конструктор данных.

В любом случае вам не нужно определять функцию для подсчета количества элементов самостоятельно. Вы можете позволить Haskell сделать его экземпляром Foldable, а затем использовать length :: Foldable f => f a -> Int:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Null | Node a (Tree a) (Tree a) deriving (<b>Foldable</b>, Show)

Если мы, например, определим пример дерева, как @AndyG написал , мы можем вычислить число Node s как:

Prelude> length (Node 0 (Node 1 Null Null) (Node 2 Null Null))
3

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

numberOfNodes :: Tree -> Int
numberOfNodes Null = 0
numberOfNodes (Node _ st1 st2) = <b>1 + numberOfNodes st1 + numberOfNodes st2</b>

Answer 3

Кажется, у вас нет определения типа данных в области видимости. Вероятно, оно должно быть

data Tree a = Null | Node a (Tree a) (Tree a)

Кроме того, код, который вы показываете, вычисляет глубину дерева ^{(в принципе, после того, как оно исправлено)} . Общее количество узлов дерева равно сумме от количества узлов в его левом и правом поддеревьях, отдавать или брать 1; не max .

Пустые (лист, Null) узлы, вероятно, не должны учитываться, т. е. их вклад в общее число, вероятно, должен быть равен 0. Вы решаете.