Написать программу для проверки двух деревьев на изоморфность - Prolog

include "binarytree.inc"
include "binarytree.con"
 
DOMAINS
   VAL = reference integer
   bin_tree = reference t(VAL,bin_tree,bin_tree); void
 
DATABASE - binarytree
   binary_tree1(bin_tree)
   binary_tree2(bin_tree)
   
PREDICATES
  get_startup_tree1(bin_tree)               %возвращает предопределённую структуру дерева
  get_startup_tree2(bin_tree)               %возвращает предопределённую структуру дерева
  collect_tree(STRING,TREELIST,TREE)
  get_tree(bin_tree,INTEGER,TREE)
  treelist_insert(TREE,TREELIST,TREELIST)       %добавляет дерево в список деревьев
 
  bin_tree_insert(integer,bin_tree,bin_tree)        %добавляет новое значение в бинарное дерево
  isotree(bin_tree, bin_tree)               %проверка изоморфности деревьев
CLAUSES
   get_startup_tree1(BinTree):-
    BinTree=t(5, t(4, t(1, void,
                   t(2, void,
                        t(3, void, void)
                     )
                ),
              void
              ),
                 t(7,t(6,void,void),
                     t(9,t(8,void,void),
                             t(12,void,void)
                           )
                       )
                  ).        
 
   get_startup_tree2(BinTree):-
    BinTree=t(5, t(7, t(9, t(12, void, void),
                   t(8, void, void)
               ),
              t(6, void, void)
              ),
                 t(4, void,
                      t(1, t(2, t(3, void, void),
                                void
                             ),
                           void)     
                       )
                  ).        
                  
  treelist_insert(TREE,[],[TREE]):-!.
  treelist_insert(_,[],[]):-!.
  treelist_insert(TREE,[H|T],[H|TNew]):-!,
    treelist_insert(TREE,T,TNew).
 
  collect_tree(NODE,[],tree(NODE,unmarked,[],0)):-!.
  collect_tree(NODE,TREEL,tree(NODE,unmarked,TREEL,0)):-!.
 
/* отображение пустой вершины для симметрии дерева */
  get_tree(void,_,TREE):-!,
    collect_tree("void",[],TREE). 
  get_tree(t(NODE, void, void),_,TREE):-!,
    str_int(StrNode, NODE),
    collect_tree(StrNode,[],TREE).
    
  get_tree(t(NODE,L,R),IdcTree,TREE):-!,
    get_tree(L,IdcTree,LTREE),
    treelist_insert(LTREE,[],TREEL),
    get_tree(R,IdcTree,RTREE),
    treelist_insert(RTREE,TREEL,TREELNew),
    str_int(StrNode, NODE),
    collect_tree(StrNode,TREELNew,TREE).    
  get_tree(_,_,tree("Other", unmarked, [], 0)):-!.
 
  %вставляем элемент в дерево 
  bin_tree_insert(Node,void,t(Node,void,void)):-!.
  bin_tree_insert(Node,t(Root,Left,Right),t(Root,LeftNew,Right)):-
    Node = Root,!,dlg_note("Такое значение уже есть в дереве!"),fail.
  bin_tree_insert(Node,t(Root,Left,Right),t(Root,LeftNew,Right)):-
     Node < Root,!,
     bin_tree_insert(Node,Left,LeftNew).
  bin_tree_insert(Node,t(Root,Left,Right),t(Root,Left,RightNew)):-
     Node > Root,!,
     bin_tree_insert(Node,Right,RightNew).

  %проверяем изоморфность
  isotree(void, void):-!.
  isotree(t(R, L1, R1), t(R, L2, R2)):-
    isotree(L1, L2), 
    isotree(R1, R2),
    !.
  isotree(t(R, L1, R1), t(R, L2, R2)):-
    isotree(L1, R2), 
    isotree(L2, R1),
    !.
PREDICATES
  pdctree_handler : EHANDLER         
 
CLAUSES
    
  %обработка события создания дерева
  pdctree_handler ( _Win, e_Create(_), 0 ) :- 
    CtrlId=win_GetCtlId(_Win),
    CtrlId=idc_tree1,
    !,
    binary_tree1(BinaryTree),
    get_tree(BinaryTree,CtrlId,Tree),
    TreeFont = font_Create ( ff_Times, [], 10 ),
    TreeWinInfo = tree_WinInfo ( TreeFont, tree_DirUp, [] ),
    tree_CreateSubClass( _Win, Tree, TreeWinInfo, [] ),
    fail.
  pdctree_handler ( _Win, e_Create(_), 0 ) :- 
    CtrlId=win_GetCtlId(_Win),
    CtrlId=idc_tree2,
    !,
    binary_tree2(BinaryTree),
    get_tree(BinaryTree,CtrlId,Tree),
    TreeFont = font_Create ( ff_Times, [], 10 ),
    TreeWinInfo = tree_WinInfo ( TreeFont, tree_DirUp, [] ),
    tree_CreateSubClass( _Win, Tree, TreeWinInfo, [] ),
    fail.
  %обработка пользовательского события (обновление дерева)
  pdctree_handler ( _Win, e_User(_,_), Return ):-
    CtrlId=win_GetCtlId(_Win),
    CtrlId=idc_tree1,
    !,
    Return=cast(long,CtrlId),       
    binary_tree1(BinaryTree),
    get_tree(BinaryTree,CtrlId,Tree),
    tree_Update( _Win, Tree, []),
    !.
  pdctree_handler ( _Win, e_User(_,_), Return ):-
    CtrlId=win_GetCtlId(_Win),
    CtrlId=idc_tree2,
    !,
    Return=cast(long,CtrlId),       
    binary_tree2(BinaryTree),
    get_tree(BinaryTree,CtrlId,Tree),
    tree_Update( _Win, Tree, []),
    !.
  pdctree_handler ( W, e_MouseDbl ( _, _, _ ), 0 ):-!,
    tree_OpenCloseNode ( W ),
    !.
        
%autogenerate code  
%BEGIN_WIN Task Window
/***************************************************************************
        Event handling for task window
***************************************************************************/
 
PREDICATES
 
  task_win_eh : EHANDLER
 
CONSTANTS
 
%BEGIN Task Window, CreateParms, 19:47:05-2.10.2005, Code automatically updated!
  task_win_Flags = [wsf_SizeBorder,wsf_TitleBar,wsf_Close,wsf_ClipSiblings,wsf_ClipChildren]
  task_win_Menu  = no_menu
  task_win_Title = "BinaryTree"
  task_win_Help  = idh_contents
%END Task Window, CreateParms
 
CLAUSES
 
%BEGIN Task Window, e_Create
  task_win_eh(_Win,e_Create(_),0):-!,
%end autogenerate code  
    retractall(binary_tree1(_)),
    get_startup_tree1(BinaryTree1),
    assert(binary_tree1(BinaryTree1)),
    retractall(binary_tree2(_)),
    get_startup_tree2(BinaryTree2),
    assert(binary_tree2(BinaryTree2)),
    class_Create("PDCTREE",pdctree_handler),
%autogenerate code  
%BEGIN Task Window, InitControls, 19:47:05-2.10.2005, Code automatically updated!
    win_CreateDynControl([customctl(wdef(wc_Custom,rct(20,28,280,270),"Tree",u_Pixels),"PDCTREE",idc_tree1,[wsf_Group,wsf_TabStop,wsf_Transparent])],_Win),
    win_CreateControl(wc_PushButton,rct(458,333,554,357),"Закрыть",_Win,[wsf_Group,wsf_TabStop],idc_ok),
    win_CreateControl(wc_PushButton,rct(127,300,202,324),"Добавить",_Win,[wsf_Group,wsf_TabStop],idc_add1),
    win_CreateControl(wc_Text,rct(23,274,202,295),"Добавление нового эл-та:",_Win,[wsf_AlignCenter],idct_label3),
    win_CreateControl(wc_Edit,rct(23,298,111,322),"",_Win,[wsf_Group,wsf_TabStop,wsf_AutoHScroll,wsf_AlignLeft],idc_new1),
    win_CreateControl(wc_Text,rct(24,4,274,23),"Дерево 1",_Win,[wsf_AlignCenter,wsf_NoClipSiblings],idc_label1),
    win_CreateControl(wc_PushButton,rct(211,271,279,295),"Очистить",_Win,[wsf_Group,wsf_TabStop],idc_clear1),
    win_CreateControl(wc_PushButton,rct(400,301,475,325),"Добавить",_Win,[wsf_Group,wsf_TabStop],idc_add2),
    win_CreateControl(wc_Edit,rct(296,299,384,323),"",_Win,[wsf_Group,wsf_TabStop,wsf_AutoHScroll,wsf_AlignLeft],idc_new2),
    win_CreateControl(wc_PushButton,rct(484,272,552,296),"Очистить",_Win,[wsf_Group,wsf_TabStop],idc_clear2),
    win_CreateControl(wc_Text,rct(296,275,475,296),"Добавление нового эл-та:",_Win,[wsf_AlignCenter],idc_label4),
    win_CreateControl(wc_Text,rct(297,5,547,24),"Дерево 2",_Win,[wsf_AlignCenter,wsf_NoClipSiblings],idc_label2),
    win_CreateDynControl([customctl(wdef(wc_Custom,rct(293,29,553,271),"Tree",u_Pixels),"PDCTREE",idc_tree2,[wsf_Group,wsf_TabStop,wsf_Transparent])],_Win),
    win_CreateControl(wc_PushButton,rct(244,334,340,358),"Изоморфны?",_Win,[wsf_Group,wsf_TabStop],idc_изоморфны),
%END Task Window, InitControls
IFDEF use_message
    msg_Create(100),
ENDDEF
    !.
 
%END Task Window, e_Create
 
%MARK Task Window, new events
 
%BEGIN Task Window, idc_изоморфны _CtlInfo
  task_win_eh(_Win,e_Control(idc_изоморфны,_CtrlType,_CtrlWin,_CtlInfo),0):-
    binary_tree1(T1),                   %взяли ранее сохранённое дерево
    binary_tree2(T2),
    isotree(T1,T2),
    !,
    dlg_MessageBox("Проверка изоморфности", "Деревья изоморфны", 
      mesbox_iconInformation, mesbox_buttonsOK, mesbox_defaultFirst,
      mesbox_suspendApplication),
    !.
 
  task_win_eh(_Win,e_Control(idc_изоморфны,_CtrlType,_CtrlWin,_CtlInfo),0):-!,
    dlg_MessageBox("Проверка изоморфности", "Деревья неизоморфны", 
      mesbox_iconInformation, mesbox_buttonsOK, mesbox_defaultFirst,
      mesbox_suspendApplication),
    !.
%END Task Window, idc_изоморфны _CtlInfo
 
%BEGIN Task Window, idc_clear2 _CtlInfo
  task_win_eh(_Win,e_Control(idc_clear2,_CtrlType,_CtrlWin,_CtlInfo),0):-!,
    retractall(binary_tree2(_)),
    assert(binary_tree2(void)),
    TreeCtrlWin =win_GetCtlHandle(_Win,idc_tree2),
    win_SendEvent(TreeCtrlWin,e_User(0,0)),
    !.
%END Task Window, idc_clear2 _CtlInfo
 
%BEGIN Task Window, idc_add2 _CtlInfo
task_win_eh(_Win,e_Control(idc_add2,_CtrlType,_CtrlWin,_CtlInfo),0):-
    %получение имени нового узла
    EditCtrlWin = win_GetCtlHandle(_Win, idc_new2), %идентификатор контрола NewNode
    Text=win_GetText(EditCtrlWin),              %значение из поля NewNode
    Text = "",
    dlg_note("Введите значение узла!"),!.
    task_win_eh(_Win,e_Control(idc_add2,_CtrlType,_CtrlWin,_CtlInfo),0):-
    %получение имени нового узла
    EditCtrlWin = win_GetCtlHandle(_Win, idc_new2), %идентификатор контрола NewNode
    Text=win_GetText(EditCtrlWin),              %значение из поля NewNode
    Text <> "",                     %значение должно быть непустым
    not(str_int(Text, _)),
    dlg_note("Значение узла должно быть целым числом!"),!.
  task_win_eh(_Win,e_Control(idc_add2,_CtrlType,_CtrlWin,_CtlInfo),0):-!,
    %получение имени нового узла
    EditCtrlWin = win_GetCtlHandle(_Win, idc_new2), %идентификатор контрола NewNode
    Text=win_GetText(EditCtrlWin),              %значение из поля NewNode
    Text <> "",                     %значение должно быть непустым
    str_int(Text, Val),                 %значение должно быть целым
    !,
    win_SetText(EditCtrlWin,""),                %очистка поля NewNode
    binary_tree2(TempTree),                 %взяли ранее сохранённое дерево
    bin_tree_insert(Val, TempTree, BinaryTree),     %вставили новый узел
    retractall(binary_tree2(_)),                %очистили все значения
    assert(binary_tree2(BinaryTree)),           %сохранили новое значение
    %обновление контрола, отображающего дерево
    TreeCtrlWin =win_GetCtlHandle(_Win,idc_tree2),      
    win_SendEvent(TreeCtrlWin,e_User(0,0)),
    !.
  task_win_eh(_Win,e_Control(idc_add2,_CtrlType,_CtrlWin,_CtlInfo),0):-!,
    dlg_error("Введите целое число."),
    !.
%END Task Window, idc_add2 _CtlInfo
 
%end autogenerate code  
%BEGIN Task Window, idc_add1 _CtlInfo
 task_win_eh(_Win,e_Control(idc_add1,_CtrlType,_CtrlWin,_CtlInfo),0):-
    %получение имени нового узла
    EditCtrlWin = win_GetCtlHandle(_Win, idc_new1), %идентификатор контрола NewNode
    Text=win_GetText(EditCtrlWin),              %значение из поля NewNode
    Text = "",  
    dlg_note("Введите значение узла!"),!.
    
    task_win_eh(_Win,e_Control(idc_add1,_CtrlType,_CtrlWin,_CtlInfo),0):-
    %получение имени нового узла
    EditCtrlWin = win_GetCtlHandle(_Win, idc_new1), %идентификатор контрола NewNode
    Text=win_GetText(EditCtrlWin),              %значение из поля NewNode
    Text <> "",                     %значение должно быть непустым
    not(str_int(Text, _)),
    dlg_note("Значение узла должно быть целым числом!"),!.
    
  task_win_eh(_Win,e_Control(idc_add1,_CtrlType,_CtrlWin,_CtlInfo),0):-
    %получение имени нового узла
    EditCtrlWin = win_GetCtlHandle(_Win, idc_new1), %идентификатор контрола NewNode
    Text=win_GetText(EditCtrlWin),              %значение из поля NewNode
    Text <> "",                     %значение должно быть непустым
    str_int(Text, Val),                 %значение должно быть целым
    !,
    win_SetText(EditCtrlWin,""),                %очистка поля NewNode
    binary_tree1(TempTree),                 %взяли ранее сохранённое дерево
    bin_tree_insert(Val, TempTree, BinaryTree),     %вставили новый узел
    retractall(binary_tree1(_)),                %очистили все значения
    assert(binary_tree1(BinaryTree)),           %сохранили новое значение
    %обновление контрола, отображающего дерево
    TreeCtrlWin =win_GetCtlHandle(_Win,idc_tree1),      
    win_SendEvent(TreeCtrlWin,e_User(0,0)),
    !.
%END Task Window, idc_add1 _CtlInfo
 
%BEGIN Task Window, idc_clear1 _CtlInfo
  task_win_eh(_Win,e_Control(idc_clear1,_CtrlType,_CtrlWin,_CtlInfo),0):-!,
    retractall(binary_tree1(_)),
    assert(binary_tree1(void)),
    TreeCtrlWin =win_GetCtlHandle(_Win,idc_tree1),
    win_SendEvent(TreeCtrlWin,e_User(0,0)),
    !.
%END Task Window, idc_clear1 _CtlInfo
 
%BEGIN Task Window, idc_ok _CtlInfo
  task_win_eh(_Win,e_Control(idc_ok,_CtrlType,_CtrlWin,_CtlInfo),0):-!,
    retractall(_, binarytree),
    win_Destroy(_Win),
    !.
%END Task Window, idc_ok _CtlInfo
 
%BEGIN Task Window, e_Destroy
  task_win_eh(_Win,e_Destroy,0):-!,
    class_Destroy("PDCTREE"),
    !.
%END Task Window, e_Destroy
 
%autogenerate code
%BEGIN Task Window, e_Update
  task_win_eh(_Win,e_Update(_UpdateRct),0):-!,
    win_Clear(_Win,color_White),
    !.
%END Task Window, e_Update
 
%BEGIN Task Window, e_Size
  task_win_eh(_Win,e_Size(_Width,_Height),0):-!,
    !.
%END Task Window, e_Size
 
/***************************************************************************
            Main Goal Project
***************************************************************************/
 
GOAL
 
IFDEF use_mdi
  vpi_SetAttrVal(attr_win_mdi,b_true),
ENDDEF
IFDEF use_3dctrl
  vpi_SetAttrVal(attr_win_3dcontrols,b_true),
ENDDEF
IFDEF use_tbar
  vpi_SetAttrVal(attr_win_tbar,use_tbar),
ENDDEF
IFDEF use_sbar
  vpi_SetAttrVal(attr_win_sbar,use_sbar),
ENDDEF
  vpi_Init(task_win_Flags,task_win_eh,task_win_Menu,"binarytree",task_win_Title).
 
%END_WIN Task Window

domains 
treetype = tree(symbol, treetype, treetype);nil  
predicates 
isotree (treetype, treetype) 
clauses 
isotree (T, T). 
isotree (tree (X,L1, R1), 
tree (X, L2, R2)):- isotree 
(L1, L2), isotree (R1, 
R2). 
isotree (tree (X, L1, R1), 
tree (X, L2, R2)):- isotree 
(L1, R2), isotree (L2, 
R1). 
 
    goal      
       isotree(tree("a",tree("b",tree("d",nil,nil),tree("e",nil,  
    nil)),tree("c",nil,nil)),      
                tree("a",tree("b",tree("d",nil,nil),tree("e",nil,  
    nil)),tree("c",nil,nil))),  
    write("true").