Kaç dolaşımları

Question

herhangi bir kastetmek (pre, post veya in-order) veya bunlardan herhangi ikisinin bir kombinasyonundan bir Binary Search Tree inşa konusunda farklı sitelerde makalelerin bir sayısına göre çok karıştı bir BST inşa etmek bilinmesi gereken . Örneğin, this sayfasında, pre, post veya level sırası geçişi, in-order geçişi ile birlikte, BST'u oluşturabilir. Ancak here ve there, yalnızca 'u pre-order'dan yapmamızı sağlarlar. Ayrıca, here bize pre ve post-order geçişlerinden BST nasıl oluşturulacağını gösterir. Diğer bazı sitelerde, yalnızca post-order geçişinden BST oluşturmak için bir çözüm buldum.

Şimdi, bunun inorder ve pre-order geçişleri göz önüne alındığında, BST'u benzersiz şekilde oluşturduğunu biliyorum. Sağladığım ilk bağlantı ile ilgili olarak, pre-order ve post-order'dan BST'u oluşturamadıklarını söyleseler de, inorder traversal değerini almak için post-order dizisini sıralayamıyorum ve sonra bunu kullanmak için pre-order dizisini kullanamıyorum BST? 4. bağlantıdaki çözümle aynı mı yoksa farklı mı? Ve yalnızca pre-order verildiğinde, in-order almak için bunu sıralayabilirim, sonra BST almak için bu ve pre-order kullanın. Yine, bu 2 ve 3 numaralı bağlantılarda çözümden farklı mı olmalı?

Özellikle, BST'u benzersiz olarak oluşturmak için ne yeterlidir? Eğer gerekli değilse, o zaman in-order geçişini elde etmek için onu sıralayabilirim ve N'den bir BST s'yi tekrarlı olarak üretin.

Answer 1

Bir BST oluşturmak için yalnızca bir (sırasız) geçişe ihtiyacınız vardır. Genel olarak, bir ikili ağaç oluşturmak için, örneğin sırayla ve ön sipariş vermek için iki geçişe ihtiyacınız olacaktır. Ancak, BST'nin özel durumu için - sıralı geçiş, öğeleri içeren her zaman sıralanmış dizidir, böylece her zaman yeniden yapılandırabilir ve ön sipariş ve sıralı geçişlerden genel bir ağacı yeniden oluşturmak için bir algoritma kullanabilirsiniz. Bu nedenle, ağacın bir BST olduğunu ve içindeki öğelerin (sırasız bile olsa) bilgisi, sıralı bir geçişe eşdeğerdir.

Bonus: neden genel bir ağaç için bir traversal yeterli değil, (bilgi olmadan bir BST)?
Yanıt: n farklı öğeleri olduğunu varsayalım. Bu n öğelerine ait n! olası liste vardır, ancak - olası ağaç sayısı çok daha büyüktür (n = n elementlerin her biri için 2 * n! Olası ağaç, her düğümde node.right = null böyledir, ağaç aslında bir listedir sağa, n! gibi ağaçlar ve her zaman n 0 ağaçları vardır. Her zaman node.left = null) Güvercin deliği prensibinden - 2 ağaç üreten en az bir liste vardır, böylece ağacı tek bir traversalden yeniden yapılandıramayız. (QED)

Answer 2

BST düğümleri için değerler verilirse, verilerin geri kalanı düğümlerin değerleri tarafından sağlandığından yalnızca bir çaprazlama yeterlidir.Fakat eğer değerler bilinmiyorsa, benim anlayışım gereği, tek bir çaprazlamadan benzersiz bir BST'nin oluşturulması mümkün değildir. Ancak önerilere açığım.