Добавление узла в дерево в SML - PullRequest
Новая
       18

Добавление узла в дерево в SML

1 голос
/ 10 октября 2010

Мне посоветовали задать это как отдельный вопрос, так что я сделаю.

У меня есть дерево людей, как в генеалогии.Он начинается с человека и разветвляется на родителей, бабушек и дедушек и т. Д. Я хочу иметь возможность вставить человека в место на дереве (в основном заменяя того, кто там есть).

Эти типы данных важны: 

datatype year    = Year of int | UnkYear | Irrelevant
datatype name    = Name of string | UnkName
datatype sex     = Man | Woman | UnkSex
datatype person  = Person of name * sex * year * year
datatype parents = Dad | Mom
datatype tree    = Unspec | Info of person * tree * tree

Назначение выглядит следующим образом: Объявите функцию insert: tree * список родителей * person -> tree, чтобы вызывающий insert (t, pos, p) вставил человека p в pos-позицию вдерево я - при условии, что позиция существует в дереве.Если этого не произойдет, он должен вернуть t.

Так что мне нужно иметь возможность взять человека в моем дереве (скажем, мама) и заменить его Люси (мама и Люси оба предварительно объявленные значения, используятип данных).

Пока что у меня есть это: 

fun insert (Info(n,mf,ft) , Mom::xs , p) = Info(p, mf, insert(ft,xs,p))
  | insert (Info(n,mf,ft) , Dad::xs , p) = Info(p, insert(mf,xs,p), ft)
  | insert (Info(n,mf,ft) , [] , p)      = Unspec

Кажется, все, что нужно сделать - это удалить любого, кто находится в позиции t, и заменить корень на p - не совсем то, что яхотите, чтобы это делалось: S Кроме того, сопоставление с образцом не завершено.

Есть какие-нибудь идеи, чтобы заставить меня переехать сюда?

1 Ответ

3 голосов
/ 10 октября 2010

Хорошо, когда вы достигаете заданной позиции, вы хотите заменить человека в этой точке дерева на данного человека.То, что вы делаете, вы заменяете человека на каждом этапе пути, кроме случаев, когда вы достигнете места назначения, и в этом случае вы просто удаляете узел, который там находится.

Итак, что вам нужно сделатьis:

В случае, если список родителей еще не пуст, не заменяйте человека n на p - просто перейдите в соответствующее поддерево.

Вв случае, когда список родителей пуст, а вы в данный момент находитесь на информационном узле, замените человека в этом узле на p.

В случае, если список родителей пуст, и вы 'в настоящее время в Unspec-узле, замените Unspec новым Info-узлом, содержащим p и два пустых поддерева (т.е. Unspec s).

В случае, когда вы достигнете узла Unspec, хотясписок родителей еще не пуст, просто верните Unspec, сохранив дерево без изменений в соответствии с заданием.

...