[Powered by Google Translate] [סעיף 7: נוח יותר] [רוב אודן] [אוניברסיטת הרווארד] [זה CS50] [CS50.TV] בסדר. אז כמו שאמרתי שלי בדוא"ל, זה הולך להיות קטע הבינארי עץ אינטנסיבי. אבל אין כל כך הרבה שאלות. אז אנחנו הולכים לנסות ולצייר את כל שאלה ונכנס לפרטים כואבים של כל הדרכים הטובות ביותר לעשות דברים. וכך, ממש בתחילתו, אנחנו עוברים לדוגמא ציורים של עצים וכל מיני דברים בינאריות. אז הנה, "זכור שעץ בינארי יש צומת דומים לאלה של רשימה מקושרת, אלא שבמקום מצביע אחד יש שתיים: אחד עבור 'הילד' השמאל ואחד עבור 'הילד' הנכון ". אז עץ בינארי הוא בדיוק כמו רשימה מקושרת, מלבד struct הולך להיות שני מצביעים. יש עצי trinary, שהולכים להיות שלשות, יש עצי N-ארי, שפשוט יש להם מצביע גנרי כי אז אתה צריך malloc להיות גדול מספיק כדי להיות מספיק מצביעים לכל ילדיו האפשריים. אז העץ בינארי פשוט קורה שיש מספר קבוע של שתיים. אם אתה רוצה, אתה יכול לתת רשימה מקושרת כעץ יונארית, אבל אני לא חושב שמישהו קורא לו ככה. "צייר תרשים תיבות-and-חצים של צומת בעץ בינארי הכולל את המספר של נייט האהוב, 7, שבו כל מצביע ילד הוא ריק ". מצב אז האייפד. 

זה הולך להיות די פשוט. אנחנו פשוט נצטרך צומת, אני אצייר אותה ככיכר. ואני אצייר את הערכים לכאן. אז הערך ילך לכאן, ולאחר מכן כאן יהיה לנו את מצביע שמאל בצד השמאל ומצביע הימני בצד ימין. וזה הרבה מאוד, אז קורא לזה כנס לימין ושמאל, את השמות המצביעים. שני אלה הולכים להיות אפס. שפשוט יהיה ריק, ושפשוט יהיו ריק. אוקיי. אז בחזרה לכאן. "עם רשימה מקושרת, היה לנו רק לאחסון מצביע לצומת הראשונה ברשימה כדי לזכור את כל הרשימה המקושרת, או את כל הרשימה. כמו כן, עם עצים, יש לנו רק לאחסון מצביע לצומת אחת כדי לזכור את העץ כולו. פסק זו היא calle 'השורש' של העץ. לבנות על התרשים שלך מקודם או לצייר אחד חדש כזה שיש לך תיאור תיבות-and-חצים של עץ בינארי עם הערך 7, ואז 3 בצד השמאל, אז 9 בצד ימין, ולאחר מכן 6 בצד הימין של 3. " בואו נראה אם ​​אני יכול לזכור את כל זה בראש שלי. אז זה הולך להיות כאן השורש אותנו. יהיה לנו כמה מצביע במקום כלשהו, ​​משהו שאנחנו נתקשר אל שורש, וזה מצביע על הבחור הזה. עכשיו להפוך את צומת חדשה, מה יש לנו, 3 בצד השמאל? אז צומת חדש עם 3, וזה בתחילה מצביע null. אני פשוט אשים את נ עכשיו אנחנו רוצים לעשות זה ללכת לצד השמאל של 7. אז אנחנו משנים את זה עכשיו מצביע להצביע על הבחור הזה. ואנחנו עושים את אותו הדבר. אנחנו רוצים 9 כאן אשר בתחילה רק אומר ריק. אנחנו הולכים לשנות את המצביע, בשלב זה עד 9, ועכשיו אנחנו רוצים לשים 6 מימין 3. אז זה הולך - לעשות 6. והבחור שיצביע שם. אוקיי. אז זה כל מה שמבקש מאתנו לעשות. 

עכשיו בואו נעבור על כמה מינוח. אנחנו כבר דברנו על איך השורש של העץ הוא עליון ביותר צומת בעץ. אחד המכיל 7. הבלוטות בחלק התחתון של העץ נקראות העלים. כל צומת שפשוט יש ריק כמו הילדים שלה הוא עלה. אז זה אפשרי, אם העץ בינארי שלנו הוא רק צומת אחת, שהעץ הוא עלה, וזהו זה. "'הגובה' של העץ הוא מספר הדילוגים שאתה צריך לעשות כדי להגיע מלמעלה לעלה. " נעשה לנו, ברגע אחד, את ההבדל בין עצי בינאריים מאוזנים ולא מאוזנים, אך לעת עתה, גובה הכולל של העץ הזה הייתי אומר הוא 3, למרות שאם אתה סופר את מספר הדילוגים אתה צריך לעשות כדי להגיע ל9, אז זה באמת רק לגובה של 2. כרגע זה עץ בינארי לא מאוזן, אבל אנחנו דברנו על איזון כאשר זה הופך להיות רלוונטי. אז עכשיו אנחנו יכולים לדבר על צומת בעץ במונחים יחסית לצומת האחרים בעץ. אז עכשיו יש לנו הורים, ילדים, אחים, אבות אבותינו, וצאצאים. הם תחושה די נפוצה, מה שהם אומרים. אם אנחנו שואלים - הורים של זה. אז מה הוא ההורה של 3? [סטודנטים] 7. >> כן. ההורה הוא רק הולך להיות מה שמצביע עליך. אז מה הם הילדים בגילי 7? [סטודנטים] 3 ו 9. >> כן. שים לב כי "ילדים" פשוטו כמשמעו ילדים, כך 6 לא יחול, כי זה כמו נכד. אבל אז אם תלכו צאצאים, אז מה הם צאצאיהם של 7? [סטודנטים] 3, 6 ו 9. >> כן. צאצאיו של צומת השורש הולכים להיות כל דבר בעץ, למעט אולי צומת השורש עצמו, אם אתה לא רוצה לקחת בחשבון שצאצא. ולבסוף, אבות, כך שזה בכיוון ההפוך. אז מה הם אבותיהם של 6? [סטודנטים] 3 ו 7. >> כן. 9 אינם כלולים. זה רק בחזרה הנצר הישיר לשורש הולך להיות אבותיך. 

"אנחנו אומרים שעץ בינארי הוא 'ההורה' אם לכל צומת בעץ, כל הצאצאים שלה בצד השמאל יש ערכים פחותים ואת כל אלה בצד ימין יש ערכים גדולים יותר. לדוגמה, העץ מעליו הוזמן, אך זה לא הסדר ההורה היחיד האפשרי. " לפני שנגיע לזה, עץ בינארי הורה ידוע גם בעץ חיפוש. כאן אנו לקרות לנקרא לזה עץ בינארי מסודר, אבל מעולם לא שמעתי שקורא בינארי עץ מזמין לפני, ועל חידון אנו נוטים יותר לשים עץ חיפוש. הם ובעונה אחת, וזה חשוב לך לזהות את ההבדל בין העץ בינארי ועץ חיפוש. עץ בינארי הוא רק עץ שמצביע על שני דברים. כל צומת מצביע על שני דברים. אין חשיבה על הערכים שהוא מצביע עליו. אז כמו כאן, מכיוון שזה עץ חיפוש בינארי, אנחנו יודעים שאם אנחנו הולכים נשארנו 7, אז את כל הערכים שאנו יכולים להגיע על ידי הולך שמאלה של 7 צריכים להיות פחות מ 7. שימו לב שכל הערכים פחות מ 7 הם 3 ו 6. אלו כולם משמאל 7. אם אנחנו הולכים בצד הימין של 7, הכל צריך להיות גדול מ 7, כך 9 הם בצד הימין של 7, כך שאנחנו טובים. זה לא המקרה של עץ בינארי, לעץ בינארי רגיל אנחנו יכולים סתם 3 בראש, 7 לשמאל, 9 משמאל 7; אין סידור של ערכים כלשהם. עכשיו, אנחנו לא באמת לעשות את זה, כי זה מעייף ומיותר, אבל "מנסה למשוך כמה שיותר עצים מסודרים כמו שאתה יכול לחשוב על באמצעות מספרים 7, 3, 9, ו 6. כמה סידורים שונים יש? מהו הגובה של כל אחד? " 

אנחנו נעשה את הזוג, אבל הרעיון המרכזי הוא, זה בשום אופן ייצוג ייחודי של עץ בינארי שמכיל את הערכים הללו. כל מה שאנחנו צריכים זה קצת עץ בינארי שמכיל 7, 3, 6, ו 9. תקף אחת אפשרי נוסף יהיה השורש הוא 3, תלכו לצד השמאל וזה 6, ללכת לשמאל וזה 7, תלכו לצד השמאל וזה 9. זה עץ חיפוש חוקי לחלוטין. זה לא מאוד מועיל, כי זה בדיוק כמו רשימה מקושרת וכל המצביעים האלה הם פשוט ריקים. אבל זה עץ בתוקף. כן? [סטודנטים] האם לא את הערכים צריכים להיות גדול יותר בצד ימין? או זה -? >> אלה שהתכוונתי ללכת לכיוון השני. יש גם - כן, בואו נעבור את זה. 9, 7, 6, 3. לתפוס טוב. עדיין יש לציית למה חיפוש עץ בינארי הוא אמור לעשות. אז כל מה שהשמאל צריך להיות פחות מכל צומת נתונה. אנחנו רק יכולים לזוז, אומרים, זה 6 ולשים אותו כאן. לא, אנחנו לא יכולים. למה אני עושה את זה? בואו לעשות - כאן הם 6, הנה 7, 6 נקודות ל3. זה עדיין עץ חיפוש חוקי. מה לא בסדר אם אני - בא נראה אם ​​אני יכול לבוא עם הסדר. כן, בסדר. אז מה לא בסדר עם העץ הזה? אני מניח שכבר נתתי רמזתי לך שיש משהו לא בסדר עם זה. למה אני עושה את זה? אוקיי. זה נראה סביר. אם אנחנו מסתכלים על כל צומת, כמו 7, אז בצד השמאל של 7 הוא 3. אז יש לנו 3, הדבר לזכותו של 3 הוא 6. ואם אתה מסתכל על 6, הדבר לזכותו של 6 הוא 9. אז למה זה לא עץ חיפוש חוקי? [סטודנטים] 9 הם עדיין בצד השמאל של 7. >> כן. זה חייב להיות נכון שכל הערכים שאתה יכול להגיע על ידי לחיצה על השמאלי של 7 הם פחות מ 7. אם תלכו עזב מתוך 7, אנחנו מקבלים עד 3 ואנחנו עדיין יכולים לקבל עד 6, אנחנו עדיין יכולים להגיע עד 9, אלא על ידי שהלכנו פחות מ 7, אנחנו לא צריכים להיות מסוגלים להגיע למספר זה גדול מ 7. אז זה לא עץ חיפוש חוקי. 

האח שלי הייתה למעשה שאלת ראיון זה היה באופן בסיסי זה, רק קוד משהו כדי לאמת אם עץ הוא עץ חיפוש בינארי, ולכן הדבר הראשון שהוא עשה היה רק ​​לבדוק אם השמאל וימין הם נכון, ולאחר מכן לעבור משם למטה. אבל אתה לא יכול פשוט לעשות את זה, יש לך לעקוב אחר עובדה שעכשיו שאני כבר הלכתי נשארתי 7, כל מה שבעץ המשנה חייב להיות פחות מ 7. האלגוריתם הנכון צריך לעקוב לגבולות שהערכים אולי יכולים לנפול פנימה אנחנו לא נעבור על כולם. קיים קשר הישנות נחמדה, למרות שעוד לא הגענו אליהם, או שלא יקבלו לאלה, הגדרה כמה אנשים באמת יש. אז יש 14 מהם. הרעיון של איך היית עושה את זה מבחינה מתמטית הוא כמו, אתה יכול לבחור כל אחד ואחד להיות צומת השורש, ואז אם אני לוקח 7 להיות צומת השורש, אז יש, יניח, כמה מספרים שיכולים ללכת להיות הצומת השמאלית שלי, ויש כמה מספרים שיכולים להיות הצומת הימנית שלי, אבל אם יש לי n מספרי סך הכל, אזי הסכום שיכול ללכת לשמאל בתוספת הסכום שיכול ללכת לימין הוא n - 1. אז המספרים שנותרו, הם צריכים להיות מסוגלים ללכת לכאן או לשמאל או לימין. קשה, כנראה, שאם אני אשים 3 ראשון ואז כל מה שיש ללכת לשמאל, אבל אם אני אשים 7, אז כמה דברים יכולים ללכת שמאלה ועוד כמה דברים יכולים ללכת לצד ימין. ועל ידי '3 הראשונה "התכוונתי הכל יכול ללכת לצד ימין. זה באמת, אתה רק צריך לחשוב על זה כ, כמה דברים יכול ללכת ברמה הבאה של העץ. וזה יוצא להיות 14, או שאתה יכול לצייר את כולם, ואז תקבל 14. 

חוזר לכאן, "עצים בינאריים ממוספרים הם מגניבים, כי אנחנו יכולים לחפש דרכם באופן דומה מאוד לחיפוש על מערך ממוין. כדי לעשות זאת, אנחנו מתחילים בשורש ואת דרך העבודה שלנו במורד העץ לקראת עלים, בודק ערכים של כל צומת מול הערכים שאנחנו מחפשים. אם הערך של הצומת הנוכחית הוא פחות מהערך שאנחנו מחפשים, אתה הולך לצד הילד הימני של הצומת. אחרת, אתה הולך לילד השמאלי של הצומת. בשלב מסוים, תוכל גם למצוא את הערך שאתה מחפש, או שנתקלת בריק, מציין את הערך לא בעץ. " יש לי לשרטט מחדש את העץ שהיינו לנו לפני; שייקח 2. אבל אנחנו רוצים להסתכל למעלה אם 6, 10, ו 1 הם בעץ. אז מה זה היה, 7, 9, 3, 6. אוקיי. מספרים שברצון להסתכל למעלה, אנחנו רוצים להסתכל למעלה 6. איך זה עובד אלגוריתם? ובכן, יש לנו גם כמה מצביע שורש לעץ שלנו. והיינו הולכים לשורש ואומרים, האם זה שווה ערך לשווי שאנחנו מחפשים? אז אנחנו מחפשים 6, אז זה לא שווה. אז אנחנו ממשיכים הלאה, ועכשיו אנחנו אומרים, אוקיי, אז 6 הם פחות מ 7. האם זה אומר שאנחנו רוצים ללכת לצד השמאל, או שאנחנו רוצים ללכת לימין? [סטודנטים] שמאל. >> כן. זה קל באופן משמעותי, כל מה שאתה צריך לעשות הוא לצייר צומת אפשרית אחד של העץ ואז אתה אל - במקום לנסות לחשוב בראש שלך, אוקיי, אם זה פחות, אני אלך לשמאל או ללכת ימינה, רק מלהסתכל על התמונה הזאת, זה מאוד ברור שאני צריך ללכת לשמאל אם הצומת הזה היא גדולה מהערך שאני מחפש. אז אתה הולך לשמאל, עכשיו אני ב 3. אני רוצה - 3 הוא פחות מהערך שאני מחפש, שעומד על 6. אז אנחנו הולכים לצד ימין, ועכשיו אני בסופו של דבר 6, שהוא הערך שאני מחפש, ולכן אני חוזר אמיתי. הערך הבא אני הולך לחפש הוא 10. אוקיי. אז 10, עכשיו, הוא הולך - לחתוך את זה - אני הולך לעקוב אחרי השורש. עכשיו, 10 הולכים להיות גדול מ 7, אז אני רוצה להסתכל לצד ימין. אני הולך לבוא לכאן, 10 הולכים להיות גדול מ 9, אז אני הולך לרוצה להסתכל לצד ימין. אני בא לכאן, אבל לכאן עכשיו אני באפס. מה עליי לעשות אם אני מכה ריק? [סטודנטים] בתמורת שווא? >> כן. לא מצאתי 10. 1 הולך להיות מקרה כמעט זהה, מלבד זה רק הולך להיות התהפך; במקום להסתכל למטה בצד ימין, אני הולך להסתכל למטה בצד השמאל. 

עכשיו אני חושב שאנחנו ממש מקבלים לקוד. כאן מקום - לפתוח את מכשיר CS50 ולנווט את הדרך לשם, אבל אתה יכול גם פשוט לעשות את זה בשטח. זה כנראה אידיאלי לעשות את זה במרחב, כי אנחנו יכולים לעבוד בשטח. "קודם כול צריכים הגדרת סוג חדשה לצומת בעץ בינארי שמכיל ערכי int. שימוש boilerplate typedef להלן, ליצור הגדרת סוג חדשה לצומת בעץ בינארי. אם אתה נתקע. . . "בלה, בלה, בלה. אוקיי. אז בואו נשים boilerplate כאן, צומת typedef struct, וצומת. כן, בסדר. אז מה הם את השדות שאנחנו הולכים רוצים בצומת שלנו? [סטודנטים] Int ולאחר מכן שני מצביעים? >> Int ערך, שני מצביעים? כיצד תאכל לכתוב את המצביעים? [סטודנטים] struct. >> אני צריך להתמקד פנימה כן, אז struct צומת * עזבה, וstruct צומת * נכון. ותזכור את הדיון מהעת האחרונה, כי זה לא הגיוני, זה לא הגיוני, זה לא הגיוני. אתה צריך כל מה שיש על מנת להגדיר struct רקורסיבית זה. אוקיי, אז זה מה שהעץ שלנו הולך להיראות. אם הייתי עושה כך עץ trinary, אז צומת עשויה להיראות כמו B1, B2, B3 * struct צומת, שם ב הוא ענף - למעשה, כבר יותר שמעתי שאני זה עזב, אבל כל מה שאמצע, נכון. אכפת לנו רק על ינארי, ולכן ימין, שמאל. "עכשיו מצהיר על משתנה * צומת עולמית לשורש של העץ". אז אנחנו לא הולכים לעשות את זה. כדי לעשות את הדברים קצת יותר קשים ויותר כלליים, לא יהיה לנו משתנה צומת עולמית. במקום זאת, בעיקרי שנכריז כל דברי הצומת שלנו, וזה אומר כי בהמשך, כאשר אנחנו מתחילים לרוץ הפונקציה שלנו מכיל והוספת הפונקציה שלנו, במקום, מכיל לתפקד רק באמצעות משתנה הצומת הגלובלית הזה, אנחנו הולכים לעשות את זה ייקח כטיעון העץ שאנחנו רוצים אותו לעבד. יש משתנה הגלובלי היה אמור להקל על מצב. אנחנו הולכים לעשות דברים קשים יותר. עכשיו קח דקה או שתיים רק כדי לעשות דברים מהסוג הזה, שם בתוך ראשי ברצונך ליצור את העץ הזה, וזה כל מה שאתה רוצה לעשות. ניסיתי לבנות את העץ הזה בפונקציה העיקרית שלך. 

אוקיי. אז אתה לא צריך אפילו בנית את העץ לכל אורך הדרך עד כה. אבל למישהו יש משהו שאני יכול למשוך את כדי להראות עד כמה שאפשר להתחיל לבנות עץ כזה? [סטודנטים] הדפיקות של מישהו, מנסים לצאת. [אודן] מישהו נוח עם בניית העץ שלהם? [סטודנטים] בטח. זה לא נעשה. >> זה בסדר גמור. אנחנו רק יכולים לסיים - הו, אתה יכול לשמור אותו? הידד. אז הנה יש לנו - הו, אני קצת מנותק. האם אני טסתי ב? להתקרב, לגלול החוצה. >> יש לי שאלה. >> כן? [סטודנטים] כשאתה מגדיר struct, הם דברים כמו אותחל לכל דבר? [אודן] מס >> אוקיי. אז היית צריך לאתחל - [אודן] מס כשאתה מגדיר, או כאשר אתה מצהיר על struct, זה אינו מאותחל כברירת מחדל; זה בדיוק כמו אם תכריז int. זה בדיוק אותו הדבר. זה כמו כל אחד מהתחומים הבודדים שלה יכול להיות בעל ערך באשפתו. >> והאם ניתן להגדיר - או להכריז struct בדרך שהיא עושה לאתחל אותם? [אודן] כן. אז, תחביר אתחול קיצור הוא הולך להיראות כמו - יש שתי דרכים שאנחנו יכולים לעשות את זה. אני חושב שאנחנו צריכים לקמפל אותו כדי להפוך את קלאנג הבטוח גם עושה את זה. סדר הטיעונים שמגיע בstruct, אתה מכניס כסדר ויכוחים בתוך סוגריים המסולסלים של אלה. אז אם אתה רוצה לאתחל אותו עד 9 ועזבת להיות בטל ומייד להיות ריק, זה יהיה 9, null, null. האלטרנטיבה היא, והעורך לא אוהב את תחביר זה, והוא חושב שאני רוצה בלוק חדש, אבל האלטרנטיבה היא משהו כמו - כאן, אני אשים אותו בשורה חדשה. אתה יכול לומר באופן מפורש, אני שוכח את התחביר המדויק. אז אתה יכול להתייחס באופן מפורש אותם בשמו, ואומר, . ג, או. ערך = 9,. NULL = שמאל. אני מנחש אלה צריכים להיות פסיקים. . זכות = NULL, אז ככה שאתה לא באמת צריך לדעת את הסדר של struct, וכשאתה קורא את זה, זה הרבה יותר מפורש על מה הערך שאותחל ל. 

זה קורה להיות אחד מהדברים ש-- כך, על פי רוב, + + C היא על של ג אתה יכול לקחת את קוד C, להזיז אותו ל-C + +, ואת זה צריך לקמפל. זה אחד מהדברים ש+ + C אינה תומכים, ולכן אנשים נוטים שלא לעשות את זה. אני לא יודע אם זה הסיבה היחידה שאנשים נוטים שלא לעשות את זה, אבל מקרה שבו הייתי צריך להשתמש בו הייתי צריך לעבוד עם + + C ולכן אני לא יכול להשתמש בזה. דוגמה נוספת למשהו שלא עובדת עם + + C היא איך malloc מחזיר "* מבוטל," מבחינה טכנית, אבל אתה פשוט יכול להגיד * x = מה malloc char, וזה יהיה באופן אוטומטי להיות יצוק לדמות *. שהגבס אוטומטי לא קורה ב-C + +. שלא לקמפל, והיית צריך לומר במפורש * Char, malloc, שיהיה, שהטיל אותו לדמות *. אין הרבה דברים שC ו-C + + תחלוק עליהן, אבל אלה הם שתיים. אז בואו נלך עם תחביר זה. אבל גם אם לא הלכתי עם זה תחביר, מה הוא - יכול להיות רע בזה? [סטודנטים] אני לא צריך dereference זה? >> כן. זכור שיש חץ dereference משתמע, ולכן כאשר אנחנו עוסקים רק בstruct, אנחנו רוצים להשתמש. כדי לקבל בבתוך שדה של struct. והפעם היחידים שאנחנו משתמשים חץ הם כאשר אנחנו רוצים לעשות - כן, החץ הוא שווה ערך ל - זה מה שזה היה יכול להיות אם הייתי חץ. כל אמצעי החץ, dereference זה, עכשיו אני בstruct, ואני יכול לקבל את השטח. או שיזיז את השדה באופן ישיר או dereference ולקבל את השדה - אני מניח שזה צריך להיות ערך. אבל כאן אני מתמודד עם רק struct, לא מצביע ל struct, ולכן אני לא יכול להשתמש בחץ. אבל זה סוג של דבר שאנחנו יכולים לעשות עבור כל צומת. אוי, אלוהים. זה 6, 7, ו 3. אז אנחנו יכולים להגדיר את הענפים בעץ שלנו, אנחנו יכולים להיות 7 - אנחנו יכולים להיות, שמאליים שלו צריכים להצביע על 3. אז איך אנחנו עושים את זה? [סטודנטים, לא מובן] כן. >> הכתובת של node3, ואם לא היה לך כתובת, אז זה פשוט לא היית משגת. אך יש לזכור כי אלה הם מצביע אל צומת הבאים. ימין צריך להצביע על 9, ו 3 אמורים להצביע על הזכות ל6. אני חושב שזה כל הקבוצה. כל הערות או שאלות? [סטודנטים, לא מובן] השורש הולך להיות 7. אנחנו רק יכולים לומר צומת * ptr = או שורש, = & node7. 

למטרות שלנו, אנחנו הולכים להיות התמודדות עם הוספה, כך אנחנו הולכים לרוצים לכתוב פונקציה להכניס לתוך העץ בינארי זה ולהוסיף בהכרח עומד להתקשר malloc ליצור צומת חדש לעץ הזה. אז הדברים הולכים להיות מלוכלך עם העובדה שחלק מצומת כרגע על הערימה וצומת אחרים הולכים לגמור על הערימה כאשר אנו מוסיפים אותם. זה חוקי לחלוטין, אבל הסיבה היחידה אנחנו מסוגלים לעשות את זה בערימה בגלל זה למשל כזה מאולץ שאנחנו יודעים העץ אמור להיות בנוי כ7, 3, 6, 9. אם לא היה לנו את זה, אז לא יהיה לנו לmalloc במקום הראשון. כפי שנראים קצת מאוחר יותר, אנחנו צריכים להיות malloc'ing. כרגע זה סביר בהחלט לשים על הערימה, אבל בואו נשנה את זה לביצוע malloc. אז כל אחד מאלה עכשיו הולך להיות משהו כמו צומת * node9 = malloc (sizeof (צומת)). ועכשיו אנחנו הולכים לעשות הבדיקה שלנו. אם (node9 == NULL) - אני לא רוצה את זה - להחזיר 1, ואז אנחנו יכולים לעשות node9-> כי עכשיו זה מצביע, ערך = 6, node9-> עזב = NULL, node9-> ימין = NULL, ואנחנו הולכים צריכים לעשות את זה לכל אחד מצומת הללו. אז במקום, בואו נגדיר את זה בתוך פונקציה נפרדת. בואו נקראים לה צומת * build_node, וזה דומה במקצת לממשקי API שאנו מספקים לאפמן קידוד. אנחנו נותנים לך פונקציות מאתחל לעץ וdeconstructor "פונקציות" לעצים האלה ואותם ליערות. 

אז הנה אנחנו הולכים להיות פונקצית מאתחל רק לבנות צומת עבורנו. וזה הולך להיראות פחות או יותר בדיוק כמו זה. וגם אני הולך להיות עצלן ולא לשנות את שמו של משתנה, למרות node9 לא הגיוני יותר. אה, אני מניח שהערך של node9 לא היה צריך להיות 6. עכשיו אנחנו יכולים לחזור node9. וכאן אנחנו צריכים להחזיר null. כולם מסכימים על כך לתפקוד צמתים לבנות? אז עכשיו אנחנו יכולים פשוט לקרוא לזה לבנות בכל צומת עם ערך נתון ומצביעי null. עכשיו אנחנו יכולים לקרוא את זה, אנחנו יכולים לעשות את הצומת * node9 = build_node (9). ובואו נעשיתי. . . 6, 3, 7, 6, 3, 7. ועכשיו אנחנו רוצים להגדיר את אותם מצביעים, אלא שעכשיו הכל כבר במונחים של מצביעים כך כבר לא צריכים את הכתובת של. אוקיי. אז מה זה הדבר האחרון שאני רוצה לעשות? יש לבדיקת שגיאות שאני לא עושה. מה לבנות תשואת צומת? [סטודנטים, לא מובנים] >> כן. אם malloc נכשלה, זה יחזיר null. אז אני הולך בעצלתיים לשים אותו פה במקום לעשות את תנאים לכל אחד. אם (node9 == NULL, או - אפילו פשוט יותר, זה שווה ערך ל רק אם לא node9. אז אם לא node9, או לא node6, או לא node3, או לא node7, לחזור 1. אולי אנחנו צריכים להדפיס malloc נכשלה, או משהו. [סטודנטים] האם שווא שווה ל null גם? [אודן] כל ערך אפס הוא שקרי. אז null הוא ערך אפס. אפס הוא ערך אפס. שקר הוא ערך אפס. כל - די 2 הערכים אפס בלבד, בטלים ואפס, המזויף הוא רק חשיש מוגדר כאפס. זה חל גם אם אנחנו מצהירים משתנים גלובליים. אם היינו לנו שורש * צומת עד כאן, אז - הדבר נחמד על משתנים הגלובליים הוא שהם תמיד יש ערך ראשוני. זה לא נכון של פונקציות, איך בתוך מכאן, אם יש לנו,, * כמו צומת או x צומת. אין לנו מושג מה x.value, x.whatever, או שאנחנו יכולים להדפיס אותם והם יכולים להיות שרירותיים. זה לא נכון של משתנים הגלובליים. שורש אז צומת או x צומת. כברירת מחדל, כל מה שגלובלי, אם לא אותחל במפורש לערך מסוים, יש ערך אפס כערך שלו. אז הנה, שורש * צומת, אנחנו לא במפורש לאתחל אותו לשום דבר, כל כך ערך ברירת המחדל שלו יהיה בטל, שהנו ערך האפס של מצביעים. ערך ברירת המחדל של x הולך אומר שx.value הוא אפס, x.left הוא ריק, וx.right הוא ריק. אז מכיוון שמדובר בstruct, כל השדות של struct יהיה אפס ערכים. למרות שאנחנו לא צריכים להשתמש בזה כאן,. [סטודנטים] בstructs שונה ממשתנים אחרים, ושאר המשתנים ערכי אשפה, אלו הם אפסים? [אודן] ערכים אחרים. אז בX, X יהיה אפס. אם זה בהיקף העולמי, יש לו ערך ראשוני. >> אוקיי. [אודן] או הערך הראשוני שנתת לו או אפס. אני חושב שמטפל בכל זה. 

אוקיי. אז את החלק הבא של השאלה שואל, "עכשיו אנחנו רוצים לכתוב פונקציה שנקראת מכיל עם אב טיפוס של bool מכיל ערך int. " אנחנו לא הולכים לעשות bool מכיל ערך int. אב הטיפוס שלנו הולך להיראות כמו bool מכיל (ערך int. ואז אנחנו גם הולכים לעבור את העץ שזה צריך להיות בדיקה כדי לראות אם יש לו ערך זה. אז צומת * עץ). אוקיי. ואז אנחנו יכולים לקרוא לזה במשהו כמו, אולי נרצה printf או משהו. מכיל 6, השורש שלנו. שצריך להחזיר אחד, או נכון, בעוד שמכיל 5 שורש צריך להחזיר שקר. אז קח שני כדי ליישם את זה. אתה יכול לעשות את זה גם באופן רקורסיבי או ערוך את. הדבר נחמד על הדרך בה אנו הגדרנו את הדברים שהוא זה משאיל את עצמו לפתרון שלנו הרבה יותר הקל רקורסיבית מהדרך הגלובלית משתנית עשתה. כי אם רק יש לנו מכיל ערך int, אז אין לנו דרך של recursing את עצי משנה. היינו צריכים להיות פונקציה נפרדת שעוזרים הרקורסיה את עצי המשנה עבורנו. אבל מאז שהחלפנו אותו לקחת את העץ כויכוח, שהוא צריך תמיד הייתי במקום הראשון, עכשיו אנחנו יכולים רקורסיבית קלות רבה יותר. אז איטרטיבי או רקורסיבי, תלכו על שניהם, אבל אנחנו נראה שקצוות רקורסיבית של דבר להיות די קל. אוקיי. למישהו יש משהו שאנחנו יכולים לעבוד איתו? 

[סטודנטים] יש לי פתרון איטרטיבי. >> בסדר, איטרטיבי. אוקיי, זה נראה טוב. אז, רוצה ללכת את זה? [סטודנטים] בטח. אז אני מגדיר משתנה זמני כדי לקבל את הצומת הראשונה של העץ. ואז אני פשוט התפתלתי בעת טמפ אינו null שווה, כך בעת ששהתה עדיין בעץ, אני מניח. ואם הערך הוא שווה הערך לטמפ שמצביע על, אז זה מחזיר את הערך. אחרת, הוא בודק אם זה בצד ימין או בצד השמאל. אם אי פעם אגיע למצב שבו אין יותר עץ, לאחר מכן הוא חוזר - עם יציאתו לולאה ומחזיר שקר. [אודן] אוקיי. אז זה נראה טוב. מישהו יש לך הערות על כל דבר? אין לי הערות נכונותו בכלל. דבר אחד שאנחנו יכולים לעשות את זה בחור הזה. אוי, זה הולך ללכת ארוך משהו קטן. אני אתקן את זה. אוקיי. 

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

האם יש למישהו פתרון רקורסיבית? אוקיי. זה אחד שאנחנו הולכים - זה כבר יכול להיות גדול, אבל אנחנו הולכים לעשות את זה אפילו טוב יותר. זהו פחות או יותר על אותו הרעיון בדיוק. זה פשוט, טוב, אתה רוצה להסביר? [סטודנטים] בטח. אז אנחנו מוודאים שהעץ אינו null ראשון, כי אם העץ הוא ריק אז זה הולך לחזור שווא, מפני שלא מצאו אותו. ואם יש עדיין עץ, אנחנו נכנסים - אנחנו קודם לבדוק אם הערך הוא הצומת הנוכחית. החזר אמיתי אם זה הוא, ואם אנחנו לא רקורסיבית על שמאל או לימין. האם זה נשמע מתאים? >> MM-הממ. (הסכם) אז שמת לב שזה כמעט - מבני דומה מאוד לפתרון איטרטיבי. זה רק שבמקום recursing, היו לנו לולאה בזמן. וכאן מקרה הבסיס בו עץ אינו שווה null היה המצב שתחתו פרץ ללולאה בזמן. הם מאוד דומים. אבל אנחנו הולכים לקחת את זה צעד אחד קדימה. עכשיו, אנחנו עושים את אותו הדבר כאן. שים לב שאנחנו חוזרים את אותו הדבר בשתי שורות אלה, פרט לטיעון אחד הוא שונה. אז אנחנו הולכים לעשות את זה לתוך משולש. אני מכה משהו אפשרות, וזה גרם לסמל. אוקיי. אז אנחנו הולכים לחזור מכיל את זה. זה הולך להיות מספר שורות, טוב, זנק בזה. בדרך כלל, כדבר סגנונית, אני לא חושב שהרבה אנשים לשים רווח אחרי החץ, אבל אני מניח שאם אתה עקבי, זה בסדר. אם הערך הוא פחות משווי עץ, אנחנו רוצים רקורסיבית על שמאל עץ, עוד אנחנו רוצים רקורסיבית על זכות עץ. אז זה היה צעד אחד של קבלת המראה הזה קטן יותר. שלב השני לשוות המראה הזה קטן יותר - אנו יכולים להפריד את זה לכמה שורות. אוקיי. שלב השני גורם לו להיראות קטן יותר הוא כאן, כל כך ערך החזרה שווה ערך עץ, או כל מה שמכיל. 

זה דבר חשוב. אני לא בטוח אם הוא אמר את זה במפורש בכיתה, אבל זה נקרא הערכה קצרה במעגל. הרעיון כאן הוא הערך == ערך עץ. אם זה נכון, אז זה נכון, ואנחנו רוצים "או" עם כל מה שהוא כאן. אז בלי לחשוב אפילו על כל מה שהוא כאן, מה הוא הביטוי כולו עומד לחזור? [סטודנטים] אמת? >> כן, בגלל אמיתי של כל דבר, or'd - or'd או אמיתי עם כל דבר הוא בהכרח נכון. אז ברגע שאנחנו רואים את ערך החזרה = ערך עץ, אנחנו פשוט הולכים להחזר אמיתי. אפילו לא הולך רקורסיבית נוסף מכיל לאורך הקו. אנחנו יכולים לקחת את זה צעד אחד קדימה. עץ שבות אינו null שווה וכל זה. זה הפך אותו לפונקציה אחת שורות. זו גם דוגמה של הערכה קצרה במעגל. אבל עכשיו זה אותו הרעיון - במקום - כך שאם עץ אינו ריק שווות - או, טוב, אם העץ עושה null שווה, וזה במקרה הרע, אם עץ שווה אפס, אז התנאי הראשון הולך להיות כוזב. אז השווא anded עם כל דבר הולך להיות מה? [סטודנטים] שקר. >> כן. זה חצי השני של הערכה קצרה במעגל, אם אין בו עץ ריק לא שווה, אז אנחנו לא הולכים אפילו ללכת - או אם העץ עושה null שווה, אז אנחנו לא הולכים לעשות את ערך == ערך עץ. אנחנו רק לחזור מייד שווא. וזה חשוב, שכן אם לא יעשה כך להעריך קצר במעגל, אז אם העץ עושה null שווה, תנאי שני זה הולך אשמת צינוק, בגלל עצים> ערך ביטול הפנית null. אז זהו זה. יכול לעשות את זה - לעבור פעם אחת מעל. זה דבר נפוץ מאוד גם, לא עושה קו זה עם זה, אבל זה דבר נפוץ בתנאים, אולי לא ממש כאן, אבל אם (עץ! = NULL, ועצים> ערך == ערך), לעשות מה. זהו מצב נפוץ מאוד, שבו במקום שיש כדי לשבור את זה לשני IFS, שם תרצו, הוא null העץ? אוקיי, זה לא ריק, כך שעכשיו הוא ערך העץ שווה ערך? לעשות את זה. במקום זאת, זה מצב, זה לעולם לא צינוק אשמה כי זה יהיה לפרוץ אם זה קורה להיות אפס. ובכן, אני מניח שאם העץ שלך הוא מצביע לחלוטין לא חוקי, הוא עדיין יכול צינוק אשמה, אבל זה לא יכול צינוק אשמה אם העץ הוא ריק. אם זה היה ריק, היא הייתה פורצת לפני שאתה בכלל dereferenced המצביע במקום הראשון. [סטודנטים] האם ההערכה עצלנית הזאת? 

[אודן] הערכה עצלה היא דבר נפרד. הערכה היא עצלנית יותר כמו שאתה מבקש ערך, אתה שואל לחישוב ערך, סוג של, אבל אתה לא צריך את זה באופן מיידי. אז עד שאתה באמת צריך אותו, הוא לא מוערך. זה לא בדיוק אותו הדבר, אבל באפמן pset, זה אומר שאנחנו "עצלות" לכתוב. הסיבה שאנחנו עושים את זה בגלל שאנחנו למעשה חציצת הכתיבה - אנחנו לא רוצים לכתוב פיסות בודדות בכל פעם, או בתים בודדים בכל פעם, במקום שאנחנו רוצים לקבל נתח מבתים. ואז ברגע שיש לנו נתח של בתים, ואז תוכל לכתוב את זה. למרות שאתה שואל אותו לכתוב - וfwrite וfread לעשות אותו דבר. הם קוראים החיץ וכותב. למרות שאתה שואל אותו לכתוב באופן מיידי, זה כנראה לא יהיה. ואתה לא יכול להיות בטוח שהדברים הולכים להיכתב עד שאתה קורא hfclose או מה שזה לא, אז מה אומר, בסדר, אני סוגר את התיק שלי, זה אומר שכדאי שאני אכתוב את כל מה שעדיין לא הספקתי לכתוב. זה אינו צריך לכתוב הכול עד שאתה סוגר את הקובץ, ולאחר מכן הוא צריך. אז זה בדיוק מה שעצלן - הוא מחכה עד שזה יקרה. זה - לקחת 51 ואתה נכנסת לזה בפירוט רב יותר, בגלל OCaml והכילו בשנת 51, הכל רקורסיה. אין איטרטיבי פתרונות, בעצם. הכל רקורסיה, והערכה עצלנית הולך להיות חשוב להרבה נסיבות היכן, אם לא בעצלות להעריך, שזה אומר - הדוגמא לכך היא זרמים, שהם אינסופיים. בתאוריה, אתה יכול לחשוב על המספרים הטבעיים כזרם של 1-2-3-4-5-6-7, דברים העריכו אז עצלות הם בסדר גמורים. אם אני אומר שאני רוצה את המספר 10, אז אני יכול להעריך עד המספר 10. אם אני רוצה את המספר מאה, אז אני יכול להעריך עד כמה מאה. ללא הערכה עצלנית, אז זה הולך לנסות ולהעריך את כל המספרים באופן מיידי. אתה הערכה רבים לאין שיעור מספרים, וזה פשוט לא אפשרי. אז יש הרבה מקרים שבם הערכה עצלנית הוא פשוט חיוני להשגת דברים לעבוד. 

עכשיו אנחנו רוצים לכתוב להכניס בי להוסיף הולכים להיות בדומה שינוי בהגדרתו. אז עכשיו זה להכניס bool (ערך int). אנחנו הולכים לשנות את זה כדי להכניס bool (int ערך, צומת * עץ). בעצם אנחנו הולכים לשנות את זה שוב בקצת, יראו למה. ובואו נעבור build_node, סתם בשביל כיף שלו, מעל להוסיף ולכן אנחנו לא צריכים לכתוב אב טיפוס פונקציה. וזה רמז שאתה הולך להיות באמצעות build_node בעלון. אוקיי. קח דקה בשביל זה. אני חושב שהצלתי את התיקון אם אתה רוצה למשוך מזה, או, לפחות, שעשיתי עכשיו. רציתי הפסקה קלה לחשוב על ההיגיון של הוספה, אם אתה לא יכול לחשוב על זה. בעיקרון, אתה היחיד שאי אפשר להכניס אל עלים. כאילו, אם אני מכניס 1, אז אני באופן בלתי נמנע הולך להיות החדרת 1 - אני אשנה לשחור - אני אהיה החדרת 1 כאן. או אם אני מכניס 4, אני רוצה להיות החדרת 4 כאן. אז לא משנה מה אתה עושה, אתה הולך להיות בהחדרת עלה. כל מה שאתה צריך לעשות הוא לחזר במורד העץ עד שתגיע לצומת שצריך להיות ההורה של הצומת, ההורה של צומת החדש, ולאחר מכן לשנות את המצביע ימינה או שמאלה, תלויים אם זה גדול יותר או קטן יותר מהצומת הנוכחית. שנה מצביע שיצביע לצומת החדשה שלך. אז לחזר במורד העץ, להפוך את נקודת העלה לצומת החדשה. גם לחשוב על הסיבה שאוסר על הסוג של מצב לפני, איפה אני בנוי העץ בינארי שבו היה נכון אם נראה רק בצומת אחת, אבל 9 היו בצד השמאל של 7 אם אתה חוזר על עצמו כל הדרך למטה. אז זה בלתי אפשרי בתרחיש זה, שכן - חושבים על החדרת 9 או משהו; בצומת הראשונה, אני הולך לראות 7 ואני רק הולך לצד ימין. אז לא משנה מה אני עושה, אם אני מחדיר על ידי הולך לעלה, ולעלה באמצעות האלגוריתם המתאים, זה הולך להיות בלתי אפשרי עבורי להכניס 9 משמאל 7 כי ברגע שאני מכה 7 אני הולך לצד ימין. האם יש למישהו משהו להתחיל איתו? [סטודנטים] שאני עושה. >> בטח. [סטודנטים, לא מובנים] [תלמיד אחר, לא מובן] [אודן] זה מוערך. אוקיי. רוצה להסביר? 

[סטודנטים] מכיוון שאנו יודעים שאנחנו מכניסים צומת חדשים בסוף העץ, אני הושחלתי דרך העץ ערוך את עד שהגעתי לצומת שהצביעה על null. ואז החלטתי לשים אותו גם בצד ימין או בצד השמאל שימוש במשתנה זה נכון, זה אמר לי איפה לשים אותו. ואז, בעצם, אני פשוט עשה שעברתי - נקודת הצומת הזמנית לצומת החדשה שהיא יוצרת, או בצד השמאל או בצד ימין, תלוי מה הערך היה נכון. לבסוף, אני מגדיר את ערך הצומת החדשה לערך של הבדיקה שלו. [אודן] אוקיי, אז אני רואה את עניין אחד. זה כמו 95% בדרך לשם. נושא אחד שאני רואה, טוב, אף אחד אחר לא רואה בעיה? מה הן הנסיבות שתחתו הם פורצים מתוך הלולאה? [סטודנטים] אם זמני הוא ריק? >> כן. אז איך אתה לפרוץ את הלולאה הוא אם זמני הוא ריקה. אבל מה אני עושה כאן? אני טמפ dereference, שהוא בהכרח בטל. אז הדבר השני שאתה צריך לעשות הוא לא רק לעקוב עד טמפ הוא ריק, אתה רוצה לשמור על מסלולו של ההורה בכל העת. גם אנחנו רוצים הורה * צומת, אני מניח שאנחנו יכולים לשמור את זה באפס בהתחלה. זה הולך לי התנהגות מוזרה לשורש של העץ, אבל אנחנו עוד נגיע לזה. אם הערך הוא גדול יותר מכל דבר אחר, אז temp = זכות זמנית. אבל לפני שאנחנו עושים את זה, הורה = זמני. או ההורים תמיד הולכים לטמפ השווה? האם זה המקרה? אם טמפ 'הוא לא ריק, אז אני הולך לרדת, לא משנה מה, לצומת שבי זמני היא ההורה. אז ההורה הולך להיות זמני, ולאחר מכן אני מזיז את טמפ. עכשיו זמני הוא אפס, אבל נקודתי הורה להורה של הדבר שהוא ריק. אז הנה, אני לא רוצה להגדיר זכות שווה 1. אז עברתי לצד ימין, כך שאם זכות = 1, ואני מניח שאתה גם רוצה לעשות - אם אתה עובר לשמאל, אתה רוצה להגדיר זכות שווה 0. או שאם אי פעם לעבור לצד ימין. כל כך נכון = 0. אם זכות = 1, עכשיו אנחנו רוצים לעשות newnode מצביע ההורה הנכון, עוד אנחנו רוצים לעשות newnode מצביע הורה השמאל. שאלות על זה? אוקיי. אז זו דרכנו - טוב, למעשה, במקום לעשות את זה, אנחנו כמעט מצפים לך להשתמש build_node. ואז, אם newnode שווה אפס, בתמורת שווא. זהו זה. עכשיו, זה מה שאנחנו מצפים ממך לעשות. 

זה מה שאת הפתרונים שצוות יעשו. אני לא מסכים עם זה כדרך "הנכונה" של הולך על זה אבל זה בסדר גמור וזה יעבוד. דבר אחד זה ממש מוזר קצת כרגע הוא אם העץ מתחיל כמו ריק, אנחנו מעבירים בעץ ריק. אני מניח שזה תלוי איך אתה מגדיר את ההתנהגות של עובר בעץ ריק. אני חושב שאם אתה עובר בעץ ריק, לאחר מכן להכניס את הערך לתוך עץ ריק פשוט צריך לחזור לעץ שבו הערך היחיד הוא שצומת אחת. האם אנשים מסכימים עם זה? אתה יכול, אם אתה רוצה, אם אתה עובר בעץ ריק ואתה רוצה להוסיף ערך לזה, בתמורת שווא. זה תלוי בך כדי להגדיר את זה. כדי לעשות את הדבר הראשון שאמרתי ואז - כן, אתה הולך מתקשה לעשות זאת, כי זה יהיה קל יותר אם היה לנו מצביע גלובלי הדבר, אבל אנחנו לא, כך שאם העץ הוא ריק, אין שום דבר שאנחנו יכולים לעשות בקשר לזה. אנחנו רק יכולים לחזור שווא. אז אני הולך לשנות להוסיף. אנחנו מבחינה טכנית פשוט יכולים לשנות זאת כאן, איך זה iterating על דברים, אבל אני הולך לשנות להוסיף לקחת צומת ** עץ. מצביעים כפולים. מה זה אומר? במקום להתמודד עם מצביעים לצומת, הדבר שאני עומד להיות מניפולציה הוא זו מצביע. אני הולך להיות מניפולצית מצביע זה. אני הולך להיות מניפולצית מצביעים באופן ישיר. זה הגיוני שכן, חושב על מה שיש - טוב, עכשיו זה נקודות לnull. מה שאני רוצה לעשות הוא לתפעל את הסמן לנקודה זו לא null. אני רוצה שזה מצביע על הצומת החדשה שלי. אם אני רק לעקוב אחר מצביעים למצביעים שלי, אז אני לא צריך לעקוב אחרי מצביע הורה. אני רק יכול לעקוב כדי לראות אם המצביע מצביע על null, ואם המצביע מצביע על null, לשנות אותו כך שתצביע על הצומת שאני רוצה. ואני יכול לשנות את זה מאז שיש לי מצביע למצביע. בואו לראות את זה עכשיו. למעשה אתה יכול לעשות את זה באופן רקורסיבי די בקלות. האם אנחנו רוצים לעשות את זה? כן, אנחנו עושים. 

בואו לראות את זה באופן רקורסיבי. ראשית, מהו מקרה הבסיס שלנו הולך להיות? כמעט תמיד מקרה הבסיס שלנו, אבל למעשה, זה סוג של מסובך. דבר ראשון, אם (עץ == NULL) אני מניח שאנחנו פשוט הולכים בתמורת שווא. זה שונה מלהיות null העץ שלך. זה מצביע למצביע השורש שלך להיות null מה שאומר שמצביע השורש שלך לא קיים. אז הנה, אם אני עושה * צומת - בואו רק שימוש חוזרים בזה. * צומת שורש = NULL, ואז אני הולך להתקשר להוספה על ידי עושה משהו כמו, להוסיף 4 ולשורש. אז & שורש, אם שורש הוא צומת * אז & שורש הולך להיות ** צומת. זה בתוקף. במקרה זה, עץ, עד כאן, העץ הוא לא ריק - או להוסיף. כאן. עץ אינו ריק; * עץ הוא ריק, וזה בסדר כי אם העץ * הוא ריק, אז אני יכול לתפעל אותו עכשיו להצביע על מה שאני רוצה שזה יצביע. אבל אם העץ הוא ריק, זה אומר שפשוט הגיע לכאן ואמר ריק. זה לא הגיוני. אני לא יכול לעשות כלום עם זה. אם העץ הוא ריק, בתמורת שווא. אז אני בעצם כבר אמרתי את מה שהמקרה שלנו הוא הבסיס האמיתי. ומה שהולך להיות? [סטודנטים, לא מובנים] [אודן] כן. אז אם (* העץ == NULL). זה מתייחס למקרה כאן שבו אם המצביע האדום שלי הוא המצביע אני מתמקד ב, אז כמו שאני מתמקד במצביע זה, עכשיו אני מתמקד במצביע זה. עכשיו אני מתמקד במצביע זה. אז אם המצביע האדום שלי, שהוא ** הצומת שלי, הוא אי - אם *, המצביע האדום שלי, הוא אי פעם null, זה אומר שאני במקרה שבו אני מתמקד במצביע שנקודות - זה הוא מצביע ששייכת לעלה. אני רוצה לשנות את מצביע זה כדי להצביע על הצומת החדשה שלי. תחזור לכאן. newnode יהיה רק ​​צומת * n = build_node (ערך) אז n, אם n = NULL, בתמורת שווא. עוד אנחנו רוצים לשנות את מה שהמצביע כיום מצביע על עכשיו להצביע על הצומת שלנו חדש שנבנתה. אנחנו באמת יכולים לעשות את זה כאן. במקום לומר n, אנחנו אומרים * אם עץ = עץ *. כולם מבינים את זה? שעל ידי התמודדות עם מצביעים למצביעים, אנחנו יכולים לשנות את מצביעי null להצביע על דברים שאנחנו רוצים שהם יצביעו. זה מקרה הבסיס שלנו. 

עכשיו ההישנות שלנו, או רקורסיה שלנו, הולך להיות דומה מאוד לכל recursions האחר שאנחנו עושים. אנחנו הולכים ברצונך להוסיף ערך, ועכשיו אני הולך להשתמש משולש שוב, אבל מה מצבנו הולך להיות? איך זה שאנחנו מחפש כדי להחליט אם אנחנו רוצים ללכת ימינה או שמאלה? בואו נעשה את זה בשלבים נפרדים. אם (ערך <) מה? [סטודנטים] הערך של העץ? [אודן] אז תזכור שאני כרגע - [סטודנטים], לא ברור, [אודן] כן, אז ממש כאן, בוא נגיד שהחץ הירוק הזה הוא דוגמה למה שהעץ הוא כיום, הוא מצביע למצביע זה. אז זה אומר שאני מצביע למצביע ל 3. Dereference פעמים נשמע טוב. מה אני - איך אני עושה את זה? [סטודנטים] Dereference פעם אחת, ולאחר מכן חץ לעשות ככה? [אודן] אז (* עץ) הוא dereference פעם אחת, -> ערך הוא הולך לתת לי את הערך של הצומת שבעקיפין אני מצביע. אז גם אני יכול לכתוב את זה ** tree.value אם אתה מעדיף את זה. כך או עובד. אם זה המקרה, אז אני רוצה להתקשר ללהכניס עם ערך. ומה היא הצומת מתעדכנת ** הולכת להיות? אני רוצה ללכת לשמאל, ולכן ** tree.left הולך להיות שמאלית. ואני רוצה את המצביע לאותו דבר כך שאם השמאל בסופו להיות המצביע הריק, אני יכול לשנות אותו כדי להצביע על הצומת החדשה שלי. 

ואילו במקרה האחר יכול להיות מאוד דומה. בואו בעצם לעשות כי המשולש שלי כרגע. הכנס ערך אם ערך <(** עץ). ערך. אז אנחנו רוצים לעדכן ** לשמאל, עוד אנחנו רוצים לעדכן ** לצד ימין. [סטודנטים] האם שמקבלים את המצביע למצביע? [אודן] זכור ש-- ** tree.right הוא כוכב צומת. [סטודנטים, לא מובנים] >> כן. ** Tree.right הוא כמו מצביע או משהו. אז על ידי לקיחה מצביע לזה, זה נותן לי מה שאני רוצה של המצביע לטיפוס הזה. [סטודנטים] נוכל ללכת שוב למה אנחנו משתמשים בשני המצביעים? [אודן] כן. אז - לא, אתה יכול, ושפתרון לפני היה דרך לעשות את זה בלי לעשות שני מצביעים. אתה צריך להיות מסוגל להבין באמצעות שני מצביעים, וזה פתרון נקי יותר. כמו כן, שים לב כי, מה קורה אם העץ שלי - מה קורה אם השורש שלי היה ריק? מה קורה אם אני עושה את המקרה הזה כאן ועכשיו? אז צומת שורש * = NULL, להוסיף 4 ולשורש. מה השורש הולך להיות אחרי זה? [סטודנטים, לא מובנים] >> כן. ערך רוט הוא הולך להיות 4. שמאל רוט הוא הולך להיות ריק, נכון שורש הולך להיות אפס. במקרה שבו אנחנו לא עוברים שורש לפי כתובת, אנחנו לא יכולים לשנות את השורש. במקרה שבו העץ - שבו השורש היה ריק, אנחנו פשוט נאלצנו לחזור שווא. אין שום דבר שאנחנו יכולים לעשות. אנחנו לא יכולים להוסיף צומת לעץ ריק. אבל עכשיו אנחנו יכולים, אנחנו פשוט עושים עץ ריק לעץ אחד צמתים. איזו היא בדרך כלל הדרך הצפויה שהוא אמור לעבוד. 

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

ומה מיוחד בפונקציה רקורסיבית זה? זה זנב רקורסיבית, ולכן כל זמן שאנו עורכים עם אופטימיזציה מסוימת, הוא יזהה את זה ואתה אף פעם לא תקבל הצפת ערימה מזה, גם אם העץ שלנו יש לו גובה של 10,000 או 10 מ'. [סטודנטים, לא מובנים] [אודן] אני חושב שהיא עושה את זה בדש - או מה רמת האופטימיזציה נדרש לרקורסיה זנב להיות מוכרים. אני חושב שהוא מכיר - GCC וקלאנג גם יש משמעויות שונות לרמות אופטימיזציה שלהם. אני רוצה לומר שזה DashO 2, בודאות שהוא יזהה רקורסיה זנב. אבל אנחנו - אתה יכול לבנות כמו למשל או משהו Fibonocci. זה לא קל כדי לבדוק עם זה, כי זה קשה לבנות עץ בינארי שכל כך גדול. אבל כן, אני חושב שזה DashO 2, כי אם אתה לקמפל עם DashO 2, זה ייראה לרקורסיה זנב ולייעל את זה. בואו נחזור ל-- הכנס פשוט כמשמעה הדבר האחרון שהוא צריך. בואו נחזור להוספה כאן לאן אנחנו הולכים לעשות את אותו הרעיון. זה עדיין יש פגם של חוסר היכולת להתמודד עם כל כאשר השורש עצמו הוא ריק, או כניסת העבר היא ריקה, במקום להתמודד עם מצביע הוריו, אלא, בואו ננסה להפעיל את אותו ההיגיון של מצביעים שומרים למצביעים. אם כאן אנחנו שומרים הצומת ** נוכ, ואנחנו לא צריכים לעקוב אחר נכונים יותר, אבל צומת ** נוכ = & עץ. ועכשיו הלולאה בזמן שלנו הולכת להיות בזמן נוכ * לא null שווה. לא צריך לעקוב אחר הורים יותר. לא צריך לעקוב אחר שמאל וימין. ואני אקרא לו זמני, כי אנחנו כבר משתמשים זמניים. אוקיי. אז אם (ערך> * זמני), אז & (* temp) -> ימין אחר temp = & (* temp) -> עזב. ועכשיו, בשלב זה, לאחר שהלולאה בזמן הזה, אני עושה את זה רק בגלל שאולי זה יותר קל לחשוב על ערוך את מרקורסיבי, אבל אחרי הלולאה בזמן הזה, * זמני הוא המצביע אנחנו רוצים לשנות. 

לפני שהיינו לנו הורים, ואנחנו רוצים לשנות או שמאליים או ימני הורה הורה, אם אנחנו רוצים לשנות את זכות הוריו, אלא, אז * זמני הוא זכות הורה, ואנחנו יכולים לשנות אותו ישירות. אז הנה, אנחנו יכולים לעשות * temp = newnode, וזהו זה. אז הודעה, כל מה שעשינו בזה, זה להזמין את שורות קוד. כדי לעקוב אחר ההורה בכל זה הוא מאמץ נוסף. הנה, אם רק לעקוב אחר המצביע למצביע, גם אם הייתי רוצה להיפטר מכל הסוגריים המסולסלים האלה עכשיו ו, לגרום לזה להיראות יותר קצר. זה עכשיו הוא אותו הפתרון המדויק, אבל פחות שורות קוד. ברגע שאתה מתחיל להכיר בזה כפתרון תקף, זה גם קל יותר מאשר על סיבה כאילו טוב, למה אני צריך את הדגל הזה בימין int? מה זה אומר? אה, זה מסמן שיש בכל פעם שאני הולך ועושה, אני צריכה להגדיר אותו, אחר אם אני הולך עזבתי אני צריך להגדיר אותו לאפס. כאן, אין לי סיבה לעל זה, זה פשוט קל יותר לחשוב עליו. שאלות? [סטודנטים, לא מובנים] >> כן. אוקיי, אז בחלק האחרון - אני מניח שתפקוד מהיר וקל אחד שאנחנו יכולים לעשות הוא, בואי - יחד, אני מניח, אנסה לכתוב מכיל פונקציה מה שלא אכפת לי אם זה עץ חיפוש. זה מכיל פונקציה צריכה להחזיר אמיתית אם בכל מקום בעץ בינארי הכללי זו הוא הערך שאנחנו מחפשים. אז בואו נעשה את זה קודם באופן רקורסיבי ואז אנחנו נעשה את זה ערוך את. אנחנו למעשה יכולים פשוט לעשות את זה ביחד, כי זה הולך להיות ממש קצר. 

מה מקרה הבסיס שלי הולך להיות? [סטודנטים, לא מובנים] [אודן] אז אם (העץ == NULL), ואז מה? [סטודנטים] בתמורת שווא. [אודן] אחר, טוב, אני לא צריך עוד. אם היה מקרה הבסיס השני שלי. הערך [סטודנטים] של העץ? >> כן. אז אם (עץ> ערך == ערך. שים לב שחזרנו ל* צומת, לא צומת של **? , מכיל לעולם לא צריך להשתמש ב** צומת, מאז אנחנו לא שינוי מצביעים. אנחנו רק חוצים אותם. אם זה יקר, אז אנחנו רוצים לחזור אמיתיים. אחר אנחנו רוצים לעבור את הילדים. אז אנחנו לא יכולים לדבר בהיגיון על שאלה אם הכל לשמאל הוא פחות והכל בצד הימין הוא גדול יותר. אז מה מצבנו הולך להיות כאן - או, מה אנחנו הולכים לעשות? [סטודנטים, לא מובנים] >> כן. חזור מכיל (ערך, עץ-> שמאל) או שהוא מכיל (ערך, עץ> מימין). וזהו זה. ושים לב יש כמה הערכה קצרה במעגל, שבו אם אנחנו לקרות כדי למצוא את הערך בעץ השמאלי, לא שאנחנו צריכים להסתכל על העץ הנכון. זה כל הפונקציה. עכשיו בואו נעשה את זה ערוך את, שהוא הולך להיות פחות נחמד. אנחנו ניקח את תחילתו הרגילה של הצומת נוכ * = עץ. בעוד (נוכ! = NULL). מהירות הולך לראות את הבעיה. אם נוכ - פה, אם אי פעם לצאת מזה, אז נגמרנו לנו דברים כדי להסתכל, אז בתמורת שווא. אם (נוכ-> ערך == ערך), החזר אמיתי. אז עכשיו, אנחנו נמצאים במקום - אנחנו לא יודעים אם אנחנו רוצים ללכת ימינה או שמאלה. אז באופן שרירותי, בואו פשוט ללכת שמאלה. ברור שאני נתקלתי בבעיה שבה אני כבר נטשתי את הכל לחלוטין - אני יחיד שאבדוק את הצד השמאלי של עץ. אני לעולם לא לבדוק כל דבר שילד זכותו של דבר. כיצד אני יכול לתקן את זה? [סטודנטים] יש לך לעקוב אחר מהשמאל ומימין בערימה. [אודן] כן. אז בוא לעשות את זה struct רשימה, צומת * n, ולאחר מכן צומת ** הבא? אני חושב שזה עובד בסדר. אנחנו רוצים ללכת על צד השמאל, או בואי - עד כאן. = רשימת רשימת struct, זה יתחיל יצא ברשימת struct זה. * רשימה = NULL. אז זה הולך להיות הרשימה המקושרת שלנו של עצי משנה שיש לנו לדלג מעל. אנחנו הולכים לעבור עכשיו עזבנו, מאז שבהכרח צריכים לחזור לימין, אבל, אנחנו מתכוונים להמשיך בצד ימין בתוך רשימת struct שלנו. אז יהיה לנו new_list או struct, struct רשימה *, new_list = malloc (sizeof (רשימה)). אני הולך להתעלם משגיאה שתוודא כי, אבל אתה צריך לבדוק אם הוא ריק של. New_list צומת זה הולך להצביע - הו, זו הסיבה שאני רוצה אותו כאן. זה הולך להצביע לרשימת struct 2. זה רק איך שמקושר לרשימות. זה אותו הדבר כמו רשימה מקושרת int למעט אנחנו רק החלפה עם int * צומת. זה בדיוק אותו הדבר. אז new_list, הערך של צומת new_list, הולך להיות נוכ-> נכון. הערך שלנו new_list-> הבא הולך להיות הרשימה המקורית שלנו, ואז אנחנו הולכים לעדכן את הרשימה שלנו להצביע על new_list. 

עכשיו אנחנו צריכים איזה דרך של דברים מושכים, כמו שכבר חצו את כל עץ משנה שמאל כולו. עכשיו אנחנו צריכים למשוך את החומר ממנו, כמו נוכ הוא ריק, אנחנו לא רוצים רק לחזור שווא. אנחנו רוצים עכשיו למשוך החוצה ברשימה החדשה שלנו. דרך נוחה ביותר לעשות זאת - טובה, למעשה, יש דרכים רבות לעשות זאת. למישהו יש הצעה? איפה כדאי לעשות את זה או איך אני אמור לעשות את זה? יש לנו רק כמה דקות, אבל כל הצעה? במקום - דרך אחת, במקום לראות את המצב שלנו להיות בזמן, מה אנחנו כרגע מסתכלים הוא לא ריק, במקום שאנחנו הולכים להמשיך ללכת עד הרשימה עוצמה היא ריקה. אז אם הרשימה שלנו בסופו להיות ריק, אז נגמרנו לנו דברים לחפש, לחפש ב. אבל זה אומר שהדבר הראשון ברשימה שלנו הוא רק הולך להיות הצומת הראשונה. הדבר הראשון שיהיה - לא עוד אנחנו צריכים לראות את זה. אז רשימה-> n יהיה העץ שלנו. רשימה-> הבא הולך להיות ריק. ועכשיו בזמן שרשימה אינה ריקה שווה. ס הולך לשלוף משהו מהרשימה שלנו. אז נוכ הולך שווה רשימה-> n. ואז רשימה הולכת שווה רשימה-> n, או רשימה-> הבא. אז אם ערך נוכ שווה ערך. עכשיו אנחנו יכולים להוסיף גם מצביע זכותנו ומצביע שמאלנו כל עוד הם לא ריקים. כאן למטה, אני מניח שאנחנו צריכים לעשות את זה במקום הראשון. אם (נוכ-> נכון! = NULL) אז אנחנו הולכים להכניס לתוך צומת שהרשימה שלנו. אם (נוכ-> שמאל), זה קצת עבודה נוספת, אבל זה בסדר. אם (נוכ-> שמאל! = NULL), ואנחנו הולכים להכניס את השמאל לרשימה המקושרת שלנו, ושצריך להיות בו. שנעמיק - כל עוד יש לנו משהו ברשימה שלנו, יש לנו צומת אחר להסתכל עליו. אז אנחנו מסתכלים כי צומת, אנחנו מקדמים הרשימה שלנו לפעם הבאה. אם צומת שהוא הערך שאנחנו מחפשים, אנחנו יכולים לחזור אמיתיים. אחר להכניס שני עצי המשנה ימניים והשמאליים שלנו, כל עוד הם לא ריקים, לרשימה שלנו כך שבהכרח לעבור עליהם. אז אם הם לא היו ריקים, אם מצביע השורש שלנו הצביע על שני דברים, אז בהתחלה הוציאה משהו כל כך הרשימה שלנו בסופו להיות אפס. ואז אנחנו שמים את שני דברים בגב, אז עכשיו הרשימה שלנו היא בגודל 2. ואז אנחנו הולכים ללולאה בחזרה ואנחנו רק הולכים למשוך, נניח, המצביע השמאלי של צומת השורש שלנו. וזה פשוט ימשיך לקרות, יהיה לנו בסופו של לופים מעל הכל. 

שים לב שזה היה משמעותי יותר מסובך בפתרון רקורסיבי. ואני כבר אמרתי מספר פעמים שפתרון רקורסיבי בדרך כלל יש הרבה במשותף עם איטרטיבי פתרון. הנה זה בדיוק מה פתרון רקורסיבי הוא עושה. השינוי היחיד הוא שבמקום להשתמש במחסנית במשתמע, ערימת התכנית, כדרך של שמירה על מסלול של מה צומת אתה עדיין צריך לבקרך, עכשיו יש לך במפורש להשתמש ברשימה מקושרת. בשני המקרים אתה עוקב אחרי מה שצומת עדיין צריכה להיות בקרה. במקרה רקורסיבית זה פשוט יותר קל, כי מחסנית מיושם עבורך כערימת תכנית. שים לב שרשימה מקושרת זה, ערימה. מה אנחנו פשוט לשים בערימה מייד הוא מה שאנחנו הולכים לעשות את המחסנית לביקור הבא. נגמרנו לנו הזמן, אבל כל שאלה? [סטודנטים, לא מובנים] [אודן] כן. אז אם יש לנו הרשימה המקושרת שלנו, נוכחי הולך להצביע על הבחור הזה, ועכשיו אנחנו רק קידום הרשימה המקושרת שלנו להתמקד בבחור הזה. אנחנו חוצים על הרשימה המקושרת בקו זה. ואז אני מניח שאנחנו צריכים לשחרר את הרשימה וחומר המקושר רגע לפני החזרת אמת או שקר, אנחנו צריכים לחזר על הרשימה המקושרת שלנו ותמיד כאן, אני מניח, אם נוכ הנכון הוא לא שווה, להוסיף אותו, אז עכשיו אנחנו רוצים לשחרר נוכ כי, ובכן, האם אנחנו שוכחים לגמרי מהרשימה? Yeah. אז זה מה שאנחנו רוצים לעשות כאן. איפה מצביע? ס היה אז - אנחנו רוצים struct רשימה * 10 שווי רשימה הבאה. רשימה חינם, רשימה = זמני. ובמקרה שבו אנחנו חוזרים נכונים, אנחנו צריכים כדי לחזר על פני יתרת הרשימה המקושרת שלנו לשחרר את הדברים. דבר נחמד על פתרון רקורסיבי הוא משחרר דברים רק אומר factorings מקפץ ערימה שתקרה לך. אז אנחנו מתרחקים ממשהו שהוא כמו 3 שורות שקשה לחשוב על הקוד- למשהו שהוא באופן משמעותי הרבה יותר קשה לחושב-על שורות קוד. עוד שאלות? בסדר. אנחנו טובים. ביי! [CS50.TV]