Veri Yapısı ve Algoritmalar - Ağaç Çaprazlama

Geçiş, bir ağacın tüm düğümlerini ziyaret etme işlemidir ve değerlerini de yazdırabilir. Çünkü, tüm düğümler kenarlar (bağlantılar) aracılığıyla birbirine bağlıdır, biz her zaman kök (baş) düğümden başlarız. Yani, bir ağaçtaki bir düğüme rastgele erişemeyiz. Bir ağacı geçmek için kullandığımız üç yol vardır -

  • Sıralı Geçiş
  • Geçiş Ön Siparişi Ver
  • Sipariş Sonrası Geçiş

Genel olarak, ağaçtaki belirli bir öğeyi veya anahtarı aramak veya bulmak veya içerdiği tüm değerleri yazdırmak için bir ağaçtan geçiyoruz.

Sıralı Geçiş

Bu geçiş yönteminde önce sol alt ağaç, ardından kök ve daha sonra sağ alt ağaç ziyaret edilir. Her düğümün bir alt ağacın kendisini temsil edebileceğini her zaman hatırlamalıyız.

Bir ikili ağaç geçilirse in-orderçıktı, artan sırada sıralı anahtar değerleri üretecektir.

Başlıyoruz Ave sırayla geçişi takiben, sol alt ağacına geçiyoruz B. Bsırayla da geçilir. İşlem, tüm düğümler ziyaret edilene kadar devam eder. Bu ağacın sıralı geçişinin çıktısı -

D → B → E → A → F → C → G

Algoritma

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Geçiş Ön Siparişi Ver

Bu geçiş yönteminde, önce kök düğüm, ardından sol alt ağaç ve son olarak sağ alt ağaç ziyaret edilir.

Başlıyoruz Ave ön sipariş geçişini takiben ilk olarak A kendisi ve sonra sol alt ağacına B. Bayrıca ön sipariş üzerinden geçilir. İşlem, tüm düğümler ziyaret edilene kadar devam eder. Bu ağacın ön sipariş geçişinin çıktısı -

A → B → D → E → C → F → G

Algoritma

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Sipariş Sonrası Geçiş

Bu çapraz geçiş yönteminde, en son kök düğüm, dolayısıyla adı ziyaret edilir. Önce soldaki alt ağaçtan, sonra sağ alt ağaçtan ve son olarak da kök düğümü geçiyoruz.

Başlıyoruz Ave Sipariş sonrası geçişi takiben, ilk olarak soldaki alt ağacı ziyaret ediyoruz B. Bayrıca sipariş sonrası da aktarılır. İşlem, tüm düğümler ziyaret edilene kadar devam eder. Bu ağacın sipariş sonrası geçişinin çıktısı -

D → E → B → F → G → C → A

Algoritma

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Ağaç geçişinin C uygulamasını kontrol etmek için lütfen buraya tıklayın .