אני צריך עזרה בתרגיל הבא:

עץ סיגמה מוגדר כ: עץ ריק או עץ המורכב משורש ו2 בנים שכל אחד הוא עץ סיגמה, כך שערך השורש גדול מסכום הערכים של כל צאצאיו או שווה לו.

אני צריך לכתוב אלגוריתם האם-העץ-סיגמה(SUM,T) המחיזר אמת אם T הוא עץ סיגמה ושקר אחרת. אם הוא דיגמה יכיל המשתנה SUM את סכום ערכי כל הצמתים.

כשאני מסתכל על עץ אני יודע איך לבדוק אם הוא סיגמה או לא, אבל אני פשוט לא מצליח לכתוב את זה בתור אלגוריתם, כל פעם אני או נתקע או מוצא טעות אחרת.

אני דיי בטוח שהפעולה אמורה להיות רקורסיבית, ולפי דעתי צריכה להתחיל מעלה ולא מהשורש (ככה אני בודק אם זה סיגמה או לא)-ולכן נראה לי שתנאי העצירה צריך להיות -אם T ריק החזר אמת. אבל אני לא בטוח וכאמור לא יודע איך להמשיך...

אודה לכם אם תכוונו אותי בדרך לפתרון, וסליחה על החפירות...

אחת ההדרכות היפות שיצא לי לקרוא לגבי כתיבת קוד רקורסיבי היא, "תניח שהקוד שלך עובד".

הרעיון הכללי הוא כזה - תנסח תנאי עצירה (או "מקרה פרטי"), וכדי לבצע את המקרה הכללי - "תניח שהקוד שלך עובד", ותשלח פרמטרים מתאימים לפונקציה הרקורסיבית.

כפתרון למה שאתה מציג, אני יכול להציע את הרעיון הבא (ב CPP)

bool isSigma(int& sum, Node* Tree)
{
  if(Tree == NULL)
    return true;

  if(((Tree->lnode == NULL) && (Tree->lnode == NULL)) || (isSigma(sum, Tree->lnode) && isSigma(sum, Tree->rnode)))
  {
    sum+= Tree->value;
    return true;
  }

  return false;
}

אני מקווה שזה עובד, לא הרצתי את זה.

אתה לא בודק אם השורש קטן מסכום ערכי צאצאיו,ככה שזה לא עובד...

הנה האלגוריתם המבוקש (בשפת C):

    int isSigmaTree(BinaryTreeNode *root, int *sum)
    {
      int leftChildSum, rightChildSum;
      int isSigmaTree = 0;

      if (NULL == root)
      {
        *sum = 0;
        isSigmaTree = 1;
      }
      else if ((root->leftChild != NULL) && (root->rightChild != NULL))
      {
        if (
          isSigmaTree(root->leftChild, &leftChildSum) &&
          isSigmaTree(root->rightChild, &rightChildSum))
        {
          if (root->value >= (leftChildSum + rightChildSum))
          {
            *sum = root->value + leftChildSum + rightChildSum;
            isSigmaTree = 1;
          }
        }
      }
      else if (isLeaf(root))
      {
        *sum = root->value;
        isSigmaTree = 1;
      }

      return isSigmaTree;
    }