Kayıtlar

CP #46: Binary Tree Problemleri 2

Resim
7. Implement In-Order Traversal Without Recursion Recursion kullanmadan, verilen bir binary tree'yi in-order seklinde traverse ederek, node degerlerini bir array icerisinde dondurunuz. Cozum Recursion kullandigimiz cozumde, ust uste revuesive fonksiyon cagrilari yaptigimizda, aslinda bizim icin bunlarin sirasini tutan bir system call stack var. Bunu simule etmek iyi bir baslangic olabilir. Adi uzerinde zaten, en son cagri yapilan fonksiyon ilk donecek olandir. Yani stack yapisi.  def inorder_non_recursive(tree):     # traverse ettigimiz degerleri tutacagimiz array     ret = []       # call-stack simulatoru     stack = []     # root node'dan basliyoruz     cur = tree     # stack'te bisey kalmadigi zaman ve de cur de None oldugu zaman     # traversal bitmis demektir.     while cur or stack:          # eger cur pointeri None degil ise          # sol subtree'ye gitmemiz gerek           if cur:               stack.append(cur)               cur = cur.left          else:     

CP #45: Binary Tree Problemleri 1

Resim
Binary Tree Birkac noktayi hatirlatalim: Her bir node sadece tek bir parent'e sahiptir. Bazi implementasyonlarda node icinde parent bilgisi de tutulmaktadir. Bu sayede time ve space compl. azaltilabilir. Akilda tutmakta yarar var. Search path: Tree'nin root node'undan, bir node kadar olan cizgi uzerindeki node'lardan olusan sequence'a o node'un search path'i adi verilir.  Bir node'un search path'inda bulunan tum node'lar, o node'un ancestor (atasi) olarak tanimlanir. Bir node'un da altinda bulunan tum node'lar descendant olarak adlandirilir. Full binary tree: Leaf node'lar haric tum node'lari 2 eleman iceren binary treedir Perfect binary tree: Tum node'lari 2 child iceren ve tum leaf node'larin depth degeri esit olan, yani kisaca full + full binary treedir.  2^(h+1)-1 node icermektedir ki h, full bintree'nin yuksekligidir. verilen h yuksekligi icin bir full bintree, log(h) eleman icermektedir.  2^h kadar leaf node