Gerçek dünya sipariş öncesi/sonrası ağaç geçişi örnekleri

Question

Ön sipariş, sipariş ve sipariş sonrası ağaç geçiş algoritmalarını çok iyi anlıyorum. (Reference). Birkaç kullanımları anlıyorum: sıralı ikili ağaçların geçişi için sırayla, bir ağacı klonlamak için ön sipariş verin. Ama hayatım boyunca yapamayacağım post-order geçişe ihtiyaç duyacağım gerçek bir dünya görevi göremiyorum.

Bana bir örnek verebilir misiniz? Ve: ön sipariş geçişi için bana daha iyi kullanımlar verebilir misiniz?

Düzenleme: Herkes bana ifade ağaçları ve RPN dışında bir örnek verebilir mi? Bu gerçekten tüm sipariş sonrası için iyi mi?

Answer 1

Topological sorting ağaç (ya da yönlendirilmiş asiklik grafikler) içindeki bir sonrası geçişine olup.

fikri grafiğin düğümleri görevleri temsil B için A bir kenar AB önce yapılması gereken olduğunu gösterir olmasıdır. Topolojik bir sıralama, bu görevleri bir görevin bütün bağımlılıkları görevin kendisinden daha önce göründüğü şekilde düzenler. UNIX make gibi herhangi bir sistem, bu algoritmayı uygulamak zorundadır. el ile bir bellek yönetimi ile bir ağaç tüm düğümler yok - -

Dario belirtilen bu örnek

bu sorunun örneğidir. Sonuçta, bir düğümü yok etme görevi çocuklarının yok olmasına bağlıdır.

Answer 2

Sipariş emri derleyiciler tarafından kullanılmaktadır. a + b + c için bir ifade ağacı düşünün, makine dili a b + c + gibi bir dizi gerektirir. Buna Reverse polish Notation (RPN) denir. Vikipedi sayfasında şöyle der: "RPN aka Postfix" ön sipariş oluşturmak/onu klonlamak için gereklidir gibi

Sonrası düzen de, bir ağaç yok etmek için gereklidir.

Answer 3

olarak Henk Holterman sonrası düzen geçişi genellikle manuel bellek yönetimini kullanarak bir ağaç olan yok, dikkat çekti.

yalancı kod:

destroy(node) { 
    if (node == null) return; 

    destroy(node.left) 
    destroy(node.right) 

    // Post-order freeing of current node 
    free(node) 
}