[Powered by Google Translate] [第7節：より快適]
[ロブボーデン] [ハーバード大学]
[これはCS50です] [CS50.TV]
かしこまりました。だから、私は私の電子メールで述べているような
これは、バイナリツリーを多用するセクションであることを行っている。
しかし、それは多くの質​​問がありません。
だから我々は試してみて、それぞれの質問を引き出すつもりだ
そして物事のすべての最善の方法の痛みを伴う詳細に入る。
だから右の初めに、我々は、二分木とかのサンプル図面を通過します。
そこでここでは、 "バイナリツリーはリンクリストと同様のノードを持っていることを忘れないでください
左側の子 'のいずれか1つではなく、ポインタのを除いて、2つがあります
そして右の "子"のための1。 "
、ちょうどリンクリストのようなものですバイナリツリーがそう
構造体を除いて、2つのポインタを持っているとしている。
3ポインタを持っているとしているトライナリ木は、、あります
ただ一般的なポインタを持っているn分​​木がありますが、
あなたは、次に持ってするのに十分な大きさにmallocする必要があることが
可能性のあるすべての子どもたちに十分なポインタ。
だからバイナリーツリーは、ちょうど2つの定数を持っていることを起こる。
必要な場合は、単項ツリーとしてリンクされたリストを与えることができ、
しかし、私は誰もがそれを呼び出すことはないと思う。
"バイナリツリーノードのボックス·アンド·矢印図を描く
それぞれの子のポインタがnullであるネイトの好きな数字、7を含む。 "
だからiPadのモード。
>> それはかなり簡単になるだろう。
私達はちょうどノードを持っているつもりです、私は正方形として描画します。
と私はここで値を描画します。
だから値が、ここに行きます
その後ダウンして、ここでは左の左ポインタと右に右にポインタがあるでしょう。
それは左と右、ポインタ名コールする慣例ので、それは非常によく似ている。
これらの両方がnullであることを行っている。
それはちょうどnullになり、それはちょうどnullになります。
オーケー。だからここに戻っています。
"リンクされたリストでは、我々は唯一のポインタを格納する必要がありました
全体リンクリスト、またはリスト全体を覚えているために、リスト内の最初のノードに。
同様に、木々が、我々は唯一のポインタを格納する必要が
ツリー全体を覚えておくために、単一のノードに。
このノードは、ツリーの "ルート"のcalleです。
前からダイアグラム上に構築するか、新しいものを描く
もしバイナリツリーのボックス·アンド·矢印の描写を持っていることなど
値7、次に3左で、と
その後9右に、その後6 3の右側にある。 "
私は私の頭の中ですべてのことを思い出すことができるかどうかを確認してみましょう。
だから、これはここに私たちの根本アップになるだろう。
我々は、どこかで我々は根を呼ぶだろうと何かをいくつかのポインタを持っています
そしてそれはこの男を指している。
ここで、新しいノードを作成し、
我々は左に、3を何を持っていますか？
3新しいノードがそう、それが最初にヌル点。
私はちょうどNを置くことにしましょう
今、私たちは7の左に行くことにしたい。
だから我々は今、この男を指すように、このポインタを変更してください。
そして、我々は同じことを行う。我々はここで9にしたい
これは、最初は単にnull言う。
我々は、9に、このポインタは、ポイントを変更するつもりだ
そして今我々は3の右に6を入れたい。
6を作る - だから、になるだろう。
そして、その男はそこに指します。
オーケー。だからすべてだそれは何を私達に求められます。
>> それでは、いくつかの用語の上に行くことができます。
我々はすでに木の根元には、ツリーの最上位ノードであるかについて話しました。
7を含む1。ツリーの一番下にあるノードは葉と呼ばれます。
ちょうどその子としてnullを持つすべてのノードはリーフです。
だから、我々のバイナリツリーが1つのノードであれば、可能ですが、
木は葉であり、それはそれだと。
"木の 'height'はあなたが作らなければならホップ数です
上から葉に取得します。 "
我々は、第二​​に、に違いを買ってあげる
バランスとアンバランスバイナリツリー間、
この木が、今のところ、全体の高さ
私は3だと思いますが、あなたは、ホップ数をカウントする場合
あなたが9に到達するために行う必要があり、それは実際に2の高さのみです。
現在の段階では、アンバランスのバイナリツリーです
それは関連性があるとなったとき、私たちはバランスの話でしょう。
だから今我々は言葉で、ツリー内のノードについて話すことができる
ツリー内の他のノードからの相対。
それで、今、私たちは、両親、子供、兄弟、先祖、子孫を持っています。
彼らは何を意味するのか、かなり常識です。
私たちが要請すれば - それは両親。
だから3の親は何ですか？
[学生] 7。 >>うん。親はただあなたを指して何になるだろう。
その後、7の子は何ですか？
[生徒] 3と9。 >>うん。
"子供"は文字通り、子供を意味していることに注意してください
それは孫のようなので、適用されない6がそう。
しかし、その後、私たちは子孫を行けば、そう7の子孫は何ですか？
[学生] 3,6,9。 >>うん。
ルートノードの子孫は、ツリー内のすべてのものになるだろう
多分を除いて、ルートノード自体は、子孫と考えるしたくない場合。
そして最後に、祖先がいるので、反対方向だ。
だから6の祖先は何ですか？
[生徒] 3と7。 >>うん。 9が含まれていません。
それだけで根に直接系統背中
あなたの先祖であることを行っている。
>> "我々は、バイナリツリーはツリーの各ノードの場合は"注文し 'ていると言う
左側に、そのすべての子孫は低い値を持つ
と右側のもののすべては、より大きな値を持っています。
たとえば、上記のツリーが注文しましたが、それが唯一の可能な秩序配列ではありませんされています。 "
私たちは、その前に、
順序付けられたバイナリツリーも二分探索木として知られています。
ここでは、それを命じたバイナリツリーを呼び出すことが起こる
しかし、私は聞いたことがないそれは、順序付けられたバイナリツリーの前に呼び出さ
とクイズで、我々ははるかに二分探索木を置く可能性が高い。
彼らは1と同じ、だ
、それはあなたがバイナリツリーと二分探索木の区別が認識が重要です。
バイナリツリーは2つだけを指している木です。
各ノードには、二つのことを指しています。
それが指す値についての推論はありません。
それが二分探索木なのでだから、こっちのように、
我々は、我々が行けば7の左ことを知っている
その後、我々はおそらく到達できることをすべての値
7の左行くことによって、7未満でなければならない。
7未満のすべての値は3と6であることに注意してください。
それらは7の左側にすべてのです。
我々は7の右側に移動しても、すべてが、7よりも大きくなければならない
そう9は7の右側にあるので、我々は良いです。
これは、二分木の場合には該当しません
通常のバイナリツリーの我々だけで、左、上、7時に3を持つことができます
7の左から9;全く全く値の順序はありません。
それが面倒で不要なので、今、私たちは実際に、これを行うことはありません
しかし、 "あなたが考えることができる限り多くの順序木を描画しよう
番号7、3、​​9、および6を使用。
明確な取り決めがいくつありますか？それぞれの高さは何ですか？ "
>> 我々は、カップルを行うだろうが、主なアイデアはある
これは決して、これらの値を格納したバイナリツリーのユニークな表現です。
いくつかのバイナリ7を含むツリー、3、6、9、我々が必要とするすべてである。
別の可能性のある有効なものは、根が3であるだろう
左に行くとそれは6だ、左に行くとそれは7ですが、
左に行くと、それは9です。
それは完全に有効な二分探索木である。
それだけでリンクリストのようなものですので、それは非常に有用ではありません
これらのポインタのすべてがちょうどnullです。
しかし、それは有効なツリーです。うん？
[生徒]の値が右に大きくなければならないか？
またはこれは - ？ >>これらは、私は他の道を行くことを意味した。
も用意されています - うん、それを切り替えてみましょう。
9、7、6、3。大漁。
それはまだ二分木探索を行うことになっているものに従わなければならない。
だから左にすべては任意のノード以下にする必要があります。
私達はちょうど、言う、この6を移動させ、それをここに置くことができます。
いいえ、私たちはできません。なぜ私はそれをやり続けるのですか？
やってみましょう - ここでは6であり、ここで7は、3から6ポイントです。
これはまだ有効な二分探索木である。
私がアレンジを考え出すことができるかどうかを確認してみましょう - 私が間違っている場合はどうでしょう。
うん、大丈夫。だから、この木を使って何が間違っている？
私はすでにあなたにそれで何かが間違っているというヒントを与えてくれたと思います。
なぜ私はそれをやり続けるのですか？
オーケー。これは合理的に見えます。
我々は、各ノードを見れば、7のように、その後7の左側に3です。
だから我々は、3を持って、3の右にあるものは6です。
あなたは6を見ればと、6の右にあるものは9です。
では、なぜこれが有効な二分探索木ではありませんか？
[学生] 9は7の左側にまだある。 >>うん。
それはあなたがおそらく7の左に行くことによって達することができるすべての値が7未満であることが真でなければなりません。
我々は7の左に行くなら、私たちは3を取得し、我々はまだ6を得ることができ、
我々はまだですが、7未満を行ったことにより、9に取得することができます
私たちは、7より大きいの番号を取得できないようにする必要があり。
だから、これは有効な二分探索木ではありません。
>> 兄は実際に面接の質問があった
つまり、コードまで検証するために何かをただ、基本的にはこれだった
木は二分探索木であるかどうか、
と彼がしたので、最初のものは、ただ見て確認されました
場合、左と右が正しいことを確認し、その後、そこに反復します。
しかし、あなたはそれを行うだけではできず、追跡する必要があります
今私が行ってきたことを7の左という事実を、
このサブツリーのすべてが7未満でなければなりません。
正しいアルゴリズムが追跡する必要があります
値はおそらくインチ落ちることができる境界の
我々はそれらのすべてを通ることはありません。
すてきな漸化式があるが、
我々はそれらをもらっていない、あるいは、我々はそれらを取得することはありませんが、
実際にいくつあるかを定義する。
だから、それらの14があります。
あなたが数学的にそれを行うだろうかというアイデアは、似ています
あなたは、ルートノードになるように任意の単一のものを選ぶことができ、
そして私は、ルートノードであることが7を選ぶ場合
その後、私の左のノードであっても行くことができますいくつかの数字が言うには、、ありますが、
そして私の右側のノードになることができるいくつかの数字がありますが、
しかし、私はその後、左に行くことができる量を合計数字をnしている場合
1 - プラス右に行くことができる量はnです。
だから、残りの番号の、彼らは左または右のいずれかに行くことができなければなりません。
それは、私は、最初の3を置けばすべてが左に行かなければならない、ということは困難と思われる
私は7を入れた場合は、その後いくつかのものは左に行くことができますし、いくつかのものは右に行くことができます。
そして、最初の'3 'で私は右に行くことができるすべてのものを意味した。
それは本当にです、あなたは同様にそれについて考える必要があり、
どのように多くの物事は、ツリーの次のレベルに行くことができます。
または、それらのすべてを描くことができ、そしてそれは14であることが出てくる
その後は、14を得るでしょう。
>> ここに戻って、
我々はそれらを介して検索することもできますので、 "順序付き二分木は涼しいです
ソートされた配列に対して検索すると非常によく似た方法インチ
そうするために、我々は、ルートから始まり、ツリーの下の私達のように動作
葉に向かって、我々が探している値に対して、各ノードの値をチェックする。
現在のノードの値は、我々が探している値よりも小さい場合は、
あなたは、ノードの右の子の隣に移動します。
そうしないと、ノードの左の子に行く。
いくつかの時点で、次のいずれかを、あなたが探している値を見つけることができます、またはあなたは、nullに実行されます、
値を示すと、ツリーではありません。 "
私たちは前に持っていたツリーを再描画する必要があり、それが第二を取るよ。
しかし、我々は6、10、1、ツリーにあるかどうかを調べたい。
だからそれが何であったか、7、9、3、6。オーケー。
あなたが検索したい数字は、我々は6を見てみたい。
これがどのようにアルゴリズムの仕組みを教えてください。
さて、私達はまた私達の木にはいくつかのルートポインタを持っています。
そして、我々はルートに行くと言うでしょう、我々が探している値に等しく、この値ですか？
だから我々は6を探しているので、それは等しくありません。
ので、6が7未満である、大丈夫、だから我々は続けるし、今我々は言う。
それは我々が左に行きたいわけではない、あるいは、我々は右に行きたいですか？
[学生]左。 >>うん。
それはかなり簡単です、あなたがしなければならないすべては、ツリーの一つの可能​​なノードを描画されている
そしてその後は無関心 - あなたの頭の中で考えようとする代わりに、
大丈夫、それが少ないのなら、私は、左に行くか右に行くのですか
ちょうどこの写真を見て、それは私が左に行かなければならないことは非常に明らかだ
このノードには、私が探している値よりも大きい場合。
だから、今私は3時だけど、左に進みます。
私がしたい - 3は6です私が探している値よりも小さい。
だから我々は右に行き、そして今、私は、6時に終わる
これは私が探している値ですので、私の場合はtrueを返します。
私が探しに行くよ隣の値は10です。
オーケー。ルートをたどるつもり - ことを断つ - 10だから、今、しようとしている。
さて、10は7以上であることを行っているので、私は右に見てみたい。
私はここに来たいと思い、10は9より大きいことになるだろう、
ので、私は右に見てみたいつもりです。
私がここに来たが、こっちの今私はヌルにいます。
私はnullをヒットした場合はどうすればよいですか？
[学生]はfalseを返します？ >>うん。私は10を見つけられませんでした。
1は、ほぼ同一のケースになるだろう、
それだけで反転することになるだろう除いて、代わりの探して
右側の下、私は左側を下に見てするつもりです。
>> 今、私は、我々は実際にコードを取得すると思います。
、CS50アプライアンスを開くと、そこにあなたの方法をナビゲートする - ここはどこだ
しかし、あなたはまた、単にスペースでそれを行うことができます。
それはおそらく空間でそれを行うことが理想的です
我々は宇宙で働くことができるので。
"まず、int型の値を格納したバイナリツリーノードのための新しい型定義を必要とするでしょう。
以下のtypedefの定型文を使って、
バイナリツリーのノードのための新しい型定義を作成します。
あなたが動けなくなる場合。 。 。 "何とか、何とか、何とか。オーケー。
それでは、ここで決まり文句を入れてみましょう
typedefは構造体ノード、およびノー​​ド。うん、大丈夫。
だから我々は我々のノードにするつもりだ分野は何ですか？
[学生] intとし、2つのポインタ？
>> Intの値が、2つのポインタ？どのように私はポインタを書くのですか？
[生徒]のStruct。 >>私は、ええ、そう構造のノード*左ズームインべき
とstructノード*右。
そして、前回の議論を覚えている
これは意味をなさないことを、これは意味がありません
これは意味をなさない。
この再帰的な構造体を定義するために、そこにすべてを必要としています。
わかりましたので、それが私達の木のように見えるように何が起こっている。
我々は三つの部分から成るツリーを実行した場合、そのノードはB1、B2、構造ノード* B3、のように見えるかもしれません
bは分岐である - 実際に、私はより多くのそれは、真ん中、右が、何を残したと聞きました。
我々は唯一の左、右のように、バイナリを気遣う。
"今、ツリーのルートのためのグローバル·ノード*変数を宣言します。"
だから我々はそれをするつもりはない。
、物事は少し難しく、より一般化させるためには
我々は、グローバル変数ノードを持ちません。
その代わりに、主に我々は、我々の全てのノードのことを宣言します
そして我々が実行して起動したときに、その下のことを意味し
私たちは、機能と私たちのinsert関数が含まれています
代わりに私たちのCONTAINSのちょうどこのグローバルノード変数を使用して機能、
我々はそれを処理したい、それが引数としてツリーを取る必要があるとしている。
グローバル変数を持つことは、物事を簡単にすることになっていた。
私たちは、物事を難しくしようとしている。
さて、この種のことを行うには分かそこらを取る
場所内のメインのこのツリーを作成したい、そしてそれはすべてあなたがしたいです。
試してみて、あなたの主な機能は、この木を構築する。
>> オーケー。だからあなたも、まだ全体の木道を構築している必要はありません。
しかし、誰も私がアップできるようなものを持っている
1つがそのような木を構築を開始する方法を示しますか？
[学生]誰かのバンギング、出ようと。
[ボーデン]彼らの木の構築と快適な誰ですか？
[学生]確かに。それが行われるわけではありません。それは結構です。>>我々だけで完了することができます -
ああ、あなたはそれを保存することができますか？めでたしめでたし。
そこでここでは持っている - ああ、私は少し切り落としています。
私は、ズームインのですか？
でズームイン、スクロールアウト。私は疑問を持っている。>> >>うん？
[学生]は、構造体を定義するときに、何かに初期のようなものはありますか？
[ボーデン]いいえ>>オーケー。だから、初期化しなければならないでしょう -
[ボーデン]あなたが定義するか、構造体を宣言するとき号、
これはデフォルトでは初期化されていない、あなたはint型を宣言した場合、それだけのようなものだ。
それはまったく同じことだ。それは個々のフィールドのそれぞれのようなものだ
それにゴミ値を持つことができます。または構造体を宣言する - >>そして、それは定義することが可能である
それがないような方法でそれらを初期化しますか？
[ボーデン]はい。だから、ショートカット初期化構文
のように起こっている -
我々はこれを行うことができる2つの方法があります。私たちはそれをコンパイルすべきだと思う
Clangのもこれを行うことを確認します。
構造体に来る引数の順序、
あなたはこれらの中括弧の内側の引数の順序として置く。
あなたが9にそれを初期化したいのであれば、左、右、nullになるヌルさと
それが9、NULL、NULLになります。
、代替手段であり、編集者は、この構文を好きではない
そしてそれは、私は新しいブロックをしたいと考えている
しかし代替案は何かに似ている -
ここで、私は新しい行に置くことにしましょう​​。
あなたが明示的に言えることは、私は正確な構文を忘れてしまった。
それで、あなたは明示的に、名前によってそれらを対処し、言うことができる
C、または。値= 9、左= NULLを。
私は、カンマであるため、これらの必要性を推測している。
これを行わない。右= NULLのため、この方法
実際には、構造体の順序を知っておく必要があります
そしてあなたがこれを読んでいるとき、それははるかに明示的な
値に初期化されていることについて。
>> これは、物事の一つであることを起こる -
そう、ほとんどの部分は、C + +でCのスーパーセットである
あなたは、C + +、それはコンパイルする必要がありますにそれを移動し、Cコードを取ることができます。
これは、C + +サポートしていないことの1つなので、人々はそれをしない傾向があります。
それは人々がそれをしない傾向がある唯一の理由かどうかはわからない、
しかし、私はそれを使用するために必要な場合は、C + +とので、私はこれを使用することができませんでしたで動作する必要がありました。
その何かのもう一つの例は、C + +では動作しません
どのようにmallocは、技術的に "は、void *"を返す
あなただけは、char * X = mallocの何でも言うことができる
そしてそれは自動的にchar *にキャストされます。
その自動キャストはでは行われません、C + +。
コンパイルされないでしょう、そしてあなたは、明示的に言う必要があるだろうと
char *には、malloc、何でも、char *型にキャストする。
CおよびC + +に同意しないことはたくさんあり​​ません
しかし、それらは2つです。
だから我々は、この構文を使用して行くつもりです。
しかし、我々はその構文で行かなかった場合でも、
何か - これで間違っているかもしれない？
[学生]私は逆参照する必要はありませんか？ >>うん。
、矢印が暗黙の逆参照を持っていることを覚えている
それで我々はただ、構造体を扱う場合
我々は、使用したい。構造体のフィールドの内部で取得します。
そして、我々は、矢印を使用する唯一の時間は、我々がやりたいときである -
よく、矢印は同等です -
それは私が矢を使用した場合、それが意図したであろうものだ。
すべての矢印手段は、間接参照、これは、今私は、構造体にいれて、私はフィールドを取得することができます。
直接または間接参照するフィールドを取得し、フィールドを取得 -
私はこれが値であるべきであると思います。
しかし、ここで私は、ちょうど構造体ではなく、構造体へのポインタを扱っている
そして私は、矢印を使用することはできません。
しかし、この種のことは、我々は、すべてのノードのために行うことができます。
オーマイゴッド。
これは、6,7、および3です。
それから私達は私達の木に支店を設定することができ、私達は7を持つことができます -
持っている私たちは、その左側には、3を指している必要がありますすることができます。
だから我々はそれをどのように行うのですか？
[学生、不明朗] >>うん。ノード3のアドレスは、
そしてあなたがアドレスを持っていなかった場合、それは単にコンパイルできません。
しかし、これらは次のノードへのポインタであることを覚えておいてください。
右は9を指している必要があります
と3は6〜右側に指している必要があります。
私は、これはすべてのセットだと思います。ご意見やご質問？
[学生、不明朗]根が7になるだろう。
我々は、ただのノードを言うことができます* ptrは=
またはroot =＆node7。
>> 私たちの目的のために、私たちは、インサートを扱うことになるだろう
ので、我々はこのバイナリツリーに挿入する関数を記述するつもりだ
とインサートは、必然的に、このツリーの新しいノードを作成するには、mallocを呼び出すために起こっている。
だから物事が事実と散らかっ得ようとしていることをいくつかのノード
スタック上に現在
と、他のノードは、我々はそれらを挿入したときに、ヒープ上に終わる予定です。
これは完全に有効ですが、唯一の理由
我々は、スタック上でこれを行うことができるしている
それは我々が知っているような不自然な例だからである
ツリーは、7、3、6、9のように構成されることになっています。
我々はこれを持っていなかったなら、私たちは最初にmallocする必要はありません。
我々は少し後で見るように、我々はmalloc'ingされるべきである。
今のところ、これは、スタック上に置くために完全に合理的だ
しかし、ここではmallocの実装にこれを変更することができます。
だから、これらの各々は、今のようなものになるだろう
ノード* node9 =はmalloc（sizeofの（ノード））。
そして今、我々は我々のチェックを行う必要があるとしている。
（node9 == NULL）の場合 - 私はそれを望んでいなかった -
1を返し、そして今それがポインタだから、我々は、node9->を行うことができます
値= 6、node9->左= NULLの場合、
node9->右= NULLの場合、
そして我々は、これらのノードのそれぞれにそれを行う必要があるとしている。
だから代わりに、のは、別の関数の中にそれを置くことができます。
そのノード* build_node呼び出してみましょう、
そしてこれは我々がハフマン符号化のための提供するAPIに似ています。
私たちは、木のためにあなたに初期化関数を与える
それらの木と森のために同じもののためとデコンストラクタ "関数"。
>> そこでここでは、初期化関数を持っているつもりです
ちょうど私達のためのノードを構築する。
そして、それはまさにこのようにかなり見えるようになるだろう。
と私も怠け者になるだろうと、変数の名前を変更していないよ
node9はもはや意味をなさないのに。
ああ、私はnode9の値が6であってはいけないと思います。
今、私たちはnode9を返すことができます。
そしてここで我々はnullを返す必要があります。
誰もがそのビルドノードの機能に同意するか？
だから今我々は単に与えられた値とNULLポインタを備えた任意のノードを構築することを呼び出すことができます。
今、私たちはそれを呼び出すことができ、我々は、ノード* node9 = build_node（9）を行うことができます。
と行いましょう。 。 。
6、3、7、6、3、7。
そして今、我々は、同じポインタを設定したい
今以外のすべては、ポインタの面ですでにだ
そう、もはやのアドレスを必要としません。
オーケー。だから私はやってみたい最後のことは何ですか？
私がやっていないことに、エラー·チェックがあります。
ノードリターンに何を建てるのですか？
[学生、不明朗] >>うん。 mallocが失敗した場合は、nullを返します。
だから私はなまけてそれぞれの条件を行うのではなく、ここでそれを置くつもりです。
もし（node9 == NULLの場合、または - さらに単純に、
これはただそうでない場合node9に相当します。
そうでない場合node9ない、またはnode6ない、またはnode3でない、またはnode7だから、1を返します。
たぶん私たちは失敗したmalloc、または何かを印刷する必要があります。
[学生]もnullに等しい偽か？
[ボーデン]任意のゼロ値はfalseです。
だからnullはゼロ値である。
ゼロはゼロの値である。 Falseの場合、ゼロ値です。
任意の - かなりわずか2ゼロの値がNULLとゼロであり、
falseはゼロとして定義だけハッシュです。
我々はグローバル変数を宣言しない場合は、それも適用されます。
私たちがやった場合は、ここでノード*の根を持っている
その後 - グローバル変数のいいところは、彼らは常に初期値を持っているということです。
つまり、ここでの機能は、どのように内部の真実ではない
我々が持っている場合は、のように、ノード*またはノードx。
私たちは何x.value、x.whatever、見当がつかない
あるいは、我々はそれらを印刷することができ、彼らは任意である可能性があります。
それは、グローバル変数の真実ではない。
だからノードまたはルートノードx。
デフォルトでは、グローバルのすべてが、明示的にいくつかの値に初期化されていない場合は、
その値としてゼロ以外の値を持っています。
そこでここでは、ノード*ルートは、明示的に何かにそれを初期化しない、
ので、そのデフォルト値はポインタの値がゼロである、nullになります。
xのデフォルト値は、x.valueがゼロであることを意味するために起こっている
x.leftがNULLで、x.right nullです。
それは構造体ですのでので、構造体のすべてのフィールドはゼロ値となります。
我々は、しかし、ここであることを使用する必要はありません。
[学生]構造体は、他の変数とは異なりますし、他の変数は
ゴミの値、これらはゼロですか？
[ボーデン]その他の値も。だからxに、xがゼロになります。
それがグローバルスコープである場合、それは初期値があります。オーケー。>>
[ボーデン]のどちらか、あなたがそれまたはゼロを与えた初期値。
私はこのすべての世話をしていると思います。
>> オーケー。だから質問の次の部分は、尋ね
"今、私たちは、含まれていると呼ばれる関数を書きたい
boolのプロトタイプを持つint型の値を含んでいます。 "
我々は、boolはint型の値が含まれている何をするつもりはありません。
我々のプロトタイプは次のように起こっている
boolは（int型の値が含まれています。
そして、我々はまた、それをツリーに合格するつもりだ
それは、その値を持っているかどうかをチェックすべきである。
だからノード*ツリー）。オーケー。
そして、我々は、のようなものでそれを呼び出すことができます
多分私達はprintfや何かしたいと思う。
6、私たちのルートを含みます。
1、またはtrueを返す必要があること
含まれているのに対し、5ルートはfalseを返す必要があります。
だから、これを実装する2つ目を取る。
あなたはどちらか、または反復して再帰的にそれを行うことができます。
我々は物事を設定している方法の良いところは、ということです
それははるかに簡単に私たちの再帰的な解決策を招
よりグローバル変数の方法はなかった。
我々だけである場合は、int型の値が含まれているため、我々は、サブツリーの下に再帰処理の方法がありません。
私達は私達のためのサブツリーを再帰的にダウンして別のヘルパー機能がなければならないでしょう。
しかし、我々は引数として木を取るためにそれを変更しましたので、
、それは常に、最初の場所でされている必要があります
今、我々はより簡単に再帰することができます。
だから反復または再帰的な、我々は、両方の上に行くよ
しかし、我々は、再帰が非常に簡単にされて終わることがわかります。
オーケー。誰もが我々が働くことができる何かを持っていますか？
>> [学生]私は反復解法を持っている。 >>すべての権利は​​、反復。
さて、これはよさそうだ。
だから、それを通じて私たちを歩きたい？
[学生]確かに。だから私は、ツリーの最初のノードを取得する一時変数を設定します。
そして私はちょうど、tempが等しく、nullをされていませんがループスルー
そう木に残っているときに、私は推測する。
と値がtempは、を指している値と等しいかどうかを
それはその値を返します。
それは右側または左側上にある場合は、それ以外の場合はチェックします。
あなたは今までにない多くの木があるような状況を取得する場合は、
それはループを抜けてfalseを返します - それが返されます。
[ボーデン]オーケー。だからそれは良いようだ。
誰もが何かコメントはありますか？
私はすべての正当性のコメントを持っていません。
我々が行うことができます一つのことは、この男だ。
ああ、それは少し長めに行くつもりだ。
私はそのアップを修正します。オーケー。
>> 誰もが三がどのように動作するかを覚えておきましょう。
確かに過去に存在クイズされている
それは、あなたに三項演算子を使用して関数を与える
および三元を使用していない何かをする、言う、これを翻訳する。
だから、これは、私が三を使用するように思うだろうというときの非常に一般的なケースです
いくつかの条件は、何かに変数を設定した場合どこに
他に何か他の人に同じ変数を設定します。
非常に頻繁にこのようなものに変換することができるものは、そのだ
どこでこれにその変数を設定する - あるいは、まあ、これは本当ですか？そして、この、他のこの。
[学生]右、trueの場合は最初のものはありますか？
[ボーデン]うん。私はいつもそれを読む方法ですが、tempは、一時値よりも大きい値に等しい
この、他のこの。それは、質問を求めている。
それは大きいですか？その後、最初のことを行う。 elseは2番目のことを行う。
私はほとんど常に - コロンは、私はちょうど - 私の頭の中で、私は他に読んだ。
>> 誰もが再帰的な解決策がありますか？
オーケー。我々がしようとしているこの1 - それはすでに偉大かもしれない、
しかし我々はそれをより良いものにするつもりだ。
これはかなり正確に同じ考えです。
それだけだ、まあ、あなたは説明したいと思いますか？
[学生]確かに。だから我々は、木が最初にnullでないことを確認しています
木がnullの場合、それは我々がそれを見つけていないのでfalseを返すために起こっているからです。
木がまだあるなら、私達は入る - 値は現在のノードである場合は、まずチェックしてください。
左または右に我々はそれが再帰的である場合にtrueを返し、そうでない場合。
そのサウンドは適切か？ >> MM-うーん。 （協定）
だから、これはほとんどであることに気づく - 反復解法と構造的に非常に似ています。
それは代わりに再帰し、我々は、whileループを持っていたというだけです。
そして木が等しく、nullをしませんここで、ベースケース
我々は、whileループから抜け出しする条件だった。
彼らは非常に似ている。しかし、我々はさらに一歩を踏み出すことになるだろう。
今、私たちはここで同じことを行う。
我々はこれらの行の両方で同じものを返そうとしているに気づく、
一つの引数を除いて異なっている。
だから我々はその三元にするつもりだ。
私はオプションの何かをヒット、それはシンボルを作った。オーケー。
だから我々は返却しようとしているが含まれています。
これは、それは、ズームイン、よく、複数行になるようになってきている。
通常、文体のものとして、私は多くの人ではないと思う
矢印の後にスペースを入れますが、私はあなたが一貫している場合、それは大丈夫だと思う。
値がツリーの値未満である場合、私たちは、木の左に再帰したい
他では、ツリーの右に再帰したい。
だから、この外観を小さくするのステップ1であった。
この外観の小型化のステップ2 -
我々は、複数の行にこれを分離することができます。
オーケー。それは小さく見えることのステップ2は、ここにある
ので、戻り値は、ツリーの値に等しい、または何が含まれています。
>> これは重要なことです。
彼はそれがクラスの中で明示的に言った場合、私はわからないんだけど
しかし、それは、短絡評価と呼ばれています。
ここの考えは値==ツリー値です。
それがtrueの場合、これは真実であり、私たちがしたい 'または'がここに終わったものは何でも。
そうであってもこっちは何でも考えることなく、
返すつもり式全体は何ですか？
[学生]トゥルー？何かの>>うん、なぜなら真、
論理和 - 何かで真または論理和は、必ずしも真実である。
だから、できるだけ早く我々が戻り値=ツリーの値を見るように、
我々だけtrueを返すつもりだ。
でも、再帰的にはいかないのが、さらにラインの下で含まれています。
我々は、さらに一歩を取ることができます。
リターンツリーが等しいヌルとこのすべてをしない。
それは1ライン機能しました。
また、これは短絡評価の一例です。
しかし、今では同じ考えだ -
代わりに - ので、ツリーがない場合等しいヌル - または、よく、
木が悪いケースです等しいnullを、ない場合
木がNULLの場合は、最初の条件が偽であることを行っている。
何とANDだから偽は何になるだろうか？
[学生]はFalseを返します。 >>うん。これは、短絡評価の残りの半分である
ツリーが等しく、nullをしない場合は、私たちも、どこへ行くに行くされていません -
ツリーが等しいヌルを行う場合は、次に我々は値==ツリーの値をするつもりはありません。
我々は、ちょうどすぐにfalseを返すつもりだ。
それは短絡評価していない場合ので、重要なのですが、
ツリーが等しいヌルをすれば、次に、この第二の条件は、セグメントフォールトに起こっている、
ツリー - >値はnullを間接参照しているためです。
だからそれはそれだ。これを行うことができます - 一度の転換。
これは、これでこの1行をしていない、また、非常に一般的なものです
それは、まさにここ多分、条件に共通のことではありません
しかし（ツリー！= NULL、およびツリー>の値==値）は、何かを行う場合。
これは非常に一般的な条件ではなく、持っている
2 IFSにこれを打破するために、好きな場所、ツリーヌルですか？
さて、それがnullではないので、今は値と等しいツリーの値ですか？これを行う。
代わりに、この条件は、これはseg faultをすることはありません
これがnullであることを起こる場合、それは打破されるためです。
まあ、私は、あなたのツリーは完全に無効なポインタである場合、それはまだseg faultをすることができますね
木がnullの場合、それはseg faultをすることはできません。
それがnullであった場合は、初めての場所にポインタを間接参照する前に、それは起こるだろう。
[学生]このいわゆる遅延評価ですか？
>> [ボーデン]遅延評価は、独立したものです。
遅延評価は、あなたが値を要求する以上のようなものです
あなたは、値の種類を計算するために尋ねるが、あなたはすぐにそれを必要としない。
あなたが実際にそれを必要とするまで、だから、それは評価されません。
これは、まったく同じものではありませんが、ハフマンpset内、
それは我々が "レイジー"を書くと言っています。
我々は実際に書き込みをバッファリングしているので、我々が行う理由は -
我々は、一度に個々のビットを書き込みたくない
または、一度に個々のバイトは、私たちの代わりにバイトのチャンクを取得したい。
我々はバイトのチャンクを持ったらすぐに、我々はそれを書こうと思います。
あなたが書くためにそれを求めるにもかかわらず - とfwriteとfreadは同じようなことを行います。
彼らはあなたの読み取りと書き込みをバッファします。
あなたはすぐに書くためにそれを求めるにもかかわらず、それはおそらくないでしょう。
そして、あなたは物事が書かれようとしていることを確認することはできません
あなたはhfclose呼ぶか何か、それがされるまで、
その後、どちらが言いますか、大丈夫、私は、私のファイルを閉じています
私はよりよい私はまだ書いていないすべてのものを書くだろうことを意味します。
それはすべてを記述する必要がありません
は、ファイルを閉じており、それが必要になるまで。
だからそれはちょうど何怠け者だ - それが起こるようになるまで待機します。
これは - 、51を取ると、あなたは、より詳細に、それに行くよ
51でOCamlのすべてが、すべてが再帰であるためです。
基本的には、解決策を反復は今のところありません。
すべてが再帰と遅延評価です
状況の多くのために重要であることを行っている
ここで、あなたがなまけて評価しなかった場合、それが意味するだろう -
例では、無限に長いなストリームです。
理論的には、1-2-3-4-5-6-7のストリームとして自然数を考えることができます
だから、遅延評価のことは問題ありません。
私は第十番号をしたいと言うなら、私は第十数まで評価することができます。
私は、百分の​​数が欲しいならば、私は百数まで評価することができます。
遅延評価がなければ、それはすぐにすべての数値を評価しようとするだろう。
あなたは、無限に多くの数字を評価していると、それだけでは不可能です。
だから状況がたくさんある場所遅延評価
物事が動くようにするだけで必要不可欠である。
>> 今、私たちは、インサートがあることを行っている場所の挿入を書き込みたい
同様にその定義に変更します。
だから今それはboolインサート（int値）です。
我々は、boolインサート（int型の値、ノード*ツリー）にあることを変更するつもりです。
我々は、実際には少しでその再度変更しようとしている、我々は、理由がわかります。
そして、だまされたと思って、build_nodeを動かしてみましょう
我々は、関数プロトタイプを記述する必要はありませんので、上記に挿入します。
あなたはどちらがインサートにbuild_nodeを使用することになるだろうというヒントです。
オーケー。その分ほどかかる。
私は、あなたがそれを取得したい場合、私はリビジョンを保存したと思う
または、少なくとも、私は今ではなかった。
私は、インサートのロジックを考えるため若干休憩したかった
あなたはそれを考えることができない場合。
基本的に、あなたは今まで葉に挿入されます。
私は1を挿入した場合、同じように、私は必然的に1を挿入するつもりです -
私は黒に変更します - I'llはこっち1を挿入することができます。
私は4を挿入した場合、または、私はここ4上を挿入したい。
だから、あなたが何をするかに関係なく、あなたはリーフで挿入されようとしていません。
あなたがしなければならないすべてはあなたがノードに到達するまで、ツリーを下に反復している
そのノードの親、新しいノードの親であるべき
その後どうかに応じて、その左または右にポインタを変更
それがより大きいか、または現在のノードよりも少ないです。
新しいノードを指すようにそのポインタを変更してください。
だから、木を切り倒し反復する新しいノードにリーフポイントを作る。
また、その前に状況のタイプを禁止している理由を考える
それが正しかったここで私は、バイナリツリーを構築場所
あなたは、単一のノードだけを見た場合、
あなたはすべての方法を反復した場合、9は7の左側にあった。
だからそれ以来、このシナリオでは不可能だ -
9か何かを挿入することを考える、非常に最初のノードで、
私は7を見に行くつもりだと私はちょうど右に行くつもりです。
だから、私はリーフに行くことによって、挿入している場合、私は何をすべきかは関係なく
し、適切なアルゴリズムを使用して葉に、
それは私が7の左側に9を挿入することは不可能になるだろう
できるだけ早く私は7を打つように私は右に行くつもりですので。
誰で開始するために何かを持っていますか？
[学生]私はありません。 >>確かに。
[学生、不明朗]
[その他学生、不明朗]
[ボーデンは]それは大歓迎だ。オーケー。説明したいと思います？
>> 我々は我々が挿入されたことを知っているので[学生]
ツリーの末尾に新しいノード、
私は繰り返しツリーループスルー
私はnullに指摘ノードに着くまで。
そして私は右側または左側のどちらかにそれを置くことを決めた
この右の変数を使用して、それはどこにそれを置くために私に言った。
そして、本質的に、私はちょうどその最後を作った -
それが作成された新しいノードへの一時ノードポイント、
値が正しかったかに応じて、左側または右側のどちらか。
最後に、私はそのテストの値に新しいノードの値を設定します。
[ボーデン]わかりましたので、私はここで一つの問題を参照してください。
これは、そこに道の95％のようなものです。
私が見ている一つの問題は、まあ、問題は誰を見ますか？
彼らはループから抜け出す際の状況は何ですか？
[学生] tempがnullの場合は？ >>うん。 tempがnullの場合、だから、ループから抜け出す方法​​です。
しかし、私はちょうどここに何をしますか？
必然的にnullである私を間接参照温度、。
tempがヌルになるまで、あなたがする必要がある他の事はただ追跡されないように、
あなたはすべての回で親を追跡したいと思います。
また、ノード*の親をしたい、私は私たちが最初にヌルでそれを保つことができると思います。
これは、ツリーのルートのための奇妙な振る舞いを持っているとしている
しかし、我々はそれに得るでしょう。
値は何でも、そしてテンポラリ=一時右より大きい場合。
しかし、我々はその、親=気温を行う前に。
または両親が常に等しくtempに行くのですか？ケースことはありますか？
tempがnullでない場合は、私は、何があって、下に移動しないつもりです
tempが親となっているノードへ。
だから親は、tempになるだろうし、私がダウンしてtempに移動します。
今すぐtempはヌルですが、nullであるものの親の親を指しています。
だからダウンここで、私は右の1に等しく設定したくない。
だから私は、そう右= 1の場合、右に移動
と私はあなたにもやってみたいと思います -
あなたが左に移動した場合は、0〜右等しく設定したいと思います。
さもないとあなたが今まで右に移動した場合。
だから右= 0。右= 1の場合、
今、私たちは、親ノードnewnode右ポインタを作りたい
他に私たちは親の左ポインタノードnewnodeを作りたい。
その上で質問がありますか？
オーケー。だから、これは我々の方法である - まあ、実際には、代わりにこれを行うための、
我々は半分あなたがbuild_nodeを使用すると予想。
ノードnewnodeがNULLの場合、その後、falseを返します。
それはそれだ。さて、これは、我々はあなたが何を期待したものです。
>> これはスタッフのソリューションは何をすべきかです。
私はそれについて行くの "正しい"方法としてこれに反対
しかし、これは完全に正常であり、それは動作します。
少し奇妙な権利です一つのことは今です
木がnullとしてオフに開始された場合、我々はヌルツリーに渡す。
私はそれはあなたがヌルのツリーを渡すの動作をどのように定義するかに依存すると思います。
私は、あなたがヌルのツリーを渡した場合と思うだろう
nullの木に値を挿入する
ただ唯一の値は、単一のノードとするツリーを返す必要があります。
人々はそれに同意しますか？あなたは、あなたが望んでいたならば、可能性
あなたはnullツリーを渡した場合
あなたはそれに値を挿入したい場合は、falseを返します。
それは、それを定義するのはあなた次第です。
その後、私が言った最初の事を行うとする -
ので、さて、あなたは、困っていることをやっているつもりだ
私たちはものにグローバルポインタを持っていた場合、それは、容易になるだろう
木がnullの場合、私たちにはないので、我々はそれについてできることは何もありません。
私たちはただfalseを返すことができます。
だから私は、挿入を変更するつもりです。
我々は、技術的にはちょうどここに、この権利を変更することができ、
それはどのように物事を反復するのは、
しかし、私は**ノードツリーを取るためにインサートを変更するつもりです。
ダブルポインタ。
これはどういう意味ですか？
代わりにノードへのポインタを扱う、
私は操作するつもりだ事は、このポインタです。
私はこのポインタを操作するつもりだ。
私は、直接ポインタを操作するつもりだ。
、ダウンを考えるので、これは理にかなっています -
まあ、今すぐこの点はnullになります。
私は何をしたいのは、NOT NULLに指すように、このポインタを操作することです。
私はそれが私の新しいノードを指すようにしたいと思います。
私はちょうど私のポインタへのポインタを追跡する場合は、
それから私は、親のポインタを追跡する必要はありません。
私はただ、ポインタがNULLを指しているかどうかを追跡することができます
とポインタがNULLを指している場合、
私がしたいノードを指すように変更します。
私はポインタへのポインタを持っているので、私はそれを変更することができます。
今これを見てみましょう。
あなたは、実際にはかなり簡単に再帰的にそれを行うことができます。
我々はそれをしたいですか？
はい、我々はありません。
>> 再帰的にそれを見てみましょう。
まず、どのような私たちのベースケースになるだろうか？
ほとんど常に私たちのベースケースは、しかし実際には、これはトリッキーの一種である。
まず最初のものは、もし（木== NULL）
私たちはただfalseを返すつもりだと思います。
これはあなたの木がNULLとは異なります。
これはあなたのrootがNULLポインタへのポインタである
これは、ルート·ポインタが存​​在しないことを意味します。
だからダウンここで、私がしなければ
ノード* - ちょうどこれを再利用してみましょう。
*ルートノード= NULL
そして私は、のような何かをすることで、挿入を呼び出すつもりだ
＆ルートに4を挿入します。
だから＆根、根はノード*の場合
その後＆rootはノード**になるだろう。
これは有効です。ここまでこのケースでは、木、、
または挿入 - 木がnullではありません。
ここに。ツリーはnullではありません。*木がnullの場合、罰金となる
*ツリーがnullの場合、私はそれを操作できるため、
今私はそれを指すように欲しいものを指すように設定します。
木がnullである場合でも、それは私はちょうどここに降りてきて言ったヌルを意味します。
それは意味をなさない。私はそれで何もすることはできません。
木がnullの場合、falseを返します。
だから私は基本的には、すでに私たちの本当のベースケースが何であるかを語った。
そして、どのようなことがあることを行っている？
[学生、不明朗]
[ボーデン]はい。だから（*ツリー== NULL）の場合。
これはこっちのケースに関し
私の赤いポインタがポインタである場合、私は、に焦点を当てている場所、
私は、このポインタに焦点を当てているようなので、今私は、このポインタに焦点を当てています。
今私は、このポインタに焦点を当てています。
もしそうなら私のノード**です私の赤いポインタ、
これまでです - *は、私の赤いポインタは、これまでにnullである場合、
それは私が私が指しているポインタに焦点を当てている場合で午前ことを意味します -
これは葉に属しポインタです。
私は私の新しいノードを指すように、このポインタを変更したい。
こっちに戻ってくる。
私newnodeが、ただのノード* N = build_node（値）となります
その後、nは、n = NULLの場合は、falseを返します。
他には、ポインタが現在指しているものに変更したい
現在、私たちの新しく建てられたノードを指すように設定します。
我々は、実際にここでそれを行うことができる。
代わりにNを言う、我々は言う*ツリー= *ツリー場合。
誰もがそれを理解できますか？そのポインタのポインタを扱うことによって、
我々はそれらを指すようにしたいものを指すようにNULLポインタを変更することができます。
それが私たちのベースケースです。
>> 現在、私たちの再発、または当社の再帰、
我々が行ってきた他のすべての再帰に非常に似ているために起こっている。
我々は、値を挿入するつもりだ
そして今、私は再び三を使用するつもりですが、どのような私たちの条件があることを行っている？
我々は、左または右に行きたいかどうかを決定するために探しているそれは何ですか？
別のステップでそれをやってみましょうの。
場合（値<）何？
[学生]ツリーの値はありますか？
[ボーデン]だから私は現在だと覚えている -
[学生、不明朗]
[ボーデン]ええ、そう右ここに、この緑の矢印と言ってみましょう
ツリーは現在あるものの例ですが、このポインタへのポインタです。
だから私は3へのポインタへのポインタのことを意味しています。
デリファレンスは二回良い感じだった。
私に何をする - どのように私はそれを行うのですか？
[学生]は一度逆参照し、次に矢印をそのようにしますか？
[ボーデンは]だから（*木）、一回間接参照です - >値
私が間接的に指していることに、ノードの値を与えるために起こっている。
だから私はまたあなたがそれを好むなら、それがtree.value **書き込むことができます。
作品のどちらか。
それがそうであるなら、私は値を使用してINSERTを呼び出す必要があります。
そして、どのような私の更新されたノードは、**になるだろうか？
私は左に行きたいので、** tree.leftは私の左になるだろう。
そして、私はその事へのポインタが欲しい
そう左が終了した場合、最大NULLポインタであることを、
私は私の新しいノードを指すように修正することができます。
>> そして、他のケースは非常に似ていると考えることができる。
実際に今、その私の三元を作ってみましょう。
値<（**木）場合に値を挿入します。値。
その後、我々は、左に私たちの**を更新したい
他に、我々は右に私たちの**を更新したい。
[学生]は、ポインタへのポインタを取得していますか？
[ボーデン]ことを覚えておいてください - ** tree.rightがノード星です。
[学生、不明朗] >>うん。
** tree.rightこのポインタか何かのようです。
だから体へのポインタを取ることによって、それは私が欲しいものを与える
あの男へのポインタ。
[学生]我々は二つのポインタを使用している理由を私たちは何度も何度も行ってもらえますか？
[ボーデン]うん。だから - いや、あなたは前にすることができ、その解
二つのポインタを行わずにそれを行うための方法でした。
あなたは、2つのポインタを使用して理解できるようにする必要があります
これはクリーンなソリューションです。
また、私の木とどうなるかを、ことに気づく -
私のルートがnullだった場合はどうなりますか？私は右ここにこのケースを行う場合はどうなりますか？
だからノード*ルート= NULL、＆ルートに4を挿入します。
何ルートはこの後になるだろうか？
[学生、不明朗] >>うん。
根の値は4であることを行っている。
ルート左側がnullであることを行っている、ルート権がヌルであることを行っている。
我々はアドレスによってルートを通過しなかった場合には、
我々はルートを変更しませんでした。
場合であっツリー - ルートがnullだった場合、
我々だけでfalseを返す必要がありました。我々は何ができることは何もありません。
私たちは、空のノードをツリーに挿入することはできません。
しかし、今、私たちすることができ、我々は、ちょうど1つのノードツリーに空の木を作る。
これは通常、それが動作するようになっていると期待される方法です。
>> さらに、これよりも大幅に短くなっている
また、親を追跡し、そのためには、すべての方法を反復します。
さて、私の親を持っている、と私はちょうど何に私の親の右側にポインタを持っている。
我々は繰り返しこれをしなかった場合は、代わりに、それは、whileループと同じ考えになると思います。
しかし、その代わりに私の親ポインタに対処することの、
代わりに私の現在のポインタがものになるだろう
私は、直接私の新しいノードを指すように変更していることに。
私はそれが左を指しているかどうかに対処する必要はありません。
私はそれが右を向いているかどうかに対処する必要はありません。
それはちょうど、このポインタが何であれ、私は私の新しいノードを指すように設定するつもりだ。
誰もがそれがどのように機能するかを理解できますか？
なぜ我々はこのようにそれをやってみたいんではない場合は、
しかし、少なくとも、この解決策として、作品？
[学生]我々は、trueを返すのですか？
[ボーデン]右ここで、おそらくですね。
我々はそれを正しく挿入した場合、trueを返します。
そうでなければ、ダウンここに私達はリターンを挿入何でも返すようにするつもりだ。
>> そして、この再帰関数についての特別な何ですか？
それは、そうある限り、我々はいくつかの最適化でコンパイルしたときに、末尾再帰だ
それがあることを認識するであろう、あなたは、このことから、スタックオーバーフローを取得することはありません
たとえ私たちのツリーは、10,000、または10万円の高さを有している。
[学生、不明朗]
[ボーデンは]私はそれがダッシュでそれをしないと思う - またはどのような最適化レベル
認識されるように、末尾再帰のために必要です。
私はそれを認識して考える - GCCとClangの
また、最適化レベルにおいて、異なる意味を持っています。
私はそれが末尾再帰を認識していることを確認するためのDashO 2、だと言いたい。
しかし、我々は、 - あなたはFibonocci例か何かのように作成する可能性があります。
それを作成することが困難だから、それは、この使用してテストを行うことは容易ではありません
ほど大きなサイズのバイナリツリー。
しかし、ええ、私はそれがDashO 2、だと思う
あなたはDashO 2を指定してコンパイルすると、それは末尾再帰を探します
その外を最適化します。
のは、に戻りましょう - 挿入は文字通りそれが必要とする最後のことだ。
こっちインサートに戻ってみましょう
ここで我々は、同じアイデアをやろうとしている。
それはまだ完全に扱うことができないという欠陥があるでしょう
、ルート自体がnullであるか、過去のエントリがnullの場合
その代わり、親のポインタを扱う、
ポインタへのポインタを保持するのと同じロジックを適用してみましょう。
ここならば、我々は、我々のノード**最新版に保つ
そして我々は、もはや右を追跡する必要はありません。
しかしノード**電流=＆ツリー。
そして今、私たちのwhileループは、* curが等しく、nullをされていませんがあることを行っている。
もう両親を追跡する必要はありません。
左と右を追跡する必要はありません。
我々はすでにtempを使っているので、私は、それを一時と呼ぶことにします。
オーケー。もしそうであれば（値> * temp）に、
その後、＆（* TEMP） - >右
他の気温=＆（* temp）に - >左。
そして今、この時点では、このwhileループの後、
多分それは約反復して再帰的に考えるよりもする方が簡単ですので、私は、これを行う
しかし、このwhileループの後、
* tempは、変更したいポインタです。
>> 前に、私たちは親を持っていた、と私たちは親の左または右の親のどちらかを変更したい
しかし、私たちは、親の権利を変更したい場合は、
次に* tempは親の権利であり、我々はそれを直接変更することができます。
だからダウンここで、我々は*気温=ノードnewnodeを行うことができます、そして、それはそれだ。
予告だから、我々はこれで行ったすべてのコード行を取り出しました。
付加的な努力であるすべての親を追跡するために。
ここでは、我々だけで、ポインタへのポインタを追跡する場合は、
そして我々は今、すべてのこれらの中括弧を取り除くために望んでいる場合でも、
それが短く見えるようにする。
これは今、まったく同じソリューションです。
しかし、コードの行数が少ない。
それがわかれば、有効な解決策として、これを認識し始める
それは、大丈夫、またのようなより約理由に簡単だ
なぜ私はint型の右側には、このフラグを持っていますか？
どういう意味ですか？ああ、それはあることを意味している
私は右に行くたびに、私はそれを設定する必要があり、
私は左に行けば他の私はそれをゼロに設定する必要があります。
ここでは、私は約理由に持っていない、それは考えることだけで簡単です。
質問はありますか？
[学生、不明朗] >>うん。
さて、最後のビットで -
私は、我々が行うことができます1迅速かつ簡単に関数があると推測
let's - 一緒に、私は推測するが、含まれている関数を試してみて、書き込み
それが二分探索木であるかどうかを気にしない。
これは、関数がtrueを返す必要があります含まれています
あればどこでもこのような一般的なバイナリツリーでは、我々が探している値です。
だから最初に再帰的にそれを行うこととし、我々は繰り返しそれをやるしてみましょう。
これは本当に短いであることを行っているので、我々は実際には、一緒にそれを行うことができます。
>> 私のベースケースは何になるつもりですか？
[学生、不明朗]
[ボーデン]それでは、（ツリー== NULL）の場合はどうでしょうか？
[学生]はfalseを返します。
[ボーデン]がそうでなければ、まあ、私は他には必要ありません。
場合は、私の他のベースケースでした。
[学生] Treeの値はありますか？ >>うん。
だから（木>の値==値なら。
我々は、ノード*ではなく、ノード** sに戻って気づく？
CONTAINSは、ノード**を使用する必要は決してありません
以来、我々は、ポインタを変更していません。
私達はちょうどそれらを横断している。
それが起こるなら、私たちは、trueを返したいと思います。
他の子どもたちを横断したいと思います。
だから我々は左に、すべてが小さいかどうかについて判断することはできません
そして右側にすべてが大きい。
それでは、私たちの条件はここにあることを行っている - あるいは、私たちは何をするつもりですか？
[学生、不明朗] >>うん。
リターンが含まれています（値は、ツリー - >左）
または（値、ツリー - >右）が含まれています。そして、それはそれだ。
そして、いくつかの短絡評価があると気付く
ここで我々は左のツリーの値を見つけることが起こる場合、
我々は、右のツリーを見てする必要はありません。
それは全体の関数です。
さて、繰り返しそれをやらせる
その少ない素敵になるだろう。
我々は、ノード*電流=木の通常の開始を取るよ。
しばらく（最新版！= NULL）。
迅速に問題を見に行く。
、ここに、私たちが今までにこれを打破した場合 - 電流もし
それから私達は見て物事を使い果たしてしまったので、falseを返します。
（最新版 - >値==値）の場合、trueを返します。
だから今、私たちは場所にある -
我々は、左または右に行きたいかどうかはわかりません。
だから勝手に、左だけ行きましょう。
私は明らかに私は完全に全てを捨ててきた問題に実行しようとしました -
私は今まで木の左側をチェックします。
私は何の右の子である何かを確認することは決してありません。
私はこれをどのように修正すればよいですか？
[学生]あなたは、スタック内の左右を追跡する必要があります。
[ボーデン]うん。それでは、それを作ってみましょう
構造体リスト、ノード* n、およびそのノード**次は？
私は正常に動作していると思います。
ここまで - 私たちは、左、またはlet'sを上に行きたい。
構造体リストlist =、それは始めましょう
この構造体のリストで出。
*リスト= NULL。だから私たちのリンクリストになるだろうという
私たちが飛ばされていることをサブツリーの。
我々は今のままにトラバースしようとしている、
しかし、我々は必然的に右に戻ってくる必要があるので、
私たちは、構造体のリストの中で右サイドを維持するつもりだ。
その後、我々は、新しいリストまたは構造体があるでしょう
構造体リスト*、新しいリスト=はmalloc（sizeofの（リスト））。
私は、エラー·チェック無視するつもりですが、あなたはそれがnullでよいかどうかを確認するためにチェックする必要があります。
それを指すように起こっているノードを新しいリスト -
私がここでそれを望んでなぜ、ああ、それはです。それが2番目の構造体のリストを指すようになるだろう。
それはリストの仕事をリンクさどれだけだ。
これはintリンクリストと同じです。
我々は、ただのノード*とint型を交換している点が異なります。
それは全く同じだ。
だから新しいリスト、私たちの新しいリストノードの値、
電流は>右になるだろう。
私たちの新しいリストの値 - >次は私達の元のリストになるだろう、
それから私達は新しいリストを指すように、私たちのリストを更新するつもりです。
>> 今、私たちは、物事を引っ張っての方法のいくつかの並べ替えが必要、
我々は左のサブツリー全体を横断しているよう。
今、私たちは、ITのものを引き出すために必要
最新版のようにnullである、我々はただfalseを返す必要はありません。
今、私たちは新しいリストに外部プルアップしたいと思います。
これを行うための便利な方法は - まあ、実際に、これを行うための複数の方法があります。
誰もが提案を持っている？
どこでこのまたはどのように私はこれを行う必要がありますしたらよいでしょうか？
我々は数分しか持っていますが、任意の提案ですか？
代わりに - 一方通行ではなく、私たちの条件の中にある、
我々が現在見ているのは、nullではありません
代わりに、私たちは私たちのリスト自体がnullになるまで行き続けていくつもりです。
私たちのリストには、nullをされて終わるのであれば
次に我々は、探すために上を検索するものがなくなってきた。
しかし、それは私たちのリストにある最初の事はちょうど最初のノードであることを行っていることを意味します。
非常に最初の事は次のようになります - 私たちは、もはやすることを参照してくださいする必要はありません。
だからリスト-> nは私たちのツリーになります。
リスト-> nextはヌルであることを行っている。
そして今、リストが等しく、nullをされていませんが。
野良犬は私たちのリストから何かを引くために起こっている。
だから電流は等しいリスト - > nになるだろう。
そして、リストが等しいに起こっているリスト - > n、またはリスト>次。
もしそうであれば電流値は値と等しくなります。
今、我々は右のポインタと私たちの左ポインタの両方を追加することができます
限り、彼らがnullではないしているとして。
ここに、私たちがいることを行っておくべきだと思うそもそもインチ
（最新版 - >右！= NULL）の場合
それから私達は私達のリストにそのノードを挿入しようとしている。
（最新版 - >左）、これは余分な作業を少しした場合ですが、それは大丈夫です。
、（最新版 - >左！= NULL）の場合
そして私達は私達のリンクリストに左を挿入しようとしている、
それはそれであるべきである。
私たちは、反復する - 私たちは私たちのリストに何かを持っている限り、
我々は見て別のノードを持っています。
だから我々は、そのノードを見
我々は次のいずれかに私たちのリストを進める。
そのノードは、我々が探している値である場合、我々は、trueを返すことができます。
そうでなければ、両方の私達の左と右のサブツリーを挿入
彼らがヌルじゃない限り、私たちのリストに
我々は、必然的にそれらの上に行くようにします。
彼らはヌルではなかったのであれば、
私たちのルート·ポインタは、二つのことを指している場合
私たちのリストがnullされて終わるので、最初に我々は何かを取り出した。
そして、我々は背中に​​2つのものを入れるので、今私達のリストのサイズは2である。
その後、我々はバックアップしてループしていると我々はただ引っ張っていくつもりですが、
私たちのルートノードの左ポインタ、言うてみましょう。
そして、それはちょうど起こっておこう、私たちはすべてのものをループになってしまいます。
>> これは非常に複雑なものにしていることに気がついた
再帰的なソリューションインチ
そして、私は何回も言ってきました
再帰的なソリューションは、通常、反復解法と多くの共通点があることを確認します。
ここでは、これは再帰的な解決策が何を示すのかである。
唯一の変更点は、代わりに、暗黙的にスタックを使用しているプログラム·スタックです
あなたはまだ訪問する必要があるどのノードを追跡するあなたの方法として、
今、あなたは明示的にリンクされたリストを使用する必要があります。
両方のケースでは、ノードがまだ訪問する必要があるかを追跡しています。
再帰的なケースでは、それだけで簡単だからスタック
プログラムスタックとしてあなたのために実装されます。
このリンクリストは、それはスタックであることに注意してください。
我々だけで、スタック上に置かれた全てのもの
我々は次の訪問には、スタックをやってのけるつもりか直後です。
我々は、時間がなくなってしまいますが、何か質問？
[学生、不明朗]
[ボーデン]うん。だから我々は、リンクされたリストを持っている場合、
現在は、この男を指すように起こっている
そして、今、私たちはただこの男に集中することが私たちのリンクリストを進めています。
我々は、その行のリンクリスト上をトラバースしている。
そして私は私達が私達のリンクリストとかを解放する必要がありますね
一度trueまたはfalseを返す前に、我々はする必要が
私達のリンクリストを反復処理し、常にダウンここで、私は推測する
我々curが右と等しくない場合、今我々が解放したい、それを追加
電流ので、まあ、我々は完全リストについて忘れたのでは？ Yeah。
だから、我々はここで何をしたいです。
ポインタはどこにありますか？
野良犬はその後だった - 私たちは、* 10は次のリストに等しい構造体のリストにしたい。
空きリストは、リスト=気温。
そして、我々がtrueを返す場合には、我々は反復する必要がありますか
物事を解放する私達のリンクリストの残りの部分の上。
再帰的なソリューションについての素晴らしい事は、物事を解放している
あなたのためだけに起こるスタックからポップしfactoringsを意味します。
だから我々はハードに思う - 約コードの3行のようなものだ何かから行ってきた
有意に、より多くの何かへのハード·ツー·シンクタンク約コードの行。
これ以上の質問は？
かしこまりました。我々は良いです。さようなら！
[CS50.TV]