Binar tree shi ne tsarin da ke da wata tsari inda kowane node zai iya samun {{CODE_1}} fiye da yara biyu, wanda ake kira left da right. Yana da gida guda kawai; nodes waɗanda ba su da yara ne ganye. Shi ne tushen BSTs, heaps, da expression trees.
1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
Level-order (BFS) zagaye yana amfani da queue kuma yana ziyarci zurfin-zurfin.
| Zagaye | Jeri | Amfani da gida |
|---|---|---|
| Inorder | L, N, R | fifo output na BST |
| Preorder | N, L, R | kwafi/serialize tree |
| Postorder | L, R, N | share tree, kimanta expr |
| Level-order | by zurfin | BFS, hanyar tafiya tree |
Kowane zagaye yana ziyarci kowane node sau guda → O(n) lokaci, O(h) sararin stack inda h shine tsayi na binar tree.
Binar trees suna tunani abubuwan da ke da tsari inda hankali ake bukata (jerin fayil, trees na fassara, jinya-jinya na kwamanda) kuma suna tushen tsarin neman kayan aiki da shirya.
Samun gari a zagaye hudu na gida yana da mahimmanci sosai — yawancin matsalolin ziyarci na tree sune canji na gida daga juna.