در این مطلب، ویدئو درختان باینری در پایتون: مقدمه و الگوریتمهای پیمایش با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,030 –> 00:00:02,070
بسیار خوب، بنابراین در این ویدیو ما به بررسی
2
00:00:02,070 –> 00:00:04,019
درخت های باینری می پردازیم، بنابراین
3
00:00:04,019 –> 00:00:05,730
به طور خلاصه
4
00:00:05,730 –> 00:00:07,140
ساختار داده های درخت باینری و نحوه تعریف
5
00:00:07,140 –> 00:00:08,910
آن را پوشش می دهیم و سپس
6
00:00:08,910 –> 00:00:10,620
پیاده سازی یک درخت باینری را در
7
00:00:10,620 –> 00:00:13,740
بنابراین برای تعریف پایتون، درخت
8
00:00:13,740 –> 00:00:15,420
باینری یک ساختار داده درختی است که در آن هر
9
00:00:15,420 –> 00:00:17,699
گره حداکثر دو فرزند دارد که
10
00:00:17,699 –> 00:00:19,439
به عنوان فرزند چپ و فرزند راست نامیده می شوند،
11
00:00:19,439 –> 00:00:22,260
بنابراین در اینجا یک تصویر مثال از یک
12
00:00:22,260 –> 00:00:24,420
درخت باینری و هر یک از این دایره ها
13
00:00:24,420 –> 00:00:26,699
در اینجا این موارد هستند. ما گره های درخت را فراخوانی می کنیم
14
00:00:26,699 –> 00:00:28,740
، بنابراین درست مانند یک لیست پیوندی،
15
00:00:28,740 –> 00:00:31,199
ما گره های یک لیست پیوندی را داشتیم که
16
00:00:31,199 –> 00:00:33,690
نوعی داده را ذخیره می کرد، بنابراین این می تواند یک
17
00:00:33,690 –> 00:00:35,070
عدد صحیح باشد، می تواند یک رشته باشد
18
00:00:35,070 –> 00:00:36,780
، در این مورد می تواند یک اشاره گر به ساختار داده
19
00:00:36,780 –> 00:00:39,300
دیگری باشد. این گره ها حاوی اعداد صحیح هستند
20
00:00:39,300 –> 00:00:42,000
بنابراین بر خلاف لیست های پیوندی که گره
21
00:00:42,000 –> 00:00:44,010
به گره بعدی در لیست اشاره می کند، یک
22
00:00:44,010 –> 00:00:47,579
درخت باینری دارای دو اشاره گر است که
23
00:00:47,579 –> 00:00:50,489
به فرزندان خود اشاره می کند، بنابراین هر گره در این
24
00:00:50,489 –> 00:00:52,379
درخت آن را در اکثر دو فرزند خواهد داشت
25
00:00:52,379 –> 00:00:55,440
و این باعث عبور از چنین داده هایی می شود.
26
00:00:55,440 –> 00:00:57,030
ساختار جالب و کمی
27
00:00:57,030 –> 00:00:59,730
متنوعتر از لیست پیوندی شماست
28
00:00:59,730 –> 00:01:01,050
و ما بعداً در این
29
00:01:01,050 –> 00:01:03,690
ویدیو به آن خواهیم رسید، بنابراین کمی اصطلاحات بیشتر در مورد
30
00:01:03,690 –> 00:01:06,240
درخت دودویی، در اینجا به این گره بالا
31
00:01:06,240 –> 00:01:08,490
به عنوان ریشه اشاره میکنیم، بنابراین در این مورد به
32
00:01:08,490 –> 00:01:10,470
گره اشاره میکنیم. که حاوی عنصر 2 است،
33
00:01:10,470 –> 00:01:12,420
این ریشه درخت است و سپس
34
00:01:12,420 –> 00:01:14,640
فرزندان چپ و راست این گره ریشه،
35
00:01:14,640 –> 00:01:16,259
گره های حاوی 7 و 5
36
00:01:16,259 –> 00:01:18,150
هستند، بنابراین آنها فرزندان چپ و
37
00:01:18,150 –> 00:01:21,240
راست 2 هستند، بنابراین اگر
38
00:01:21,240 –> 00:01:23,220
این گره را در اینجا در نظر بگیریم، این گره است. که شامل یک
39
00:01:23,220 –> 00:01:26,009
7 است، همچنین حداکثر 2 فرزند دارد، بنابراین
40
00:01:26,009 –> 00:01:27,360
فرزندان چپ و راست گره های
41
00:01:27,360 –> 00:01:30,270
حاوی 2 و 6 هستند و می گوییم که 7
42
00:01:30,270 –> 00:01:33,030
یک گره والد است نسبت به 2 و 6 بنابراین
43
00:01:33,030 –> 00:01:35,490
7 این گره در اینجا حاوی 7
44
00:01:35,490 –> 00:01:37,680
والد است. گره های حاوی 2 و 6
45
00:01:37,680 –> 00:01:40,290
و همینطور این گره در اینجا حاوی
46
00:01:40,290 –> 00:01:44,070
2 والد 7 و 5 است، بنابراین وقتی
47
00:01:44,070 –> 00:01:45,899
از درخت بالا می رویم،
48
00:01:45,899 –> 00:01:48,119
اگر دوست دارید از نوع شجره نامه بالا می رویم – اینجا
49
00:01:48,119 –> 00:01:51,420
نوه 2 است پس 2 مهربان است. از
50
00:01:51,420 –> 00:01:54,030
پدربزرگ و مادربزرگ و پدربزرگ و فرزند و شما
51
00:01:54,030 –> 00:01:55,680
می توانید goi نگه دارید از بالای درخت، ما فقط
52
00:01:55,680 –> 00:02:01,439
به 2 به عنوان اجداد 2 در اینجا اشاره می کنیم،
53
00:02:01,439 –> 00:02:03,630
بنابراین چند قطعه دیگر از اصطلاحات در اینجا
54
00:02:03,630 –> 00:02:06,060
به گره های
55
00:02:06,060 –> 00:02:08,340
انتهای درخت به عنوان برگ اشاره می کنیم، بنابراین ریشه در اینجا بالا
56
00:02:08,340 –> 00:02:10,050
است و برگ ها خیلی پایین
57
00:02:10,050 –> 00:02:12,870
میتوانیم به عمق درخت اشاره کنیم، بنابراین
58
00:02:12,870 –> 00:02:13,590
اگر
59
00:02:13,590 –> 00:02:16,319
از بالا در اینجا از ریشه شروع کنیم و به
60
00:02:16,319 –> 00:02:18,209
پایینروی ادامه دهیم،
61
00:02:18,209 –> 00:02:20,069
تعداد سطوحی را که به سمت پایین طی کردهایم محاسبه میکنیم
62
00:02:20,069 –> 00:02:22,410
، برای مثال این ریشه در اینجا
63
00:02:22,410 –> 00:02:24,720
در سطح فرض کنید میتوانید از صفر
64
00:02:24,720 –> 00:02:27,450
یا یک شروع کنید و سپس وقتی پایین میروید، این
65
00:02:27,450 –> 00:02:29,160
گرهها در اینجا در سطوح بعدی
66
00:02:29,160 –> 00:02:31,950
هستند، مثلاً در سطح یک دو هستند و
67
00:02:31,950 –> 00:02:34,650
سپس هرچه بیشتر پایین میرویم، این گرهها 2
68
00:02:34,650 –> 00:02:36,599
6 و 9 سطح بعدی هستند. بنابراین
69
00:02:36,599 –> 00:02:39,330
آنها در عمق 3 هستند و سپس این گره ها
70
00:02:39,330 –> 00:02:41,970
در اینجا این برگ ها عمق 4 هستند بنابراین 1
71
00:02:41,970 –> 00:02:43,620
2 3 4
72
00:02:43,620 –> 00:02:46,650
عمق 4 از پایین به بالا می شمارند
73
00:02:46,650 –> 00:02:48,840
و این به ما ارتفاع می دهد بنابراین
74
00:02:48,840 –> 00:02:51,180
اگر برگ ها در سطح پایینی باشند.
75
00:02:51,180 –> 00:02:54,000
فرض کنید سطح ارتفاع 1 باشد، سپس میتوانیم به
76
00:02:54,000 –> 00:02:55,950
سطح بعدی برویم، این گرهها
77
00:02:55,950 –> 00:02:59,040
در سطح 2 سطح 3 و سپس l هستند. evel 4 بنابراین
78
00:02:59,040 –> 00:03:02,430
این درخت دارای ارتفاع 4 است بنابراین
79
00:03:02,430 –> 00:03:04,470
انواع مختلفی از درختان باینری وجود دارد و این
80
00:03:04,470 –> 00:03:07,379
لیست کامل نیست. تعداد زیادی
81
00:03:07,379 –> 00:03:09,030
از انواع درخت های باینری وجود دارد که می توانید در
82
00:03:09,030 –> 00:03:10,860
نظر بگیرید، اما ما می توانیم دو مورد را در نظر بگیریم
83
00:03:10,860 –> 00:03:12,209
که ما فقط در این
84
00:03:12,209 –> 00:03:14,910
اسلاید به آنها اشاره می کنیم. یک درخت باینری کامل، بنابراین
85
00:03:14,910 –> 00:03:16,440
این مثالی از یک درخت باینری کامل است
86
00:03:16,440 –> 00:03:19,019
و یک درخت باینری کامل، درختی است که در آن
87
00:03:19,019 –> 00:03:21,720
هر سطح به جز احتمالاً آخرین سطح، به
88
00:03:21,720 –> 00:03:23,340
طور کامل پر شده است، تمام گرهها در
89
00:03:23,340 –> 00:03:25,350
آخرین سطح تا حد امکان در سمت چپ هستند،
90
00:03:25,350 –> 00:03:27,959
بنابراین این سطح کاملاً پر است. شما
91
00:03:27,959 –> 00:03:30,060
فقط می توانید یک گره در اینجا داشته باشید این سطح
92
00:03:30,060 –> 00:03:32,220
کاملاً پر است.
93
00:03:32,220 –> 00:03:34,079
94
00:03:34,079 –> 00:03:35,910
95
00:03:35,910 –> 00:03:37,739
96
00:03:37,739 –> 00:03:39,239
97
00:03:39,239 –> 00:03:42,540
کامل است بنابراین در اینجا
98
00:03:42,540 –> 00:03:44,549
در تعریف داریم که احتمالاً آخرین
99
00:03:44,549 –> 00:03:46,859
سطح به طور کامل پر نشده است و همچنین
100
00:03:46,859 –> 00:03:48,720
گره های آخرین سطح برگ ها
101
00:03:48,720 –> 00:03:51,269
به سمت چپ فشار داده می شوند بنابراین این گره
102
00:03:51,269 –> 00:03:53,340
تا جایی که می توانید به سمت چپ بروید بنابراین در o
103
00:03:53,340 –> 00:03:54,840
برای این که
104
00:03:54,840 –> 00:03:56,849
خاصیت یک درخت باینری کامل بودن را حفظ
105
00:03:56,849 –> 00:03:58,109
کنیم، گره بعدی که درج می کنیم
106
00:03:58,109 –> 00:04:00,870
باید فرزند مناسب این گره 4 و
107
00:04:00,870 –> 00:04:03,870
غیره و غیره باشد، بنابراین
108
00:04:03,870 –> 00:04:05,940
گاهی اوقات به یک درخت باینری کامل به عنوان یک درخت باینری یا مناسب گفته می شود.
109
00:04:05,940 –> 00:04:08,130
درخت دودویی ساده و این درختی است که در آن
110
00:04:08,130 –> 00:04:10,889
هر گره منفرد 0 یا 2
111
00:04:10,889 –> 00:04:12,989
فرزند دارد، بنابراین هر گره در درخت دارای 2
112
00:04:12,989 –> 00:04:14,400
فرزند است به جز برگ هایی
113
00:04:14,400 –> 00:04:16,918
که 0 فرزند دارند، بنابراین این درخت پر است
114
00:04:16,918 –> 00:04:19,858
هر یک مانند یک فاصله در این
115
00:04:19,858 –> 00:04:21,810
درخت گرفته می شود. مزیت این است که این یک
116
00:04:21,810 –> 00:04:24,960
درخت باینری کامل است، بنابراین
117
00:04:24,960 –> 00:04:26,789
اصطلاحات و اطلاعات کافی برای
118
00:04:26,789 –> 00:04:27,300
شروع
119
00:04:27,300 –> 00:04:29,370
تعریف ساختار داده یک
120
00:04:29,370 –> 00:04:30,930
درخت باینری داریم و ما شاهد همپوشانی های زیادی
121
00:04:30,930 –> 00:04:33,120
با آنچه دیدیم، ساختار داده یک درخت را تعریف می کنیم.
122
00:04:33,120 –> 00:04:35,580
لیست پیوندی، بنابراین
123
00:04:35,580 –> 00:04:37,889
توصیه میکنم اگر
124
00:04:37,889 –> 00:04:39,659
آن سری را بررسی نکردهاید یا اگر باید
125
00:04:39,659 –> 00:04:41,879
فهرستهای پیوندی را بررسی کنید، بهخصوص نحوه
126
00:04:41,879 –> 00:04:43,800
تعریف آنها، اجازه دهید در پایتون بگوییم
127
00:04:43,800 –> 00:04:45,090
که چگونه میخواهیم آن را
128
00:04:45,090 –> 00:04:47,250
گسترش دهیم. شما را تشویق می کرد برای
129
00:04:47,250 –> 00:04:49,050
رفتن به آن سری از ویدیوها و بررسی آن
130
00:04:49,050 –> 00:04:50,550
ممکن است اولین دو ویدیو
131
00:04:50,550 –> 00:04:52,710
فقط برای فهمیدن اینکه چگونه می
132
00:04:52,710 –> 00:04:54,810
توان چنین ساختار داده ای را تعریف کرد و هنگامی
133
00:04:54,810 –> 00:04:56,099
که با آن احساس راحتی کردید
134
00:04:56,099 –> 00:04:57,659
به ترمینال می رویم و شروع می کنیم برای
135
00:04:57,659 –> 00:05:01,560
تعریف یک درخت باینری خوب است، بنابراین اجازه دهید
136
00:05:01,560 –> 00:05:04,139
پیش برویم و ساختار داده درختی باینری خود را کدنویسی کنیم
137
00:05:04,139 –> 00:05:05,669
تا این کار را انجام دهیم،
138
00:05:05,669 –> 00:05:08,099
ابتدا یک کلاس گره تعریف می کنیم، بنابراین این
139
00:05:08,099 –> 00:05:09,360
کار واقعاً شبیه کاری است که
140
00:05:09,360 –> 00:05:11,430
در هنگام تعریف داده های لیست پیوندی انجام دادیم.
141
00:05:11,430 –> 00:05:13,110
ساختاری که در آن یک کلاس گره
142
00:05:13,110 –> 00:05:15,810
نیز برای گرههای موجود در لیست پیوندی
143
00:05:15,810 –> 00:05:18,389
داشتیم، بنابراین میگوییم گره کلاس و سپس بیایید
144
00:05:18,389 –> 00:05:19,800
پیش برویم و سازنده را برای این کلاس تعریف کنیم،
145
00:05:19,800 –> 00:05:22,550
بنابراین در آن میگوییم def و
146
00:05:22,550 –> 00:05:25,080
درست مانند سازنده
147
00:05:25,080 –> 00:05:27,270
کلاس know برای یک لیست پیوندی،
148
00:05:27,270 –> 00:05:28,979
خود را به عنوان عضوی از این
149
00:05:28,979 –> 00:05:31,560
کلاس و همچنین مقدار می گیرد، بنابراین این
150
00:05:31,560 –> 00:05:33,330
نوع مقداری است که ما می خواهیم در این
151
00:05:33,330 –> 00:05:35,580
گره خاص ذخیره کنیم، بنابراین مقدار متغیر کلاس
152
00:05:35,580 –> 00:05:37,830
را برابر با آنچه ارسال شده است تنظیم می کنیم. در
153
00:05:37,830 –> 00:05:40,560
اینجا و سپس بر خلاف لیست پیوندی که در آن
154
00:05:40,560 –> 00:05:43,080
w e متغییر کلاس مجموعه بعدی
155
00:05:43,080 –> 00:05:46,080
برابر با none داشت، چپ
156
00:05:46,080 –> 00:05:48,840
و راست برابر با هیچی خواهیم داشت،
157
00:05:48,840 –> 00:05:50,909
پس این نشانگر بود که به
158
00:05:50,909 –> 00:05:53,219
گره بعدی در لیست پیوند داده شده اشاره می کند، در اینجا
159
00:05:53,219 –> 00:05:55,229
دو عدد دیگر را خواهیم داشت. نشانگرهای چپ
160
00:05:55,229 –> 00:05:56,520
و راست که قرار است به
161
00:05:56,520 –> 00:05:58,650
ترتیب به فرزندان چپ و راست گره داده شده اشاره
162
00:05:58,650 –> 00:06:00,270
کنند، بنابراین می گوییم خود نقطه
163
00:06:00,270 –> 00:06:03,419
چپ در ابتدا برابر است با هیچ و سپس
164
00:06:03,419 –> 00:06:06,180
خود نقطه سمت راست برابر با هیچ است
165
00:06:06,180 –> 00:06:07,529
بسیار شبیه به آنچه در آن مشاهده کردیم.
166
00:06:07,529 –> 00:06:09,029
کلاس لیست پیوندی به استثنای
167
00:06:09,029 –> 00:06:11,610
آن دو متغیر آخر، بیایید به جلو برویم
168
00:06:11,610 –> 00:06:14,789
و کلاس درختی باینری خود را تعریف کنیم، بنابراین در اینجا
169
00:06:14,789 –> 00:06:15,930
کاری که میخواهیم انجام دهیم این است که
170
00:06:15,930 –> 00:06:18,659
سازنده خود را نیز تعریف کنیم تا
171
00:06:18,659 –> 00:06:20,550
خود به خود بگیرد اگر عضوی از آن است. کلاس و
172
00:06:20,550 –> 00:06:22,830
همچنین root به عنوان آن درخت را تعریف می کند،
173
00:06:22,830 –> 00:06:25,800
بنابراین می گوییم ریشه self dot برابر
174
00:06:25,800 –> 00:06:28,289
با یک گره ریشه خواهد بود، بنابراین کاری که من در اینجا انجام می دهم این
175
00:06:28,289 –> 00:06:30,629
است که فرض می کنم مقداری مانند
176
00:06:30,629 –> 00:06:32,789
رشته یا یک عدد صحیح خواهد بود.
177
00:06:32,789 –> 00:06:34,919
برای تعریف درخت باینری ارسال می شود و سپس
178
00:06:34,919 –> 00:06:36,089
کاری که من انجام می دهم این است که تنظیم می کنم متغیر کلاس
179
00:06:36,089 –> 00:06:38,880
ریشه self dot برابر با یک گره
180
00:06:38,880 –> 00:06:41,040
از آن است، بنابراین ما در حال تبدیل اطلاعاتی هستیم که
181
00:06:41,040 –> 00:06:43,770
در آن داده می شود،
182
00:06:43,770 –> 00:06:45,420
آن را به یک گره ذخیره می کنیم و آن را
183
00:06:45,420 –> 00:06:48,390
به عنوان ریشه درخت خود در اینجا تنظیم می کنیم، بنابراین این
184
00:06:48,390 –> 00:06:50,520
تقریباً تمام چیزی است که ما انجام می دهیم. باید شروع
185
00:06:50,520 –> 00:06:51,930
کنیم، در واقع میتوانیم این درخت را پر کنیم
186
00:06:51,930 –> 00:06:53,220
، اگرچه
187
00:06:53,220 –> 00:06:55,500
در حال حاضر نمیتوانیم چیزی را چاپ کنیم، بنابراین میتوانیم بگوییم
188
00:06:55,500 –> 00:07:00,600
ریشه نقطه درخت برابر است با فرض کنید یا
189
00:07:00,600 –> 00:07:01,620
در واقع ابتدا باید یک
190
00:07:01,620 –> 00:07:03,720
اشیاء درختی باینری را تعریف کنیم. می گوییم بیایید بگوییم
191
00:07:03,720 –> 00:07:06,390
درخت دودویی یا حتی
192
00:07:06,390 –> 00:07:08,460
در اینجا کمی مختصرتر می شود، می گوییم درخت برابر است با
193
00:07:08,460 –> 00:07:12,240
درخت دودویی و در این استدلال
194
00:07:12,240 –> 00:07:14,640
می خواهیم مقدار
195
00:07:14,640 –> 00:07:16,440
اولیه ریشه را وارد کنیم، بنابراین ما قرار خواهیم داد ادامه دهید
196
00:07:16,440 –> 00:07:18,870
و یکی را در آنجا قرار دهید تا اکنون یک شی درخت داشته باشیم
197
00:07:18,870 –> 00:07:20,460
و کاری که میتوانیم انجام دهیم این است که میتوانیم
198
00:07:20,460 –> 00:07:23,850
گرههای
199
00:07:23,850 –> 00:07:25,170
فرزندان چپ و راست این ریشه خاص را پر کنیم
200
00:07:25,170 –> 00:07:26,700
تا کاری که میتوانیم انجام دهیم این است که
201
00:07:26,700 –> 00:07:30,390
بگوییم ریشه نقطه درخت سمت چپ برابر است با
202
00:07:30,390 –> 00:07:32,790
گره دو، بنابراین کاری که قرار است انجام دهد
203
00:07:32,790 –> 00:07:34,410
این است که ما شروع خواهیم کرد w
204
00:07:34,410 –> 00:07:37,170
در اینجا یک گره ریشه است، بنابراین یکی
205
00:07:37,170 –> 00:07:39,060
ریشه درخت است و سپس کاری که ما انجام می دهیم این است
206
00:07:39,060 –> 00:07:42,030
که ایجاد می کنیم، بیایید ببینیم
207
00:07:42,030 –> 00:07:43,890
آیا می توانم اسلش درست را بدست بیاورم، بنابراین
208
00:07:43,890 –> 00:07:46,140
یک فرزند چپ از این گره ریشه ایجاد می کنیم.
209
00:07:46,140 –> 00:07:47,550
و ما مقدار آن را
210
00:07:47,550 –> 00:07:49,860
برابر با دو می فرستیم تا بتوانیم
211
00:07:49,860 –> 00:07:51,660
فرزند سمت راست گره ریشه ایجاد کنیم و می توانیم
212
00:07:51,660 –> 00:07:54,150
بگوییم نقطه رایگان ریشه نقطه راست برابر با
213
00:07:54,150 –> 00:07:56,550
گره است.
214
00:07:56,550 –> 00:07:59,280
بنابراین در اینجا کاری که
215
00:07:59,280 –> 00:08:00,510
میتوانیم انجام دهیم این است که
216
00:08:00,510 –> 00:08:02,040
فرزند مناسب را برای این چیز
217
00:08:02,040 –> 00:08:04,830
تعریف کنیم، آن را برابر با مقدار سه قرار
218
00:08:04,830 –> 00:08:06,150
میدهیم و میتوانیم ادامه دهیم تا بتوانیم بگوییم
219
00:08:06,150 –> 00:08:10,260
ریشه درخت نقطه چپ نقطه چپ برابر است با گره
220
00:08:10,260 –> 00:08:12,030
بیایید بگوییم اگر بنابراین، کاری که قرار است
221
00:08:12,030 –> 00:08:13,620
انجام دهد این است که تعریف کند، بیایید
222
00:08:13,620 –> 00:08:17,400
فضای بیشتری در اینجا داشته باشیم، این را به
223
00:08:17,400 –> 00:08:20,640
اینجا منتقل کنیم، کمی فضای بیشتری را به
224
00:08:20,640 –> 00:08:25,320
آنجا منتقل کنیم، بنابراین بیایید ببینیم بیایید
225
00:08:25,320 –> 00:08:27,150
اینها را به طور مناسب از هم جدا کنیم تا دو
226
00:08:27,150 –> 00:08:29,340
فرزند فرزند باقی بماند. ریشه یک و سپس دو
227
00:08:29,340 –> 00:08:31,680
قرار است حالا بچه دار شوند، بنابراین دو
228
00:08:31,680 –> 00:08:35,840
نفر بچه دار می شوند یک بچه چپ
229
00:08:36,840 –> 00:08:41,909
بیایید اینجا را ببینیم این را به اینجا منتقل
230
00:08:41,909 –> 00:08:44,510
کنید تا یک فرزند چپ چهار ساله داشته باشیم و
231
00:08:44,510 –> 00:08:47,550
سپس میتوانیم تعریف کنیم مثلاً
232
00:08:47,550 –> 00:08:50,310
نقطه درخت ریشه نقطه چپ نقطه راست برابر است با
233
00:08:50,310 –> 00:08:52,529
هیچ دو پنج، بنابراین کاری که من اینجا انجام میدهم این است
234
00:08:52,529 –> 00:08:55,770
که میگویم آن نقطه درختی نقطه ریشه سمت چپ
235
00:08:55,770 –> 00:08:58,260
پس اینجا ما اینجا هستیم نقطه سمت راست پس
236
00:08:58,260 –> 00:09:01,529
سمت راست گره سمت راست دو خواهد بود بنابراین می
237
00:09:01,529 –> 00:09:05,339
توانیم آن را برابر با مقدار پنج قرار دهیم مانند
238
00:09:05,339 –> 00:09:07,710
آن و می توانیم به این ترتیب ادامه دهیم بنابراین
239
00:09:07,710 –> 00:09:10,770
اگر می خواهیم گره ها را در یک درخت وارد کنیم به
240
00:09:10,770 –> 00:09:12,210
این ترتیب، این چیزی است که این
241
00:09:12,210 –> 00:09:14,130
درخت خاص در
242
00:09:14,130 –> 00:09:16,890
این مورد به نظر می رسد، بنابراین ما می توانیم جلوتر برویم و
243
00:09:16,890 –> 00:09:18,900
این را کمی بیشتر پر کنیم، بنابراین من
244
00:09:18,900 –> 00:09:20,910
جلوتر رفتم و درخت را پر کردم تا
245
00:09:20,910 –> 00:09:22,710
کمی کامل تر شود. در اینجا دو
246
00:09:22,710 –> 00:09:26,070
گره دیگر از این گره را دقیقاً در اینجا
247
00:09:26,070 –> 00:09:27,930
اضافه میکنم، بنابراین من یک فرزند چپ و فرزند راست را
248
00:09:27,930 –> 00:09:30,120
برای این گره در اینجا اضافه کردهام، بنابراین فقط
249
00:09:30,120 –> 00:09:31,740
درخت را کمی بیشتر پر میکنم که لازم نیست، اما
250
00:09:31,740 –> 00:09:33,570
دادههای کمی بیشتر برای بازی
251
00:09:33,570 –> 00:09:35,460
در اختیار ما قرار میدهد. کاری که میخواهیم انجام دهیم این است که
252
00:09:35,460 –> 00:09:37,170
میخواهیم راهی پیدا کنیم تا واقعاً
253
00:09:37,170 –> 00:09:38,910
از درخت عبور کنیم و به طریقی از آن عبور کنیم
254
00:09:38,910 –> 00:09:39,240
255
00:09:39,240 –> 00:09:40,920
در واقع عناصر
256
00:09:40,920 –> 00:09:42,960
ذخیره شده در گره های مربوطه را چاپ کنید،
257
00:09:42,960 –> 00:09:44,880
بنابراین برای یک لیست پیوندی به یاد داشته باشید
258
00:09:44,880 –> 00:09:46,440
که تقریبا یک راه برای عبور از آن
259
00:09:46,440 –> 00:09:48,450
وجود داشت، یک راه خطی بود که ما
260
00:09:48,450 –> 00:09:50,220
از جلوی لیست شروع کردیم و
261
00:09:50,220 –> 00:09:51,630
سپس گاهی اوقات به تدریج در
262
00:09:51,630 –> 00:09:52,980
لیست حرکت می کردیم. شما ممکن است با دو نشانگر کار جالبی انجام دهید که
263
00:09:52,980 –> 00:09:55,080
در آن
264
00:09:55,080 –> 00:09:56,790
یک اشاره گر دارید که
265
00:09:56,790 –> 00:09:58,530
چند گره جلوتر از نشانگر اول می رود و
266
00:09:58,530 –> 00:10:00,210
سپس با استفاده از دو نشانگر از آن عبور می کنید،
267
00:10:00,210 –> 00:10:02,220
اما همچنان لیست را
268
00:10:02,220 –> 00:10:05,640
به صورت خطی طی می کنید، بنابراین در اینجا با یک درخت
269
00:10:05,640 –> 00:10:06,810
از آنجایی که ما نوع متفاوتی از
270
00:10:06,810 –> 00:10:08,430
ساختار داریم، در مورد
271
00:10:08,430 –> 00:10:10,230
انواع مختلف راههایی که میتوان از
272
00:10:10,230 –> 00:10:12,089
درخت عبور کرد فکر میکنیم و به
273
00:10:12,089 –> 00:10:14,640
نوعی ابتداییترین راههایی را بررسی میکنیم که از طریق
274
00:10:14,640 –> 00:10:17,220
آنها میتوان ابتدا تمرکز کرد. در چیزی
275
00:10:17,220 –> 00:10:19,110
به نام جستجوی ابتدا در عمق و
276
00:10:19,110 –> 00:10:20,339
سه طعم مختلف برای
277
00:10:20,339 –> 00:10:22,620
پوشش وجود دارد که عبارتند از سفارش پیشسفارش
278
00:10:22,620 –> 00:10:24,839
و پیمایش پس از سفارش، بنابراین ما آنها را
279
00:10:24,839 –> 00:10:26,550
پوشش میدهیم و سپس خواهیم دید که
280
00:10:26,550 –> 00:10:27,990
چگونه میتوانیم آن را اعمال کنیم. هر یک از آن
281
00:10:27,990 –> 00:10:30,570
پیمایش ها را در پایتون قرار دهید و اگر
282
00:10:30,570 –> 00:10:33,029
یک روش بازگشتی برای تعریف هر یک از
283
00:10:33,029 –> 00:10:35,459
آن پیمایش ها در نظر بگیریم، پس از تعریف
284
00:10:35,459 –> 00:10:36,930
یکی از آنها،
285
00:10:36,930 –> 00:10:39,089
تعریف دو مورد باقی مانده بسیار ساده است، بنابراین ما
286
00:10:39,089 –> 00:10:42,839
آن را در ادامه به اسلایدهایی که قبلا ذکر کردیم پوشش می دهیم.
287
00:10:42,839 –> 00:10:44,279
پیمایش درخت برای
288
00:10:44,279 –> 00:10:46,890
درختهای باینری در اینجا فرآیندی است برای
289
00:10:46,890 –> 00:10:48,900
بررسی و/یا بهروزرسانی هر
290
00:10:48,900 –> 00:10:50,170
گره در یک
291
00:10:50,170 –> 00:10:52,750
ساختار دقیقاً یک بار، همانطور که
292
00:10:52,750 –> 00:10:54,970
قبلاً ذکر شد بر خلاف لیست پیوند یا هر
293
00:10:54,970 –> 00:10:56,560
ساختار دادهای 1 بعدی دیگر مانند آرایهای
294
00:10:56,560 –> 00:10:59,230
که به صورت خطی از
295
00:10:59,230 –> 00:11:01,420
درختان عبور میکنند. می توان به روش های مختلف پیمایش کرد
296
00:11:01,420 –> 00:11:02,500
و ما قصد داریم
297
00:11:02,500 –> 00:11:03,940
برخی از آنها را بررسی کنیم، بنابراین
298
00:11:03,940 –> 00:11:05,649
ابتدا بر روی جستجوی عمقی تمرکز خواهیم کرد
299
00:11:05,649 –> 00:11:07,930
و آن سه روش متفاوتی
300
00:11:07,930 –> 00:11:10,120
که ما ذکر کردیم، پیمایش قبل از ارسال و
301
00:11:10,120 –> 00:11:12,100
پیمایش نامرتب خواهد بود. طعمهای جستجوی عمقی اول
302
00:11:12,100 –> 00:11:15,430
و همانطور که اشاره کردم، حدس میزنم که
303
00:11:15,430 –> 00:11:16,870
این فقط نوعی تکرار همان چیزی است که
304
00:11:16,870 –> 00:11:18,310
قبلاً ذکر کردم، چند
305
00:11:18,310 –> 00:11:20,500
راه متداول برای انجام این کار وجود دارد و ترتیب جستجوی اول در عمق
306
00:11:20,500 –> 00:11:23,110
وجود دارد. این
307
00:11:23,110 –> 00:11:25,079
سه نوع مختلف از
308
00:11:25,079 –> 00:11:26,880
طرحهای پیمایش سفارش را در نظر میگیریم،
309
00:11:26,880 –> 00:11:29,279
بنابراین اجازه دهید ابتدا پیمایش قبل از سفارش را پوشش دهیم،
310
00:11:29,279 –> 00:11:31,570
بنابراین کاری که در اینجا انجام میدهیم این است که از
311
00:11:31,570 –> 00:11:34,750
ریشه شروع میکنیم و بررسی میکنیم که آیا ریشه خالی است و
312
00:11:34,750 –> 00:11:37,720
سپس از
313
00:11:37,720 –> 00:11:39,820
زیر درخت سمت چپ پایین میرویم و سپس به بالا برمی گردیم و
314
00:11:39,820 –> 00:11:41,589
سپس زیردرخت مناسب را در نظر می گیریم، بنابراین
315
00:11:41,589 –> 00:11:43,240
اجازه دهید در واقع به نوعی دنبال کنیم که چگونه
316
00:11:43,240 –> 00:11:45,970
پیمایش پیش سفارش پیش می رود، بنابراین از اینجا شروع
317
00:11:45,970 –> 00:11:47,980
می کنیم، از ریشه شروع می کنیم و عنصر ریشه
318
00:11:47,980 –> 00:11:49,750
319
00:11:49,750 –> 00:11:52,000
را چاپ می کنیم تا اولین مورد را به ما بدهد. خروجی
320
00:11:52,000 –> 00:11:54,579
پیمایش پیشسفارش در اینجا این F است، پس
321
00:11:54,579 –> 00:11:57,220
از زیر درخت سمت چپ به سمت پایین حرکت میکنیم، بنابراین
322
00:11:57,220 –> 00:11:59,410
ما اینجا هستیم، در B هستیم و بنابراین
323
00:11:59,410 –> 00:12:01,180
عنصری را در B چاپ میکنیم که عنصر دوم
324
00:12:01,180 –> 00:12:03,579
را در اینجا به ما میدهد و بنابراین بررسی میکنیم که آیا
325
00:12:03,579 –> 00:12:06,519
گره سمت چپ این یکی نه خیر نیست،
326
00:12:06,519 –> 00:12:08,680
بنابراین ما آن را در اینجا دنبال می کنیم و سپس
327
00:12:08,680 –> 00:12:10,990
عنصر را در آن عنصر در آن
328
00:12:10,990 –> 00:12:13,510
گره که a است چاپ می کنیم و سپس
329
00:12:13,510 –> 00:12:16,390
سمت چپ را بررسی می کنیم و بررسی می کنیم که آیا گره سمت چپ آن گره وجود دارد یا خیر.
330
00:12:16,390 –> 00:12:18,640
اینجا هستید پس هیچ
331
00:12:18,640 –> 00:12:21,130
گره سمت چپی در اینجا وجود ندارد پس همین است null بنابراین کاری که
332
00:12:21,130 –> 00:12:23,350
ما انجام می دهیم این است که به این گره در
333
00:12:23,350 –> 00:12:25,120
اینجا B برگردیم و سپس همین الان
334
00:12:25,120 –> 00:12:27,820
را بررسی می کنیم بنابراین به اینجا به D این گره
335
00:12:27,820 –> 00:12:29,800
در اینجا با شما آن را چاپ می کنیم بنابراین اکنون
336
00:12:29,800 –> 00:12:32,440
یک D هستیم و سپس دنبال می کنیم درخت فرعی سمت چپ،
337
00:12:32,440 –> 00:12:34,839
بنابراین ما از اینجا شروع می کنیم، اکنون اینجا هستیم
338
00:12:34,839 –> 00:12:37,750
در D، به سمت چپ می رویم، می بینیم که در C هستیم،
339
00:12:37,750 –> 00:12:40,000
اکنون چاپ کنید، بررسی می کنیم که آیا
340
00:12:40,000 –> 00:12:42,160
گره سمت چپی در اینجا وجود دارد تا ببینیم خالی آن وجود ندارد،
341
00:12:42,160 –> 00:12:44,560
بنابراین به C برمی گردیم.
342
00:12:44,560 –> 00:12:46,449
از اینجا به سمت D برمی گردیم و سپس
343
00:12:46,449 –> 00:12:48,490
زیردرخت سمت راست D را بررسی می کنیم، بنابراین به اینجا می رویم
344
00:12:48,490 –> 00:12:51,819
تا چاپ شود، آن را چک کنید، هیچ چیز را
345
00:12:51,819 –> 00:12:54,910
بررسی کنید، راست چیزی را بررسی کنید، به سمت بالا حرکت کنید، به سمت
346
00:12:54,910 –> 00:12:56,199
بالا برگردید، به ریشه ای که قبلاً
347
00:12:56,199 –> 00:12:57,760
آن را پوشش داده بودیم. اکنون
348
00:12:57,760 –> 00:12:59,589
به زیردرخت سمت راست می رویم، بنابراین به سمت زیر درخت سمت راست حرکت می کنیم،
349
00:12:59,589 –> 00:13:01,660
جایی که یک G چاپ می کنیم که در
350
00:13:01,660 –> 00:13:03,910
آنجا بررسی می کنیم که آیا یک گره سمت چپ
351
00:13:03,910 –> 00:13:05,350
وجود دارد، چیزی آنجا نیست، بنابراین ما هیچ
352
00:13:05,350 –> 00:13:06,670
کاری در آنجا انجام ندهیم، بنابراین بررسی می کنیم که آیا گره سمت راستی وجود دارد یا خیر.
353
00:13:06,670 –> 00:13:09,220
is and that is I، بنابراین
354
00:13:09,220 –> 00:13:11,200
I را روی صفحه چاپ می کنیم و سپس
355
00:13:11,200 –> 00:13:12,610
بررسی می کنیم که آیا گره سمت چپی وجود دارد یا خیر،
356
00:13:12,610 –> 00:13:14,560
اجازه دهید H پیش برویم و p rint that out
357
00:13:14,560 –> 00:13:16,480
ما بررسی می کنیم که آیا گره چپ وجود دارد، گره چپ وجود
358
00:13:16,480 –> 00:13:19,000
ندارد، گره راست نه گره راست،
359
00:13:19,000 –> 00:13:20,890
به اینجا برگردیم تا بررسی کنم که آیا
360
00:13:20,890 –> 00:13:22,660
گره سمت راستی وجود دارد، چیزی وجود ندارد، بنابراین پس از آن به
361
00:13:22,660 –> 00:13:24,490
سمت بالا حرکت می کنیم، به سمت بالا حرکت می کنیم و کارمان تمام
362
00:13:24,490 –> 00:13:26,380
می شود. پیمایش پیشسفارش را در
363
00:13:26,380 –> 00:13:28,720
آنجا دریافت کردهایم، بنابراین کاری که میخواهیم انجام دهیم این است که این
364
00:13:28,720 –> 00:13:31,060
را کدنویسی میکنیم و
365
00:13:31,060 –> 00:13:33,130
سپس برای پوشش دو
366
00:13:33,130 –> 00:13:36,040
الگوریتم پیمایش دیگر برمیگردیم و این دو الگوریتم
367
00:13:36,040 –> 00:13:38,020
بسیار شبیه به هم هستند. شرایط
368
00:13:38,020 –> 00:13:39,940
پیاده سازی از
369
00:13:39,940 –> 00:13:42,040
نقطه نظر بازگشتی و هنگامی که این یکی را درک کردیم،
370
00:13:42,040 –> 00:13:44,350
اجرای دو مورد دیگر باید
371
00:13:44,350 –> 00:13:47,680
کاملاً ساده باشد، بنابراین اکنون
372
00:13:47,680 –> 00:13:49,270
در کد به اینجا بازگشته ایم، اجازه دهید
373
00:13:49,270 –> 00:13:51,070
پیش برویم و یک تابع چاپ پیش سفارش ایجاد کنیم
374
00:13:51,070 –> 00:13:52,510
که مسئول آن خواهد بود. برای
375
00:13:52,510 –> 00:13:54,100
چاپ گرهها به صورت پیشسفارش،
376
00:13:54,100 –> 00:13:55,000
377
00:13:55,000 –> 00:13:57,700
بنابراین میگوییم که چاپهای پیشسفارش
378
00:13:57,700 –> 00:13:59,070
خود به خود انجام میشود، زیرا عضوی از کلاس
379
00:13:59,070 –> 00:14:02,290
شروع است، این گرهای است که
380
00:14:02,290 –> 00:14:04,840
در هر فراخوانی بازگشتی این تابع بهروزرسانی میشود.
381
00:14:04,840 –> 00:14:07,180