İçeriğe geç

İkili ağaçlar

Ders 2 / 14 · 4 dk

İkili ağaçlar

Adım 1/11

İkili bir düğümün (node) tam iki çocuk (child) slot'u vardır: sol ve sağ. Asla üç değil.

Fikir

İkili ağaç her düğüme tam iki çocuk (child) slot'u verir: sol ve sağ. Slot'lardan biri boş kalabilir ve ikisi birbirinin yerine geçemez; yani yerlerini değiştirmek (swap) farklı bir ağaç üretir. Bir algoritmanın "sola git" deyip kesin bir şey kastedebilmesini sağlayan da bu sabit şekildir.

Gerçek hayattan örnek

Bir TV anteni dağıtıcısını düşün. Bir kablo girer, iki kablo çıkar; her çıkış başka bir dağıtıcıya ya da doğrudan bir televizyona gider. Hiçbir şey geri birleşmez ve iki soket fiziksel olarak farklıdır, yerlerini değiştirebileceğin bir çift değildir.

Kod

Sıra sende

Adımları doğru sıraya koy.

  1. Sol alt ağacı özyinelemeli olarak say
  2. Düğüm boşsa 0 döndür
  3. Bu düğüm için bir ekle ve toplamı döndür
  4. Sağ alt ağacı özyinelemeli olarak say

Mini quiz

1 / 3

İkili ağaçta bir düğümün kaç çocuğu olabilir?