1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [第7節：より快適]

2
00:00:02,770 --> 00:00:05,090
[ロブボーデン] [ハーバード大学]

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
左側の子 'のいずれか1つではなく、ポインタのを除いて、2つがあります

12
00:00:38,150 --> 00:00:41,950
そして右の "子"のための1。 "

13
00:00:41,950 --> 00:00:45,630
、ちょうどリンクリストのようなものですバイナリツリーがそう

14
00:00:45,630 --> 00:00:47,910
構造体を除いて、2つのポインタを持っているとしている。

15
00:00:47,910 --> 00:00:51,390
3ポインタを持っているとしているトライナリ木は、、あります

16
00:00:51,390 --> 00:00:56,540
ただ一般的なポインタを持っているn分​​木がありますが、

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
だからバイナリーツリーは、ちょうど2つの定数を持っていることを起こる。

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
それぞれの子のポインタがnullであるネイトの好きな数字、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
これらの両方がnullであることを行っている。

32
00:01:52,460 --> 00:01:57,870
それはちょうどnullになり、それはちょうど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
これは、最初は単にnull言う。

55
00:03:14,620 --> 00:03:19,600
我々は、9に、このポインタは、ポイントを変更するつもりだ

56
00:03:19,600 --> 00:03:23,310
そして今我々は3の右に6を入れたい。

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を含む1。ツリーの一番下にあるノードは葉と呼ばれます。

63
00:03:54,720 --> 00:04:01,240
ちょうどその子としてnullを持つすべてのノードはリーフです。

64
00:04:01,240 --> 00:04:03,680
だから、我々のバイナリツリーが1つのノードであれば、可能ですが、

65
00:04:03,680 --> 00:04:10,130
木は葉であり、それはそれだと。

66
00:04:10,130 --> 00:04:12,060
"木の 'height'はあなたが作らなければならホップ数です

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
彼らは1と同じ、だ

105
00:06:49,250 --> 00:06:54,580
、それはあなたがバイナリツリーと二分探索木の区別が認識が重要です。

106
00:06:54,580 --> 00:06:58,830
バイナリツリーは2つだけを指している木です。

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
通常のバイナリツリーの我々だけで、左、上、7時に3を持つことができます

119
00:07:40,020 --> 00:07:47,630
7の左から9;全く全く値の順序はありません。

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
これらのポインタのすべてがちょうどnullです。

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は、3から6ポイントです。

143
00:09:35,350 --> 00:09:39,290
これはまだ有効な二分探索木である。

144
00:09:39,290 --> 00:09:49,260
私がアレンジを考え出すことができるかどうかを確認してみましょう - 私が間違っている場合はどうでしょう。

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
我々はまだですが、7未満を行ったことにより、9に取得することができます

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
しかし、私はその後、左に行くことができる量を合計数字をnしている場合

180
00:12:15,090 --> 00:12:18,820
1  - プラス右に行くことができる量はnです。

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
いくつかの時点で、次のいずれかを、あなたが探している値を見つけることができます、またはあなたは、nullに実行されます、

198
00:13:22,800 --> 00:13:28,520
値を示すと、ツリーではありません。 "

199
00:13:28,520 --> 00:13:32,450
私たちは前に持っていたツリーを再描画する必要があり、それが第二を取るよ。

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
そしてその後は無関心 - あなたの頭の中で考えようとする代わりに、

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
これは私が探している値ですので、私の場合はtrueを返します。

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
私はnullをヒットした場合はどうすればよいですか？

226
00:15:44,170 --> 00:15:47,440
[学生]はfalseを返します？ >>うん。私は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
以下の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
それでは、ここで決まり文句を入れてみましょう

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
[学生] intとし、2つのポインタ？

243
00:16:46,520 --> 00:16:49,700
>> Intの値が、2つのポインタ？どのように私はポインタを書くのですか？

244
00:16:49,700 --> 00:16:58,440
[生徒]のStruct。 >>私は、ええ、そう構造のノード*左ズームインべき

245
00:16:58,440 --> 00:17:01,320
とstructノード*右。

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
私たちは、機能と私たちのinsert関数が含まれています

261
00:18:23,130 --> 00:18:27,410
代わりに私たちのCONTAINSのちょうどこのグローバルノード変数を使用して機能、

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
1つがそのような木を構築を開始する方法を示しますか？

271
00:20:03,130 --> 00:20:08,080
[学生]誰かのバンギング、出ようと。

272
00:20:08,080 --> 00:20:13,100
[ボーデン]彼らの木の構築と快適な誰ですか？

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
[ボーデン]いいえ>>オーケー。だから、初期化しなければならないでしょう - 

280
00:20:47,160 --> 00:20:50,450
[ボーデン]あなたが定義するか、構造体を宣言するとき号、

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
[ボーデン]はい。だから、ショートカット初期化構文

286
00:21:13,200 --> 00:21:18,660
のように起こっている - 

287
00:21:18,660 --> 00:21:22,200
我々はこれを行うことができる2つの方法があります。私たちはそれをコンパイルすべきだと思う

288
00:21:22,200 --> 00:21:25,840
Clangのもこれを行うことを確認します。

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にそれを初期化したいのであれば、左、右、nullになるヌルさと

292
00:21:35,690 --> 00:21:41,570
それが9、NULL、NULLになります。

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
C、または。値= 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 + +でCのスーパーセットである

307
00:22:49,100 --> 00:22:54,160
あなたは、C + +、それはコンパイルする必要がありますにそれを移動し、Cコードを取ることができます。

308
00:22:54,160 --> 00:22:59,570
これは、C + +サポートしていないことの1つなので、人々はそれをしない傾向があります。

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は、技術的に "は、void *"を返す

313
00:23:16,940 --> 00:23:20,200
あなただけは、char * X = mallocの何でも言うことができる

314
00:23:20,200 --> 00:23:22,840
そしてそれは自動的にchar *にキャストされます。

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
char *には、malloc、何でも、char *型にキャストする。

318
00:23:34,510 --> 00:23:37,270
CおよびC + +に同意しないことはたくさんあり​​ません

319
00:23:37,270 --> 00:23:40,620
しかし、それらは2つです。

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
[学生]私は逆参照する必要はありませんか？ >>うん。

324
00:23:52,170 --> 00:23:55,110
、矢印が暗黙の逆参照を持っていることを覚えている

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
すべての矢印手段は、間接参照、これは、今私は、構造体にいれて、私はフィールドを取得することができます。

331
00:24:24,600 --> 00:24:28,040
直接または間接参照するフィールドを取得し、フィールドを取得 - 

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
[学生、不明朗] >>うん。ノード3のアドレスは、

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
またはroot =＆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
そしてこれは我々がハフマン符号化のための提供するAPIに似ています。

375
00:28:09,050 --> 00:28:12,730
私たちは、木のためにあなたに初期化関数を与える

376
00:28:12,730 --> 00:28:20,520
それらの木と森のために同じもののためとデコンストラクタ "関数"。

377
00:28:20,520 --> 00:28:22,570
>> そこでここでは、初期化関数を持っているつもりです

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
だから今我々は単に与えられた値とNULLポインタを備えた任意のノードを構築することを呼び出すことができます。

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が失敗した場合は、nullを返します。

397
00:30:11,660 --> 00:30:16,460
だから私はなまけてそれぞれの条件を行うのではなく、ここでそれを置くつもりです。

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
[ボーデン]任意のゼロ値はfalseです。

404
00:30:51,290 --> 00:30:53,920
だからnullはゼロ値である。

405
00:30:53,920 --> 00:30:56,780
ゼロはゼロの値である。 Falseの場合、ゼロ値です。

406
00:30:56,780 --> 00:31:02,130
任意の - かなりわずか2ゼロの値がNULLとゼロであり、

407
00:31:02,130 --> 00:31:07,900
falseはゼロとして定義だけハッシュです。

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がNULLで、x.right nullです。

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
[ボーデン]その他の値も。だからxに、xがゼロになります。

428
00:32:36,220 --> 00:32:40,070
それがグローバルスコープである場合、それは初期値があります。オーケー。>>

429
00:32:40,070 --> 00:32:48,950
[ボーデン]のどちらか、あなたがそれまたはゼロを与えた初期値。

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
boolのプロトタイプを持つint型の値を含んでいます。 "

434
00:33:04,930 --> 00:33:08,340
我々は、boolはint型の値が含まれている何をするつもりはありません。

435
00:33:08,340 --> 00:33:15,110
我々のプロトタイプは次のように起こっている

436
00:33:15,110 --> 00:33:22,380
boolは（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
1、またはtrueを返す必要があること

444
00:33:54,300 --> 00:33:59,390
含まれているのに対し、5ルートはfalseを返す必要があります。

445
00:33:59,390 --> 00:34:02,690
だから、これを実装する2つ目を取る。

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型の値が含まれているため、我々は、サブツリーの下に再帰処理の方法がありません。

451
00:34:19,750 --> 00:34:24,130
私達は私達のためのサブツリーを再帰的にダウンして別のヘルパー機能がなければならないでしょう。

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
今、我々はより簡単に再帰することができます。

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
そして私はちょうど、tempが等しく、nullをされていませんがループスルー

463
00:35:28,330 --> 00:35:31,700
そう木に残っているときに、私は推測する。

464
00:35:31,700 --> 00:35:35,710
と値がtempは、を指している値と等しいかどうかを

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
それはループを抜けてfalseを返します - それが返されます。

469
00:35:47,330 --> 00:35:52,190
[ボーデン]オーケー。だからそれは良いようだ。

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
[学生]右、trueの場合は最初のものはありますか？

485
00:37:18,550 --> 00:37:25,570
[ボーデン]うん。私はいつもそれを読む方法ですが、tempは、一時値よりも大きい値に等しい

486
00:37:25,570 --> 00:37:30,680
この、他のこの。それは、質問を求めている。

487
00:37:30,680 --> 00:37:35,200
それは大きいですか？その後、最初のことを行う。 elseは2番目のことを行う。

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
オーケー。我々がしようとしているこの1  - それはすでに偉大かもしれない、

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
[学生]確かに。だから我々は、木が最初にnullでないことを確認しています

495
00:38:08,340 --> 00:38:13,380
木がnullの場合、それは我々がそれを見つけていないのでfalseを返すために起こっているからです。

496
00:38:13,380 --> 00:38:19,200
木がまだあるなら、私達は入る - 値は現在のノードである場合は、まずチェックしてください。

497
00:38:19,200 --> 00:38:23,740
左または右に我々はそれが再帰的である場合にtrueを返し、そうでない場合。

498
00:38:23,740 --> 00:38:25,970
そのサウンドは適切か？ >> MM-うーん。 （協定）

499
00:38:25,970 --> 00:38:33,880
だから、これはほとんどであることに気づく - 反復解法と構造的に非常に似ています。

500
00:38:33,880 --> 00:38:38,200
それは代わりに再帰し、我々は、whileループを持っていたというだけです。

501
00:38:38,200 --> 00:38:40,840
そして木が等しく、nullをしませんここで、ベースケース

502
00:38:40,840 --> 00:38:44,850
我々は、whileループから抜け出しする条件だった。

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
値がツリーの値未満である場合、私たちは、木の左に再帰したい

514
00:39:44,320 --> 00:39:53,890
他では、ツリーの右に再帰したい。

515
00:39:53,890 --> 00:39:58,610
だから、この外観を小さくするのステップ1であった。

516
00:39:58,610 --> 00:40:02,660
この外観の小型化のステップ2  - 

517
00:40:02,660 --> 00:40:09,150
我々は、複数の行にこれを分離することができます。

518
00:40:09,150 --> 00:40:16,500
オーケー。それは小さく見えることのステップ2は、ここにある

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
それがtrueの場合、これは真実であり、私たちがしたい 'または'がここに終わったものは何でも。

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
論理和 - 何かで真または論理和は、必ずしも真実である。

529
00:41:04,990 --> 00:41:08,150
だから、できるだけ早く我々が戻り値=ツリーの値を見るように、

530
00:41:08,150 --> 00:41:10,140
我々だけtrueを返すつもりだ。

531
00:41:10,140 --> 00:41:15,710
でも、再帰的にはいかないのが、さらにラインの下で含まれています。

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
それは1ライン機能しました。

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
木が悪いケースです等しいnullを、ない場合

539
00:41:49,580 --> 00:41:54,790
木がNULLの場合は、最初の条件が偽であることを行っている。

540
00:41:54,790 --> 00:42:00,550
何とANDだから偽は何になるだろうか？

541
00:42:00,550 --> 00:42:04,640
[学生]はFalseを返します。 >>うん。これは、短絡評価の残りの半分である

542
00:42:04,640 --> 00:42:10,710
ツリーが等しく、nullをしない場合は、私たちも、どこへ行くに行くされていません - 

543
00:42:10,710 --> 00:42:14,930
ツリーが等しいヌルを行う場合は、次に我々は値==ツリーの値をするつもりはありません。

544
00:42:14,930 --> 00:42:17,010
我々は、ちょうどすぐにfalseを返すつもりだ。

545
00:42:17,010 --> 00:42:20,970
それは短絡評価していない場合ので、重要なのですが、

546
00:42:20,970 --> 00:42:25,860
ツリーが等しいヌルをすれば、次に、この第二の条件は、セグメントフォールトに起こっている、

547
00:42:25,860 --> 00:42:32,510
ツリー - >値はnullを間接参照しているためです。

548
00:42:32,510 --> 00:42:40,490
だからそれはそれだ。これを行うことができます - 一度の転換。

549
00:42:40,490 --> 00:42:44,840
これは、これでこの1行をしていない、また、非常に一般的なものです

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
2 IFSにこれを打破するために、好きな場所、ツリーヌルですか？

554
00:43:06,770 --> 00:43:11,780
さて、それがnullではないので、今は値と等しいツリーの値ですか？これを行う。

555
00:43:11,780 --> 00:43:17,300
代わりに、この条件は、これはseg faultをすることはありません

556
00:43:17,300 --> 00:43:21,220
これがnullであることを起こる場合、それは打破されるためです。

557
00:43:21,220 --> 00:43:24,000
まあ、私は、あなたのツリーは完全に無効なポインタである場合、それはまだseg faultをすることができますね

558
00:43:24,000 --> 00:43:26,620
木がnullの場合、それはseg faultをすることはできません。

559
00:43:26,620 --> 00:43:32,900
それがnullであった場合は、初めての場所にポインタを間接参照する前に、それは起こるだろう。

560
00:43:32,900 --> 00:43:35,000
[学生]このいわゆる遅延評価ですか？

561
00:43:35,000 --> 00:43:40,770
>> [ボーデン]遅延評価は、独立したものです。

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
それは我々が "レイジー"を書くと言っています。

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
51でOCamlのすべてが、すべてが再帰であるためです。

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
ここで、あなたがなまけて評価しなかった場合、それが意味するだろう - 

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
だから、遅延評価のことは問題ありません。

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
だから今それはboolインサート（int値）です。

599
00:46:10,470 --> 00:46:23,850
我々は、boolインサート（int型の値、ノード*ツリー）にあることを変更するつもりです。

600
00:46:23,850 --> 00:46:29,120
我々は、実際には少しでその再度変更しようとしている、我々は、理由がわかります。

601
00:46:29,120 --> 00:46:32,210
そして、だまされたと思って、build_nodeを動かしてみましょう

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
それは私が7の左側に9を挿入することは不可能になるだろう

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
[ボーデンは]それは大歓迎だ。オーケー。説明したいと思います？

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
私はnullに指摘ノードに着くまで。

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
[ボーデン]わかりましたので、私はここで一つの問題を参照してください。

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
[学生] tempがnullの場合は？ >>うん。 tempがnullの場合、だから、ループから抜け出す方法​​です。

651
00:50:22,100 --> 00:50:30,220
しかし、私はちょうどここに何をしますか？

652
00:50:30,220 --> 00:50:35,410
必然的にnullである私を間接参照温度、。

653
00:50:35,410 --> 00:50:39,840
tempがヌルになるまで、あなたがする必要がある他の事はただ追跡されないように、

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
または両親が常に等しくtempに行くのですか？ケースことはありますか？

661
00:51:14,500 --> 00:51:19,560
tempがnullでない場合は、私は、何があって、下に移動しないつもりです

662
00:51:19,560 --> 00:51:24,030
tempが親となっているノードへ。

663
00:51:24,030 --> 00:51:27,500
だから親は、tempになるだろうし、私がダウンしてtempに移動します。

664
00:51:27,500 --> 00:51:32,410
今すぐtempはヌルですが、nullであるものの親の親を指しています。

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
我々は半分あなたがbuild_nodeを使用すると予想。

676
00:52:29,630 --> 00:52:40,450
ノードnewnodeがNULLの場合、その後、falseを返します。

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
木がnullとしてオフに開始された場合、我々はヌルツリーに渡す。

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
nullの木に値を挿入する

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
あなたはnullツリーを渡した場合

689
00:53:28,050 --> 00:53:31,320
あなたはそれに値を挿入したい場合は、falseを返します。

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
木がnullの場合、私たちにはないので、我々はそれについてできることは何もありません。

695
00:53:48,570 --> 00:53:50,960
私たちはただfalseを返すことができます。

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
まあ、今すぐこの点はnullになります。

708
00:54:33,340 --> 00:54:38,130
私は何をしたいのは、NOT NULLに指すように、このポインタを操作することです。

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
私はただ、ポインタがNULLを指しているかどうかを追跡することができます

713
00:54:52,640 --> 00:54:54,580
とポインタがNULLを指している場合、

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
私たちはただfalseを返すつもりだと思います。

725
00:55:37,550 --> 00:55:40,460
これはあなたの木がNULLとは異なります。

726
00:55:40,460 --> 00:55:44,510
これはあなたのrootがNULLポインタへのポインタである

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
その後＆rootはノード**になるだろう。

735
00:56:11,170 --> 00:56:15,120
これは有効です。ここまでこのケースでは、木、、

736
00:56:15,120 --> 00:56:20,120
または挿入 - 木がnullではありません。

737
00:56:20,120 --> 00:56:24,630
ここに。ツリーはnullではありません。*木がnullの場合、罰金となる

738
00:56:24,630 --> 00:56:26,680
*ツリーがnullの場合、私はそれを操作できるため、

739
00:56:26,680 --> 00:56:29,210
今私はそれを指すように欲しいものを指すように設定します。

740
00:56:29,210 --> 00:56:34,750
木がnullである場合でも、それは私はちょうどここに降りてきて言ったヌルを意味します。

741
00:56:34,750 --> 00:56:42,710
それは意味をなさない。私はそれで何もすることはできません。

742
00:56:42,710 --> 00:56:45,540
木がnullの場合、falseを返します。

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
[ボーデン]はい。だから（*ツリー== 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
これまでです -  *は、私の赤いポインタは、これまでにnullである場合、

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の場合は、falseを返します。

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
我々はそれらを指すようにしたいものを指すようにNULLポインタを変更することができます。

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
[ボーデン]だから私は現在だと覚えている - 

775
00:59:27,490 --> 00:59:31,260
[学生、不明朗]

776
00:59:31,260 --> 00:59:34,140
[ボーデン]ええ、そう右ここに、この緑の矢印と言ってみましょう

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
デリファレンスは二回良い感じだった。

780
00:59:48,800 --> 00:59:51,010
私に何をする - どのように私はそれを行うのですか？

781
00:59:51,010 --> 00:59:53,210
[学生]は一度逆参照し、次に矢印をそのようにしますか？

782
00:59:53,210 --> 00:59:58,420
[ボーデンは]だから（*木）、一回間接参照です - >値

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
それがそうであるなら、私は値を使用してINSERTを呼び出す必要があります。

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
そう左が終了した場合、最大NULLポインタであることを、

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
[ボーデン]ことを覚えておいてください -  ** 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
[ボーデン]うん。だから - いや、あなたは前にすることができ、その解

805
01:01:58,220 --> 01:02:04,540
二つのポインタを行わずにそれを行うための方法でした。

806
01:02:04,540 --> 01:02:08,740
あなたは、2つのポインタを使用して理解できるようにする必要があります

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
私のルートがnullだった場合はどうなりますか？私は右ここにこのケースを行う場合はどうなりますか？

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
ルート左側がnullであることを行っている、ルート権がヌルであることを行っている。

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
場合であっツリー - ルートがnullだった場合、

818
01:02:56,020 --> 01:02:58,410
我々だけでfalseを返す必要がありました。我々は何ができることは何もありません。

819
01:02:58,410 --> 01:03:01,520
私たちは、空のノードをツリーに挿入することはできません。

820
01:03:01,520 --> 01:03:06,810
しかし、今、私たちすることができ、我々は、ちょうど1つのノードツリーに空の木を作る。

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
我々は繰り返しこれをしなかった場合は、代わりに、それは、whileループと同じ考えになると思います。

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
[学生]我々は、trueを返すのですか？

836
01:04:17,110 --> 01:04:21,550
[ボーデン]右ここで、おそらくですね。

837
01:04:21,550 --> 01:04:26,690
我々はそれを正しく挿入した場合、trueを返します。

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
[ボーデンは]私はそれがダッシュでそれをしないと思う - またはどのような最適化レベル

845
01:05:00,310 --> 01:05:03,820
認識されるように、末尾再帰のために必要です。

846
01:05:03,820 --> 01:05:09,350
私はそれを認識して考える -  GCCとClangの

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
、ルート自体がnullであるか、過去のエントリがnullの場合

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
そして今、私たちのwhileループは、* curが等しく、nullをされていませんがあることを行っている。

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
我々はすでにtempを使っているので、私は、それを一時と呼ぶことにします。

869
01:07:10,190 --> 01:07:17,200
オーケー。もしそうであれば（値> * temp）に、

870
01:07:17,200 --> 01:07:24,010
その後、＆（* TEMP） - >右

871
01:07:24,010 --> 01:07:29,250
他の気温=＆（* temp）に - >左。

872
01:07:29,250 --> 01:07:32,730
そして今、この時点では、このwhileループの後、

873
01:07:32,730 --> 01:07:36,380
多分それは約反復して再帰的に考えるよりもする方が簡単ですので、私は、これを行う

874
01:07:36,380 --> 01:07:39,010
しかし、このwhileループの後、

875
01:07:39,010 --> 01:07:43,820
* tempは、変更したいポインタです。

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
次に* tempは親の権利であり、我々はそれを直接変更することができます。

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
私は、我々が行うことができます1迅速かつ簡単に関数があると推測

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
これは、関数がtrueを返す必要があります含まれています

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
[ボーデン]それでは、（ツリー== NULL）の場合はどうでしょうか？

907
01:10:18,230 --> 01:10:22,740
[学生]はfalseを返します。

908
01:10:22,740 --> 01:10:26,160
[ボーデン]がそうでなければ、まあ、私は他には必要ありません。

909
01:10:26,160 --> 01:10:30,250
場合は、私の他のベースケースでした。

910
01:10:30,250 --> 01:10:32,450
[学生] Treeの値はありますか？ >>うん。

911
01:10:32,450 --> 01:10:36,430
だから（木>の値==値なら。

912
01:10:36,430 --> 01:10:39,920
我々は、ノード*ではなく、ノード** sに戻って気づく？

913
01:10:39,920 --> 01:10:42,990
CONTAINSは、ノード**を使用する必要は決してありません

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
それが起こるなら、私たちは、trueを返したいと思います。

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
それから私達は見て物事を使い果たしてしまったので、falseを返します。

935
01:12:16,020 --> 01:12:24,810
（最新版 - >値==値）の場合、trueを返します。

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
[ボーデン]うん。それでは、それを作ってみましょう

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
構造体リストlist =、それは始めましょう

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
私たちが飛ばされていることをサブツリーの。

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
その後、我々は、新しいリストまたは構造体があるでしょう

956
01:14:32,620 --> 01:14:41,080
構造体リスト*、新しいリスト=はmalloc（sizeofの（リスト））。

957
01:14:41,080 --> 01:14:44,920
私は、エラー·チェック無視するつもりですが、あなたはそれがnullでよいかどうかを確認するためにチェックする必要があります。

958
01:14:44,920 --> 01:14:50,540
それを指すように起こっているノードを新しいリスト - 

959
01:14:50,540 --> 01:14:56,890
私がここでそれを望んでなぜ、ああ、それはです。それが2番目の構造体のリストを指すようになるだろう。

960
01:14:56,890 --> 01:15:02,380
それはリストの仕事をリンクさどれだけだ。

961
01:15:02,380 --> 01:15:04,810
これはintリンクリストと同じです。

962
01:15:04,810 --> 01:15:06,960
我々は、ただのノード*とint型を交換している点が異なります。

963
01:15:06,960 --> 01:15:11,040
それは全く同じだ。

964
01:15:11,040 --> 01:15:15,100
だから新しいリスト、私たちの新しいリストノードの値、

965
01:15:15,100 --> 01:15:19,120
電流は>右になるだろう。

966
01:15:19,120 --> 01:15:24,280
私たちの新しいリストの値 - >次は私達の元のリストになるだろう、

967
01:15:24,280 --> 01:15:30,760
それから私達は新しいリストを指すように、私たちのリストを更新するつもりです。

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
今、私たちは、ITのものを引き出すために必要

971
01:15:40,480 --> 01:15:43,850
最新版のようにnullである、我々はただfalseを返す必要はありません。

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
我々が現在見ているのは、nullではありません

979
01:16:17,090 --> 01:16:22,340
代わりに、私たちは私たちのリスト自体がnullになるまで行き続けていくつもりです。

980
01:16:22,340 --> 01:16:25,680
私たちのリストには、nullをされて終わるのであれば

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
リスト-> nextはヌルであることを行っている。

986
01:17:02,860 --> 01:17:07,580
そして今、リストが等しく、nullをされていませんが。

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
限り、彼らがnullではないしているとして。

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
そのノードは、我々が探している値である場合、我々は、trueを返すことができます。

1005
01:18:34,060 --> 01:18:37,640
そうでなければ、両方の私達の左と右のサブツリーを挿入

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
私たちのリストがnullされて終わるので、最初に我々は何かを取り出した。

1011
01:18:51,670 --> 01:18:56,890
そして、我々は背中に​​2つのものを入れるので、今私達のリストのサイズは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
[ボーデン]うん。だから我々は、リンクされたリストを持っている場合、

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
一度trueまたはfalseを返す前に、我々はする必要が

1037
01:20:53,880 --> 01:20:57,360
私達のリンクリストを反復処理し、常にダウンここで、私は推測する

1038
01:20:57,360 --> 01:21:03,900
我々curが右と等しくない場合、今我々が解放したい、それを追加

1039
01:21:03,900 --> 01:21:09,600
電流ので、まあ、我々は完全リストについて忘れたのでは？ Yeah。

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
そして、我々がtrueを返す場合には、我々は反復する必要がありますか

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]