در این مطلب، ویدئو درختان باینری در پایتون: پیمایش مرتبه سطح با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,030 –> 00:00:02,070
بسیار خوب، بنابراین در این ویدیو ما
2
00:00:02,070 –> 00:00:04,140
به ادامه کار با درختان باینری می پردازیم و
3
00:00:04,140 –> 00:00:05,819
4
00:00:05,819 –> 00:00:08,790
نحوه عبور از درخت را در یک مرتبه تراز بررسی
5
00:00:08,790 –> 00:00:12,210
می کنیم، بنابراین اگر این درخت باینری ما
6
00:00:12,210 –> 00:00:15,210
در اینجا است، ترتیب سطح چاپ می شود. یا
7
00:00:15,210 –> 00:00:16,949
راهی که در آن میتوانیم این درخت را
8
00:00:16,949 –> 00:00:19,619
به ترتیب تراز طی کنیم، از اینجا
9
00:00:19,619 –> 00:00:22,140
در گره ریشه شروع میشود و سپس
10
00:00:22,140 –> 00:00:24,090
سطح بعدی را پایین در نظر میگیریم، بنابراین
11
00:00:24,090 –> 00:00:25,769
گرهها را در سطح دوم چاپ
12
00:00:25,769 –> 00:00:28,769
میکنیم که دو و سه خواهند بود و این
13
00:00:28,769 –> 00:00:30,720
تمام میکند. گرهها در این سطح دوم اینجا هستند،
14
00:00:30,720 –> 00:00:32,189
بنابراین به سطح سوم پیش
15
00:00:32,189 –> 00:00:33,840
میرویم و تمام گرهها را
16
00:00:33,840 –> 00:00:35,219
در اینجا در سطح سوم چاپ میکنیم که
17
00:00:35,219 –> 00:00:37,380
فقط دو تا از آنها چهار و پنج هستند، بنابراین
18
00:00:37,380 –> 00:00:38,940
پیمایش ترتیب سطح این درخت
19
00:00:38,940 –> 00:00:41,100
از اینجا شروع میشود. در سطح اول
20
00:00:41,100 –> 00:00:43,620
فقط گره در آنجا وجود دارد سپس
21
00:00:43,620 –> 00:00:45,690
به سطح بعدی دو و سه می رود و
22
00:00:45,690 –> 00:00:48,090
سپس سطح نهایی ما
23
00:00:48,090 –> 00:00:50,250
عناصر چهار و پنج را داریم بنابراین
24
00:00:50,250 –> 00:00:52,410
این خروجی یک پیمایش مرتبه سطح از
25
00:00:52,410 –> 00:00:55,170
این درخت باینری خاص خواهد بود. ‘روی
26
00:00:55,170 –> 00:00:56,340
رفتن به او ببینید چگونه میخواهیم
27
00:00:56,340 –> 00:00:58,739
واقعاً این کار را انجام دهیم و سپس
28
00:00:58,739 –> 00:01:00,149
29
00:01:00,149 –> 00:01:02,489
پیادهسازی این الگوریتم برای
30
00:01:02,489 –> 00:01:05,820
پیمایش مرتبه سطح در پایتون را ارائه میکنیم، بنابراین
31
00:01:05,820 –> 00:01:08,280
روش کلی
32
00:01:08,280 –> 00:01:10,140
برای انجام پیمایش ترتیب سطح شامل
33
00:01:10,140 –> 00:01:12,930
استفاده از یک ساختار داده صف استفاده می کنیم و ما
34
00:01:12,930 –> 00:01:14,610
از آن به روش زیر استفاده می کنیم، بنابراین
35
00:01:14,610 –> 00:01:16,320
من می خواهم از طریق مثالی از
36
00:01:16,320 –> 00:01:18,930
نحوه استفاده از یک صف قدم بگذارم و
37
00:01:18,930 –> 00:01:20,580
امیدواریم الگوی کلی
38
00:01:20,580 –> 00:01:22,830
بر اساس این مثال خاص مشخص
39
00:01:22,830 –> 00:01:25,320
شود. روشی که ما شروع می کنیم این است که ما یک
40
00:01:25,320 –> 00:01:27,930
ساختار داده صف داریم و
41
00:01:27,930 –> 00:01:29,790
عنصر اولیه آن صف را در
42
00:01:29,790 –> 00:01:33,390
صف اولین عنصر پیمایش مرتبه سطح قرار می دهیم
43
00:01:33,390 –> 00:01:35,159
که در این حالت
44
00:01:35,159 –> 00:01:36,630
اولین گره خواهد بود که ریشه خواهد بود،
45
00:01:36,630 –> 00:01:38,579
بنابراین شروع می کنیم با فقط در
46
00:01:38,579 –> 00:01:40,530
صف قرار دادن گره ریشه در صف خود
47
00:01:40,530 –> 00:01:43,979
و سپس کاری که پس از داشتن این انجام می دهیم این
48
00:01:43,979 –> 00:01:45,780
است که یک حلقه while داریم که
49
00:01:45,780 –> 00:01:47,790
از این صف عبور می کند و
50
00:01:47,790 –> 00:01:51,329
تا زمانی که این صف خاص خالی شود به کار ادامه
51
00:01:51,329 –> 00:01:53,610
می دهیم، بنابراین در این مورد چه خواهیم کرد حلقه این است که ما بررسی خواهیم کرد که
52
00:01:53,610 –> 00:01:56,250
چه چیزی اولین عنصر
53
00:01:56,250 –> 00:01:57,600
صف این است که بنابراین ما یک عملیات پیک را
54
00:01:57,600 –> 00:01:59,759
انجام خواهیم داد، این به ما امکان می دهد بفهمیم چه
55
00:01:59,759 –> 00:02:02,729
کسی در صف اول است، بنابراین اگر
56
00:02:02,729 –> 00:02:04,829
این کار را انجام دهیم، می بینیم که
57
00:02:04,829 –> 00:02:06,780
ما البته فقط ریشه را در صف قرار داده ایم
58
00:02:06,780 –> 00:02:09,209
. یک و بنابراین ما آن را به عنوان
59
00:02:09,209 –> 00:02:10,830
اولین عنصر برای
60
00:02:10,830 –> 00:02:13,830
پیمایش ترتیب سطح چاپ می کنیم، پس در حین حرکت چه کاری انجام
61
00:02:13,830 –> 00:02:15,990
می دهیم و سپس از شما می
62
00:02:15,990 –> 00:02:18,420
خواهیم فرزندان چپ و راست گره ای را
63
00:02:18,420 –> 00:02:19,770
که به تازگی بیرون آورده اید به من بدهید، بنابراین ما
64
00:02:19,770 –> 00:02:22,710
این را بیرون کشیدیم. در اینجا توجه داشته باشید که ما آن را
65
00:02:22,710 –> 00:02:25,020
از نشانه DQ’d کردیم و سپس می خواهیم
66
00:02:25,020 –> 00:02:26,970
بپرسیم فرزندان چپ و راست
67
00:02:26,970 –> 00:02:29,400
این گره چیست که فقط از نشانه DQ’d کرده ایم،
68
00:02:29,400 –> 00:02:31,440
بنابراین و چه چیزی دیگر آنجا نیست،
69
00:02:31,440 –> 00:02:32,700
یکی از آنها را بررسی می کنیم. بچه های چپ و راست،
70
00:02:32,700 –> 00:02:34,830
بنابراین ما دو و سه به عنوان
71
00:02:34,830 –> 00:02:36,750
این گره ها داریم که فرزندان چپ و راست
72
00:02:36,750 –> 00:02:38,970
این گره هستند که ما فقط آنها را DQ’d کردیم
73
00:02:38,970 –> 00:02:40,440
و بنابراین کاری که می خواهیم انجام دهیم این است
74
00:02:40,440 –> 00:02:42,570
که آنها را یک به یک علامت بزنیم. یکی از
75
00:02:42,570 –> 00:02:45,630
چپ و سپس به راست وارد نشانه می شود، بنابراین
76
00:02:45,630 –> 00:02:47,730
ما دو علامت داریم که ابتدا در خط می روند و
77
00:02:47,730 –> 00:02:50,070
سپس نت سمت راست به دنبال
78
00:02:50,070 –> 00:02:51,480
سمت راست قرار می گیرد. آن را در نشانه پنهان کنید
79
00:02:51,480 –> 00:02:54,000
، پس کاری که انجام میدهیم این است که از
80
00:02:54,000 –> 00:02:55,950
رویهای پیروی میکنیم که قبل از
81
00:02:55,950 –> 00:02:57,990
بررسی اولین عنصر در صف اولین عنصر در صف است
82
00:02:57,990 –> 00:03:00,390
، بنابراین میبینیم که
83
00:03:00,390 –> 00:03:02,070
دو در صف اول هستند، بنابراین آن را به عنوان عنصر دوم خود دریافت میکنیم.
84
00:03:02,070 –> 00:03:03,840
به عنوان خروجی
85
00:03:03,840 –> 00:03:06,330
پیمایش ترتیب سطح و سپس کاری که
86
00:03:06,330 –> 00:03:08,700
انجام میدهیم این است که آن گره را بیرون میآوریم، در
87
00:03:08,700 –> 00:03:10,020
واقع گرهی را که نگاهی به آن انداختهایم، به آن
88
00:03:10,020 –> 00:03:13,380
نگاه میکنیم و میپرسیم
89
00:03:13,380 –> 00:03:14,970
این گره به خصوص
90
00:03:14,970 –> 00:03:16,740
چه کسانی چه فرزندانی دارد که چپ هستند و فرزندان سمت
91
00:03:16,740 –> 00:03:18,810
راست این گره که ما فقط به آنها
92
00:03:18,810 –> 00:03:21,480
نگاه کردیم و فقط DQ’d کردیم تا آن گره
93
00:03:21,480 –> 00:03:23,190
دیگر در صف نباشد، آن را DQ’d کردیم و
94
00:03:23,190 –> 00:03:24,750
سپس متوجه می شویم که فرزندان چپ و راست
95
00:03:24,750 –> 00:03:26,760
این گره در اینجا با دو
96
00:03:26,760 –> 00:03:29,430
چهار و پنج هستند، بنابراین کاری که ما انجام می دهیم این است که
97
00:03:29,430 –> 00:03:31,350
می گوییم خوب بیایید هر دو و
98
00:03:31,350 –> 00:03:33,600
پنج را دوباره
99
00:03:33,600 –> 00:03:36,900
100
00:03:36,900 –> 00:03:39,120
در صف قرار دهیم.
101
00:03:39,120 –> 00:03:41,220
102
00:03:41,220 –> 00:03:42,780
در جلو و سپس چهار و
103
00:03:42,780 –> 00:03:44,820
پنج نفری که فقط در صف ایستادیم
104
00:03:44,820 –> 00:03:47,340
مرحله قبلی در اینجا و کاری که اکنون انجام می دهیم این است که
105
00:03:47,340 –> 00:03:49,380
از یک الگوی مشابه پیروی کنیم که به
106
00:03:49,380 –> 00:03:51,239
اولین عنصر صف نگاه می کنیم و آن عنصر را در صف قرار می
107
00:03:51,239 –> 00:03:52,800
دهیم
108
00:03:52,800 –> 00:03:55,440
سپس می خواهیم بپرسیم که
109
00:03:55,440 –> 00:03:57,209
چپ چیست و بچه های راست این عنصر را
110
00:03:57,209 –> 00:03:59,310
که ما فقط DQ’d کردیم تا بتوانیم اینجا برویم
111
00:03:59,310 –> 00:04:01,080
به این درخت، می بینیم که هیچ سمت چپی
112
00:04:01,080 –> 00:04:03,780
وجود ندارد، نه راستی وجود دارد، بنابراین می گوییم خوب است
113
00:04:03,780 –> 00:04:05,130
، بچه های چپ و راست وجود ندارند، بنابراین
114
00:04:05,130 –> 00:04:06,650
لازم نیست چیزی به آن اضافه کنیم. صف
115
00:04:06,650 –> 00:04:09,360
را جلو می رویم و دوباره نگاهی می اندازیم
116
00:04:09,360 –> 00:04:11,370
اگر نگاهی بیندازیم، چهار را در اینجا پرینت می
117
00:04:11,370 –> 00:04:14,030
کنیم و dq4 را جلو می گیریم،
118
00:04:14,030 –> 00:04:16,978
بنابراین DQ چهار می کنیم و سپس می پرسیم که
119
00:04:16,978 –> 00:04:18,149
فرزندان چپ و راست این
120
00:04:18,149 –> 00:04:20,548
خاص چیست؟ گره، بنابراین ما به چهار نگاه می کنیم،
121
00:04:20,548 –> 00:04:21,988
می گوییم خوب، چپ وجود ندارد، سمت راست وجود ندارد،
122
00:04:21,988 –> 00:04:24,720
بنابراین ما چیزی به
123
00:04:24,720 –> 00:04:26,010
صف اضافه نمی کنیم، در اینجا چیزی به پشت اضافه نمی کنیم،
124
00:04:26,010 –> 00:04:27,510
بنابراین ما فقط می گوییم خوب
125
00:04:27,510 –> 00:04:29,970
است، پنج، زیرا ما به این یک نگاه می
126
00:04:29,970 –> 00:04:31,310
کنیم و ما درست در امتداد حرکت کنید
127
00:04:31,310 –> 00:04:34,710
تا ما DQ کنیم سپس بدانیم که ما به اوج خود رسیده
128
00:04:34,710 –> 00:04:36,960
ایم که پنج است.
129
00:04:36,960 –> 00:04:38,670
از پنج،
130
00:04:38,670 –> 00:04:41,970
این تقریباً تنها کاری است که باید
131
00:04:41,970 –> 00:04:43,440
انجام دهیم، بنابراین هیچ فرزند چپ یا راستی
132
00:04:43,440 –> 00:04:45,390
از این گره وجود ندارد، ما قبلاً
133
00:04:45,390 –> 00:04:48,390
پیمایش ترتیب سطح سطح را چاپ کرده ایم و
134
00:04:48,390 –> 00:04:50,730
بررسی می کنیم که دوباره مطمئن شویم حلقه ای که
135
00:04:50,730 –> 00:04:52,470
در اینجا داریم در حال ایجاد است. مطمئن شوید که ما
136
00:04:52,470 –> 00:04:54,450
تا زمانی که صف خالی شود حلقه می زنیم، بنابراین در این
137
00:04:54,450 –> 00:04:56,040
مرحله هیچ عنصر دیگری برای
138
00:04:56,040 –> 00:04:58,230
پردازش در صف وجود ندارد، بنابراین ما
139
00:04:58,230 –> 00:05:00,420
تمام می کنیم و این تمام چیزی است که برای پیمایش ترتیب سطح نیاز داریم،
140
00:05:00,420 –> 00:05:03,330
بنابراین اکنون که
141
00:05:03,330 –> 00:05:05,040
اساساً متوجه شدیم که این پیمایش ترتیب سطح چگونه
142
00:05:05,040 –> 00:05:07,500
کار می کند، اجازه دهید ادامه دهید و به
143
00:05:07,500 –> 00:05:10,160
محیط برنامه نویسی ما بروید و این را کدنویسی کنید،
144
00:05:10,160 –> 00:05:13,110
بنابراین من در پایتون هستم و این فقط
145
00:05:13,110 –> 00:05:14,700
دنبال کردن ویدیوی قبلی است
146
00:05:14,700 –> 00:05:17,190
که روی درخت های باینری انجام دادیم اگر ندیدید
147
00:05:17,190 –> 00:05:20,010
که آن کد را می توان از github من دریافت کرد
148
00:05:20,010 –> 00:05:22,170
و اگر کدی را میخواهید که من با آن شروع میکنم، میتوانید به پیوند
149
00:05:22,170 –> 00:05:24,000
در توضیحات زیر برای این ویدیو
150
00:05:24,000 –> 00:05:26,910
یا ویدیو قبلی مراجعه
151
00:05:26,910 –> 00:05:29,580
کنید، بنابراین کاری که
152
00:05:29,580 –> 00:05:30,480
میخواهیم انجام دهیم این است که
153
00:05:30,480 –> 00:05:32,520
تابعی را تعریف کنیم که به ما اجازه میدهد. برای
154
00:05:32,520 –> 00:05:34,860
انجام یک دستور سطح پیمایش و
155
00:05:34,860 –> 00:05:37,350
دوباره کاری که با اسلایدها در
156
00:05:37,350 –> 00:05:39,240
مثالی که مرور کردیم انجام دادیم، از
157
00:05:39,240 –> 00:05:41,460
یک ساختار داده زیبا استفاده کردیم، بنابراین
158
00:05:41,460 –> 00:05:43,620
یک کلاس Q بسیار سریع کدنویسی می کنیم
159
00:05:43,620 –> 00:05:46,230
که به ما امکان می دهد
160
00:05:46,230 –> 00:05:49,350
مواردی را که می خواهیم دستکاری کنیم. همانطور که در اسلایدها انجام دادیم، درخت را به داخل بکشید،
161
00:05:49,350 –> 00:05:51,090
بنابراین میخواهیم از
162
00:05:51,090 –> 00:05:53,370
اینجا بالا برویم و بالاتر از کلاس گره
163
00:05:53,370 –> 00:05:55,650
برویم و یک کلاس Q ایجاد کنیم
164
00:05:55,650 –> 00:05:58,110
که در این مشکل برای ما مفید خواهد بود،
165
00:05:58,110 –> 00:06:02,580
بنابراین کلاس Q را میگوییم. شی و
166
00:06:02,580 –> 00:06:05,220
سپس در سازنده این Q
167
00:06:05,220 –> 00:06:06,630
اساساً کاری که میخواهیم انجام دهیم این است
168
00:06:06,630 –> 00:06:08,790
که ما فقط به نوعی
169
00:06:08,790 –> 00:06:12,170
ساختار داده فهرست پایتون را که به
170
00:06:12,170 –> 00:06:14,460
طور ضمنی با پایتون همراه است تغییر میدهیم و ما آن
171
00:06:14,460 –> 00:06:17,670
را تغییر میدهیم تا حدس میزنم آن را تطبیق دهیم. برای اینکه
172
00:06:17,670 –> 00:06:21,090
عملکرد آن مانند یک Q باشد، درست
173
00:06:21,090 –> 00:06:22,710
مانند کاری که ما برای پشته انجام دادیم، اگر
174
00:06:22,710 –> 00:06:24,750
این سری از ویدیوهای استوک را دیدید، ما
175
00:06:24,750 –> 00:06:25,920
همین کار را انجام دادیم وقتی کلاس
176
00:06:25,920 –> 00:06:28,530
تعریف شده یک پشته را تعریف کردیم و اساساً
177
00:06:28,530 –> 00:06:32,580
ویژگی لیست را در پایتون،
178
00:06:32,580 –> 00:06:33,930
داده های لیست را تغییر دادیم. ساختاری که در
179
00:06:33,930 –> 00:06:36,090
زبان پایتون به طور ضمنی به عنوان یک سهام wou رفتار می کند
180
00:06:36,090 –> 00:06:37,140
بنابراین ما همان
181
00:06:37,140 –> 00:06:39,990
کار را در اینجا به عنوان Q انجام خواهیم داد، بنابراین برای سازنده،
182
00:06:39,990 –> 00:06:41,220
کاری که میخواهیم انجام دهیم این
183
00:06:41,220 –> 00:06:44,130
است که آیتمهای خود را با یک
184
00:06:44,130 –> 00:06:46,890
لیست خالی و سپس کاری که میخواهیم انجام دهیم برابر است. آیا
185
00:06:46,890 –> 00:06:48,630
ما قصد داریم چند تابع را
186
00:06:48,630 –> 00:06:50,460
در اینجا بنویسیم، بنابراین اجازه دهید ابتدا تابع Q را تعریف کنیم،
187
00:06:50,460 –> 00:06:52,620
بنابراین این برای افزودن چیزهایی
188
00:06:52,620 –> 00:06:55,470
به صف است، بنابراین ما می خواهیم در
189
00:06:55,470 –> 00:06:57,750
لیست پارامترهای خود و همچنین چیزی
190
00:06:57,750 –> 00:06:59,190
که می خواهیم اضافه کنیم. به
191
00:06:59,190 –> 00:07:02,400
عنوان آیتم اشاره می کنیم و ما می گوییم آیتم های خود نقطه ای، درج نقطه،
192
00:07:02,400 –> 00:07:04,170
زیرا می خواهیم این
193
00:07:04,170 –> 00:07:07,230
را در عنصر صفر صف وارد
194
00:07:07,230 –> 00:07:08,430
کنیم، بنابراین ادامه می دهیم و این کار را انجام می دهیم، بنابراین می
195
00:07:08,430 –> 00:07:10,110
خواهیم این عنصر را در یک مکان بسیار خاص درج کنیم.
196
00:07:10,110 –> 00:07:12,420
مکان در صفی
197
00:07:12,420 –> 00:07:14,370
که در حال تعریف آن هستیم و سپس ما همچنین یک
198
00:07:14,370 –> 00:07:17,400
عملیات DQ می خواهیم که چیز را از جلوی خط حذف می کند،
199
00:07:17,400 –> 00:07:18,950
بنابراین می گوییم
200
00:07:18,950 –> 00:07:24,480
DQ self نیازی به ارائه آرگومان های بیشتری به آن ندارد
201
00:07:24,480 –> 00:07:27,810
و ما. میگویم اگر
202
00:07:27,810 –> 00:07:29,550
نقطۀ خود خالی است، ادامه میدهیم و
203
00:07:29,550 –> 00:07:32,190
بهزودی آن را بهعنوان تابع خالی تعریف میکنیم تا
204
00:07:32,190 –> 00:07:34,350
زمانی که صف خالی نباشد.
205
00:07:34,350 –> 00:07:35,970
کاری که انجام می دهیم این است که به جلو برویم
206
00:07:35,970 –> 00:07:38,760
و آیتم های pop not pop خود را برگردانیم، بنابراین
207
00:07:38,760 –> 00:07:41,610
آیتم صف را بیرون می آوریم و سپس آن را
208
00:07:41,610 –> 00:07:44,010
برمی گردانیم تا ببینیم در
209
00:07:44,010 –> 00:07:46,770
این مورد آن گره چگونه به نظر می رسد. بنابراین
210
00:07:46,770 –> 00:07:49,140
ما توابع in queue و DEQ خود را داریم، اجازه دهید ادامه دهیم
211
00:07:49,140 –> 00:07:50,460
و تابع خالی را تعریف
212
00:07:50,460 –> 00:07:51,990
کنیم که استفاده
213
00:07:51,990 –> 00:07:55,290
کردیم، بنابراین می گوییم خالی است، خودش انجام می شود
2