Prolog, BST ağaçlarını inorder listesinden yeniden oluştur

BST ağacı için inorder uygulamasını iyi biliyoruz.Prolog, BST ağaçlarını inorder listesinden yeniden oluştur

inorder(nil, []). 
inorder(t(Root, L, R), List) :- 
    inorder(L, ListLeft), 
    inorder(R, ListRight), 
    append(ListLeft, [Root|ListRight], List).

Ancak, liste için bunu yapmak mümkün mü? Mümkün olan tüm BST ağaçlarını yeniden yapılandırmak istiyorum, örneğin:

inorder(X, [1,2,3]). 
X = t(1, nil, t(2, nil, t(3, nil, nil)))); 
X = t(3, t(2, t(1, nil, nil), nil), nil), nil); 
X = t(2, t(1, nil, nil), t(3, nil, nil)); 
false.

Benim için imkansız gibi görünüyor.

kaynak

2016-05-20 Anonymous

olabilir Gereken tek değişiklik isterseniz, olacak Sonunda DCG (Kesin Aletli Dilbilgisi) hakkında bilgi edinmek için, neden şimdi değil. Zaman ayırın ve Markus Triska tarafından yazılan [mükemmel primer] (https://www.metalevel.at/prolog/dcg.html) okuyun. Tam olarak bu soruna bir çözüm de dahil olmak üzere birçok altın külçeleri var. Bu bağlantı için –

teşekkürler. –

Öncelikle bize listelerine ağaçları ilişkilendirilmesi için bir Kesin Madde Dilbilgisi (dcg) kullanalım:

 
inorder(nil) --> []. 
inorder(t(Root, L, R)) --> 
    inorder(L), 
    [Root], 
    inorder(R).

Şimdi Taming Sol Özyineleme içinde Ulrich NEUMERKEL en dissertation açıklanan tabi tutacaktır hüner.

"... biz yeni karşılaşılan nonterminallerin tarafından kullanılabilecek jeton sayısı için başka devlet ekleyin. Tek bir kural dahilinde terminaller tarafından okunacaktır jeton sayısı dolayısıyla önceden saklıdır." Bizim durumumuzda

 
inorder(nil, Es, Es) --> []. 
inorder(t(Root, L, R), [_|Es0], Es) --> 
    inorder(L, Es0, Es1), 
    [Root], 
    inorder(R, Es1, Es).

Örnek sorgu (Ls atlanmış):

 
?- Ls = [1,2,3], phrase(inorder(Tree, Ls, _), Ls). 
Tree = t(1, nil, t(2, nil, t(3, nil, nil))) ; 
Tree = t(1, nil, t(3, t(2, nil, nil), nil)) ; 
Tree = t(2, t(1, nil, nil), t(3, nil, nil)) ; 
Tree = t(3, t(1, nil, t(2, nil, nil)), nil) ; 
Tree = t(3, t(2, t(1, nil, nil), nil), nil) ; 
false.

tür sorunları çözmek için başka bir yolu da Prolog sistemin tablolama mekanizmasını kullanmaktır.

kaynak

2016-05-20 12:03:17 mat

Lütfen alçakgönüllü olmayın ve bu yazımın çözümüne zaten sahip olan [DCG Primer] (https://www.metalevel.at/prolog/dcg.html) ile bağlantı kurmayın. –

Teşvik için teşekkürler. Bununla birlikte, özellikle ona bağlanan başkaları tarafından seviniyorum ve içeriği yaymak için bu yolu tercih ediyorum. Bu ayrıca bana gerçekten yararlı ve etrafta olmaya değer olduğuna dair bana güven veriyor. – mat

Söyle bana, 'Es1', inorder (L, Es0, Es1) 'tarafından kalan sembollerin kalanı? Sonra 'inorder (R, Es1, Es)' 'e değiniriz.': Es1'den daha fazla jeton kullanamazsınız. Geri kalanı "Es" olarak geri döner. Evet –

ben here önerdiğimiz hile, sen Prolog öğrenme konusunda ciddi iseniz

 
:- use_module(carlo(snippets/when_)).

inorder(t(Root, L, R), List) -:- ...

ve şimdi

?- inorder(T,[1,2,3]). 
T = t(1, nil, t(2, nil, t(3, nil, nil))) ; 
T = t(1, nil, t(3, t(2, nil, nil), nil)) ; 
T = t(2, t(1, nil, nil), t(3, nil, nil)) ; 
T = t(3, t(1, nil, t(2, nil, nil)), nil) ; 
T = t(3, t(2, t(1, nil, nil), nil), nil) ; 
false.

kaynak

2016-05-21 08:32:32 CapelliC

Prolog, BST ağaçlarını inorder listesinden yeniden oluştur

cevap

İlgili konular