A binary tree ni muundo wa tabaka ambao kila node ina zaidi ya watoto wawili, wanaitwa left na . Ina moja tu; nodi bila watoto ni . Ni msingi wa BST, heaps, na miti ya usemi.
A binary tree ni muundo wa tabaka ambao kila node ina zaidi ya watoto wawili, wanaitwa left na . Ina moja tu; nodi bila watoto ni . Ni msingi wa BST, heaps, na miti ya usemi.
right 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)
A level-order (BFS) kuvuka hutumia foleni na kutembelea kwa kina kwa kina.
| Traversal | Order | Common use |
|---|---|---|
| Inorder | L, N, R | sorted output of a BST |
| Preorder | N, L, R | copy/serialize a tree |
| Postorder | L, R, N | delete a tree, evaluate expr |
| Level-order | by depth | BFS, shortest path on tree |
Kila kuvuka kutembelea kila nodi mara moja → O(n) wakati, O(h) nafasi ya stack ambapo h ni urefu wa mti.
Miti ya binary inaiga kwa kawaida data inayojenga ngazi (mifumo ya faili, miti ya uchambuzi, miti ya maamuzi) na ni msingi wa miundo yenye ufanisi wa utafutaji na upangaji.
Kufahamiana na kuvuka kwa nne ni muhimu sana — matatizo mengi ya mti katika mahojiano ni tofauti ya moja yao.