ორობითი ხე არის იერარქიული სტრუქტურა, სადაც თითოეულ კვანძს აქვს მაქსიმუმ ორი შვილი, რომელსაც ეწოდება left და . მას აქვს ერთი ; კვანძებს, რომლებსაც შვილი არ აქვთ, ეწოდება. ეს არის BST-ების, გროვების და გამოხატულების ხეების საფუძველი.
ორობითი ხე არის იერარქიული სტრუქტურა, სადაც თითოეულ კვანძს აქვს მაქსიმუმ ორი შვილი, რომელსაც ეწოდება left და . მას აქვს ერთი ; კვანძებს, რომლებსაც შვილი არ აქვთ, ეწოდება. ეს არის BST-ების, გროვების და გამოხატულების ხეების საფუძველი.
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)
დონის მიხედვით (BFS) გავლა იყენებს რიგს და ვიზიტ ხდება სიღრმე-სიღრმეში.
| გავლა | რიგი | საერთო გამოყენება |
|---|---|---|
| ინორდერი | L, N, R | BST-ის დალაგებული გამოშედეგი |
| პრეორდერი | N, L, R | ხის კოპირება/სერიალიზება |
| პოსტორდერი | L, R, N | ხის წაშლა, გამოხატულების შეფასება |
| დონის მიხედვით | სიღრმეს მიხედვით | BFS, უმოკლესი გზა ხეზე |
თითოეული გავლა ვიზიტ ხდება თითოეულ კვანძს ერთხელ → O(n) დრო, O(h) სტეკის მეხსიერება, სადაც h არის ხის სიმაღლე.
ორობითი ხეები ბუნებრივად მოდელირებენ იერარქიული მონაცემებს (ფაილის სისტემები, ანალიზის ხეები, გადაწყვეტილების ხეები) და ეფუძნება ეფექტიან ძებნას და დახარისხების სტრუქტურებს.
ოთხი გავლის ათვისება აუცილებელია — ხის ინტერვიუს უმეტესი პრობლემა მათ ერთ-ერთი ვარიაციაა.