Удаление и добавление узлов в дерево - PullRequest
Новая
       25

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

3 голосов
/ 09 октября 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

Сначала я должен иметь возможность удалить кого-либо из этой позиции и все, что находится "под ней", поэтому удаление "Мамы" приведет к удалению мамы и ее родителей, бабушек и дедушек и т. Д. Если в названной должности нет никого, функция верни дерево. Это должно быть так: удалить: дерево * список родителей -> дерево и вызов удалить (t, pos)

Это то, что у меня есть, но это не совсем верно. Мне сказали, что я могу сделать это в 4 строки. 

fun replace (Info(n,mf,ft) , Mom::[]) = Info(n,replace(mf,[]),Unspec)
  | replace (Info(n,mf,ft) , Dad::[]) = Info(n,Unspec,replace(ft,[]))
  | replace (Info(n,mf,ft) , [])      = Info(n,mf,ft)
  | replace (Info(n,mf,ft) , Mom::xs) = Info(n,replace(mf,[]),replace(ft,xs))
  | replace (Info(n,mf,ft) , Dad::xs) = Info(n,replace(mf,xs),replace(ft,[]))
  | replace (Unspec , x::xs)          = Unspec
  | replace (Unspec , [])             = Unspec;

У меня есть идея: 

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

Но это не правильно. Что мне делать?

Я также должен иметь возможность вставить человека p в дерево t в позиции pos - если позиция не существует, он должен просто вернуть дерево. вставить: дерево * список родителей * человек -> дерево

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

1 Ответ

2 голосов
/ 09 октября 2010

(Повторно, поскольку мой предыдущий ответ, по-видимому, не выдержал краха БД).

Вы берете главу списка, чтобы решить, следует ли переходить в поддерево матери или отцу. Это правильно. Затем вы используете хвост списка в качестве остальной части пути. Это тоже правильно. Однако, когда список пуст (т. Е. Вы достигли пункта назначения), вы делаете это: 

| remove (Info(n,mf,ft) , [])      = Info(n,mf,ft)

Другими словами: ничего. Если вы измените это на: 

| remove (Info(n,mf,ft) , [])      = Unspec

Он будет работать как положено, заменив Узел дерева, к которому ведет вас ваш путь, на Unspec.

...