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

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

Типы данных:

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

Во-первых, мне нужно иметь возможность удалить кого-то из этой позиции и все, что находится под ней, поэтому удаление «Мамы» удалит маму и ее родителей, бабушек и дедушек и т. д. Если в вызываемой позиции нет человека, функция должна вернуть дерево . Это должно быть так: remove : Tree * parent list -> Tree и вызов remove(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 - если позиция не существует, она должна просто вернуть дерево. вставка: дерево * список родителей * человек -> дерево

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


tree sml
person GeorgeWChubby    schedule 08.10.2010    source источник
comment
Сейчас исправил, надеюсь, у меня все в порядке. n является корнем дерева и имеет тип person. Информация (n, mf, ft), Информация о человеке * дереве * дереве   -  person GeorgeWChubby    schedule 09.10.2010
comment
у кого-нибудь есть какие-либо указатели на замену элемента BST?   -  person CyprUS    schedule 02.11.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

person sepp2k    schedule 09.10.2010
comment
Огромное спасибо! Вы знаете, как я бы вставил человека в дерево (или вы можете подтолкнуть меня в правильном направлении)? - person GeorgeWChubby; 09.10.2010
comment
@George: Вероятно, вам следует задать это как отдельный вопрос с дополнительной информацией, в том числе: Куда вы хотите вставить нового человека? В соответствии с путем, как с удалить? Если да, то что должно произойти с человеком, который сейчас занимает эту должность? Или вы хотите разрешить вставку человека только на позицию, которая в настоящее время не определена? И самое главное: что у вас есть на данный момент? - person sepp2k; 09.10.2010
comment
Хороший вопрос, спасибо. Я сам еще немного поработаю, а если ничего не получится, вернусь сюда :) - person GeorgeWChubby; 09.10.2010