1 00:00:00,000 --> 00:00:02,770 [Powered by Google Translate] بخش 7: راحت تر] 2 00:00:02,770 --> 00:00:05,090 [راب Bowden] [دانشگاه هاروارد] 3 00:00:05,090 --> 00:00:07,930 [این CS50] [CS50.TV] 4 00:00:07,930 --> 00:00:10,110 بسیار خوب. بنابراین مثل من ایمیل من گفت، 5 00:00:10,110 --> 00:00:14,060 این است که برای رفتن به بخش دودویی درخت فشرده است. 6 00:00:14,060 --> 00:00:16,820 اما این است که بسیاری از سوالات وجود ندارد. 7 00:00:16,820 --> 00:00:18,920 بنابراین ما قصد داریم به تلاش و رسم هر سوال 8 00:00:18,920 --> 00:00:25,430 و به جزئیات دردناک از همه بهترین راه برای انجام کارها است. 9 00:00:25,430 --> 00:00:31,200 بنابراین در آغاز، ما را از طریق نقشه های نمونه ای از درخت های دودویی و چیزهای بروید. 10 00:00:31,200 --> 00:00:35,970 بنابراین در اینجا، "به یاد داشته باشید که یک درخت دودویی گره ها شبیه به کسانی که از یک لیست پیوندی، 11 00:00:35,970 --> 00:00:38,150 به جز به جای آن از یک اشاره گر دو وجود دارد: یکی برای کودک سمت چپ 12 00:00:38,150 --> 00:00:41,950 و یکی برای حق کودک است. " 13 00:00:41,950 --> 00:00:45,630 بنابراین یک درخت دودویی است که درست مثل یک لیست پیوندی، 14 00:00:45,630 --> 00:00:47,910 به جز ساختار به دو اشاره گر. 15 00:00:47,910 --> 00:00:51,390 درختان سه گانه، که در حال رفتن به سه اشاره گر وجود دارد، 16 00:00:51,390 --> 00:00:56,540 N-ARY درختان، وجود دارد که فقط باید یک اشاره گر عمومی 17 00:00:56,540 --> 00:01:00,320 که بعد از آن شما به malloc به اندازه کافی بزرگ را به 18 00:01:00,320 --> 00:01:04,840 اشاره گر به اندازه کافی برای همه کودکان ممکن است. 19 00:01:04,840 --> 00:01:08,200 بنابراین درخت باینری فقط اتفاق می افتد که یک شماره ثابت از دو است. 20 00:01:08,200 --> 00:01:11,260 اگر شما می خواهید، شما می توانید یک لیست پیوندی به عنوان یک درخت یگانی، 21 00:01:11,260 --> 00:01:15,360 اما من فکر نمی کنم هر کسی خواستار آن است که. 22 00:01:15,360 --> 00:01:18,060 "رسم نمودار جعبه و فلش از یک گره در درخت جستجوی دودویی 23 00:01:18,060 --> 00:01:24,110 حاوی شماره مورد علاقه مقابله، 7، که در آن هر کودک اشاره گر تهی است. " 24 00:01:24,110 --> 00:01:27,780 بنابراین iPad در حالت. 25 00:01:27,780 --> 00:01:30,280 >> رفتن به صورت کاملا سر راست است. 26 00:01:30,280 --> 00:01:36,150 ما در حال رفتن به یک گره، من آن را به عنوان یک مربع رسم کنید. 27 00:01:36,150 --> 00:01:38,730 و من از ارزش ها در اینجا جلب کند. 28 00:01:38,730 --> 00:01:41,090 بنابراین ارزش در اینجا، 29 00:01:41,090 --> 00:01:44,770 و سپس در اینجا ما می خواهیم اشاره گر چپ در سمت چپ و اشاره گر راست در سمت راست داشته باشد. 30 00:01:44,770 --> 00:01:50,430 و آن را بسیار بسیار، بنابراین کنوانسیون آن را به چپ و راست، نام اشاره گر است. 31 00:01:50,430 --> 00:01:52,460 هر دو از این رفتن به تهی. 32 00:01:52,460 --> 00:01:57,870 این تنها تهی می شود، و این فقط null خواهد بود. 33 00:01:57,870 --> 00:02:03,630 باشه. پس به اینجا عقب. 34 00:02:03,630 --> 00:02:05,700 "با لیست پیوندی، ما فقط تا به حال به یک اشاره گر ذخیره 35 00:02:05,700 --> 00:02:09,639 به اولین گره در لیست به منظور به یاد داشته باشید کل مرتبط با لیست و فهرست کامل است. 36 00:02:09,639 --> 00:02:11,650 به همین ترتیب، با درختان، ما فقط باید برای ذخیره یک اشاره گر 37 00:02:11,650 --> 00:02:13,420 به یک گره تنها به منظور به یاد داشته باشید تمام درخت. 38 00:02:13,420 --> 00:02:15,980 این گره calle 'ریشه' درخت. 39 00:02:15,980 --> 00:02:18,320 بر نمودار خود را قبل از ساخت و یا قرعه کشی یک 40 00:02:18,320 --> 00:02:21,690 به طوری که شما باید تصویر جعبه و فلش از یک درخت دودویی 41 00:02:21,690 --> 00:02:25,730 با ارزش 7 و سپس 3 و در سمت چپ، 42 00:02:25,730 --> 00:02:32,760 پس از آن 9 در سمت راست، و پس از آن 6 در سمت راست از 3 است. " 43 00:02:32,760 --> 00:02:34,810 بیایید ببینید اگر من می توانم تمام آن در سر من به یاد داشته باشید. 44 00:02:34,810 --> 00:02:37,670 پس این است که برای رفتن به ریشه ما تا اینجا. 45 00:02:37,670 --> 00:02:41,600 خواهیم برخی از اشاره گر را در جایی داشته باشند، و این چیزی است که خواهیم ریشه تماس، 46 00:02:41,600 --> 00:02:45,140 و آن را با اشاره به این پسر. 47 00:02:45,140 --> 00:02:48,490 در حال حاضر به یک گره جدید 48 00:02:48,490 --> 00:02:52,870 چه چیزی ما را داشته باشد، 3 در سمت چپ است؟ 49 00:02:52,870 --> 00:02:57,140 بنابراین یک گره جدید با 3 است، و آن را در ابتدا اشاره تهی. 50 00:02:57,140 --> 00:02:59,190 من فقط N. قرار داده است 51 00:02:59,190 --> 00:03:02,250 حالا ما می خواهیم را که رفتن به سمت چپ 7. 52 00:03:02,250 --> 00:03:06,840 پس این اشاره گر را تغییر داد به حال به این پسر. 53 00:03:06,840 --> 00:03:12,420 و ما همین کار را بکنند. ما می خواهیم 9 در اینجا 54 00:03:12,420 --> 00:03:14,620 که در ابتدا فقط تهی می گوید. 55 00:03:14,620 --> 00:03:19,600 ما در حال رفتن به تغییر این اشاره گر، نقطه تا 9، 56 00:03:19,600 --> 00:03:23,310 و در حال حاضر ما می خواهم برای قرار دادن 6 به حق 3. 57 00:03:23,310 --> 00:03:32,170 پس از آن رفتن به - از 6. 58 00:03:32,170 --> 00:03:34,310 و این مرد وجود دارد نقطه. 59 00:03:34,310 --> 00:03:38,320 باشه. به طوری که همه از ما می خواهد را انجام دهد. 60 00:03:38,320 --> 00:03:42,770 >> در حال حاضر به بیش از بعضی از اصطلاحات. 61 00:03:42,770 --> 00:03:46,690 ما در حال حاضر در مورد چگونگی ریشه از درخت بالا ترین گره در درخت است صحبت کردیم. 62 00:03:46,690 --> 00:03:54,720 شامل 7. گره در پایین درخت برگ نامیده می شوند. 63 00:03:54,720 --> 00:04:01,240 هر گره که فقط آن را به عنوان فرزندان آن تهی است، یک برگ است. 64 00:04:01,240 --> 00:04:03,680 پس از آن امکان پذیر است، اگر درخت باینری ما این است که فقط یک گره، 65 00:04:03,680 --> 00:04:10,130 که یک درخت یک برگ است، و این از آن است. 66 00:04:10,130 --> 00:04:12,060 "" ارتفاع درخت تعدادی از گره شما را 67 00:04:12,060 --> 00:04:16,620 از بالا به یک برگ است. " 68 00:04:16,620 --> 00:04:18,640 خواهیم به دریافت، در یک ثانیه، تفاوت 69 00:04:18,640 --> 00:04:21,940 بین درخت دودویی متعادل و نامتعادل، 70 00:04:21,940 --> 00:04:29,470 اما در حال حاضر، ارتفاع این درخت 71 00:04:29,470 --> 00:04:34,520 من می خواهم بگویم 3 است، هر چند اگر شما تعداد دفعات مشاهده تعدادی از گره 72 00:04:34,520 --> 00:04:39,710 شما باید به منظور رسیدن به 9، سپس آن را واقعا فقط یک ارتفاع 2. 73 00:04:39,710 --> 00:04:43,340 در حال حاضر این درخت دودویی نامتعادل است، 74 00:04:43,340 --> 00:04:49,840 اما ما در مورد متعادل زمانی که آن را می شود می شود مربوط است. 75 00:04:49,840 --> 00:04:52,040 بنابراین در حال حاضر ما می توانیم در مورد گره ها در یک درخت در شرایط صحبت کنید 76 00:04:52,040 --> 00:04:54,700 نسبت به سایر گره در درخت است. 77 00:04:54,700 --> 00:04:59,730 بنابراین در حال حاضر ما به پدر و مادر، فرزندان، خواهران و برادران، اجداد و فرزندان است. 78 00:04:59,730 --> 00:05:05,650 آنها حس بسیار رایج است، آنها چیست. 79 00:05:05,650 --> 00:05:09,610 اگر ما بخواهید - پدر و مادر آن است. 80 00:05:09,610 --> 00:05:12,830 پس چه شده است پدر و مادر، از مجموع 3 81 00:05:12,830 --> 00:05:16,090 [دانش آموزان] 7. >> آره. پدر و مادر فقط رفتن به چه نکاتی به شما. 82 00:05:16,090 --> 00:05:20,510 پس چه هستند کودکان از 7 است؟ 83 00:05:20,510 --> 00:05:23,860 [دانش آموزان] 3 و 9. >> آره. 84 00:05:23,860 --> 00:05:26,460 توجه داشته باشید که "کودکان" به معنای واقعی کلمه به معنی کودکان، 85 00:05:26,460 --> 00:05:31,010 تا 6 اعمال می شود، به دلیل آن را مانند یک نوه است. 86 00:05:31,010 --> 00:05:35,540 اما پس از آن اگر ما به فرزندان، پس چه فرزندان از 7؟ 87 00:05:35,540 --> 00:05:37,500 [دانش آموزان] 3، 6 و 9. >> آره. 88 00:05:37,500 --> 00:05:42,330 فرزندان گره ریشه است برای رفتن به همه چیز را در درخت، 89 00:05:42,330 --> 00:05:47,950 به جز شاید گره ریشه خود را، اگر شما نمی خواهید که یک نسل را به در نظر بگیرند. 90 00:05:47,950 --> 00:05:50,750 و در نهایت، اجداد، به طوری که آن را به جهت مخالف است. 91 00:05:50,750 --> 00:05:55,740 پس چه هستند اجداد از 6؟ 92 00:05:55,740 --> 00:05:58,920 [دانش آموزان] 3 و 7. >> آره. 9 شامل نمی شود. 93 00:05:58,920 --> 00:06:02,520 این فقط پشت دودمان مستقیم به ریشه 94 00:06:02,520 --> 00:06:13,230 رفتن به نیاکان شما. 95 00:06:13,230 --> 00:06:16,300 >> "ما می گویند که یک درخت دودویی است" دستور داد: «اگر برای هر گره در درخت، 96 00:06:16,300 --> 00:06:19,530 همه از فرزندان خود را در سمت چپ دارای ارزش کمتر 97 00:06:19,530 --> 00:06:22,890 و همه آنهایی که در سمت راست ارزش بیشتری دارند. 98 00:06:22,890 --> 00:06:27,060 به عنوان مثال، از درخت بالا دستور داده شده است اما این تنها راه ممکن تنظیم دستور داده است. " 99 00:06:27,060 --> 00:06:30,180 قبل از اینکه ما به آن 100 00:06:30,180 --> 00:06:36,420 دستور داد درخت دودویی است که همچنین به عنوان یک درخت جستجوی دودویی شناخته شده است. 101 00:06:36,420 --> 00:06:38,660 در اینجا ما اتفاق می افتد را به خواستار آن دستور داده درخت جستجوی دودویی، 102 00:06:38,660 --> 00:06:41,850 اما من شنیده ام که هرگز آن را به نام درخت دودویی دستور داده قبل از، 103 00:06:41,850 --> 00:06:46,650 و در مسابقه ما هستند احتمال بیشتری برای قرار دادن درخت جستجوی دودویی است. 104 00:06:46,650 --> 00:06:49,250 آنها یکی و همان، 105 00:06:49,250 --> 00:06:54,580 و این مهم است که شما تشخیص تمایز بین درخت و درخت جستجوی دودویی. 106 00:06:54,580 --> 00:06:58,830 درخت جستجوی دودویی یک درخت است که به دو چیز است. 107 00:06:58,830 --> 00:07:02,120 هر گره به دو چیز اشاره. 108 00:07:02,120 --> 00:07:06,310 هیچ استدلال در مورد ارزش هایی که به آن اشاره وجود دارد. 109 00:07:06,310 --> 00:07:11,370 پس مثل اینجا، از آن درخت جستجوی دودویی، 110 00:07:11,370 --> 00:07:14,030 ما می دانیم که اگر ما به از 7 باقی مانده است، 111 00:07:14,030 --> 00:07:16,670 پس از آن همه از ارزش است که ما احتمالا می تواند رسیدن به 112 00:07:16,670 --> 00:07:19,310 با رفتن به سمت چپ از 7 باید کمتر از 7. 113 00:07:19,310 --> 00:07:24,070 توجه کنید که تمام مقادیر کمتر از 7 3 و 6. 114 00:07:24,070 --> 00:07:26,040 اینها همه به سمت چپ 7. 115 00:07:26,040 --> 00:07:29,020 اگر ما به حق از 7، همه چیز را به بالاتر از 7، 116 00:07:29,020 --> 00:07:33,220 بنابراین 9 است که به حق از 7، پس ما خوب است. 117 00:07:33,220 --> 00:07:36,150 این مورد برای یک درخت دودویی است، 118 00:07:36,150 --> 00:07:40,020 برای یک درخت دودویی به طور منظم ما فقط می تواند 3 در بالا، 7 به سمت چپ داشته باشد، 119 00:07:40,020 --> 00:07:47,630 9 به سمت چپ از 7 سفارش از ارزش آنچه وجود دارد می باشد. 120 00:07:47,630 --> 00:07:56,140 در حال حاضر، ما در واقع نمی کنند، این به این دلیل آن را خسته کننده و غیر ضروری، 121 00:07:56,140 --> 00:07:59,400 اما "سعی کنید به عنوان بسیاری را به منظور جلب دستور داد درختان به عنوان شما می توانید از فکر می کنم 122 00:07:59,400 --> 00:08:01,900 با استفاده از 7 اعداد، 3، 9 و 6. 123 00:08:01,900 --> 00:08:06,800 چگونه بسیاری از ترتیبات متمایز وجود دارد؟ ارتفاع هر یک چیست؟ 124 00:08:06,800 --> 00:08:10,480 >> خواهیم یک زن و شوهر انجام دهد، اما ایده اصلی این است، 125 00:08:10,480 --> 00:08:16,530 این است که به هیچ وجه به نمایندگی از منحصر به فرد یک درخت دودویی حاوی این مقادیر است. 126 00:08:16,530 --> 00:08:22,760 همه ما نیاز داریم این است که یک درخت دودویی است که شامل 7، 3، 6، و 9. 127 00:08:22,760 --> 00:08:25,960 یکی دیگر ممکن است معتبر خواهد بود 3 ریشه است، 128 00:08:25,960 --> 00:08:30,260 به سمت چپ بروید و آن را به 6، به سمت چپ صفحه بروید و آن را به 7، 129 00:08:30,260 --> 00:08:32,730 به سمت چپ بروید و آن را به 9 است. 130 00:08:32,730 --> 00:08:36,169 این درخت جستجوی دودویی کاملا معتبر است. 131 00:08:36,169 --> 00:08:39,570 این بسیار مفید است، زیرا آن را فقط مانند یک لیست پیوندی 132 00:08:39,570 --> 00:08:43,750 و همه از این اشاره گر ها فقط تهی است. 133 00:08:43,750 --> 00:08:48,900 اما آن را به یک درخت معتبر است. آره؟ 134 00:08:48,900 --> 00:08:51,310 [دانشجو] آیا مقادیر باید بیشتر در سمت راست نیست؟ 135 00:08:51,310 --> 00:08:56,700 یا این - >> این به معنای به راه دیگر. 136 00:08:56,700 --> 00:09:00,960 نیز وجود دارد - آره، اجازه دهید تغییر دهید که. 137 00:09:00,960 --> 00:09:07,770 9، 7، 6، 3. گرفتن خوب است. 138 00:09:07,770 --> 00:09:11,730 هنوز هم به اطاعت آنچه یک درخت جستجوی دودویی قرار است انجام دهد. 139 00:09:11,730 --> 00:09:15,650 بنابراین همه چیز را به سمت چپ به کمتر از هر گره داده شده است. 140 00:09:15,650 --> 00:09:23,180 ما فقط می تواند حرکت می کند می گویند، این 6 قرار داده و آن را در اینجا. 141 00:09:23,180 --> 00:09:26,880 نه، ما نمی تواند. چرا من را در انجام این کار؟ 142 00:09:26,880 --> 00:09:35,350 اجازه دهید - در اینجا 6 است، در اینجا 7، 6 امتیاز 3. 143 00:09:35,350 --> 00:09:39,290 این است که هنوز هم معتبر درخت جستجوی دودویی است. 144 00:09:39,290 --> 00:09:49,260 چه اشتباه است اگر I - اجازه دهید را ببینید اگر من می توانم با آرایش. 145 00:09:49,260 --> 00:09:52,280 بله، درست است. بنابراین چه چیزی اشتباه است با این درخت؟ 146 00:09:52,280 --> 00:10:08,920 من حدس می زنم من در حال حاضر با توجه به اشاره است که مشکلی با آن وجود دارد. 147 00:10:08,920 --> 00:10:14,430 چرا من را در انجام این کار؟ 148 00:10:14,430 --> 00:10:18,510 باشه. این معقول به نظر می رسد. 149 00:10:18,510 --> 00:10:22,590 اگر ما در هر گره، مانند 7 و سپس به سمت چپ از 7 3 است. 150 00:10:22,590 --> 00:10:24,960 بنابراین ما باید 3، چیزی که به حق از 3 است 6. 151 00:10:24,960 --> 00:10:27,750 و اگر شما در 6 نگاه کنید، چیزی که به حق از 6 به 9 است. 152 00:10:27,750 --> 00:10:30,910 پس چرا این درخت جستجوی دودویی معتبر نیست؟ 153 00:10:30,910 --> 00:10:36,330 [دانش آموزان] 9 است که هنوز هم به سمت چپ 7. >> آره. 154 00:10:36,330 --> 00:10:43,710 باید آن را درست است که تمام مقادیر احتمالا شما می توانید با رفتن به سمت چپ از 7 رسیدن آنها کمتر از 7 است. 155 00:10:43,710 --> 00:10:49,120 اگر ما به سمت چپ از 7 به 3 است و ما هنوز هم می تواند تا 6، 156 00:10:49,120 --> 00:10:52,520 ما هنوز هم می تواند تا 9، اما با داشتن رفته کمتر از 7 157 00:10:52,520 --> 00:10:55,070 ما باید قادر باشد که برای رسیدن به یک شماره که بیشتر از 7 است. 158 00:10:55,070 --> 00:10:59,830 پس این درخت جستجوی دودویی معتبر نمی باشد. 159 00:10:59,830 --> 00:11:02,330 >> برادر من در واقع تا به حال یک سوال مصاحبه 160 00:11:02,330 --> 00:11:07,760 بود که اساسا با این کار، فقط کد بالا چیزی است که به اعتبار 161 00:11:07,760 --> 00:11:10,500 آیا یک درخت یک درخت جستجوی دودویی است، 162 00:11:10,500 --> 00:11:13,580 و پس اولین کاری که او انجام داد، فقط چک کنید 163 00:11:13,580 --> 00:11:17,020 اگر در سمت چپ و راست درست است، و سپس تکرار وجود دارد. 164 00:11:17,020 --> 00:11:19,700 اما شما می توانید نه تنها انجام این کار، شما باید برای پیگیری 165 00:11:19,700 --> 00:11:22,550 از این واقعیت که در حال حاضر که من در سمت چپ از 7 رفته، 166 00:11:22,550 --> 00:11:26,340 همه چیز را در این درخت باید کمتر از 7 است. 167 00:11:26,340 --> 00:11:28,430 الگوریتم صحیح نیاز به پیگیری 168 00:11:28,430 --> 00:11:35,970 از مرزهای که ارزش و احتمالا می تواند به سقوط شوید. 169 00:11:35,970 --> 00:11:38,360 ما نمی خواهد رفتن را از طریق تمام از آنها است. 170 00:11:38,360 --> 00:11:41,630 یک رابطه خوب عود وجود دارد، 171 00:11:41,630 --> 00:11:44,810 هر چند که ما به کسانی که بدست، یا ما نمی توانیم به کسانی که، 172 00:11:44,810 --> 00:11:47,030 تعریف چگونه در واقع بسیاری وجود دارد. 173 00:11:47,030 --> 00:11:53,180 بنابراین 14 از آنها وجود دارد. 174 00:11:53,180 --> 00:11:56,020 ایده چگونه شما می توانید آن را انجام دهید ریاضی است، مانند 175 00:11:56,020 --> 00:11:59,770 شما می توانید هر یک را به انتخاب گره ریشه، 176 00:11:59,770 --> 00:12:03,160 و پس از آن اگر من را انتخاب کنید 7 تا گره ریشه، 177 00:12:03,160 --> 00:12:08,150 پس از آن، می گویند، وجود دارد برخی از اعداد است که می تواند به گره سمت چپ من، 178 00:12:08,150 --> 00:12:10,440 و برخی از اعداد است که می تواند گره راست من وجود دارد، 179 00:12:10,440 --> 00:12:15,090 اما اگر من نفر تعداد کل، پس از آن مقدار است که می تواند به سمت چپ بروید 180 00:12:15,090 --> 00:12:18,820 به علاوه مقدار است که می تواند به سمت راست بروید N - 1. 181 00:12:18,820 --> 00:12:26,130 بنابراین از اعداد باقی مانده، آنها باید قادر به رفتن یا به سمت چپ و یا سمت راست. 182 00:12:26,130 --> 00:12:31,580 مشکل به نظر می رسد که اگر من قرار دادن 3 نخست پس از آن همه چیز برای رفتن به سمت چپ، 183 00:12:31,580 --> 00:12:35,080 اما اگر من قرار 7، پس از آن برخی از چیزهایی را می توانید در سمت چپ بروید و برخی از چیزهایی که می تواند به سمت راست بروید. 184 00:12:35,080 --> 00:12:39,570 و با '3 اول من به معنای همه چیز را می تواند به سمت راست بروید. 185 00:12:39,570 --> 00:12:42,350 این در واقع، شما فقط باید در مورد آن فکر می کنم، 186 00:12:42,350 --> 00:12:47,980 چگونه بسیاری از چیزهای را می توان در سطح بعدی درخت بروید. 187 00:12:47,980 --> 00:12:50,420 و از آن بیرون می آید به 14 و یا شما می توانید از آنها قرعه کشی، 188 00:12:50,420 --> 00:12:54,650 و سپس شما 14 دریافت کنید. 189 00:12:54,650 --> 00:13:01,120 >> رفتن به اینجا، 190 00:13:01,120 --> 00:13:03,510 "درخت دودویی مرتب سرد است چرا که ما می توانیم از طریق آنها جستجو 191 00:13:03,510 --> 00:13:06,910 در راه که بسیار شبیه به بیش از یک آرایه مرتب شده است. 192 00:13:06,910 --> 00:13:10,120 برای انجام این کار، ما را در ریشه شروع و کار راه خود را به پایین درخت 193 00:13:10,120 --> 00:13:13,440 نسبت به برگ، چک کردن ارزش در برابر ارزش های ما در حال جستجو برای هر گره است. 194 00:13:13,440 --> 00:13:15,810 اگر مقدار گره فعلی را کمتر از ارزش ما به دنبال، 195 00:13:15,810 --> 00:13:18,050 شما به فرزند راست گره بعدی بروید. 196 00:13:18,050 --> 00:13:20,030 در غیر این صورت، شما به فرزند چپ گره بروید. 197 00:13:20,030 --> 00:13:22,800 در برخی موارد، شما می خواهید ارزش است که شما به دنبال آن هستید، پیدا کردن و یا شما را به تهی اجرا شود، 198 00:13:22,800 --> 00:13:28,520 نشان می دهد ارزش در درخت نیست. " 199 00:13:28,520 --> 00:13:32,450 من به redraw درخت ما تا به حال قبل از، است که می خواهید یک دوم. 200 00:13:32,450 --> 00:13:38,280 اما ما می خواهیم به نگاه کردن آیا 6، 10، و (1) در درخت هستند. 201 00:13:38,280 --> 00:13:49,180 بنابراین، آنچه در آن بود، 7، 9، 3، 6. باشه. 202 00:13:49,180 --> 00:13:52,730 شما می خواهید به نگاه کردن، ما می خواهیم به نگاه تا 6. 203 00:13:52,730 --> 00:13:55,440 چگونه این کار الگوریتم؟ 204 00:13:55,440 --> 00:14:03,040 خب، ما نیز به برخی از اشاره گر ریشه به درخت ما را داشته باشد. 205 00:14:03,040 --> 00:14:12,460 و ما را به ریشه بروید و می گویند، این مقدار برابر با ارزش است که ما در حال جستجو برای است؟ 206 00:14:12,460 --> 00:14:15,000 بنابراین ما به دنبال به مدت 6، پس از آن برابر نیست. 207 00:14:15,000 --> 00:14:20,140 بنابراین ما نگه داشتن رفتن، و در حال حاضر ما می گویند، درست است، به طوری که 6 از 7 کمتر است. 208 00:14:20,140 --> 00:14:23,940 کند که ما می خواهیم برای رفتن به سمت چپ، و یا اینکه ما می خواهیم برای رفتن به سمت راست؟ 209 00:14:23,940 --> 00:14:27,340 [دانشجو] باقی مانده است. >> آره. 210 00:14:27,340 --> 00:14:33,340 این کار به میزان قابل توجهی ساده تر، همه شما باید انجام دهید این است که قرعه کشی یک گره از درخت 211 00:14:33,340 --> 00:14:37,760 و سپس شما می don't - به جای تلاش برای در سر خود فکر می کنم، 212 00:14:37,760 --> 00:14:40,020 خوب، اگر آن را کمتر می توانم به سمت چپ بروید و یا رفتن به سمت راست، 213 00:14:40,020 --> 00:14:43,030 تنها با نگاه کردن به این تصویر، آن را بسیار روشن است که من باید برای رفتن به سمت چپ 214 00:14:43,030 --> 00:14:47,700 اگر این گره بیشتر از ارزش است که من به دنبال. 215 00:14:47,700 --> 00:14:52,600 بنابراین شما را به سمت چپ بروید، در حال حاضر من در 3 هستم. 216 00:14:52,600 --> 00:14:57,770 من می خواهم 3 - کمتر از ارزش من به دنبال، که 6 است. 217 00:14:57,770 --> 00:15:03,420 بنابراین ما به سمت راست بروید، و در حال حاضر من در نهایت در 6، 218 00:15:03,420 --> 00:15:07,380 که ارزش من به دنبال، بنابراین بازگشت من درست است. 219 00:15:07,380 --> 00:15:15,760 ارزش من قصد دارم به دنبال 10 است. 220 00:15:15,760 --> 00:15:23,230 باشه. پس 10، در حال حاضر، در حال رفتن به - قطع که - رفتن به دنبال ریشه است. 221 00:15:23,230 --> 00:15:27,670 در حال حاضر، 10 رفتن به بیشتر از 7، بنابراین من می خواهم به نگاه به سمت راست. 222 00:15:27,670 --> 00:15:31,660 من قصد دارم در اینجا، 10 رفتن به بزرگتر از 9، 223 00:15:31,660 --> 00:15:34,520 بنابراین من می خواهم به نگاه به سمت راست. 224 00:15:34,520 --> 00:15:42,100 آمده ام اینجا، اما در اینجا در حال حاضر من در تهی هستم. 225 00:15:42,100 --> 00:15:44,170 چه کار کنم اگر من ضربه تهی؟ 226 00:15:44,170 --> 00:15:47,440 [دانشجو] [بازگشت غلط؟ >> آره. من 10 پیدا کند. 227 00:15:47,440 --> 00:15:49,800 (1) برای رفتن به یک مورد تقریبا یکسان است، 228 00:15:49,800 --> 00:15:51,950 به جز آن رفتن به بدبختانه، به جای به دنبال 229 00:15:51,950 --> 00:15:56,540 پایین سمت راست، من قصد دارم به نگاه کردن به سمت چپ است. 230 00:15:56,540 --> 00:16:00,430 >> حالا من فکر می کنم ما در واقع به کد. 231 00:16:00,430 --> 00:16:04,070 در اینجا این است که در آن - باز کردن دستگاه CS50 و حرکت به راه خود را وجود دارد، 232 00:16:04,070 --> 00:16:07,010 اما شما همچنین می توانید فقط آن را در فضا است. 233 00:16:07,010 --> 00:16:09,170 این احتمالا به ایده آل برای آن را در فضا انجام دهد، 234 00:16:09,170 --> 00:16:13,760 زیرا ما می توانیم در فضای کار می کنند. 235 00:16:13,760 --> 00:16:19,170 "در ابتدا ما می خواهیم یک تعریف جدید برای یک گره درخت باینری حاوی مقادیر نوع int نیاز دارند. 236 00:16:19,170 --> 00:16:21,400 با استفاده از boilerplate typedef زیر، 237 00:16:21,400 --> 00:16:24,510 ایجاد یک تعریف جدید برای یک گره در درخت جستجوی دودویی. 238 00:16:24,510 --> 00:16:27,930 اگر شما گیر کرده است. است. است. "اه، اه، اه، باشه. 239 00:16:27,930 --> 00:16:30,380 پس اجازه قرار دادن boilerplate اینجا، 240 00:16:30,380 --> 00:16:41,630 typedef ساختار گره و گره. بله، درست است. 241 00:16:41,630 --> 00:16:44,270 پس چه زمینه ما در حال رفتن به در گره می خواهید؟ 242 00:16:44,270 --> 00:16:46,520 [دانشجو] بین المللی و سپس دو اشاره گر؟ 243 00:16:46,520 --> 00:16:49,700 >> بین المللی ارزش، دو اشاره گر؟ چگونه می توانم اشاره گر را من می نویسم؟ 244 00:16:49,700 --> 00:16:58,440 [دانشجو] ساختار. >> من باید زوم شوید. آره، تا گره در ساختار * سمت چپ، 245 00:16:58,440 --> 00:17:01,320 و ساختار گره * درست است. 246 00:17:01,320 --> 00:17:03,460 و به یاد داشته باشید بحث از زمان گذشته، 247 00:17:03,460 --> 00:17:15,290 که این باعث می شود که احساس، این را می سازد هیچ حس، 248 00:17:15,290 --> 00:17:18,270 این باعث می شود حس. 249 00:17:18,270 --> 00:17:25,000 شما نیاز به همه چیز وجود دارد به منظور تعیین این ساختار بازگشتی. 250 00:17:25,000 --> 00:17:27,970 خوب، به طوری که این چیزی است که درخت ما این است که به شبیه. 251 00:17:27,970 --> 00:17:37,670 اگر ما درخت سه تایی، سپس یک گره ممکن است مانند B1، B2، ساختار گره * B3 نگاه کنید، 252 00:17:37,670 --> 00:17:43,470 که در آن B است شاخه ای - در واقع، من بیشتر آن را شنیده سمت چپ، وسط، راست، اما هر چه. 253 00:17:43,470 --> 00:17:55,610 ما فقط در مورد باینری مراقبت، راست، چپ. 254 00:17:55,610 --> 00:17:59,110 "در حال حاضر جهانی متغیر * گره ریشه درخت را اعلام کنند." 255 00:17:59,110 --> 00:18:01,510 بنابراین ما قصد داریم برای انجام این کار است. 256 00:18:01,510 --> 00:18:08,950 به منظور تا همه چیز را کمی سخت تر و عمومی تر، 257 00:18:08,950 --> 00:18:11,570 ما یک متغیر جهانی گره را ندارد. 258 00:18:11,570 --> 00:18:16,710 در عوض، در اصلی ما خواهد همه چیز گره ما اعلام 259 00:18:16,710 --> 00:18:20,500 و این بدان معناست که در زیر آمده است، هنگامی که ما شروع به در حال اجرا 260 00:18:20,500 --> 00:18:23,130 عملکرد ما شامل و تابع قرار دادن ما، 261 00:18:23,130 --> 00:18:27,410 به جای آن حاوی ما فقط تابع را با استفاده از این متغیر جهانی گره، 262 00:18:27,410 --> 00:18:34,280 ما قصد داریم به عنوان یک استدلال به آن درخت را که ما می خواهیم آن را به پردازش. 263 00:18:34,280 --> 00:18:36,650 داشتن متغیر جهانی قرار بود تا همه چیز را آسان تر شده است. 264 00:18:36,650 --> 00:18:42,310 ما قصد داریم تا همه چیز سخت تر است. 265 00:18:42,310 --> 00:18:51,210 در حال حاضر یک دقیقه یا بیشتر به این نوع از چیزی که به انجام درست کنند، 266 00:18:51,210 --> 00:18:57,690 که در آن به داخل اصلی شما می خواهید برای ایجاد این درخت، و این که همه شما می خواهید به انجام. 267 00:18:57,690 --> 00:19:04,530 سعی کنید و این درخت در عملکرد اصلی خود را ساخت. 268 00:19:42,760 --> 00:19:47,610 >> باشه. بنابراین شما حتی نمی باید به درخت ساخته اند راه تمام نشده است. 269 00:19:47,610 --> 00:19:49,840 اما هر کسی چیزی است که من می تواند بالا بکشد 270 00:19:49,840 --> 00:20:03,130 تا نشان دهد که چگونه ممکن است شروع به ساختن چنین یک درخت؟ 271 00:20:03,130 --> 00:20:08,080 [دانشجو] زدن کسی، تلاش کرد تا خود را رها کند. 272 00:20:08,080 --> 00:20:13,100 [Bowden] هر کس راحت با ساخت درخت خود را؟ 273 00:20:13,100 --> 00:20:15,520 [دانشجو] مطمئنا. آن را انجام نداده است. >> این خوب است. ما فقط می تواند به پایان برسد - 274 00:20:15,520 --> 00:20:26,860 آه، می توانید آن را ذخیره کنید؟ آفرین. 275 00:20:26,860 --> 00:20:32,020 بنابراین در اینجا ما - آه، من کمی قطع. 276 00:20:32,020 --> 00:20:34,770 من در بزرگنمایی؟ 277 00:20:34,770 --> 00:20:37,730 بزرگنمایی، حرکت کردن. >> من یک سوال. >> آره؟ 278 00:20:37,730 --> 00:20:44,410 [دانشجو] وقتی ساختار تعریف می کنید، چیزهایی مثل مقدار دهی اولیه به هر چیزی؟ 279 00:20:44,410 --> 00:20:47,160 [Bowden] شماره >> خوب است. بنابراین شما می توانید به مقداردهی اولیه - 280 00:20:47,160 --> 00:20:50,450 [Bowden] شماره هنگامی که تعریف می کنید، و یا زمانی که شما اعلام ساختار، 281 00:20:50,450 --> 00:20:55,600 از آن است که به طور پیش فرض مقدار دهی اولیه، آن را فقط دوست دارم اگر از نوع int به شما اعلام شده است. 282 00:20:55,600 --> 00:20:59,020 این دقیقا همان چیزی است. مانند هر یک از زمینه های فردی خود را 283 00:20:59,020 --> 00:21:04,460 می توانید یک مقدار زباله را در آن داشته باشد. >> و ممکن است برای تعریف - و یا به اعلام یک ساختار 284 00:21:04,460 --> 00:21:07,740 در یک راه است که آن را نشانی از آنها را مقداردهی اولیه؟ 285 00:21:07,740 --> 00:21:13,200 [Bowden] بله. بنابراین، میانبر نحو دهی اولیه 286 00:21:13,200 --> 00:21:18,660 رفتن به شبیه - 287 00:21:18,660 --> 00:21:22,200 دو راه وجود دارد ما می توانیم این کار را انجام دهند. من فکر می کنم ما باید آن را کامپایل 288 00:21:22,200 --> 00:21:25,840 را به مطمئن شوید که صدای جرنگ جرنگ می کند این است. 289 00:21:25,840 --> 00:21:28,510 منظور از استدلال است که می آید در ساختار، 290 00:21:28,510 --> 00:21:32,170 شما به عنوان منظور از استدلال در داخل این آکولاد قرار داده است. 291 00:21:32,170 --> 00:21:35,690 بنابراین اگر شما می خواهید آن را مقداردهی اولیه به 9 سمت چپ و تهی و سپس راست تهی باشد، 292 00:21:35,690 --> 00:21:41,570 این امر می تواند 9، پوچ، پوچ است. 293 00:21:41,570 --> 00:21:47,890 جایگزین است، و سردبیر این نحو را دوست ندارد، 294 00:21:47,890 --> 00:21:50,300 و آن فکر می کند من می خواهم یک بلوک جدید، 295 00:21:50,300 --> 00:22:01,800 اما جایگزین چیزی شبیه - 296 00:22:01,800 --> 00:22:04,190 در اینجا، من آن را در یک خط جدید قرار داده است. 297 00:22:04,190 --> 00:22:09,140 شما به صراحت می توان گفت، من را فراموش کرده ام نحو دقیق است. 298 00:22:09,140 --> 00:22:13,110 بنابراین شما به صراحت می توانید آنها را با نام و نام خانوادگی آدرس، و می گویند، 299 00:22:13,110 --> 00:22:21,570 ج. ارزش = 9 = NULL چپ. 300 00:22:21,570 --> 00:22:24,540 من حدس می زنم این نیاز به کاما از هم است. 301 00:22:24,540 --> 00:22:29,110 راست = NULL، بنابراین در این روش شما انجام نمی 302 00:22:29,110 --> 00:22:33,780 در واقع نیاز به دانستن منظور از ساختار، 303 00:22:33,780 --> 00:22:36,650 و هنگامی که شما در حال خواندن این کار، آن را به مراتب صریح تر 304 00:22:36,650 --> 00:22:41,920 در مورد آنچه که ارزش به مقداردهی اولیه به. 305 00:22:41,920 --> 00:22:44,080 >> این اتفاق می افتد به عنوان یکی از چیزهایی که - 306 00:22:44,080 --> 00:22:49,100 بنابراین، برای بیشتر قسمت ها، C + + superset از C. 307 00:22:49,100 --> 00:22:54,160 شما نمی توانید کدهای C، حرکت آن را به C + +، و آن را باید کامپایل. 308 00:22:54,160 --> 00:22:59,570 این یکی از چیزهایی است که C + + را پشتیبانی نمی کند، بنابراین مردم تمایل به آن را انجام دهد. 309 00:22:59,570 --> 00:23:01,850 من نمی دانم در صورتی که تنها به این دلیل که مردم تمایل به آن را انجام دهد، 310 00:23:01,850 --> 00:23:10,540 اما در مورد جایی که من نیاز به استفاده از آن نیاز به کار با C + + و بنابراین من می تواند این استفاده نمی کند. 311 00:23:10,540 --> 00:23:14,000 یک مثال دیگر از چیزی است که با C + + کار نمی کند 312 00:23:14,000 --> 00:23:16,940 چگونه malloc "* خالی را بر می گرداند، مشخصات فنی، 313 00:23:16,940 --> 00:23:20,200 اما شما فقط می تواند کاراکتر * x = malloc هر آنچه که می گویند، 314 00:23:20,200 --> 00:23:22,840 و آن را به طور خودکار به * کاراکتر ریخته شده است. 315 00:23:22,840 --> 00:23:25,450 آن به سایر نظرسنجی ها به صورت خودکار اتفاق نمی افتد در C + +. 316 00:23:25,450 --> 00:23:28,150 که نمی خواهد کامپایل، و شما به صراحت نیاز به گفتن 317 00:23:28,150 --> 00:23:34,510 * کاراکتر، malloc، حالا هر چی، به آن بازیگران * کاراکتر. 318 00:23:34,510 --> 00:23:37,270 بسیاری از چیزهایی هستند که C و C + + در مخالفت وجود ندارد، 319 00:23:37,270 --> 00:23:40,620 اما آن دو است. 320 00:23:40,620 --> 00:23:43,120 بنابراین ما با این نحو بروید. 321 00:23:43,120 --> 00:23:46,150 اما حتی اگر ما با آن نحو از رفتن نیست، 322 00:23:46,150 --> 00:23:49,470 است - ممکن است با این اشتباه است؟ 323 00:23:49,470 --> 00:23:52,170 [دانشجو] من لازم نیست به dereference آن؟ >> آره. 324 00:23:52,170 --> 00:23:55,110 به یاد داشته باشید که فلش dereference ضمنی، 325 00:23:55,110 --> 00:23:58,230 و تا زمانی که ما فقط با یک ساختار خرید و فروش، 326 00:23:58,230 --> 00:24:04,300 ما مایل به استفاده از. در داخل میدان از ساختار. 327 00:24:04,300 --> 00:24:07,200 و تنها زمانی ما با استفاده از فلش زمانی است که ما می خواهیم انجام دهیم - 328 00:24:07,200 --> 00:24:13,450 خوب، فلش معادل است - 329 00:24:13,450 --> 00:24:17,020 این چیزی است که آن را به معنای اگر من با استفاده از فلش است. 330 00:24:17,020 --> 00:24:24,600 همه به معنی پیکان، dereference این، در حال حاضر من در یک ساختار هستم، و من می توانم این زمینه دریافت کنید. 331 00:24:24,600 --> 00:24:28,040 در هر دو زمینه به طور مستقیم و یا dereference و این زمینه را دریافت کنید - 332 00:24:28,040 --> 00:24:30,380 من حدس می زنم این باید ارزش. 333 00:24:30,380 --> 00:24:33,910 اما در اینجا من خرید و فروش تنها با یک ساختار، یک اشاره گر به ساختار 334 00:24:33,910 --> 00:24:38,780 و بنابراین من می توانید از فلش استفاده نمی کند. 335 00:24:38,780 --> 00:24:47,510 اما این نوع از چیزی که ما می توانیم برای تمام گره ها انجام دهد. 336 00:24:47,510 --> 00:24:55,790 اوه خدای من. 337 00:24:55,790 --> 00:25:09,540 این 6، 7، و 3 است. 338 00:25:09,540 --> 00:25:16,470 پس ما می توانیم راه اندازی شاخه در درخت ما، ما می توانیم 7 - 339 00:25:16,470 --> 00:25:21,650 ما می توانیم در سمت چپ آن باید تا 3. 340 00:25:21,650 --> 00:25:25,130 پس ما چگونه انجام این کار؟ 341 00:25:25,130 --> 00:25:29,320 [دانش آموزان، ناخوانا] >> آره. این آدرس از node3، 342 00:25:29,320 --> 00:25:34,170 و اگر شما آدرس ندارد، و سپس آن را نه تنها می کامپایل. 343 00:25:34,170 --> 00:25:38,190 اما به یاد داشته باشید که این اشاره گر به گره بعدی. 344 00:25:38,190 --> 00:25:44,930 حق باید تا 9، 345 00:25:44,930 --> 00:25:53,330 و 3 باید در سمت راست به 6 نقطه. 346 00:25:53,330 --> 00:25:58,480 من فکر می کنم این است که همه مجموعه است. هر گونه نظر و یا سوال؟ 347 00:25:58,480 --> 00:26:02,060 [دانشجو، ناخوانا] ریشه در حال رفتن بود 7. 348 00:26:02,060 --> 00:26:08,210 ما فقط می تواند گره می گویند * PTR = 349 00:26:08,210 --> 00:26:14,160 و یا ریشه، = node7. 350 00:26:14,160 --> 00:26:20,730 >> برای اهداف ما، ما در حال رفتن به خرید و فروش با درج 351 00:26:20,730 --> 00:26:25,490 بنابراین ما در حال رفتن به یک تابع برای وارد کردن به این درخت دودویی برای نوشتن 352 00:26:25,490 --> 00:26:34,230 و درج ناچار به تماس malloc یک گره جدید برای این درخت برای ایجاد. 353 00:26:34,230 --> 00:26:36,590 بنابراین همه چیز کثیف با این واقعیت است که بعضی از گره ها 354 00:26:36,590 --> 00:26:38,590 در حال حاضر بر روی پشته 355 00:26:38,590 --> 00:26:43,680 و گره های دیگر می رویم برای پایان دادن به پشته هنگامی که آنها را وارد. 356 00:26:43,680 --> 00:26:47,640 این کاملا معتبر است، اما تنها به این دلیل 357 00:26:47,640 --> 00:26:49,600 ما قادر به انجام این کار را بر روی پشته 358 00:26:49,600 --> 00:26:51,840 به دلیل آن را مانند یک مثال ساختگی است که ما می دانیم 359 00:26:51,840 --> 00:26:56,360 درخت قرار است به عنوان 7، 3، 6، 9 ساخته شده است. 360 00:26:56,360 --> 00:27:02,970 اگر ما این را نداشته باشند، پس ما نمی خواهد به malloc در وهله اول. 361 00:27:02,970 --> 00:27:06,160 همانطور که خواهیم دید و کمی بعد، ما باید malloc'ing. 362 00:27:06,160 --> 00:27:08,570 در حال حاضر آن را کاملا معقول و منطقی را بر روی پشته قرار داده است، 363 00:27:08,570 --> 00:27:14,750 اما اجازه دهید را تغییر دهید این برای پیاده سازی malloc. 364 00:27:14,750 --> 00:27:17,160 بنابراین هر یک از این است که در حال حاضر چیزی شبیه به رفتن به 365 00:27:17,160 --> 00:27:24,240 گره * node9 = malloc (sizeof (گره)). 366 00:27:24,240 --> 00:27:28,040 و در حال حاضر ما در حال رفتن به چک ما را به انجام. 367 00:27:28,040 --> 00:27:34,010 اگر (node9 == NULL) - من که می خواهند - 368 00:27:34,010 --> 00:27:40,950 بازگشت 1، و پس از آن ما می توانیم node9> چرا که در حال حاضر آن را در یک اشاره گر، 369 00:27:40,950 --> 00:27:45,300 ارزش = 6، node9-> سمت چپ = NULL، 370 00:27:45,300 --> 00:27:48,930 node9-> حق = NULL، 371 00:27:48,930 --> 00:27:51,410 و ما قصد داریم که باید به انجام این کار برای هر یک از کسانی که گره. 372 00:27:51,410 --> 00:27:57,490 بنابراین به جای آن، اجازه دهید آن را قرار داده و در داخل یک تابع جداگانه. 373 00:27:57,490 --> 00:28:00,620 اجازه دهید آن گره * build_node، 374 00:28:00,620 --> 00:28:09,050 و این تا حدودی شبیه به رابط های برنامه کاربردی که برای کدگذاری هافمن ارائه است. 375 00:28:09,050 --> 00:28:12,730 ما به شما توابع برنامه initializer را برای یک درخت 376 00:28:12,730 --> 00:28:20,520 deconstructor "از توابع" برای آن دسته از درختان و همین کار را برای جنگل. 377 00:28:20,520 --> 00:28:22,570 >> بنابراین در اینجا ما در حال رفتن به یک تابع initializer از 378 00:28:22,570 --> 00:28:25,170 فقط به ساخت یک گره را برای ما است. 379 00:28:25,170 --> 00:28:29,320 و آن را به نگاه دقیقا مانند این بسیار است. 380 00:28:29,320 --> 00:28:32,230 و من حتی به تنبل و تغییر نام متغیر نیست، 381 00:28:32,230 --> 00:28:34,380 حتی اگر node9 می سازد هیچ حس دیگر. 382 00:28:34,380 --> 00:28:38,610 آه، من حدس می زنم ارزش node9 نباید است 6. 383 00:28:38,610 --> 00:28:42,800 در حال حاضر ما می توانیم node9 بازگشت. 384 00:28:42,800 --> 00:28:49,550 و در اینجا ما باید بازگشتی NULL است. 385 00:28:49,550 --> 00:28:52,690 هر کس در آن تابع ساخت گره موافق هستید؟ 386 00:28:52,690 --> 00:28:59,780 بنابراین در حال حاضر ما فقط می تواند که برای ساخت هر گره با مقدار داده می شود و اشاره گر تهی تماس بگیرید. 387 00:28:59,780 --> 00:29:09,750 در حال حاضر ما می توانیم که تماس بگیرید، ما می توانیم گره * node9 = build_node (9) را انجام دهد. 388 00:29:09,750 --> 00:29:25,810 و اجازه دهید. است. است. 389 00:29:25,810 --> 00:29:33,980 6، 3، 7، 6، 3، 7. 390 00:29:33,980 --> 00:29:39,330 و در حال حاضر ما می خواهم به راه اندازی همان اشاره گر، 391 00:29:39,330 --> 00:29:42,470 جز در حال حاضر همه چیز در حال حاضر در شرایط استفاده از اشاره گرها 392 00:29:42,470 --> 00:29:48,480 بنابراین دیگر نیازی به آدرس. 393 00:29:48,480 --> 00:29:56,300 باشه. پس چیزی که من می خواهم به انجام این کار؟ 394 00:29:56,300 --> 00:30:03,850 چک کردن خطا که من انجام نمی وجود دارد. 395 00:30:03,850 --> 00:30:06,800 چه بازگشت گره؟ 396 00:30:06,800 --> 00:30:11,660 [دانشجو، ناخوانا] >> آره. اگر malloc شکست خورد، آن را بر می گردیم تهی. 397 00:30:11,660 --> 00:30:16,460 بنابراین من قصد دارم به lazily آن را در اینجا به جای انجام یک شرط برای هر. 398 00:30:16,460 --> 00:30:22,320 اگر (node9 == NULL، و یا - حتی ساده تر، 399 00:30:22,320 --> 00:30:28,020 این معادل فقط اگر node9 نیست. 400 00:30:28,020 --> 00:30:38,310 پس اگر نه node9، یا نه node6، یا نه node3، یا نه node7 بازگشت 1. 401 00:30:38,310 --> 00:30:42,850 شاید ما باید چاپ malloc شکست خورده، و یا چیزی. 402 00:30:42,850 --> 00:30:46,680 [دانشجو] نادرست است برابر با null به عنوان؟ 403 00:30:46,680 --> 00:30:51,290 [Bowden] هر مقدار صفر غلط است. 404 00:30:51,290 --> 00:30:53,920 تهی مقدار صفر است. 405 00:30:53,920 --> 00:30:56,780 صفر صفر است. غلط مقدار صفر است. 406 00:30:56,780 --> 00:31:02,130 هر - زیبا 2 تنها مقادیر صفر پوچ و صفر، 407 00:31:02,130 --> 00:31:07,900 غلط است فقط مخلوط به عنوان صفر تعریف شده است. 408 00:31:07,900 --> 00:31:13,030 که همچنین شامل اگر ما اعلام متغیر جهانی است. 409 00:31:13,030 --> 00:31:17,890 اگر ما گره ریشه * در اینجا، 410 00:31:17,890 --> 00:31:24,150 پس از آن - چیز خوب در مورد متغیر های جهانی این است که آنها همیشه یک مقدار اولیه است. 411 00:31:24,150 --> 00:31:27,500 که از توابع درست نیست، چه در داخل از اینجا، 412 00:31:27,500 --> 00:31:34,870 اگر ما، مانند، * گره یا گره X. 413 00:31:34,870 --> 00:31:37,380 ما هیچ ایده چه چیزی x.value، x.whatever، 414 00:31:37,380 --> 00:31:40,700 یا ما می توانیم به آنها و چاپ آنها می تواند خودسرانه باشد. 415 00:31:40,700 --> 00:31:44,980 که از متغیرهای جهانی درست نیست. 416 00:31:44,980 --> 00:31:47,450 بنابراین گره ریشه یا گره X. 417 00:31:47,450 --> 00:31:53,410 به طور پیش فرض، همه چیز جهانی، اگر نه به صراحت به برخی از ارزش دهی اولیه 418 00:31:53,410 --> 00:31:57,390 مقدار صفر را به عنوان ارزش خود را دارد. 419 00:31:57,390 --> 00:32:01,150 بنابراین در اینجا، گره ریشه *، ما به صراحت و نه آن را مقداردهی اولیه به هر چیزی، 420 00:32:01,150 --> 00:32:06,350 بنابراین مقدار پیش فرض آن null خواهد بود، که مقدار صفر از اشاره گر است. 421 00:32:06,350 --> 00:32:11,870 مقدار پیش فرض X به این معنی است که x.value صفر است، 422 00:32:11,870 --> 00:32:14,260 x.left تهی است، و x.right تهی است. 423 00:32:14,260 --> 00:32:21,070 پس از آن است که ساختار، همه زمینه های ساختار، صفر خواهد بود ارزش. 424 00:32:21,070 --> 00:32:24,410 ما لازم نیست برای استفاده از آن در اینجا، هر چند. 425 00:32:24,410 --> 00:32:27,320 [دانشجو] ساختمانها متفاوت هستند نسبت به سایر متغیرها و متغیرهای دیگر 426 00:32:27,320 --> 00:32:31,400 ارزش زباله، این صفر؟ 427 00:32:31,400 --> 00:32:36,220 [Bowden] دیگر مقادیر بیش از حد. بنابراین در X، X صفر خواهد بود. 428 00:32:36,220 --> 00:32:40,070 اگر آن را در حوزه جهانی است، آن را تا مقدار اولیه است. >> درست است. 429 00:32:40,070 --> 00:32:48,950 [Bowden] در هر صورت مقدار اولیه به شما داد آن را یا صفر است. 430 00:32:48,950 --> 00:32:53,260 من فکر می کنم که طول می کشد مراقبت از همه از این است. 431 00:32:53,260 --> 00:32:58,390 >> باشه. بنابراین بخش بعدی از این سوال می پرسد، 432 00:32:58,390 --> 00:33:01,260 "در حال حاضر ما می خواهیم برای نوشتن یک تابع نامیده می شود شامل 433 00:33:01,260 --> 00:33:04,930 با یک نمونه اولیه از بولی شامل مقدار int است. " 434 00:33:04,930 --> 00:33:08,340 ما قصد نداریم به انجام بولی حاوی مقدار از نوع int است. 435 00:33:08,340 --> 00:33:15,110 نمونه اولیه ما این است که رفتن به شبیه 436 00:33:15,110 --> 00:33:22,380 بولی شامل (مقدار از نوع int است. 437 00:33:22,380 --> 00:33:24,490 و پس از آن ما در حال رفتن به آن درخت عبور 438 00:33:24,490 --> 00:33:28,870 که باید آن را چک تا ببینید که آیا آن است که ارزش است. 439 00:33:28,870 --> 00:33:38,290 بنابراین گره * درخت). باشه. 440 00:33:38,290 --> 00:33:44,440 و پس از آن ما می توانیم آن را با چیزی شبیه تماس بگیرید. 441 00:33:44,440 --> 00:33:46,090 شاید ما باید برای printf و یا چیزی را می خواهم. 442 00:33:46,090 --> 00:33:51,040 شامل 6، ریشه ما است. 443 00:33:51,040 --> 00:33:54,300 که باید یکی، یا به راست، 444 00:33:54,300 --> 00:33:59,390 در حالی که شامل 5 ریشه باید بازگشت نادرست است. 445 00:33:59,390 --> 00:34:02,690 بنابراین یک ثانیه برای انجام این کار کنند. 446 00:34:02,690 --> 00:34:06,780 شما می توانید آن را به صورت تکرار شونده و یا به صورت بازگشتی انجام دهد. 447 00:34:06,780 --> 00:34:09,739 چیز خوب در مورد راه ایم تا چیز این است که 448 00:34:09,739 --> 00:34:12,300 آن را به خود آشنایی به راه حل بازگشتی ما بسیار آسان تر 449 00:34:12,300 --> 00:34:14,719 از راه جهانی متغیر بود. 450 00:34:14,719 --> 00:34:19,750 چرا که اگر ما فقط باید حاوی مقدار از نوع int است، پس ما باید هیچ راهی از recursing پایین subtrees. 451 00:34:19,750 --> 00:34:24,130 ما می خواهیم یک تابع کمکی جداگانه که recurses از subtrees برای ما به. 452 00:34:24,130 --> 00:34:29,610 اما از آنجایی که ما تغییر داده اید آن را به درخت به عنوان یک استدلال، 453 00:34:29,610 --> 00:34:32,760 که آن را باید همیشه در وهله اول بوده است. 454 00:34:32,760 --> 00:34:35,710 در حال حاضر ما می توانیم RECURSE آسان تر. 455 00:34:35,710 --> 00:34:38,960 بنابراین تکرار شونده و یا بازگشتی، ما بیش از هر دو، 456 00:34:38,960 --> 00:34:46,139 اما ما به پایان می رسد بازگشتی بودن بسیار آسان را ببینید. 457 00:34:59,140 --> 00:35:02,480 باشه. آیا کسی چیزی است که ما می توانیم با آن کار کنند؟ 458 00:35:02,480 --> 00:35:12,000 >> [دانشجو] من تکرار شونده راه حل است. >> همه حق است، تکرار می شوند. 459 00:35:12,000 --> 00:35:16,030 خوب، این به نظر می رسد خوب است. 460 00:35:16,030 --> 00:35:18,920 بنابراین، می خواهند به ما راه رفتن را از طریق آن؟ 461 00:35:18,920 --> 00:35:25,780 [دانشجو] مطمئنا. بنابراین من یک متغیر موقت به اولین گره از درخت است. 462 00:35:25,780 --> 00:35:28,330 و بعد من فقط از طریق در حالی که دما تهی برابر نیست لوپ، 463 00:35:28,330 --> 00:35:31,700 بنابراین در حالی که هنوز در درخت بود، من حدس می زنم. 464 00:35:31,700 --> 00:35:35,710 و اگر این مقدار برابر با ارزش است که موقت است با اشاره به 465 00:35:35,710 --> 00:35:37,640 سپس آن را که ارزش را بر می گرداند. 466 00:35:37,640 --> 00:35:40,210 در غیر این صورت، آن را چک می کند اگر آن را در سمت راست یا سمت چپ است. 467 00:35:40,210 --> 00:35:43,400 اگر شما تا کنون یک وضعیت که در آن هیچ درخت بیشتر وجود دارد، 468 00:35:43,400 --> 00:35:47,330 سپس آن را برمی گرداند - خروج از حلقه و نادرست را برمی گرداند. 469 00:35:47,330 --> 00:35:52,190 [Bowden] باشه. به طوری که به نظر می رسد خوب است. 470 00:35:52,190 --> 00:35:58,470 هر کسی هر گونه نظر در مورد هر چیزی؟ 471 00:35:58,470 --> 00:36:02,400 من نظری نداده اند صحت در همه. 472 00:36:02,400 --> 00:36:11,020 چیزی که ما می توانیم انجام دهیم، این پسر است. 473 00:36:11,020 --> 00:36:21,660 آه، آن رفتن به دراز کمی. 474 00:36:21,660 --> 00:36:33,460 من که تا حل کنند. باشه. 475 00:36:33,460 --> 00:36:37,150 >> هر کس باید به یاد داشته باشید که چگونه سه تایی کار می کند. 476 00:36:37,150 --> 00:36:38,610 قطعا وجود داشته است آزمونها در گذشته 477 00:36:38,610 --> 00:36:41,170 که شما یک تابع را با استفاده از عملگر سه تایی را، 478 00:36:41,170 --> 00:36:45,750 و می گویند، ترجمه، انجام کاری می کند که سه تایی استفاده نمی. 479 00:36:45,750 --> 00:36:49,140 بنابراین این یک مورد بسیار معمول است زمانی که من فکر می کنم به استفاده از سه تایی، 480 00:36:49,140 --> 00:36:54,610 جایی که اگر برخی از شرایط تعیین یک متغیر را به چیزی، 481 00:36:54,610 --> 00:36:58,580 دیگری که متغیر به چیز دیگری تنظیم شده است. 482 00:36:58,580 --> 00:37:03,390 این چیزی است که اغلب می توان به این نوع از چیزی تبدیل 483 00:37:03,390 --> 00:37:14,420 که در آن مجموعه ای که متغیر به این - یا خوب است، این درست است؟ سپس این دیگری این است. 484 00:37:14,420 --> 00:37:18,550 [دانشجو] یکی از اولین، اگر درست باشد، درست است؟ 485 00:37:18,550 --> 00:37:25,570 [Bowden] آره. من همیشه آن را بخوانید، دمای برابر است با مقدار بیشتر از مقدار موقت، 486 00:37:25,570 --> 00:37:30,680 پس از این، به دیگری این است. پرسیدن یک سوال است. 487 00:37:30,680 --> 00:37:35,200 آیا این بیشتر؟ اولین چیزی که پس از آن انجام دهد. چیز دیگری را انجام دهد. 488 00:37:35,200 --> 00:37:41,670 من تقریبا همیشه - روده بزرگ، من فقط - در سر من، من به عنوان خوانده شده دیگری است. 489 00:37:41,670 --> 00:37:47,180 >> آیا کسی که یک راه حل بازگشتی؟ 490 00:37:47,180 --> 00:37:49,670 باشه. این یکی که ما در حال رفتن به - آن را در حال حاضر می تواند بزرگ باشد، 491 00:37:49,670 --> 00:37:53,990 اما ما در حال رفتن به آن را حتی بهتر. 492 00:37:53,990 --> 00:37:58,720 این خیلی ایده یکسان است. 493 00:37:58,720 --> 00:38:03,060 این فقط، به خوبی، آیا شما می خواهید به توضیح؟ 494 00:38:03,060 --> 00:38:08,340 [دانشجو] مطمئنا. بنابراین ما در حال مطمئن شوید که درخت پوچ است اولین بار نیست، 495 00:38:08,340 --> 00:38:13,380 زیرا اگر درخت تهی است و سپس آن را به بازگشت به غلط چون ما آن را یافت نشد. 496 00:38:13,380 --> 00:38:19,200 و اگر هنوز هم وجود دارد یک درخت، ما را به - ما برای اولین بار چک کنید اگر مقدار گره فعلی. 497 00:38:19,200 --> 00:38:23,740 بازگشت واقعی آن است، و اگر نه ما در سمت چپ یا راست RECURSE. 498 00:38:23,740 --> 00:38:25,970 کند که صدا مناسب است؟ >> MM-HMM. (توافقنامه) 499 00:38:25,970 --> 00:38:33,880 به طوری که این است که تقریبا متوجه - ساختاری بسیار شبیه به راه حل تکرار شونده است. 500 00:38:33,880 --> 00:38:38,200 این درست است که به جای recursing، ما تا به حال یک حلقه در حالی که. 501 00:38:38,200 --> 00:38:40,840 و در مورد پایه در اینجا که در آن درخت تهی برابر نیست 502 00:38:40,840 --> 00:38:44,850 که تحت آن شرایط ما از حلقه در حالی که شکست بود. 503 00:38:44,850 --> 00:38:50,200 آنها بسیار مشابه است. اما ما در حال رفتن به یک مرحله دیگر است. 504 00:38:50,200 --> 00:38:54,190 در حال حاضر، ما همان چیزی که در اینجا. 505 00:38:54,190 --> 00:38:57,680 توجه داشته باشید که ما در حال بازگشت به همان چیزی که در هر دو این خطوط، 506 00:38:57,680 --> 00:39:00,220 به جز یک استدلال متفاوت است. 507 00:39:00,220 --> 00:39:07,950 بنابراین ما در حال رفتن را که به یک سه گانه است. 508 00:39:07,950 --> 00:39:13,790 من ضربه چیزی گزینه، و یک نماد آن ساخته شده است. باشه. 509 00:39:13,790 --> 00:39:21,720 بنابراین ما قصد داریم به بازگشت که شامل. 510 00:39:21,720 --> 00:39:28,030 این است که به چند خط، به خوبی، به بزرگنمایی در آن است. 511 00:39:28,030 --> 00:39:31,060 معمولا، به عنوان یک چیز سبکی، من بسیاری از مردم فکر نمی کنم 512 00:39:31,060 --> 00:39:38,640 قرار دادن یک فضای بعد از فلش است، اما من حدس می زنم اگر شما سازگار باشد، خوب است. 513 00:39:38,640 --> 00:39:44,320 اگر مقدار کمتر از ارزش درخت است، ما می خواهیم به RECURSE در سمت چپ درخت، 514 00:39:44,320 --> 00:39:53,890 دیگری ما را به RECURSE در سمت راست درخت می خواهم. 515 00:39:53,890 --> 00:39:58,610 به طوری که گام اول ساخت این نگاه کوچکتر بود. 516 00:39:58,610 --> 00:40:02,660 گام دوم این نگاه کوچکتر - 517 00:40:02,660 --> 00:40:09,150 ما می توانیم این را به چند خط از هم جدا کنید. 518 00:40:09,150 --> 00:40:16,500 باشه. مرحله دو و آن را نگاه کوچکتر است که در اینجا، 519 00:40:16,500 --> 00:40:25,860 بنابراین مقدار بازگشتی برابر با ارزش درخت، و یا شامل هر چیز دیگری است. 520 00:40:25,860 --> 00:40:28,340 >> این یک نکته مهم است. 521 00:40:28,340 --> 00:40:30,860 من مطمئن نیستم که او گفت که آن را در کلاس به صراحت، 522 00:40:30,860 --> 00:40:34,740 اما آن را ارزیابی کوتاه مدار نامیده می شود. 523 00:40:34,740 --> 00:40:41,060 این ایده در اینجا ارزش است == ارزش درخت. 524 00:40:41,060 --> 00:40:49,960 در صورتی که درست است، پس این درست است، و ما می خواهیم به "یا" که با آنچه در اینجا. 525 00:40:49,960 --> 00:40:52,520 بدون حتی فکر کردن در مورد آنچه در اینجا، 526 00:40:52,520 --> 00:40:55,070 تمام بیان رفتن به بازگشت چه چیزی است؟ 527 00:40:55,070 --> 00:40:59,430 [دانش آموز] درست است؟ >> آره، چرا که درست از هر چیز، 528 00:40:59,430 --> 00:41:04,990 or'd - or'd یا واقعی با هر چیزی لزوما درست است. 529 00:41:04,990 --> 00:41:08,150 تا به زودی به عنوان مقدار بازگشتی = ارزش درخت، 530 00:41:08,150 --> 00:41:10,140 ما فقط رفتن به بازگشت واقعی است. 531 00:41:10,140 --> 00:41:15,710 حتی رفتن به RECURSE بیشتر شامل پایین خط. 532 00:41:15,710 --> 00:41:20,980 ما می توانیم این مرحله را بیشتر. 533 00:41:20,980 --> 00:41:29,490 درخت بازگشت تهی برابر و همه از این نیست. 534 00:41:29,490 --> 00:41:32,650 آن ساخته شده آن را یک تابع یک خط. 535 00:41:32,650 --> 00:41:36,790 این هم یک نمونه از مدار کوتاه ارزیابی است. 536 00:41:36,790 --> 00:41:40,680 اما در حال حاضر از آن همان ایده - 537 00:41:40,680 --> 00:41:47,320 به جای - بنابراین اگر درخت برابر تهی نیست - و یا، به خوبی، 538 00:41:47,320 --> 00:41:49,580 اگر درخت تهی مساوی، که مورد بد است، 539 00:41:49,580 --> 00:41:54,790 اگر درخت برابر تهی است، پس از آن اولین شرط رفتن نادرست می شود. 540 00:41:54,790 --> 00:42:00,550 غلط anded با هر چیزی است برای رفتن به چه؟ 541 00:42:00,550 --> 00:42:04,640 [دانشجو] غلط است. >> آره. این نیمه دیگر ارزیابی مدار کوتاه است، 542 00:42:04,640 --> 00:42:10,710 جایی که اگر درخت تهی برابر نیست، پس از آن ما می رویم حتی - 543 00:42:10,710 --> 00:42:14,930 یا اگر درخت تهی برابر است، پس از آن ما می رویم نه به ارزش ارزش == درخت. 544 00:42:14,930 --> 00:42:17,010 ما فقط رفتن به برگرداندن غلط است. 545 00:42:17,010 --> 00:42:20,970 که مهم است، چرا که اگر آن را انجام ارزیابی نیست اتصال کوتاه، 546 00:42:20,970 --> 00:42:25,860 پس از آن اگر درخت تهی مساوی، این شرط دوم این است که رفتن به گسل SEG، 547 00:42:25,860 --> 00:42:32,510 چون درخت> ارزش غیر مرجع تهی. 548 00:42:32,510 --> 00:42:40,490 به طوری که که. آیا می توانید این را - یک بار بیش از تغییر. 549 00:42:40,490 --> 00:42:44,840 این یک چیزی که بسیار شایع است، ساخت این خط یکی با این، 550 00:42:44,840 --> 00:42:49,000 اما این یک چیز مشترک در شرایط، شاید حق در اینجا، 551 00:42:49,000 --> 00:42:59,380 اما اگر (درخت! = NULL، و درخت> ارزش ارزش ==)، انجام هر کاری است. 552 00:42:59,380 --> 00:43:01,560 این یک وضعیت بسیار شایع است، که در آن به جای داشتن 553 00:43:01,560 --> 00:43:06,770 برای شکستن این به دو IFS، جایی که دوست دارید، درخت تهی است؟ 554 00:43:06,770 --> 00:43:11,780 خوب، آن تهی نیست، بنابراین در حال حاضر ارزش درخت برابر با ارزش است؟ انجام این کار. 555 00:43:11,780 --> 00:43:17,300 در عوض، این وضعیت، این کار را گسل SEG هرگز 556 00:43:17,300 --> 00:43:21,220 چرا که آن را خواهد شکست اگر این اتفاق می افتد به تهی. 557 00:43:21,220 --> 00:43:24,000 خوب، من حدس می زنم اگر درخت خود را به طور کامل اشاره گر نامعتبر باشد، آن را هنوز هم می تواند SEG گسل، 558 00:43:24,000 --> 00:43:26,620 اما می توان آن را گسل SEG اگر درخت تهی است. 559 00:43:26,620 --> 00:43:32,900 اگر آن تهی بود، آن را قبل از شما تا به حال اشاره گر در وهله اول بصورت غیر مرجع. 560 00:43:32,900 --> 00:43:35,000 [دانشجو] آیا این ارزیابی به اصطلاح تنبل؟ 561 00:43:35,000 --> 00:43:40,770 >> [Bowden] ارزیابی کند و آهسته یک چیز جداگانه است. 562 00:43:40,770 --> 00:43:49,880 ارزیابی کند و آهسته است و بیشتر شبیه به شما را برای یک مقدار می پرسند، 563 00:43:49,880 --> 00:43:54,270 شما بخواهید برای محاسبه یک مقدار، نوع، اما شما آن را نیاز ندارد بلافاصله. 564 00:43:54,270 --> 00:43:59,040 بنابراین تا زمانی که شما به آن نیاز دارید، آن را مورد ارزیابی قرار نگرفته است. 565 00:43:59,040 --> 00:44:03,920 این دقیقا همان چیزی نیست، اما در هافمن pset، 566 00:44:03,920 --> 00:44:06,520 آن را می گوید که ما "lazily" نوشتن. 567 00:44:06,520 --> 00:44:08,670 به این دلیل که ما انجام این کار است زیرا ما در واقع بافر نوشتن - 568 00:44:08,670 --> 00:44:11,820 ما نمی خواهیم به نوشتن بیت های فردی در یک زمان، 569 00:44:11,820 --> 00:44:15,450 و یا بایت های فرد در یک زمان، ما به جای می خواهم برای به دست آوردن یک تکه از کلمه در ادامه متن. 570 00:44:15,450 --> 00:44:19,270 هنگامی که یک تکه از بایت، و سپس خواهیم آن را بنویسید. 571 00:44:19,270 --> 00:44:22,640 حتی اگر شما آن را بخواهید برای نوشتن - و fwrite و fread انجام مرتب کردن بر اساس همان چیزی. 572 00:44:22,640 --> 00:44:26,260 می خواند و می نویسد: بافر می کنند. 573 00:44:26,260 --> 00:44:31,610 حتی اگر شما از آنها بخواهید برای نوشتن بلافاصله، آن را احتمالا نخواهد بود. 574 00:44:31,610 --> 00:44:34,540 و شما می توانید مطمئن باشید که همه چیز در حال رفتن به نوشته 575 00:44:34,540 --> 00:44:37,540 تا زمانی که با شما تماس hfclose و یا هر آنچه در آن است، 576 00:44:37,540 --> 00:44:39,620 که پس از آن می گوید: بسیار خوب، من بستن فایل، 577 00:44:39,620 --> 00:44:43,450 این بدان معناست که من بهتر نوشتن همه چیز را من نوشته شده است هنوز رتبهدهی نشده است. 578 00:44:43,450 --> 00:44:45,770 آن را بدون نیاز به نوشتن همه چیز 579 00:44:45,770 --> 00:44:49,010 تا زمانی که شما در حال بسته شدن فایل، و سپس به آن نیاز دارد. 580 00:44:49,010 --> 00:44:56,220 به طوری که فقط آنچه را تنبل - از آن منتظر می ماند تا زمانی آن را به رخ می دهد. 581 00:44:56,220 --> 00:44:59,990 - نگاهی به 51 و شما را به آن را در جزئیات بیشتر بروید 582 00:44:59,990 --> 00:45:05,470 زیرا OCaml و همه چیز در 51، بازگشت همه چیز است. 583 00:45:05,470 --> 00:45:08,890 هیچ راه حل های تکراری، اساسا وجود ندارد. 584 00:45:08,890 --> 00:45:11,550 بازگشت همه چیز، و ارزیابی تنبل 585 00:45:11,550 --> 00:45:14,790 رفتن به مهم برای بسیاری از شرایط 586 00:45:14,790 --> 00:45:19,920 که در آن، اگر شما lazily ارزیابی، به معنای - 587 00:45:19,920 --> 00:45:24,760 به عنوان مثال، رودخانه ها، که بی نهایت طولانی است. 588 00:45:24,760 --> 00:45:30,990 در تئوری، شما می توانید از اعداد طبیعی به عنوان یک جریان 1-2-3-4-5-6-7 فکر می کنم، 589 00:45:30,990 --> 00:45:33,090 تا lazily بررسی قرار گرفت همه چیز خوب است. 590 00:45:33,090 --> 00:45:37,210 اگر من می گویند من می خواهم شماره دهم، و سپس من می توانم ارزیابی تا شماره دهم. 591 00:45:37,210 --> 00:45:40,300 اگر من می خواهم شماره صدم، و سپس من می توانم ارزیابی به شماره صدم. 592 00:45:40,300 --> 00:45:46,290 بدون ارزیابی تنبل، سپس آن را به تلاش برای بررسی تمام اعداد را بلافاصله. 593 00:45:46,290 --> 00:45:50,000 شما در حال ارزیابی بسیاری از اعداد بی نهایت، و این ممکن نیست. 594 00:45:50,000 --> 00:45:52,080 بنابراین بسیاری از شرایط وجود دارد که در آن ارزیابی تنبل 595 00:45:52,080 --> 00:45:57,840 فقط ضروری برای به دست آوردن همه چیز را به کار است. 596 00:45:57,840 --> 00:46:05,260 >> حالا ما می خواهیم به نوشتن را وارد کنید که در آن درج می شود 597 00:46:05,260 --> 00:46:08,430 به همین ترتیب در حال تغییر در تعریف آن است. 598 00:46:08,430 --> 00:46:10,470 بنابراین در حال حاضر آن را درج بولی (ارزش بین المللی). 599 00:46:10,470 --> 00:46:23,850 ما در حال رفتن به تغییر است که برای وارد کردن بولی (هوشمند ارزش، گره درخت *). 600 00:46:23,850 --> 00:46:29,120 ما در واقع رفتن به تغییر آن دوباره در یک بیت، خواهیم دید که چرا. 601 00:46:29,120 --> 00:46:32,210 و اجازه حرکت build_node، فقط برای heck از آن، 602 00:46:32,210 --> 00:46:36,730 بنابراین ما لازم نیست که یک نمونه تابع به نوشتن درج کنید. 603 00:46:36,730 --> 00:46:42,450 که اشاره به این است که شما در حال رفتن به استفاده از build_node در درج. 604 00:46:42,450 --> 00:46:49,590 باشه. نگاهی از یک دقیقه برای آن. 605 00:46:49,590 --> 00:46:52,130 من فکر می کنم که من را نجات داد تجدید نظر اگر شما می خواهید از آن بکشد، 606 00:46:52,130 --> 00:47:00,240 و یا، حداقل، من در حال حاضر. 607 00:47:00,240 --> 00:47:04,190 من می خواستم استراحت کمی به فکر می کنم در مورد منطق قرار دادن، 608 00:47:04,190 --> 00:47:08,750 اگر شما نمی توانید از آن فکر می کنم. 609 00:47:08,750 --> 00:47:12,860 در واقع، شما فقط تا به حال قرار دادن در برگ است. 610 00:47:12,860 --> 00:47:18,640 مانند، اگر من وارد 1، پس از آن من به ناچار از رفتن به می شود قرار دادن 1 - 611 00:47:18,640 --> 00:47:21,820 من به سیاه و سفید تغییر دهید - I'll قرار دادن 1 در اینجا. 612 00:47:21,820 --> 00:47:28,070 یا اگر من وارد 4، من می خواهم به قرار دادن 4 در اینجا. 613 00:47:28,070 --> 00:47:32,180 بنابراین بدون توجه به آنچه شما انجام دهد، شما در حال رفتن به قرار دادن در یک برگ. 614 00:47:32,180 --> 00:47:36,130 همه شما باید انجام دهید این است که تکرار پایین درخت تا زمانی که شما به گره 615 00:47:36,130 --> 00:47:40,890 است که باید به پدر و مادر گره، پدر و مادر گره جدید 616 00:47:40,890 --> 00:47:44,560 و سپس به سمت چپ یا راست خود اشاره گر، بسته به اینکه آیا تغییر 617 00:47:44,560 --> 00:47:47,060 آن را بزرگتر یا کمتر از گره فعلی است. 618 00:47:47,060 --> 00:47:51,180 تغییری که اشاره گر به اشاره به گره جدید خود را. 619 00:47:51,180 --> 00:48:05,490 بنابراین تکرار درخت، نقطه برگ را به گره جدید است. 620 00:48:05,490 --> 00:48:09,810 همچنین در مورد اینکه چرا این نوع وضعیت را ممنوع قبل از فکر می کنم، 621 00:48:09,810 --> 00:48:17,990 جایی که من درخت دودویی است که در آن ساخته شده آن درست بود 622 00:48:17,990 --> 00:48:19,920 اگر شما تنها در تنها یک گره نگاه کرد، 623 00:48:19,920 --> 00:48:24,830 اما 9 بود به سمت چپ از 7 اگر شما تکرار کردن تمام راه. 624 00:48:24,830 --> 00:48:29,770 به طوری که غیر ممکن است در این سناریو، از - 625 00:48:29,770 --> 00:48:32,530 فکر می کنم در مورد قرار دادن 9 یا چیزی در گره اول، 626 00:48:32,530 --> 00:48:35,350 من قصد دارم برای دیدن 7 و من فقط برای رفتن به سمت راست. 627 00:48:35,350 --> 00:48:38,490 بنابراین بدون توجه به آنچه که من انجام می دهند، اگر من قرار دادن با رفتن به برگ، 628 00:48:38,490 --> 00:48:40,790 و برگ با استفاده از الگوریتم مناسب، 629 00:48:40,790 --> 00:48:43,130 رفتن به غیر ممکن است برای من برای وارد کردن 9 به سمت چپ از 7 630 00:48:43,130 --> 00:48:48,250 چرا که به زودی به عنوان من ضربه 7 من قصد دارم برای رفتن به سمت راست. 631 00:48:59,740 --> 00:49:02,070 آیا کسی هم چیزی دارند که برای شروع با؟ 632 00:49:02,070 --> 00:49:05,480 [دانشجو] من انجام دهد. >> مطمئنا. 633 00:49:05,480 --> 00:49:09,200 [دانشجو، ناخوانا] 634 00:49:09,200 --> 00:49:14,390 [دانشجویی، ناخوانا] 635 00:49:14,390 --> 00:49:18,330 [Bowden] قدردانی است. باشه. می خواهم که توضیح می دهند؟ 636 00:49:18,330 --> 00:49:20,690 >> [دانشجو] از آنجا که ما می دانیم که ما در قرار دادن 637 00:49:20,690 --> 00:49:24,060 گره های جدید در پایان از درخت، 638 00:49:24,060 --> 00:49:28,070 من را از طریق درخت لوپ تکرار شونده 639 00:49:28,070 --> 00:49:31,360 تا زمانی که من به یک گره که با اشاره به تهی شدم. 640 00:49:31,360 --> 00:49:34,220 و پس از آن تصمیم گرفتم آن را قرار داده یا در سمت راست یا سمت چپ 641 00:49:34,220 --> 00:49:37,420 با استفاده از این متغیر سمت راست، آن را به من گفت که در آن به آن قرار داده است. 642 00:49:37,420 --> 00:49:41,850 و پس از آن، در اصل، من فقط ساخته شده است که تاریخ و زمان آخرین - 643 00:49:41,850 --> 00:49:47,520 که دما نقطه گره به گره جدید است که آن را ایجاد، 644 00:49:47,520 --> 00:49:50,770 یا در سمت چپ و یا در سمت راست، با توجه به آنچه ارزش بود. 645 00:49:50,770 --> 00:49:56,530 در نهایت، من مجموعه ای از مقدار گره جدید به ارزش تست خود. 646 00:49:56,530 --> 00:49:59,550 [Bowden] خوب، پس یک شماره به من اینجا را ببینید. 647 00:49:59,550 --> 00:50:02,050 این 95٪ از این راه وجود دارد. 648 00:50:02,050 --> 00:50:07,550 خوب، این مسئله است که من می بینم، هر کس دیگری را دیدن موضوع؟ 649 00:50:07,550 --> 00:50:18,400 شرایطی که تحت آن آنها شکستن حلقه چیست؟ 650 00:50:18,400 --> 00:50:22,100 [دانشجو] اگر دما تهی است؟ >> آره. پس چگونه شما به خارج از حلقه است اگر دما صفر است. 651 00:50:22,100 --> 00:50:30,220 اما آنچه می توانم حق در اینجا؟ 652 00:50:30,220 --> 00:50:35,410 من dereference موقت، است که ناگزیر تهی است. 653 00:50:35,410 --> 00:50:39,840 بنابراین چیزی که شما نیاز به انجام پیگیری تا دما تهی است، 654 00:50:39,840 --> 00:50:45,590 شما می خواهید برای پیگیری از پدر و مادر در تمام زمان. 655 00:50:45,590 --> 00:50:52,190 ما همچنین می خواهیم گره پدر *، من حدس می زنم ما می توانیم که در تهی در ابتدا نگه دارید. 656 00:50:52,190 --> 00:50:55,480 این امر به رفتار عجیب و غریب برای ریشه درخت، 657 00:50:55,480 --> 00:50:59,210 اما ما را به آن را دریافت کنید. 658 00:50:59,210 --> 00:51:03,950 اگر مقدار بیشتر از هر چیز دیگری، و سپس دما = حق موقت است. 659 00:51:03,950 --> 00:51:07,910 اما قبل از انجام این کار، پدر و مادر دما =. 660 00:51:07,910 --> 00:51:14,500 یا پدر و مادر همیشه به دما برابر می رود؟ این است که در مورد؟ 661 00:51:14,500 --> 00:51:19,560 اگر دما تهی نیست، پس من قصد دارم به پایین حرکت کند، بدون توجه به آنچه. 662 00:51:19,560 --> 00:51:24,030 به یک گره که موقت است پدر و مادر است. 663 00:51:24,030 --> 00:51:27,500 پس پدر و مادر رفتن به دما، و پس از آن من حرکت دما پایین است. 664 00:51:27,500 --> 00:51:32,410 کن دما صفر است، اما پدر و مادر به پدر و مادر از چیزی است که تهی. 665 00:51:32,410 --> 00:51:39,110 تا پایین در اینجا، من نمی خواهم به حق مجموعه ای معادل 1. 666 00:51:39,110 --> 00:51:41,300 بنابراین من به سمت راست نقل مکان کرد، به طوری که اگر درست = 1، 667 00:51:41,300 --> 00:51:45,130 و من حدس می زنم شما می خواهید برای انجام - 668 00:51:45,130 --> 00:51:48,530 اگر شما به سمت چپ حرکت می کند، شما می خواهید به حق مجموعه ای برابر با 0 است. 669 00:51:48,530 --> 00:51:55,950 وگرنه اگر شما همیشه به سمت راست حرکت می کند. 670 00:51:55,950 --> 00:51:58,590 تا حق = 0. اگر درست = 1، 671 00:51:58,590 --> 00:52:04,260 در حال حاضر ما می خواهید را به پدر و مادر newnode اشاره گر راست، 672 00:52:04,260 --> 00:52:08,520 دیگری که ما می خواهیم را به پدر و مادر newnode اشاره گر چپ. 673 00:52:08,520 --> 00:52:16,850 سوالات مطرح شده در آن؟ 674 00:52:16,850 --> 00:52:24,880 باشه. بنابراین این راه ما است - خب، در واقع، به جای انجام این کار، 675 00:52:24,880 --> 00:52:29,630 ما 1/2 انتظار می رود شما را به استفاده build_node. 676 00:52:29,630 --> 00:52:40,450 و پس از آن اگر newnode برابر تهی، بازگشت نادرست است. 677 00:52:40,450 --> 00:52:44,170 که که. در حال حاضر، این چیزی است که ما انتظار می رود شما را به انجام است. 678 00:52:44,170 --> 00:52:47,690 >> این همان چیزی است که راه حل های پرسنل می باشد. 679 00:52:47,690 --> 00:52:52,360 من این را به عنوان "حق" راه رفتن در مورد آن اختلاف نظر دارند 680 00:52:52,360 --> 00:52:57,820 اما این کاملا خوب و آن کار خواهد کرد. 681 00:52:57,820 --> 00:53:02,840 یک چیز که حق کمی عجیب و غریب است در حال حاضر است 682 00:53:02,840 --> 00:53:08,310 اگر درخت شروع می شود به عنوان تهی، ما در یک درخت تهی منتقل می کند. 683 00:53:08,310 --> 00:53:12,650 من حدس می زنم آن را در مورد چگونگی رفتار گذرا در یک درخت تهی تعریف می کنید بستگی دارد. 684 00:53:12,650 --> 00:53:15,490 من فکر می کنم که اگر شما در یک درخت تهی می گذرد، 685 00:53:15,490 --> 00:53:17,520 پس از آن قرار دادن این مقدار را به یک درخت تهی 686 00:53:17,520 --> 00:53:23,030 باید فقط بازگشت به یک درخت که در آن ارزش تنها این است که گره تک. 687 00:53:23,030 --> 00:53:25,830 آیا مردم با آن موافق هستید؟ شما می توانید، اگر شما می خواهید، 688 00:53:25,830 --> 00:53:28,050 اگر شما در یک درخت تهی 689 00:53:28,050 --> 00:53:31,320 و شما می خواهید برای قرار دادن یک مقدار به آن بازگشت، نادرست است. 690 00:53:31,320 --> 00:53:33,830 آن تا به شما برای تعریف آن است. 691 00:53:33,830 --> 00:53:38,320 برای انجام این کار اولین چیزی که من گفتم و پس از آن - 692 00:53:38,320 --> 00:53:40,720 خوب، شما در حال رفتن به انجام این کار مشکل است، زیرا 693 00:53:40,720 --> 00:53:44,090 آن ساده تر خواهد بود اگر ما تا به حال یک اشاره گر جهانی به چیزی، 694 00:53:44,090 --> 00:53:48,570 اما ما، نه بنابراین اگر درخت تهی، چیزی نیست که ما می توانیم در مورد آن انجام دهید وجود دارد. 695 00:53:48,570 --> 00:53:50,960 ما فقط می تواند بازگشت کاذب. 696 00:53:50,960 --> 00:53:52,840 بنابراین من قصد دارم برای تغییر را وارد کنید. 697 00:53:52,840 --> 00:53:56,540 ما به لحاظ فنی فقط می تواند این حق در اینجا تغییر دهید، 698 00:53:56,540 --> 00:53:58,400 چگونه آن را تکرار بیش از همه چیز، 699 00:53:58,400 --> 00:54:04,530 اما من قصد دارم برای تغییر درج یک گره به درخت **. 700 00:54:04,530 --> 00:54:07,510 اشاره گر دو برابر شود. 701 00:54:07,510 --> 00:54:09,710 این به چه معنی؟ 702 00:54:09,710 --> 00:54:12,330 به جای خرید و فروش با اشاره گر به گره، 703 00:54:12,330 --> 00:54:16,690 چیزی که من قصد دارم به دستکاری این اشاره گر است. 704 00:54:16,690 --> 00:54:18,790 من قصد دارم به دستکاری این اشاره گر است. 705 00:54:18,790 --> 00:54:21,770 من قصد دارم به دستکاری اشاره گر به طور مستقیم. 706 00:54:21,770 --> 00:54:25,760 این را حس می کند از آن زمان، در مورد پایین فکر می کنم - 707 00:54:25,760 --> 00:54:33,340 خوب، در حال حاضر این امتیاز به تهی. 708 00:54:33,340 --> 00:54:38,130 چیزی که من می خواهم به انجام این کار این است که دستکاری این اشاره گر به نقطه تهی نیست. 709 00:54:38,130 --> 00:54:40,970 من می خواهم آن را برای اشاره به گره جدید من. 710 00:54:40,970 --> 00:54:44,870 اگر من فقط آهنگ از اشاره گر به اشاره گر من نگه دارید، 711 00:54:44,870 --> 00:54:47,840 پس از آن من لازم نیست به پیگیری از اشاره گر پدر و مادر است. 712 00:54:47,840 --> 00:54:52,640 من فقط می تواند مسیر برای دیدن در صورتی که اشاره گر با اشاره به تهی، 713 00:54:52,640 --> 00:54:54,580 و در صورتی که اشاره گر با اشاره به تهی، 714 00:54:54,580 --> 00:54:57,370 برای اشاره به گره من می خواهم آن را تغییر دهید. 715 00:54:57,370 --> 00:55:00,070 و من می توانم آن را از من به یک اشاره گر به اشاره گر را تغییر دهید. 716 00:55:00,070 --> 00:55:02,040 اجازه بدهید این حق را در حال حاضر. 717 00:55:02,040 --> 00:55:05,470 شما در واقع می توانید آن را به صورت بازگشتی زیبا به راحتی انجام دهد. 718 00:55:05,470 --> 00:55:08,080 آیا ما می خواهیم به انجام این کار؟ 719 00:55:08,080 --> 00:55:10,980 بله، کار می کنیم. 720 00:55:10,980 --> 00:55:16,790 >> اجازه دهید آن را به صورت بازگشتی. 721 00:55:16,790 --> 00:55:24,070 اول، چیزی است که در مورد پایگاه ما خواهد بود؟ 722 00:55:24,070 --> 00:55:29,140 تقریبا همیشه مورد پایگاه ما، اما در واقع، این نوع از روی حیله و تزویر است. 723 00:55:29,140 --> 00:55:34,370 اولین چیزهایی اول، اگر (درخت == NULL) 724 00:55:34,370 --> 00:55:37,550 من حدس می زنم ما فقط رفتن به بازگشت غلط است. 725 00:55:37,550 --> 00:55:40,460 این است که از درخت تهی بودن متفاوت است. 726 00:55:40,460 --> 00:55:44,510 این اشاره گر به اشاره گر ریشه خود تهی است 727 00:55:44,510 --> 00:55:48,360 که بدان معنی است که اشاره گر ریشه خود وجود ندارد. 728 00:55:48,360 --> 00:55:52,390 تا پایین در اینجا، اگر من 729 00:55:52,390 --> 00:55:55,760 * گره - اجازه دهید فقط استفاده مجدد از این. 730 00:55:55,760 --> 00:55:58,960 گره ریشه = NULL، 731 00:55:58,960 --> 00:56:00,730 و پس از آن من قصد دارم به تماس قرار دادن با انجام کاری مانند، 732 00:56:00,730 --> 00:56:04,540 درج 4 به و ریشه. 733 00:56:04,540 --> 00:56:06,560 بنابراین و ریشه، اگر ریشه * گره 734 00:56:06,560 --> 00:56:11,170 پس از آن و ریشه است که برای رفتن به ** گره. 735 00:56:11,170 --> 00:56:15,120 این درست است. در این مورد، درخت، تا اینجا، 736 00:56:15,120 --> 00:56:20,120 درخت تهی نیست - و یا قرار دادن. 737 00:56:20,120 --> 00:56:24,630 اینجا. درخت تهی است، درخت * تهی است، که خوب است 738 00:56:24,630 --> 00:56:26,680 چرا که اگر درخت * تهی است، پس از آن من می توانید آن را دستکاری 739 00:56:26,680 --> 00:56:29,210 در حال حاضر به چه من می خواهم آن را به نقطه به نقطه. 740 00:56:29,210 --> 00:56:34,750 اما اگر درخت تهی، این بدان معناست که من فقط پایین آمد و گفت: تهی. 741 00:56:34,750 --> 00:56:42,710 که معنی ندارد. من می تواند هر چیزی را با آن انجام نمی شود. 742 00:56:42,710 --> 00:56:45,540 اگر درخت تهی، بازگشت نادرست است. 743 00:56:45,540 --> 00:56:48,220 بنابراین من اساسا در حال حاضر گفت: آنچه مورد پایگاه ما واقعی است. 744 00:56:48,220 --> 00:56:50,580 و آنچه که خواهد بود؟ 745 00:56:50,580 --> 00:56:55,030 [دانشجو، ناخوانا] 746 00:56:55,030 --> 00:57:00,000 [Bowden] بله. بنابراین اگر (* درخت == NULL). 747 00:57:00,000 --> 00:57:04,520 این مربوط به این مورد را در اینجا 748 00:57:04,520 --> 00:57:09,640 اگر اشاره گر قرمز من است که اشاره گر من متمرکز شده است، 749 00:57:09,640 --> 00:57:12,960 بنابراین من در این اشاره گر متمرکز، در حال حاضر من در این اشاره گر متمرکز شده است. 750 00:57:12,960 --> 00:57:15,150 در حال حاضر من در این اشاره گر متمرکز شده است. 751 00:57:15,150 --> 00:57:18,160 بنابراین اگر اشاره گر قرمز من است، که ** گره من، 752 00:57:18,160 --> 00:57:22,880 همیشه - اگر *، اشاره گر قرمز من، همیشه تهی است، 753 00:57:22,880 --> 00:57:28,470 که بدان معنی است که من در مورد جایی که من هستم تمرکز بر روی یک اشاره گر است که نقاط هستم - 754 00:57:28,470 --> 00:57:32,530 این یک اشاره گر است که متعلق به یک برگ است. 755 00:57:32,530 --> 00:57:41,090 من می خواهم برای تغییر این اشاره گر به اشاره به گره جدید است. 756 00:57:41,090 --> 00:57:45,230 دوباره در اینجا. 757 00:57:45,230 --> 00:57:56,490 newnode من فقط گره * N = build_node (ارزش) 758 00:57:56,490 --> 00:58:07,300 پس از آن، N اگر N = NULL، بازگشت نادرست است. 759 00:58:07,300 --> 00:58:12,600 دیگری که ما می خواهیم برای تغییر آنچه را که اشاره گر در حال حاضر به اشاره 760 00:58:12,600 --> 00:58:17,830 در حال حاضر به ما گره تازه ساخته شده. 761 00:58:17,830 --> 00:58:20,280 ما در واقع می تواند که در اینجا انجام دهید. 762 00:58:20,280 --> 00:58:30,660 به جای گفتن N، ما می گوییم * = درخت اگر درخت *. 763 00:58:30,660 --> 00:58:35,450 هر کس بفهمد که؟ که با خرید و فروش با اشاره گر به اشاره گر، 764 00:58:35,450 --> 00:58:40,750 ما می توانیم از اشاره گر تهی به نقطه را به چیزهایی که ما می خواهیم آنها را به نقطه تغییر دهید. 765 00:58:40,750 --> 00:58:42,820 که مورد پایگاه ما است. 766 00:58:42,820 --> 00:58:45,740 >> در حال حاضر عود ما، و یا بازگشت ما، 767 00:58:45,740 --> 00:58:51,430 رفتن به بسیار شبیه به بازگشتی دیگر ما انجام داده ایم. 768 00:58:51,430 --> 00:58:55,830 ما در حال رفتن به خواهید برای وارد کردن ارزش، 769 00:58:55,830 --> 00:58:59,040 و در حال حاضر من قصد استفاده از سه تایی دوباره، اما وضعیت ما خواهد بود؟ 770 00:58:59,040 --> 00:59:05,180 آن چه ما به دنبال آن هستید تا تصمیم بگیرید که آیا می خواهید برای رفتن به سمت چپ یا راست؟ 771 00:59:05,180 --> 00:59:07,760 بیایید آن را انجام دهد در مراحل جداگانه. 772 00:59:07,760 --> 00:59:18,850 اگر (ارزش) چیست؟ 773 00:59:18,850 --> 00:59:23,200 [دانشجو] ارزش درخت؟ 774 00:59:23,200 --> 00:59:27,490 [Bowden] پس به یاد داشته باشید که من در حال حاضر - 775 00:59:27,490 --> 00:59:31,260 [دانش آموزان، ناخوانا] 776 00:59:31,260 --> 00:59:34,140 [Bowden] آره، حق در اینجا، اجازه دهید بگویم که این فلش سبز 777 00:59:34,140 --> 00:59:39,050 نمونه ای از همان درخت در حال حاضر، یک اشاره گر به اشاره گر است. 778 00:59:39,050 --> 00:59:46,610 بنابراین این بدان معناست که من یک اشاره گر به اشاره گر تا 3. 779 00:59:46,610 --> 00:59:48,800 dereference دو بار صدا خوب است. 780 00:59:48,800 --> 00:59:51,010 چه کار کنم - چگونه می توانم انجام این کار؟ 781 00:59:51,010 --> 00:59:53,210 [دانشجو] Dereference یک بار، و پس از آن انجام فلش که در راه است؟ 782 00:59:53,210 --> 00:59:58,420 [Bowden] پس (درخت *) dereference یک بار، -> ارزش 783 00:59:58,420 --> 01:00:05,960 رفتن به مقدار گره است که من به طور غیر مستقیم به اشاره به من می دهد. 784 01:00:05,960 --> 01:00:11,980 پس من هم می توانید آن را ** tree.value اگر شما ترجیح می دهید که می نویسم. 785 01:00:11,980 --> 01:00:18,490 در هر دو صورت کار می کند. 786 01:00:18,490 --> 01:00:26,190 در صورتی که این مورد، پس از آن من می خواهم به تماس قرار دادن با ارزش است. 787 01:00:26,190 --> 01:00:32,590 و به روز شده است من گره ** خواهد بود؟ 788 01:00:32,590 --> 01:00:39,440 من می خواهم برای رفتن به سمت چپ، به طوری tree.left ** رفتن به سمت چپ من. 789 01:00:39,440 --> 01:00:41,900 و من می خواهم اشاره گر به چیزی که 790 01:00:41,900 --> 01:00:44,930 به طوری که اگر در سمت چپ به پایان می رسد تا اشاره گر تهی، 791 01:00:44,930 --> 01:00:48,360 من می توانم آن را برای اشاره به گره جدید من را تغییر دهند. 792 01:00:48,360 --> 01:00:51,460 >> و در مورد دیگر می تواند بسیار مشابه است. 793 01:00:51,460 --> 01:00:55,600 اجازه دهید در واقع که سه تایی من در حال حاضر. 794 01:00:55,600 --> 01:01:04,480 قرار دادن مقدار اگر مقدار <(درخت **). ارزش. 795 01:01:04,480 --> 01:01:11,040 سپس ما می خواهیم برای به روز رسانی ** ما را به سمت چپ، 796 01:01:11,040 --> 01:01:17,030 دیگری که ما می خواهیم برای به روز رسانی ** ما را به سمت راست. 797 01:01:17,030 --> 01:01:22,540 [دانشجو] که اشاره گر به اشاره گر؟ 798 01:01:22,540 --> 01:01:30,940 [Bowden] به یاد داشته باشید که - ** tree.right یک ستاره گره. 799 01:01:30,940 --> 01:01:35,040 [دانشجو، ناخوانا] >> آره. 800 01:01:35,040 --> 01:01:41,140 ** tree.right مانند این اشاره گر و یا چیزی است. 801 01:01:41,140 --> 01:01:45,140 بنابراین با در نظر گرفتن اشاره گر به آن که مرا به آنچه من می خواهم 802 01:01:45,140 --> 01:01:50,090 اشاره گر به آن مرد است. 803 01:01:50,090 --> 01:01:54,260 [دانشجو] آیا ما به بیش از دوباره همین دلیل ما در حال استفاده از این دو اشاره گر؟ 804 01:01:54,260 --> 01:01:58,220 [Bowden] آره. پس - نه، شما می توانید، و این راه حل را قبل از 805 01:01:58,220 --> 01:02:04,540 یک راه انجام آن بدون انجام دو اشاره گر بود. 806 01:02:04,540 --> 01:02:08,740 شما باید قادر به درک با استفاده از دو اشاره گر، 807 01:02:08,740 --> 01:02:11,660 و این یک راه حل پاک کننده است. 808 01:02:11,660 --> 01:02:16,090 همچنین، توجه کنید که، چه اتفاقی می افتد اگر درخت من - 809 01:02:16,090 --> 01:02:24,480 چه اتفاقی می افتد اگر ریشه من تهی بود؟ اگر من این کار را در مورد حق در اینجا، چه اتفاقی می افتد؟ 810 01:02:24,480 --> 01:02:30,540 بنابراین گره * ریشه = NULL، قرار دادن 4 به و ریشه. 811 01:02:30,540 --> 01:02:35,110 چه ریشه می خواهم بعد از این می شود؟ 812 01:02:35,110 --> 01:02:37,470 [دانشجو، ناخوانا] >> آره. 813 01:02:37,470 --> 01:02:41,710 ارزش ریشه به 4. 814 01:02:41,710 --> 01:02:45,510 سمت چپ ریشه رفتن به تهی، حق ریشه است برای رفتن به تهی. 815 01:02:45,510 --> 01:02:49,490 در مورد که در آن ما از ریشه با آدرس منتقل می کند نیست، 816 01:02:49,490 --> 01:02:52,490 ما می تواند ریشه را تغییر دهید. 817 01:02:52,490 --> 01:02:56,020 در مورد که در آن درخت - از کجا ریشه تهی بود، 818 01:02:56,020 --> 01:02:58,410 ما فقط مجبور به بازگشت به نادرست. چیزی که می تواند انجام دهد وجود دارد. 819 01:02:58,410 --> 01:03:01,520 ما می توانیم از یک گره به درخت خالی درج نیست. 820 01:03:01,520 --> 01:03:06,810 اما در حال حاضر ما می توانیم، ما فقط یک درخت خالی را به یک درخت یک گره است. 821 01:03:06,810 --> 01:03:13,400 که معمولا انتظار می رود که آن را قرار است به کار است. 822 01:03:13,400 --> 01:03:21,610 >> علاوه بر این، این است که به طور معنی داری کوتاه تر از 823 01:03:21,610 --> 01:03:26,240 همچنین پیگیری از پدر و مادر، و بنابراین شما تکرار کردن تمام راه را. 824 01:03:26,240 --> 01:03:30,140 حالا من باید پدر و مادر من، و من فقط باید به پدر و مادر اشاره گر من حق را به هر چیز دیگری. 825 01:03:30,140 --> 01:03:35,640 در عوض، اگر ما این تکرار شونده، آن را می شود ایده همین کار را با حلقه در حالی که. 826 01:03:35,640 --> 01:03:38,100 اما به جای داشتن برای مقابله با اشاره پدر و مادر من، 827 01:03:38,100 --> 01:03:40,600 به جای اشاره گر فعلی من خواهد بود چیزی که 828 01:03:40,600 --> 01:03:43,790 که من به طور مستقیم تغییر برای اشاره به گره جدید است. 829 01:03:43,790 --> 01:03:46,090 من لازم نیست که برای مقابله با آیا آن را با اشاره به سمت چپ. 830 01:03:46,090 --> 01:03:48,810 من لازم نیست که برای مقابله با آیا آن را با اشاره به سمت راست. 831 01:03:48,810 --> 01:04:00,860 فقط هر چه این اشاره گر، من قصد دارم به آن را برای اشاره به گره جدید است. 832 01:04:00,860 --> 01:04:05,740 هر کس به درک چگونه کار می کند؟ 833 01:04:05,740 --> 01:04:09,460 اگر نه چرا ما می خواهیم به این ترتیب آن را انجام دهد، 834 01:04:09,460 --> 01:04:14,920 اما حداقل است که این کار را به عنوان یک راه حل است؟ 835 01:04:14,920 --> 01:04:17,110 [دانشجو] از کجا ما بازگشت درست است؟ 836 01:04:17,110 --> 01:04:21,550 [Bowden] که احتمالا حق در اینجا. 837 01:04:21,550 --> 01:04:26,690 اگر ما به درستی آن را درج کنید، بازگشت درست است. 838 01:04:26,690 --> 01:04:32,010 دیگری، پایین در اینجا ما قصد داریم که می خواهید به بازگشت هر چه بازده درج. 839 01:04:32,010 --> 01:04:35,950 >> و چه چیزی خاص در مورد این تابع بازگشتی؟ 840 01:04:35,950 --> 01:04:43,010 این دم بازگشتی است، بنابراین تا زمانی که ما با برخی از بهینه سازی کامپایل، 841 01:04:43,010 --> 01:04:48,060 آن را خواهد داد که و شناسایی شما خواهد شد سرریز پشته از این هرگز، 842 01:04:48,060 --> 01:04:53,230 حتی اگر درخت به ارتفاع 10،000 یا 10 میلیون. 843 01:04:53,230 --> 01:04:55,630 [دانشجو، ناخوانا] 844 01:04:55,630 --> 01:05:00,310 [Bowden] من فکر می کنم آن را در داش - و یا چه سطحی بهینه سازی 845 01:05:00,310 --> 01:05:03,820 برای بازگشت دم به رسمیت شناخته شود، مورد نیاز است. 846 01:05:03,820 --> 01:05:09,350 من فکر می کنم آن را به رسمیت می شناسد - شورای همکاری خلیج فارس و صدای جرنگ جرنگ 847 01:05:09,350 --> 01:05:12,610 همچنین معانی مختلف برای سطح بهینه سازی خود را داشته باشد. 848 01:05:12,610 --> 01:05:17,870 من می خواهم بگویم آن DashO 2، مطمئن باشید که آن را بازگشت دم به رسمیت. 849 01:05:17,870 --> 01:05:27,880 اما ما - شما می تواند مانند یک مثال و یا چیزی Fibonocci ساخت. 850 01:05:27,880 --> 01:05:30,030 این آسان برای تست با این نیست، چرا که این مشکل را برای ساخت 851 01:05:30,030 --> 01:05:32,600 یک درخت دودویی است که خیلی بزرگ است. 852 01:05:32,600 --> 01:05:37,140 اما بله، من فکر می کنم آن را DashO 2، 853 01:05:37,140 --> 01:05:40,580 اگر شما با DashO 2 کامپایل، آن را برای بازگشت دم نگاه 854 01:05:40,580 --> 01:05:54,030 و بهینه سازی که از. 855 01:05:54,030 --> 01:05:58,190 بازگشت به - قرار دادن به معنای واقعی کلمه آخرین چیزی که به آن نیاز دارد. 856 01:05:58,190 --> 01:06:04,900 بیایید برگردید به درج در اینجا 857 01:06:04,900 --> 01:06:07,840 جایی که ما قصد انجام همان ایده است. 858 01:06:07,840 --> 01:06:14,340 هنوز هم نقص که نمی توانند به طور کامل مسئولیت رسیدگی به 859 01:06:14,340 --> 01:06:17,940 زمانی که ریشه خود تهی است، و یا ورود به گذشته تهی است، 860 01:06:17,940 --> 01:06:20,060 اما به جای برخورد با پدر و مادر اشاره گر، 861 01:06:20,060 --> 01:06:27,430 اجازه دهید به کار بردن منطق همان نگه داشتن اشاره گر به اشاره گر. 862 01:06:27,430 --> 01:06:35,580 اگر اینجا ما حفظ گره ** فعلی، 863 01:06:35,580 --> 01:06:37,860 و ما لازم نیست برای پیگیری دیگر 864 01:06:37,860 --> 01:06:47,190 اما گره ** فعلی = درخت. 865 01:06:47,190 --> 01:06:54,800 و حلقه در حالی که در حال حاضر ما این است که در حالی که فعلی * تهی برابر نیست. 866 01:06:54,800 --> 01:07:00,270 آیا لازم نیست آهنگ از پدر و مادر برای حفظ دیگر. 867 01:07:00,270 --> 01:07:04,180 آیا نیاز به پیگیری از چپ و راست. 868 01:07:04,180 --> 01:07:10,190 و من آن را موقت تماس بگیرید، چرا که ما در حال حاضر با استفاده از دما است. 869 01:07:10,190 --> 01:07:17,200 باشه. بنابراین اگر (ارزش> * دما)، 870 01:07:17,200 --> 01:07:24,010 پس از آن و (موقت) -> حق 871 01:07:24,010 --> 01:07:29,250 دیگری دما = (* دما) -> سمت چپ. 872 01:07:29,250 --> 01:07:32,730 و در حال حاضر، در این مرحله، پس از این حلقه در حالی که، 873 01:07:32,730 --> 01:07:36,380 من فقط این کار را چرا که شاید آن را آسان تر به فکر می کنم در مورد مکررا از به صورت بازگشتی، 874 01:07:36,380 --> 01:07:39,010 اما پس از این حلقه در حالی که، 875 01:07:39,010 --> 01:07:43,820 * موقت اشاره گر ما می خواهید به تغییر است. 876 01:07:43,820 --> 01:07:48,960 >> قبل از اینکه ما تا به حال پدر و مادر، و ما می خواستیم به تغییر یا چپ پدر و مادر و یا پدر و مادر حق، 877 01:07:48,960 --> 01:07:51,310 اما اگر می خواهید به تغییر حق پدر و مادر، 878 01:07:51,310 --> 01:07:54,550 پس از آن دما * حق پدر و مادر است، و ما می توانیم آن را به طور مستقیم تغییر دهید. 879 01:07:54,550 --> 01:08:05,860 تا پایین در اینجا، ما می توانیم * دما = newnode، انجام دهند و که در آن است. 880 01:08:05,860 --> 01:08:09,540 بنابراین اطلاع، همه ما در این بود را از خط کد. 881 01:08:09,540 --> 01:08:14,770 به منظور پیگیری از پدر و مادر در این است که تلاش اضافی. 882 01:08:14,770 --> 01:08:18,689 در اینجا، اگر ما فقط پیگیری از اشاره گر به اشاره گر، 883 01:08:18,689 --> 01:08:22,990 و حتی اگر ما می خواستیم به خلاص شدن از شر تمام این آکولاد در حال حاضر، 884 01:08:22,990 --> 01:08:27,170 این که آن را کوتاه تر است. 885 01:08:27,170 --> 01:08:32,529 این در حال حاضر راه حل همان است، 886 01:08:32,529 --> 01:08:38,210 اما خطوط کمتری از کد. 887 01:08:38,210 --> 01:08:41,229 هنگامی که شما شروع به شناخت این امر به عنوان یک راه حل معتبر، 888 01:08:41,229 --> 01:08:43,529 آن را نیز آسان تر است به همین دلیل در مورد از مانند، خوب، 889 01:08:43,529 --> 01:08:45,779 چرا این پرچم در سمت راست داده int؟ 890 01:08:45,779 --> 01:08:49,290 به چه معنا است؟ آه، آن را به این مفهوم است که 891 01:08:49,290 --> 01:08:51,370 هر بار که من به حق، من نیاز به آن مجموعه، 892 01:08:51,370 --> 01:08:53,819 اگر دیگری به سمت چپ من نیاز به آن را به صفر است. 893 01:08:53,819 --> 01:09:04,060 در اینجا، من را ندارد به همین دلیل است که در مورد آن را فقط ساده تر به فکر کردن در مورد. 894 01:09:04,060 --> 01:09:06,710 پرسش و پاسخ؟ 895 01:09:06,710 --> 01:09:16,290 [دانشجو، ناخوانا] >> آره. 896 01:09:16,290 --> 01:09:23,359 خوب، پس در بیت آخر - 897 01:09:23,359 --> 01:09:28,080 من حدس می زنم سریع و آسان تابع ما می توانیم انجام دهیم این است، 898 01:09:28,080 --> 01:09:34,910 let's - با هم، من حدس می زنم، سعی کنید و ارسال نامه شامل تابع 899 01:09:34,910 --> 01:09:38,899 که اصلا برام مهم نیست که آیا آن است که یک درخت جستجوی دودویی. 900 01:09:38,899 --> 01:09:43,770 این تابع شامل بازگشت واقعی 901 01:09:43,770 --> 01:09:58,330 اگر در هر جای این درخت به طور کلی ارزش ما به دنبال است. 902 01:09:58,330 --> 01:10:02,520 بنابراین برای اولین بار آن را انجام دهد به صورت بازگشتی و سپس ما آن را مکررا انجام دهد. 903 01:10:02,520 --> 01:10:07,300 ما در واقع فقط می توانید آن را با هم انجام دهید، به دلیل این است که رفتن به واقعا کوتاه است. 904 01:10:07,300 --> 01:10:11,510 >> مورد پایه من چه می شود؟ 905 01:10:11,510 --> 01:10:13,890 [دانشجو، ناخوانا] 906 01:10:13,890 --> 01:10:18,230 [Bowden] پس اگر (درخت == NULL)، پس از آن چه؟ 907 01:10:18,230 --> 01:10:22,740 [دانشجو] [بازگشت نادرست است. 908 01:10:22,740 --> 01:10:26,160 [Bowden دیگر، خوب، من دیگری نیاز نیست. 909 01:10:26,160 --> 01:10:30,250 اگر مورد پایه دیگر من بود. 910 01:10:30,250 --> 01:10:32,450 ارزش [دانشجو] درخت؟ >> آره. 911 01:10:32,450 --> 01:10:36,430 بنابراین اگر (درخت> مقدار ==. 912 01:10:36,430 --> 01:10:39,920 توجه داشته باشید که ما در حال بازگشت به * گره، گره ** نیست؟ 913 01:10:39,920 --> 01:10:42,990 حاوی هرگز نیاز به استفاده از یک گره ** 914 01:10:42,990 --> 01:10:45,480 از آنجایی که ما در حال تغییر اشاره گر نیست. 915 01:10:45,480 --> 01:10:50,540 ما فقط آنها را به تراورس. 916 01:10:50,540 --> 01:10:53,830 در صورتی که اتفاق می افتد، پس از آن ما می خواهیم به بازگشت واقعی است. 917 01:10:53,830 --> 01:10:58,270 دیگری که ما می خواهیم به گذشتن از کودکان است. 918 01:10:58,270 --> 01:11:02,620 بنابراین ما نمی توانیم استدلال در مورد اینکه آیا همه چیز را به سمت چپ کمتر است 919 01:11:02,620 --> 01:11:05,390 و همه چیز را به سمت راست بزرگتر است. 920 01:11:05,390 --> 01:11:09,590 پس چه وضعیت ما خواهد بود در اینجا - و یا، چه می خواهیم کاری انجام دهید؟ 921 01:11:09,590 --> 01:11:11,840 [دانشجو، ناخوانا] >> آره. 922 01:11:11,840 --> 01:11:17,400 بازگشت شامل (ارزش، درخت،> سمت چپ) 923 01:11:17,400 --> 01:11:26,860 و یا شامل (ارزش، درخت،> سمت راست). و آن است. 924 01:11:26,860 --> 01:11:29,080 و متوجه است که برخی از ارزیابی اتصال کوتاه وجود دارد، 925 01:11:29,080 --> 01:11:32,520 جایی که اگر ما اتفاق می افتد را به پیدا کردن مقدار در سمت چپ درخت، 926 01:11:32,520 --> 01:11:36,820 ما هرگز نیاز به در درخت سمت راست نگاه کنید. 927 01:11:36,820 --> 01:11:40,430 این تابع کل است. 928 01:11:40,430 --> 01:11:43,690 در حال حاضر این کار را انجام تکرار شونده، 929 01:11:43,690 --> 01:11:48,060 است که به کمتر خوب است. 930 01:11:48,060 --> 01:11:54,750 ما می خواهیم شروع معمول گره * درخت فعلی =. 931 01:11:54,750 --> 01:12:03,250 در حالی که (فعلی = NULL). 932 01:12:03,250 --> 01:12:08,600 به سرعت با رفتن به یک مشکل. 933 01:12:08,600 --> 01:12:12,250 اگر فعلی - در اینجا، اگر ما تا به حال از این، 934 01:12:12,250 --> 01:12:16,020 پس از آن ما را از اداره امور را به نگاهی، به طوری بازگشت کاذب. 935 01:12:16,020 --> 01:12:24,810 اگر (فعلی> مقدار ==) بازگشت، درست است. 936 01:12:24,810 --> 01:12:32,910 بنابراین در حال حاضر، ما در یک محل - 937 01:12:32,910 --> 01:12:36,250 ما نمی دانیم که آیا ما می خواهیم برای رفتن به سمت چپ یا راست. 938 01:12:36,250 --> 01:12:44,590 پس خودسرانه، اجازه دهید فقط به سمت چپ. 939 01:12:44,590 --> 01:12:47,910 من به وضوح به شماره جایی که من همه چیز را به طور کامل رها شده اجرا می شود - 940 01:12:47,910 --> 01:12:50,760 من فقط تا کنون در سمت چپ یک درخت را بررسی کنید. 941 01:12:50,760 --> 01:12:56,050 من به هر چیزی است که فرزند راست هر چیزی را بررسی کنید هرگز. 942 01:12:56,050 --> 01:13:00,910 چگونه می توانم این را حل کنم؟ 943 01:13:00,910 --> 01:13:05,260 [دانشجو] شما را به نگه داشتن مسیر از سمت چپ و راست در پشته. 944 01:13:05,260 --> 01:13:13,710 [Bowden] آره. بنابراین ایجاد آن 945 01:13:13,710 --> 01:13:32,360 ساختار فهرست، گره * N، و سپس گره * بعد؟ 946 01:13:32,360 --> 01:13:40,240 من فکر می کنم که خوب کار می کند. 947 01:13:40,240 --> 01:13:45,940 ما می خواهیم به بیش از چپ، یا let's - تا اینجا. 948 01:13:45,940 --> 01:13:54,350 ساختار لیست = فهرست، آن را شروع 949 01:13:54,350 --> 01:13:58,170 از در این لیست ساختار. 950 01:13:58,170 --> 01:14:04,040 * فهرست = NULL. به طوری که برای رفتن به لیست پیوندی ما 951 01:14:04,040 --> 01:14:08,430 subtrees که ما از آنها صرف بیش از 952 01:14:08,430 --> 01:14:13,800 ما می رویم به تراورس به سمت چپ در حال حاضر، 953 01:14:13,800 --> 01:14:17,870 اما از آنجایی که ما به ناچار نیاز به دوباره به سمت راست، 954 01:14:17,870 --> 01:14:26,140 ما قصد داریم برای حفظ سمت راست در داخل لیست ساختار ما. 955 01:14:26,140 --> 01:14:32,620 سپس خواهیم new_list یا ساختار داشته باشد، 956 01:14:32,620 --> 01:14:41,080 ساختار فهرست *، new_list = malloc (sizeof (فهرست)). 957 01:14:41,080 --> 01:14:44,920 من قصد دارم به چشم پوشی از خطا چک کردن اینکه، اما شما باید چک کردن null در صورتی که آن را برای دیدن. 958 01:14:44,920 --> 01:14:50,540 New_list گره آن را برای رفتن به نقطه را به - 959 01:14:50,540 --> 01:14:56,890 آه، به همین دلیل است که من آن را می خواستم تا در اینجا. رفتن به نقطه را به یک لیست ساختار دوم. 960 01:14:56,890 --> 01:15:02,380 که چقدر مرتبط با کار لیست. 961 01:15:02,380 --> 01:15:04,810 این همان است که در فهرست اعضای هیات تحریریه در ارتباط است 962 01:15:04,810 --> 01:15:06,960 به جز ما فقط به جای بین المللی همراه با گره. 963 01:15:06,960 --> 01:15:11,040 این دقیقا همان است. 964 01:15:11,040 --> 01:15:15,100 بنابراین new_list، به ارزش گره new_list ما، 965 01:15:15,100 --> 01:15:19,120 رفتن به فعلی حق است. 966 01:15:19,120 --> 01:15:24,280 به ارزش ما new_list بعدی> رفتن به فهرست اصلی ما، 967 01:15:24,280 --> 01:15:30,760 و پس از آن ما قصد داریم برای به روز رسانی فهرست ما را به اشاره به new_list. 968 01:15:30,760 --> 01:15:33,650 >> در حال حاضر ما نیاز به نوعی از راه از همه چیز کشیدن، 969 01:15:33,650 --> 01:15:37,020 داریم طی کل زیر درخت سمت چپ است. 970 01:15:37,020 --> 01:15:40,480 در حال حاضر ما نیاز به جلو و مسائل خارج از آن، 971 01:15:40,480 --> 01:15:43,850 مانند فعلی تهی است، ما نمی خواهیم فقط به بازگشت غلط است. 972 01:15:43,850 --> 01:15:50,370 ما می خواهیم به جلو و در حال حاضر در خارج در فهرست جدید ما. 973 01:15:50,370 --> 01:15:53,690 یک راه مناسب برای انجام این کار - خب، در واقع، راه های متعدد برای انجام این کار وجود دارد. 974 01:15:53,690 --> 01:15:56,680 هر کس یک پیشنهاد؟ 975 01:15:56,680 --> 01:15:58,790 که در آن من باید از این و یا چگونه من باید این کار را انجام دهند کاری انجام دهید؟ 976 01:15:58,790 --> 01:16:08,010 ما فقط چند دقیقه، اما هر گونه پیشنهاد؟ 977 01:16:08,010 --> 01:16:14,750 به جای - یکی از راه، به جای آن از وضعیت ما در حالی که، 978 01:16:14,750 --> 01:16:17,090 چیزی است که ما در حال حاضر به دنبال این است تهی نیست، 979 01:16:17,090 --> 01:16:22,340 در عوض ما در حال رفتن به ادامه بروید تا لیست ما به خودی خود پوچ است. 980 01:16:22,340 --> 01:16:25,680 بنابراین اگر لیست ما به پایان می رسد تا اینکه تهی، 981 01:16:25,680 --> 01:16:30,680 پس از آن ما از اداره امور را به دنبال، به جستجوی. 982 01:16:30,680 --> 01:16:39,860 اما این بدان معنی است که اولین چیزی که در فهرست ما فقط رفتن به اولین گره. 983 01:16:39,860 --> 01:16:49,730 اولین چیزی که بسیار خواهد بود - ما دیگر نیازی به دید که. 984 01:16:49,730 --> 01:16:58,710 لیست> N درخت ما خواهد بود. 985 01:16:58,710 --> 01:17:02,860 لیست بعدی> رفتن به تهی. 986 01:17:02,860 --> 01:17:07,580 و حالا در حالی که لیست تهی برابر نیست. 987 01:17:07,580 --> 01:17:11,610 فعلی است که رفتن به جلو و چیزی از لیست ما است. 988 01:17:11,610 --> 01:17:13,500 بنابراین فعلی برابر لیست> N. 989 01:17:13,500 --> 01:17:20,850 و سپس رفتن به برابر لیست> N و یا لیست بعدی>. 990 01:17:20,850 --> 01:17:23,480 بنابراین اگر ارزش فعلی برابر است با ارزش. 991 01:17:23,480 --> 01:17:28,790 در حال حاضر ما می توانیم هر دو اشاره گر حق ما و اشاره گر چپ ما اضافه کنید 992 01:17:28,790 --> 01:17:32,900 تا زمانی که آنها تهی نیست. 993 01:17:32,900 --> 01:17:36,390 را در اینجا، من حدس می زنم که ما باید انجام داده اند که در وهله اول. 994 01:17:36,390 --> 01:17:44,080 اگر (فعلی> حق! = NULL) 995 01:17:44,080 --> 01:17:56,380 پس از آن ما در حال رفتن به درج این گره را به لیست ما است. 996 01:17:56,380 --> 01:17:59,290 اگر (فعلی سمت چپ)، این است که یک کمی کار اضافی است، اما آن را خوب است. 997 01:17:59,290 --> 01:18:02,690 اگر (فعلی سمت چپ = NULL)، 998 01:18:02,690 --> 01:18:14,310 و ما در حال رفتن به سمت چپ به ما لیست پیوندی درج، 999 01:18:14,310 --> 01:18:19,700 و است که باید آن است. 1000 01:18:19,700 --> 01:18:22,670 ما تکرار - تا زمانی که ما چیزی در لیست ما، 1001 01:18:22,670 --> 01:18:26,640 ما باید یکی دیگر از گره به نگاه در. 1002 01:18:26,640 --> 01:18:28,920 بنابراین ما نگاه کنید که در آن گره، 1003 01:18:28,920 --> 01:18:31,390 لیست ما پیشرفت ما را به یکی بعدی. 1004 01:18:31,390 --> 01:18:34,060 در صورتی که گره ارزش است که ما به دنبال آن هستید، ما می توانیم بازگشت درست است. 1005 01:18:34,060 --> 01:18:37,640 دیگری هر دو سمت چپ و راست ما subtrees درج، 1006 01:18:37,640 --> 01:18:40,510 تا زمانی که آنها تهی نیست، به لیست ما 1007 01:18:40,510 --> 01:18:43,120 به طوری که ما به ناچار بر آنها بروید. 1008 01:18:43,120 --> 01:18:45,160 بنابراین اگر آنها تهی نیست، 1009 01:18:45,160 --> 01:18:47,950 اگر اشاره گر ریشه ما با اشاره به دو چیز، 1010 01:18:47,950 --> 01:18:51,670 پس از آن در ابتدا ما کشیده چیزی از لیست ما به پایان می رسد تا اینکه تهی است. 1011 01:18:51,670 --> 01:18:56,890 ما را دو چیز را پشت در، به طوری که در حال حاضر لیست ما است از اندازه 2. 1012 01:18:56,890 --> 01:19:00,030 آنگاه ما در حال رفتن به حلقه به بالا و ما فقط رفتن به جلو، 1013 01:19:00,030 --> 01:19:04,250 بیایید می گویند، اشاره گر چپ گره ریشه ما. 1014 01:19:04,250 --> 01:19:07,730 و این فقط اتفاق می افتد نگه دارید، ما را به پایان خواهم حلقه بیش از همه چیز. 1015 01:19:07,730 --> 01:19:11,280 >> توجه داشته باشید که این به طور قابل توجهی پیچیده تر بود 1016 01:19:11,280 --> 01:19:14,160 در راه حل بازگشتی. 1017 01:19:14,160 --> 01:19:17,260 و من چند بار گفته ام 1018 01:19:17,260 --> 01:19:25,120 که راه حل بازگشتی معمولا دارای نقاط مشترک زیادی با تکرار راه حل است. 1019 01:19:25,120 --> 01:19:30,820 در اینجا این است که دقیقا همان چیزی است که راه حل بازگشتی در حال انجام است. 1020 01:19:30,820 --> 01:19:36,740 تنها تغییر این است که به جای به طور ضمنی با استفاده از پشته، پشته برنامه، 1021 01:19:36,740 --> 01:19:40,840 به عنوان راه خود را از پیگیری از گره شما هنوز هم نیاز به بازدید، 1022 01:19:40,840 --> 01:19:45,430 در حال حاضر شما به صراحت با استفاده از لیست پیوندی. 1023 01:19:45,430 --> 01:19:49,070 در هر دو مورد شما پیگیری از چه گره هنوز هم نیاز به بازدید. 1024 01:19:49,070 --> 01:19:51,790 در صورت بازگشتی آن فقط ساده تر چون پشته 1025 01:19:51,790 --> 01:19:57,100 برای شما به عنوان پشته برنامه اجرا شده است. 1026 01:19:57,100 --> 01:19:59,550 توجه کنید که این لیست در ارتباط، آن است که یک پشته. 1027 01:19:59,550 --> 01:20:01,580 هر چه ما فقط در پشته قرار داده است 1028 01:20:01,580 --> 01:20:09,960 است، بلافاصله آنچه که ما در حال رفتن به جلو و پشته به دیدار بعدی. 1029 01:20:09,960 --> 01:20:14,380 ما از زمان است، اما هر گونه سؤال؟ 1030 01:20:14,380 --> 01:20:23,530 [دانشجو، ناخوانا] 1031 01:20:23,530 --> 01:20:27,790 [Bowden] آره. بنابراین اگر ما لیست پیوندی ما 1032 01:20:27,790 --> 01:20:30,150 در حال حاضر در حال رفتن به نقطه را به این پسر، 1033 01:20:30,150 --> 01:20:34,690 و در حال حاضر ما فقط لیست پیوندی ما به تمرکز بر روی این پسر. 1034 01:20:34,690 --> 01:20:44,200 ما در حال عبور بر روی لیست پیوندی که در خط است. 1035 01:20:44,200 --> 01:20:51,200 و پس از آن من حدس می زنم که ما باید به لیست پیوندی و چیزهای رایگان 1036 01:20:51,200 --> 01:20:53,880 یک بار قبل از بازگشت به درست یا غلط، ما نیاز به 1037 01:20:53,880 --> 01:20:57,360 تکرار بیش از ما لیست پیوندی و همیشه در اینجا، من حدس می زنم، 1038 01:20:57,360 --> 01:21:03,900 اگر ما فعلی برابر است، آن را اضافه کنید، بنابراین در حال حاضر ما می خواهیم آزاد 1039 01:21:03,900 --> 01:21:09,600 فعلی است، زیرا به خوبی، اما ما به طور کامل در مورد این لیست را فراموش کرده ام؟ آره. 1040 01:21:09,600 --> 01:21:12,880 به طوری که این چیزی است که ما می خواهیم به انجام می باشد. 1041 01:21:12,880 --> 01:21:16,730 اشاره گر کجاست؟ 1042 01:21:16,730 --> 01:21:23,320 فعلی بود و سپس - ما می خواهیم به ساختار * 10 برابر است لیست بعدی. 1043 01:21:23,320 --> 01:21:29,240 رایگان فهرست، فهرست = دمای 1044 01:21:29,240 --> 01:21:32,820 و در مورد که در آن ما به راست، ما نیازی به تکرار 1045 01:21:32,820 --> 01:21:37,050 بیش از باقی مانده از لیست پیوندی ما آزاد همه چیز است. 1046 01:21:37,050 --> 01:21:39,700 چیز خوب در مورد راه حل بازگشتی آزاد همه چیز 1047 01:21:39,700 --> 01:21:44,930 فقط بدان معناست factorings ظاهر کردن پشته که برای شما اتفاق می افتد. 1048 01:21:44,930 --> 01:21:50,720 بنابراین ما از چیزی است که مانند 3 خط سخت به فکر می کنم در مورد کد رفته 1049 01:21:50,720 --> 01:21:57,520 به چیزی است که به طور معنی داری بیشتر بسیاری از سخت به فکر می کنم در مورد خط کد است. 1050 01:21:57,520 --> 01:22:00,620 هر گونه سؤال؟ 1051 01:22:00,620 --> 01:22:08,760 بسیار خوب. ما خوب است. خداحافظ! 1052 01:22:08,760 --> 01:22:11,760 [CS50.TV]