שאלת מבחן במבוא למדעי המחשב - אוניברסיטת בר-אילן 2023 - רקורסיה

כתבו פונקציה **רקורסיבית** printDepthVal המקבלת שורש של עץ חיפוש בינארי root וערך מספרי num, ומדפיסה את כל הקדקודים בעץ ששורשו ב-root ושהם באותו העומק בעץ כמו הקדקד עם הערך num (כולל num עצמו), באופן ממויין בסדר עולה (המספר הנמוך ביותר משמאל, והגבוה ביותר מימין). אם הערך לא נמצא בעץ, היא לא תדפיס דבר. לדוגמה: אם נשלח את שורש העץ הנתון ואת הערך 5, הפונקציה תדפיס את הערכים 2,5,9,11. אם נשלח את הערך 7, הפונקציה תדפיס את הערך 7 בלבד. ואם נשלח את הערך 14, היא לא תדפיס כלום. ```c typedef struct BTree { struct BTree *left; struct BTree *right; int data; } BTree; void printDepthVal(BTree *root, int num); ```

רמז: ראשית מצאו את העומק של num בעץ (ניצול BST: אם num < root הלך שמאלה, אחרת ימינה). לאחר מכן הדפיסו את כל הצמתים באותו עומק (in-order כדי לקבל סדר עולה). השתמשו בפונקציית עזר שמדפיסה צמתים בעומק מסוים.

פתרון: ```c int findDepth(BTree *root, int num, int depth) { if (!root) return -1; if (root->data == num) return depth; if (num < root->data) return findDepth(root->left, num, depth + 1); return findDepth(root->right, num, depth + 1); } void printAtDepth(BTree *root, int depth) { if (!root) return; if (depth == 0) { printf("%d ", root->data); return; } printAtDepth(root->left, depth - 1); printAtDepth(root->right, depth - 1); } void printDepthVal(BTree *root, int num) { int d = findDepth(root, num, 0); if (d == -1) return; printAtDepth(root, d); } ``` **הסבר:** `findDepth` מוצאת את העומק של num בעץ BST (ניצול תכונת BST לחיפוש יעיל). `printAtDepth` מדפיסה בסדר in-order (שמאל→שורש→ימין) את כל הצמתים בעומק נתון — מבטיחה סדר עולה כי העץ הוא BST. $\blacksquare$