Is crann dhénártha struchtúr ordlathach ann ina bhfuil dhá leanbh ar a mhéad ag gach nód, ar a dtugtar left agus . Tá singil aici; tugtar ar nódanna gan leanbhanna. Is é an bonn atá faoi BSTs, heaps, agus crann ionsúchain.
Is crann dhénártha struchtúr ordlathach ann ina bhfuil dhá leanbh ar a mhéad ag gach nód, ar a dtugtar left agus . Tá singil aici; tugtar ar nódanna gan leanbhanna. Is é an bonn atá faoi BSTs, heaps, agus crann ionsúchain.
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)
Úsáideann trasnú level-order (BFS) scuaine agus thaistil domhain ar dhomhain.
| Trasnú | Ord | Úsáid choitianta |
|---|---|---|
| Inorder | L, N, R | aschur sórtáilte de BST |
| Preorder | N, L, R | crann a chóipeáil/a shéaladh |
| Postorder | L, R, N | crann a scriosadh, ionsúchain a mheas |
| Level-order | de réir domhain | BFS, conair is gearr ar chrann |
Biseach gach nód a dtugann gach trasnú cuairt air — O(n) am, O(h) spás stac ina bhfuil h ina airde.
Déanann cranna dhénártha samhail ar shonraí ordlathach go nádúrtha (córais chomhaid, cranna phársála, cranna chinnteoireachta) agus bíonn siad mar bhun do struchtúir éadrom cuardaigh agus sórtála.
Bheith de dhíth air an ceithre trasnú a thuiscint go maith — is éagsúlacht a bhíonn i bhformhór na bhfadhbanna agus a raibh agallamh ann ar chrann de cheann díobh.
Leabharlann de cheisteanna agallaimh TF le freagraí mionsonraithe — ó Shóisearach go Sinsearach.
Síntiús