gpt-4o-mini-2024-07-18· OpenAI
WildChat-4.8M (AI2)
اريد قانون لحساب ارتفاع شجرة بحث ثنائية غير كاملة
- User
اريد قانون لحساب ارتفاع شجرة بحث ثنائية غير كاملة
- Assistant
لحساب ارتفاع شجرة بحث ثنائية غير كاملة، يمكن استخدام مفهوم ارتفاع الشجرة. ارتفاع الشجرة هو عدد الحواف (أو المستويات) في المسار الأطول من الجذر إلى أي من أوراق الشجرة.
تعريفات:
- شجرة بحث ثنائية (BST): هي هيكل بيانات يتم فيه تخزين العناصر بحيث يكون العنصر في العقدة اليسرى أقل من العنصر في العقدة الأم، والعنصر في العقدة اليمنى أكبر.
- ارتفاع الشجرة: هو العدد الأقصى من الحواف الموجودة على المسار من الجذر إلى أبعد ورقة.
طرق حساب الارتفاع:
يمكن حساب ارتفاع الشجرة باستخدام أسلوبين:
-
أسلوب التكرار (Recursive Method): يمكنك استخدام دالة تكرارية (Recursive Function) لحساب ارتفاع الشجرة، كالتالي:
class Node: def __init__(self, key): self.left = None self.right = None self.value = key def height(node): if node is None: return -1 # إذا كانت الشجرة فارغة، يتم إرجاع -1 else: left_height = height(node.left) right_height = height(node.right) return 1 + max(left_height, right_height) # مثال على كيفية استخدامه root = Node(10) root.left = Node(5) root.right = Node(20) root.left.left = Node(3) root.left.right = Node(7) print("ارتفاع الشجرة هو:", height(root)) -
أسلوب التكرار (Iterative Method): يمكن أيضًا استخدام أسلوب متكرر عبر استخدام هيكل بيانات قائمة الانتظار (Queue) لحساب الارتفاع. هذا أقل استخدامًا بالنسبة للشجرات غير الكاملة:
from collections import deque def height_iterative(root): if not root: return -1 queue = deque([root]) height = -1 while queue: height += 1 level_size = len(queue) for _ in range(level_size): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return height # مثال على كيفية استخدامه print("ارتفاع الشجرة هو:", height_iterative(root))
ملاحظات
- إذا كانت الشجرة غير مكتملة، قد يكون ارتفاعها أقرب إلى ارتفاع شجرة كاملة، ولكن لا يمكن أن تتجاوز ارتفاع شجرة كاملة بنفس العدد من العقد.
- الشجرة غير المكتملة يمكن أن تؤدي إلى ارتفاعات أكبر بسبب التوزيع غير المتوازن للعقد.
استخدم الطرق المذكورة أعلاه لحساب ارتفاع شجرة البحث الثنائية غير الكاملة.