Нахождение количества узлов в 2-3 дереве в SML

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

Дерево 2-3 - это дерево, в котором каждый нелистовой узел может иметь двух или трех дочерних элементов, а все поддеревья узла имеют одинаковую высоту. Если мы проигнорируем условие высоты поддеревьев, мы можем сделать следующее определение типа SML:

тип данных ’a twoThreeTree = | Пустой

| Двоичный из ’a *’ a twoThreeTree * ’a twoThreeTree

| Ternary of ’a *’ a twoThreeTree * ’a twoThreeTree *’ a twoThreeTree;

а. Напишите рекурсивную функцию N, которая вычисляет количество узлов в 2–3 дереве.

б. Напишите рекурсивную функцию ht, которая вычисляет высоту 2-3-х деревьев. (По аналогии с бинарными деревьями сделайте высоту пустого дерева равной -1.

Во всяком случае, все, что мне нужно, - это помощь с частью а. Думаю, я мог бы использовать то, что я узнал из а), для выполнения б).


tree sml treenode
person emdz0128    schedule 06.11.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Это должно помочь с (а).

fun N(Empty)            = 0
  | N(Binary(_,x,y))    = 1 + (N(x)) + (N(y))
  | N(Ternary(_,x,y,z)) = 1 + (N(x)) + (N(y)) + (N(z))

Мы предполагаем, что количество узлов для Empty равно 0, и для каждого из других типов узлов мы считаем сам узел и количество других узлов.

Для b вместо того, чтобы складывать вещи вместе. Подумайте, как вы определяете высоту следующего дерева

         NODE
         / \
LEFT_TREE   RIGHT_TREE

Если LEFT_TREE имеет высоту H_left, а RIGHT_TREE имеет высоту H_right. Можете ли вы выразить высоту всего дерева как функцию от H_left и H_right? Что, если бы у дерева было трое детей?

fun ht(Empty)            = -1
  | ht(Binary(_,x,y))    = ...
  | ht(Ternary(_,x,y,z)) = ...
person Jon    schedule 06.11.2014