Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-mini-2024-07-18· OpenAIAi2 WildChat-4.8M (AI2)

اريد قانون لحساب ارتفاع شجرة بحث ثنائية غير كاملة

  1. User

    اريد قانون لحساب ارتفاع شجرة بحث ثنائية غير كاملة

  2. Assistant

    لحساب ارتفاع شجرة بحث ثنائية غير كاملة، يمكن استخدام مفهوم ارتفاع الشجرة. ارتفاع الشجرة هو عدد الحواف (أو المستويات) في المسار الأطول من الجذر إلى أي من أوراق الشجرة.

    تعريفات:

    • شجرة بحث ثنائية (BST): هي هيكل بيانات يتم فيه تخزين العناصر بحيث يكون العنصر في العقدة اليسرى أقل من العنصر في العقدة الأم، والعنصر في العقدة اليمنى أكبر.
    • ارتفاع الشجرة: هو العدد الأقصى من الحواف الموجودة على المسار من الجذر إلى أبعد ورقة.

    طرق حساب الارتفاع:

    يمكن حساب ارتفاع الشجرة باستخدام أسلوبين:

    1. أسلوب التكرار (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))
      
    2. أسلوب التكرار (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))
      

    ملاحظات

    • إذا كانت الشجرة غير مكتملة، قد يكون ارتفاعها أقرب إلى ارتفاع شجرة كاملة، ولكن لا يمكن أن تتجاوز ارتفاع شجرة كاملة بنفس العدد من العقد.
    • الشجرة غير المكتملة يمكن أن تؤدي إلى ارتفاعات أكبر بسبب التوزيع غير المتوازن للعقد.

    استخدم الطرق المذكورة أعلاه لحساب ارتفاع شجرة البحث الثنائية غير الكاملة.