درخت های دودویی (Binary Trees)
«درخت دودویی (Binary Tree)» نوعی درخت است که هر «گره (Node)» حداکثر دو فرزند دارد؛ چپ و راست. این محدودیت، الگوریتم ها را ساده و سریع می کند.
ایده درخت های دودویی
با دو فرزند، درج و حذف ساده تر می شود. همچنین مرتب سازی و جستجو بهتر می شود. زیرا مسیرها واضح تر هستند.
- پیمایش، جستجو، درج و حذف آسان تر و سریع تر است.
- درخت جستجوی دودویی، جستجو را بسیار کارآمد می کند.
- متعادل سازی روی دو فرزند ساده تر انجام می شود.
- می توان نمایش آرایه ای هم داشت و حافظه صرفه جو شد.
پیاده سازی پایه درخت دودویی
مثل لیست پیوندی است؛ اما هر گره دو اشاره گر دارد: left و right.
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD
nodeB.left = nodeE
nodeB.right = nodeF
nodeF.left = nodeG
print("root.right.left.data:", root.right.left.data)
پیمایش درخت دودویی
«پیمایش (Traversal)» یعنی بازدید همه گره ها با ترتیب مشخص. دو خانواده معروف داریم: «BFS» در عرض، و «DFS» در عمق.
پیش سفری (Pre-order) — DFS
الگو: ریشه، چپ، راست. برای کپی درخت و نمایش پیشوندی کاربردی است.
def preOrderTraversal(node):
if node is None:
return
print(node.data, end=", ")
preOrderTraversal(node.left)
preOrderTraversal(node.right)
میان سفری (In-order) — DFS
الگو: چپ، ریشه، راست. روی BST خروجی صعودی می دهد.
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
پس سفری (Post-order) — DFS
الگو: چپ، راست، ریشه. برای حذف ایمن درخت مفید است.
def postOrderTraversal(node):
if node is None:
return
postOrderTraversal(node.left)
postOrderTraversal(node.right)
print(node.data, end=", ")
انواع رایج درخت دودویی
متعادل (Balanced): اختلاف ارتفاع زیر درخت ها حداکثر یک است.
کامل (Complete): همه لایه ها پرند؛ آخرین لایه از چپ پر می شود.
کاملِ دوفرزندی (Full): هر گره یا صفر فرزند دارد یا دو فرزند.
بی نقص (Perfect): همه برگ ها هم ترازند و همه لایه ها کاملند.
گام های عملی
- کلاس TreeNode با left و right بساز.
- گره ها را ایجاد کن و پیوند بده.
- یکی از پیمایش های DFS را اجرا کن.
نکته: برای مفاهیم مقدماتی به درخت ها سر بزن. برای جستجو مرتب، صفحه درخت جستجوی دودویی را ببین.
جمع بندی سریع
- هر گره حداکثر دو فرزند دارد.
- DFS سه حالت معروف دارد.
- In-order روی BST مرتب برمی گرداند.
- ساخت و پیمایش بسیار سرراست است.