A binary tree என்பது ஒரு படிநிலை কட்டமைப்பு ஆகும், இதில் ஒவ்வொரு node க்கும் அதிகபட்சம் இரண்டு children உள்ளன, அவை left மற்றும் என்று அழைக்கப்படுகின்றன. இதில் ஒரே உள்ளது; குழந்தைகள் இல்லாத nodes . இது BST, heaps மற்றும் expression trees இன் அடிப்படை ஆகும்.
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) traversal ஒரு queue ஐ பயன்படுத்தி depth by depth ஐ பார்க்கிறது.
| 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 |
ஒவ்வொரு traversal ஆனது ஒவ்வொரு node ஐ ஒரு முறை பார்க்கிறது → O(n) time, O(h) stack space இதில் h என்பது ட்ரீயின் உயரம்.
பைனரி ட்ரீ இயல்பாகவே படிநிலை தரவுகளை (file systems, parse trees, decision trees) மாதிரிப்படுத்துகிறது மற்றும் திறமையான search மற்றும் sorting structures இன் அடிப்படை ஆகும்.
நான்கு traversals ஐ புரிந்துகொள்வது அவசியம் — பெரும்பாலான ட்ரீ interview problems அவற்றில் ஒன்றின் மாறுபாடு ஆகும்.