[Powered by Google Translate] [第7項] [あまり快適] [ネイトHardison] [ハーバード大学] [これはCS50です。] [CS50.TV] 第7章へようこそ。ハリケーンサンディのおかげで、代わりに今週通常のセクションを持っていることの、我々は、質問のセクションを介して、ウォークスルーでこれをやっている。私は、6仕様を設定して問題と一緒に次のようにするつもりですとの質問のすべてを通過質問セクションのセクション。何か質問がある場合は、 CS50論議でこれらを投稿してください。よし。始めましょう。今、私は問題セット仕様の3ページ目で探しています。我々は最初の二分木について話し始めるつもりですそれらは、今週の問題セットへの関連性の多くを持っているので - ハフマン木のエンコーディング。我々はCS50での話、非常に最初のデータ構造の一つが配列だった。配列は要素のシーケンスであることを忘れないでください - 同じタイプのすべて - メモリ内で隣同士に右に格納されている。私は、このボックスナンバー - 整数のスタイルを使用して描くことができる整数の配列を持っている場合 - 私は最初のボックスに5を持っていると言うてみましょう、私は、第二の7を持っているそれから私は、最終的なボックスに8、10、20を持っています。、この配列は約2本当に良いものを覚えている我々は、任意の特定の要素にこの一定時間のアクセスを持っているということです配列内の我々は、そのインデックスを知っていれば。たとえば、私は、配列の3番目の要素を取得したい場合 - 私たちのゼロベースのインデックスシステムを使用して、インデックス2 - 私は文字通り単純な数学的な計算をしなければならない、配列内のその位置にホップ、、そこに格納されている8を抜くそして、私が行ってもいいよ。この配列の悪口の一つ - 我々は話を我々は、リンクされたリストについて説明したときに - 私は、この配列に要素を挿入する場合ということです私はいくつかの周りにシフトを行う必要があるつもりです。右ここでたとえば、この配列ソートされた順序になっている - 昇順にソート - その後その後その後その後、5、7、8、10、20 - しかし私は、この配列に9番を挿入したい場合は、私は、スペースを作るためにいくつかの要素をシフトする必要がありますするつもりです。私たちはここで、これを引き出すことができます。私は5,7を移動する必要があるとして、その後8だ。私は9を置くことができる隙間を作りますその後10と20は9の右に行くことができます。これは最悪のシナリオであるため痛みの種類です - 私たちは、始めまたは終わりのどちらに挿入することしているとき - 私たちがシフトしている方法に応じて、配列の我々は、すべての要素をシフトすることに終わるかもしれない我々は現在、配列に格納していること。だから、これを回避する方法は何でしたか？これを回避する方法はどこに私達のリンクリスト方式に行くことだった - 代わりに、要素5、7、8、10、メモリ内の隣同士に20すべてを格納する - 我々はそれらを保存したい場所に私たちの代わりに種類のそれらを格納されたなかったもの私はここに描いてるこれらのリンクされたリスト内のノードは、アドホックの一種。そして、我々はこれらの次のポインタを使用して、それらを一緒に接続されています。私は、5日から7日へのポインタを持つことができます 7から8へのポインタ、 8から10へのポインタ、そして最後に、10から20へのポインタ、その後何も残っていないことを示す20でnullポインタ。我々がここにあるトレードオフ私たちは、ソートされたリストに番号9を挿入したい場合、それは、今ある我々がしなければならないすべては、9で新しいノードを作成している、適切な場所を指すようにそれを配線その後、再配線8を9にダウン指すようにします。それは我々が9を挿入したい場所を正確に私たちが知っていると仮定して、かなり速いのです。しかし、これと引き換えにトレードオフは、我々は今、一定時間のアクセスを失ってしまったということです我々のデータ構造内の特定の要素に。たとえば、私は、このリンクリスト内の4番目の要素を検索する場合は、私はリストの冒頭に開始する必要がありますするつもり私は4分の1を見つけるまで、ノード単位をカウントを通して私のように動作します。リンクされたリストよりも優れたアクセス性能を得るために - しかし、また、我々が持っていた利点のいくつかを保持リンクされたリストから、挿入時間に換算すると - バイナリツリーは少しより多くのメモリを使用する必要があるために起こっている。特に、だけではなく、バイナリツリーノードで一つのポインタを持っていることの - リンクリストのようにノードがありません - 我々は、バイナリツリーノードへの2つのポインタを追加するつもりです。だけではなく、次の要素に1つのポインタを持つ我々は左の子と右の子へのポインタを持っているつもりです。のが実際のように見えるかを確認するために絵を描いてみましょう。繰り返しますが、私はこれらのボックスと矢印を使用するつもりです。バイナリツリーノードは、単純なボックスとオフを開始します。これは、値のためのスペースを持っているために起こっているそしてそれはまた、左の子と右の子のためのスペースを持っているために起こっている。私はここでそれらにラベルを付けるつもりです。我々は左の子を持っているつもりですし、我々は右の子を持っているつもりです。これを行うためのさまざまな方法があります。時には空間と利便性のため、私が下にここでやっているように私は実際にそれを描くよ私は一番上にある値を持っているつもりですここで、その後右下の右の子、左下のと左の子。この一番上の図に戻って、我々は、最上部に値を持っている次に我々は左の子ポインタを持っているし、我々は右の子ポインタを持っています。問題セットの仕様では、我々は、値7を持つノードの描画の話してから、左の子はnullになりポインタ、nullである右の子ポインタ。我々は、いずれかのためのスペースに資本NULLを書き込むことができます両方の左の子と右の子、あるいは、我々はこの斜線を描くことができますボックスのそれぞれを介して、それがnullであることを示します。私はそれが簡単だという理由だけでそれを行うつもりです。非常に単純なバイナリツリーノードを図式化には二つの方法があなたがここで見るアールここで我々は、値7とヌル子のポインタを持つ。どのようにリンクされたリストを使用して約当社指定の話の第二部 - 覚えて、我々はリスト内の非常に最初の要素を保持しなければならなかったリスト全体を覚えて - と同様に、バイナリツリーで、我々は唯一のツリーに一つのポインタを保持する必要がデータ構造全体の制御を維持するためである。ツリーのこの特別な要素は、ツリーのルート·ノードと呼ばれます。たとえば、この1ノード - 値7を含む、このノード - nullの左と右の子ポインタを持つ、私たちのツリー内の唯一の値であったこれは私たちのルートノードとなる。それは私達の木の非常に始まりです。私たちはツリーにノードを追加し始めると、我々は明らかに、このもう少し見ることができます。私は新しいページをアップしましょう。今、私たちは、ルートに7を持つツリーを描画しようとしているそして左の子、右の子の9内の3内側。繰り返しますが、これは非常に単純です。私達は7を持っている、3ノードのため、9用のノードを描画するそして私は3を含むノードを指すように7の左の子のポインタを設定するつもりだ、と9を含むノードまで7を含むノードの右の子ポインタ。さて、3と9以降の任意の子供を持っていない、我々は、NULLにすることは、その子のポインタをすべて設定するつもりです。ここでは、私たちのツリーのルートは7番を含むノードに対応しています。我々が持っているのが、そのルートノードへのポインタである場合は、それを見ることができます私達は、私達の木の中を歩くと、子ノードの両方にアクセスすることができます - 3と9の両方。いいえ、ツリー上のすべての単一のノードへのポインタを保持する必要がありません。よし。今、私たちは、この図に別のノードを追加するつもりです。我々は、6を含むノードを追加しようとしているそして我々は3を含むノードの右の子として追加するつもりです。そのために、私は3つのノードでそのヌルポインタを消去するつもりですと6を含むノードを指すようにそれを配線します。よし。この時点での専門用語を少し上に行くことができます。、これは特にバイナリツリーと呼ばれている理由を起動するにはそれが2つの子へのポインタを持っているということです。以上の子へのポインタを持っている木の他の種類があります。具体的には、問題セット5で '試し'でした。あなたはその試みで、あなたは別の子供たちに27種類のポインタを持っていたことに気づくでしょう - 英語のアルファベット26文字のそれぞれに1つずつ、アポストロフィ、次いで27日 - そう、それは木の型に似ています。しかし、ここでは、それはバイナリ以来、私たちは、2つだけの子へのポインタを持っています。我々は話をこのルートノードに加えて、我々はまた、この用語の周りに投げてきた "子供"。 1ノードが別のノードの子であるためにそれは何を意味するのでしょうか？これは文字通り、子ノードが別のノードの子であることを意味しますそのほかのノードは、そのノードを指すように設定され、その子ポインタのいずれかを持っている場合。、より具体的にこれを入れて 3は7の子ポインタのいずれかによって指されている場合、3は7の子です。 - 私たちは7の子が何であるかを把握した場合さて、私たちは、7は3へのポインタと9へのポインタを持っていることがわかりので、9と3が7の子です。ナインは、その子へのポインタがnullであるため、子を持たない、と3には1つしか子、6を有している。そのポインタの両方がnullであるため、シックスはまた、我々は今すぐに描画します、これは子を持ちません。さらに、我々はまた、特定のノードの親の話これは、あなたが期待するように、この子の説明とは逆になります。あなたは人間と予想されるであろう2つの代わりに - 各ノードは親を1つしか持っています。たとえば、3つの親は7です。 9の親も7であり、6の親は3です。それにはあまりない。我々はまた、祖父母と孫の話をするための用語を持っているそしてより一般的に、我々は先祖の話と、特定のノードの子孫。ノードのむしろや先祖、、 - ノードの祖先 - rootからそのノードへのパス上に存在するすべてのノードである。たとえば、私はノード6で探していた場合、その後の祖先は3と7の両方になるだろうしている。 9の祖先は、例えば、 - 私はノード9で探していた場合 - 次に9の祖先はわずか7です。そして子孫はまったく逆である。私は7のすべての子孫を見たい場合は、その後、私はその下のすべてのノードを見なければなりません。だから、私は、3,9、および7の子孫として6すべてを持っています。我々が話だろうという最後の項は、兄弟であることのこの概念です。兄弟 - これらの家族の条件に沿って続いての一種 - ツリー内の同じレベルにあるノードです。彼らは、ツリー内の同じレベルにあるためこのように、3と9は兄弟です。彼らは両方とも同じ親、7を持っている。 9が子を持っていないため、6兄弟はありません。それが私たちのツリーのルートだからと7は、任意の兄弟を持っていませんとしか1ルートがあります。 7人の兄弟を持っているためにそこには7つ上のノードでなければならないであろう。 7はもはやツリーのルートにないでしょう、その場合、7の親がなければならないだろう。その後7の新しい親も、子供がなければならないでしょうその子はその後7の兄弟であろう。よし。上を移動する。我々は、二分木の我々の議論を始めたとき、我々はそれらを使用しようとしていた方法について話しました配列やリンクリストの両方の上の優位性を得る。そして、我々はそれをやろうとしている方法は、この順序付けプロパティである。我々は、仕様に応じて、バイナリツリーを注文していると言う私たちのツリーの各ノードの場合は、左側にそのすべての子孫 - 左の子と左の子の子孫のすべて - 低い値は、右側にあるすべてのノードを持っている - 右の子と右の子の子孫のすべて - 我々が見ていること、現在のノードの値より大きいノードを持つ。ただ簡単にするために、我々は、ツリー内の任意の重複したノードが存在しないと仮定するつもりです。たとえば、このツリーには、我々はケースに対処するつもりはないここで我々はルートに値7を持っているそれから私達はまた他の場所でツリーに値7を持っています。このケースでは、この木が実際に命じられていることに気づくでしょう。我々はルートに値7を持っています。 7の左側にあるすべて - 私はここで、これらの小さなマークのすべてを取り消す場合 - 7の左側にあるすべてのもの - 3、6 - これらの値は、両方の7未満であり、右側にあるものをすべて - ちょうどこの9 - 7より大きい。これは、これらの値を含む順序木だけではありませんが、しかし、ここではそれらのいくつかのより多くを描くことができます。我々はこれを行うことができる方法の全体の束は、実際にあります。私はちょうどここで物事をシンプルに保つために速記を使用するつもりだ - 全体ではなく、ボックスアンド矢印を引き出す - 私は数字だけを描き、それらを接続する矢印を追加するつもりです。開始するには、我々だけで、3それから私達は7を持っていたところ、再び私たちの元のツリーを記述して、よその後3は、6に戻って右に指摘したおよび7は9であった右の子を持っていた。よし。我々はこの木を書くことができることを別の方法は何ですか？代わりに7の左の子である3持っていることの、我々はまた、6,7の左の子である可能性がありますその後3は6の左の子である。私は7を持っているところであるが、右ここにこの木のようになります。その後、6、3、右に9。私達はまた私達のルートノードとして7を持っている必要はありません。私達はまた私達のルートノードとして6を及ぼす可能性があります。どのように見えるのでしょうか？我々はこの順序付きプロパティを維持するつもりなら、 6の左側にあるすべてのものは、それ以下にする必要があります。そこに唯一の一つの可能性だし、それは3だ。しかし、その後、6の右の子のように、我々は2つの可能性を高めています。まず、我々は、7その後9を及ぼす可能性がありますあるいは、我々はそれを描くこと - 私はここで何をしようとしているような - 我々は6の右の子として9を有する場合、その後9の左の子のように7。さて、7と6は、rootに対してのみ可能な値ではありません。我々はまた、3ルートになる可能性があります。 3ルートにある場合はどうなりますか？ここでは、物事は少し面白くなる。三つには、それより小さい値はすべてを持っていませんそう、ツリーのその全体の左側はnullであることを行っている。そこに何かがあるようにはならないだろう。右側には、我々は、昇順で物事をリストできます。次に次に次に図3、図6、図7、図9を及ぼす可能性があります。または、我々はそれから9,7その後、6次に、3を行うことができます。または、我々はその後、7、6、9次に、3を行うことができます。または、3,7 - 実際には、我々はもう7を行うことはできません。それはそこに私たちの一つのことだ。我々は9を行うことができ、その後9時から、我々は6、その後7を行うことができます。または、我々はそれから9,7次に、3の操作を行い、[6することができます。ここにあなたの注意を引くために一つのことはあるこれらの木は少し奇妙に見えるしていること。特に、我々は右側の4木を見れば - 私はここに、それらを一周します - これらの木はほぼ正確にリンクされたリストのように見えます。各ノードには、子が1つしかなく、それで我々は、例えば、我々が見ているこのツリー状の構造のいずれかを持っていない左下のこっちにこの1孤独な木インチこれらの木は実際にはバイナリツリーを縮退と呼ばれ、そして我々は、将来的にこれらのよりについて話そう - あなたは、他のコンピュータサイエンスのコースを取るために行く場合は特に。これらの木は、縮退している。、確かに、この構造は向いているので、彼らは非常に有用ではありませんリンクリストと同様の時間をルックアップします。私たちは余分なメモリを活用するために得ることはありません - この余分なポインタを - なぜなら我々の構造のこのように悪いこと。むしろより上に行くとルートに9を持っている、バイナリツリーを引き出す、我々が持っている最後のケースは、これです我々は、この他の用語について少し話をしようとして、この時点では、代わりにしている高さと呼ばれる木々と書かれている場合、我々は、使用している。ツリーの高さは、ルートから最も遠いノードまでの距離であるというよりあなたがするために行う必要があることにホップ数 rootから起動して、ツリー内の最も遠いノードで終わる。我々はここに描かれてきたこれらの木のいくつかを、見てみると我々は我々が左上隅にこの木を取り、私達は3時に開始した場合見ることができ、次に我々は、6に到達するために1ホップを作るために7を取得する2番目のホップを持って、と9に到達するために第三ホップ。だから、この木の高さは3です。我々は、この緑で囲ま他の木のために同じ運動を行うことができますそして我々は、これらの木のすべての高さは実際にも3であることがわかります。それは彼らが退化作るものの一部だ - その高さは、全体のツリー内のノードの数より一つ少ないこと。、我々は赤で囲まれているこの他の木を見れば、その一方で - 私たちは、最も遠いリーフノードが6と9であることがわかり子を持たないそれらのノードである葉。だから、ルートノードから6または9のいずれかに到達するために、私たちは、7に到達するために1ホップを作るために持っているし、9に到達するために第二ホップと同様に、7からわずか2番目のホップは6に取得します。だから、ここを介してこの木の高さは2です。あなたは戻って、我々は以前に説明した他の木々のすべてのことを行うことができます 7,6で始まる、そしてあなたは、木のすべての高さも2であることがわかります。私たちが話してきた理由は、バイナリツリーを命じたあなたは、これらを経由して検索することができますので、彼らはクールだ理由ですソートされた配列に対して検索すると非常によく似た方法。これは、我々はその改善ルックアップ時間を得ることについて話をする場所です単純なリンクリスト上。リンクリストと - あなたは、特定の要素を検索したい場合 - あなたは、最高の状態で線形探索のいくつかの並べ替えをやろうとしている - あなたは、リストとホップ一つずつの先頭から開始場所いずれかのノードで、1つのノード - あなたはあなたが探しているものは何でも見つかるまで、リスト全体を通じ。は、この素敵なフォーマットで保存されているバイナリツリーを持っている場合、一方あなたは、実際に起こってバイナリサーチの多くを得ることができますあなたは、分割統治場所各ステップでのツリーの適切な半部を検索してください。のは、その仕組みを見てみましょう。我々が持っている場合 - もう一度、私たちの元の木に戻って - 我々は、右側に、我々は左の3を持って、7時9を起動と3の下、我々は6を持っています。我々はこのツリー内の数字6を検索したい場合、我々は、ルートから始まると思います。我々は、6と言う、我々が探している値と比較します我々が現在見ていることをノードに格納された値、7、 6は確かに7未満であるので、我々は左に移動したいことがわかります。 6の値が7以上であった場合、我々はその代わりに右に移動していただろう。我々は知っているので、その - 私たちの順序付けられたバイナリツリーの構造に起因する - 7未満のすべての値は、7の左側に格納することとしているでも、木の右側を通って見て気にする必要はありません。かつて我々は左に移動し、我々は3を含むノードで今なら、我々は3と6を比較するところ、我々は再びその同じ比較を行うことができます。、3より大きいです - 我々が探している価値 - 私たちは、しばらく6はわかり我々は、3を含むノードの右側に行くことができます。そこには左側がここにないので、我々はそれを無視している可能性があります。しかし、我々は唯一の、私たちは木そのものを見ていることを知っているので、そして我々は木が子を持たないことがわかります。それは、我々は人間として私達自身をやっている場合、このツリーに6をルックアップするためにも非常に簡単ですしかし、どうなるのがコンピュータのように機械的に、次のプロセスに従いましょう実際にアルゴリズムを理解する。この時点で、我々は今、6を含むノードを見ているそして我々は、値6を探しているそう、確かに、我々は適切なノードを発見した。私たちは、ツリー内の値6を発見し、我々は検索を停止できます。この時点で、何が起こっているかに応じて、私たちが言うことができる、そう、我々は値6を発見した、それは私たちのツリーに存在します。または、我々はノードを挿入したり、何かをする予定になっているならば、我々は、この時点でそれを行うことができる。どれだけこの作品を見てカップルより多くのルックアップをやってみましょうの。のは、我々がしようとすると、10の値をルックアップした場合に何が起こるか見てみましょう。私たちは、10の値をルックアップした場合、我々はルートから始まります。我々は10が7以上であることがわかると思いますので、私たちは右に移動したいと思います。我々は9に取得し、10から9を比較し、9は確かに10未満であることがわかると思います。だからもう一度、私たちは右に移動しようと思います。しかし、この時点で、我々は我々がnullノードにいることに気づくと思います。そこには何もありません。 10は、あるべきものは何もありません。ツリーには10が実際に存在しないことを - 私たちは失敗を報告することができる場所です。そして最後に、のは私たちがツリーに1をルックアップしようとしているケースを介して行くことができます。これは、右に行くの代わりにを除いて、我々は10を見れば何が起こるかに似ています我々は左に行くつもりです。私達は7時に始まって、1が7未満であることがわかるので、我々は左に移動します。私たちは3を取得すると1が3未満であることがわかりますので、再び我々は左に移動してみてください。この時点で我々がnullノードを持っているので、再び我々は失敗を報告することができます。あなたは、バイナリツリーの詳細についてはしたい場合は、あなたも一緒に行うことができます楽しい小さな問題の全体の束があります。私は、これらの図を一つずつの描画を練習することをお勧めと、別のステップのすべてを介して次のこれが超便利になるだろうので、あなたは、ハフマン符号化された問題セットをやっているときだけでなく、だけでなく、将来のコースで - ただ、これらのデータ構造を引き出すと問題を通して考える方法を学ぶペンと紙や、この場合には、iPadとスタイラス。しかしこの時点で、我々はいくつかのコーディングの練習を行うために移動するつもりだそして、実際にこれらのバイナリツリーと遊ぶ参照してください。私は自分のコンピュータに上にスイッチバックするつもりです。セクションのこの部分のため、代わりにCS50 CS50ランまたはスペースを使用するのではなく、私は、アプライアンスを使用するつもりです。問題セットの仕様に沿って続いて、私は、私は、アプライアンスを開くことになっていることがわかり、私のDropboxフォルダに移動し、第7節と呼ばれるフォルダを作成その後binary_tree.cという名前のファイルを作成します。ここに私達は行く。私は、アプライアンスがすでに開いて持っている。私は、端子をプルアップして行きます。私はDropboxのフォルダに行くつもりです、section7というディレクトリを作り、そしてそれは完全に空です参照してください。今私はbinary_tree.cを開くつもりです。よし。ここに私達は行く - 空のファイルを。のが仕様に戻りましょう。仕様は新しい型定義を作成するか尋ね int型の値を格納したバイナリツリーノードの - ちょうど私達が私達の前に、作図中で描いたような値。我々は、我々がここに行ったことこの決まり文句は、typedefを使用するつもりだあなたは問題セット5から認識しなければならない - あなたは征服スペルチェックプログラムのハッシュテーブルのやり方をしなかった場合。また、先週のセクションから、それを認識しなければならないここで我々は、リンクリストについて話しました。我々は、構造ノードのこのtypedefを持っているそして我々はあらかじめ構造ノードのこの名前は、この構造体のノードを与えてくれた我々にはstructノードのポインタを持ってしたいと思うので、我々はそれを参照できるように私たちの構造体の一部として、私たちはその後、これを包囲しました - いやむしろ、これを囲んで - typedefでだから、それ以降のコードでは、代わりに構造ノードのノードだけでは、この構造体を参照することができます。これは、我々が先週見た、片方向リンクリストの定義に非常に似ているために起こっている。これを行うには、単に定型文を書くことから始めてみましょう。私たちは、整数値を持たなければならないことを知っているので、我々はint値を入れ、その後、代わりに次の要素にただ一つのポインタを持つのだろう - 我々は、片方向リンクリストの場合と同じように - 我々は左と右の子へのポインタを持っているつもりです。それはあまりにも非常に簡単です - 構造体のノード*左の子; とstructノード*右の子;クール。これはかなり良いスタートのように見えます。のが仕様に戻りましょう。今、私たちはツリーのルートのためのグローバル·ノード*変数を宣言する必要があります。我々はまた、グローバルな私達のリンクリストの最初のポインタを作っただけのように、これはグローバルにするつもりだ。これは、我々が記述した関数でようでした我々は、このルートを回す維持する必要はありません - 私たちは、あなたが再帰的にこれらの関数を記述したいのであればことがわかりますけれども、それは最初の場所であってもグローバル変数として、それを周りに渡さないほうがよいかもしれませんそして代わりに、メイン関数内で局所的にそれを初期化します。しかし、我々は、開始するために、グローバルにそれをやる。再び、我々はスペースのカップルを与えるだろう、と私は、ノード*ルートを宣言するつもりです。ただ私はこれが初期化されていないままにしないことを確認するために、私がnullに等しいそれを設定するつもりです。さて、main関数で - 私たちは右ここでは本当に速く書こうと思います - int型のmain（int型のargc、const char *型のargv []） - と私はちょうどので、私が知っているconstとして私のargv配列を宣言する開始するつもりだこれらの引数は、私はおそらく変更したくないの引数であること。私はそれらを修正したい場合、私はおそらくそれらのコピーを作成する必要があります。このコードの多くが表示されます。これは、いずれかの方法で大丈夫です。それをとして残していいのよ - あなたがご希望の場合はconstを省略します。私は通常、ちょうどので、私は自分自身を思い出させることにそれを置く私はおそらく、これらの引数を変更したくない。いつものように、私はメインの最後に、このリターン0の行を含めるつもりです。ここでは、私は私のルートノードを初期化します。それが今立っているように、私は、nullに設定されているポインタを持っているそうそれは何を指している。、実際にはノードの構築を開始するために私が最初にそれ用のメモリを確保する必要があります。私は、mallocを使用してヒープ上のメモリにすることによってそれを行うつもりです。私は、mallocの結果と同じルートを設定するつもりだと私は、ノードのサイズを計算するためにsizeof演算子を使用するつもりです。とは対照的に、私はsizeof演算ノードを使用している理由は、言う、 malloc関数（4 +4 +4）またはmalloc - 12 - このような何かを私は私のコードはできるだけ互換性を持たせたいからです。私はこのcファイルを取ることができるようにしたい、アプライアンス上でそれをコンパイルし、そしてその後、私の64ビットのMac上でそれをコンパイルする - または完全に異なるアーキテクチャ上で - と私はこのすべてが同じ仕事をしたい。私は変数のサイズについての仮定を作ってる場合 - intやポインタのサイズの大きさ - その後、私はまた、アーキテクチャの種類について仮定を作ってるんだ実行時にどんな私のコードは正常にコンパイルできます。手動で構造体のフィールドを加算するのではなく、常にsizeofを使用しています。他の理由は、コンパイラがstructにパディングを置くことがあるかもしれないということです。だけでも、個々のフィールドを加算することで、一般的にやりたいことは何かありませんが、ので、その行を削除します。さて、実際には、このルートノードを初期化する私は、その異なる各フィールドの値をプラグインする必要がありますするつもりです。たとえば、値のために私は7に初期化したい知っている、そして今の私は左の子がnullに設定するつもりですそして右の子もNULLにする。すばらしい！我々は、仕様のその部分をやった。 3ページの一番下にある仕様ダウンより3つのノードを作成するために私に尋ねる - 3、6を含むもの、及び9と1を含む1 - それはまさに私たちの樹形図のようになりますので、それらをしてから配線する我々は以前に話したこと。ここでかなり迅速にそれを行うてみましょう。あなたは、私は重複したコードの束の書き込みを開始するつもりだ本当にすぐわかります。私は、ノード*を作成するつもりですし、私はそれ3呼び出すつもりです。私は、malloc（sizeofの（ノード））と等しくなるように設定するつもりです。私は3->値= 3を設定するつもりです。三 - > left_child = NULL; 3 - >右_child = NULL;同様。その根を初期化することにかなり似ています、それが正確に何を私は同様に6と9を初期起動した場合に行う必要があるつもりです。私はすぐにここでは本当にそれを行うだろう - 実際に、私は少しのコピー＆ペーストをするつもりです、大丈夫 - と、私は確認してください。今、私はそれをコピーして持っていると私は先に行くと、6〜この等しいを設定することができます。あなたは、これはしばらくかかり、超効率的ではないことがわかります。ほんの少しで、私たちは私たちのためにこれを行います関数を記述します。私は9でこれを置き換えたい、6でそれを交換してください。今、我々はすべてのノードに作成および初期化を持っている。私達は私達のルート7と等しくなるように設定するか、値7を含有し、持っている 3を含む我々のノード、6を含む我々のノード、および9を含む我々のノード。この時点で、我々がしなければならないすべてはすべてのものを線である。私はnullにすべてのポインタを初期化した理由は、私はそのことを確認してくださいちょうどそうということである私は偶然そこに初期化されていないポインタを持っていない。また、以来、この時点で、私は実際にお互いにノードを接続する必要があります - それらが実際に接続していることをものに - 私は通過するとする必要はありませんすべてNULLが適切な場所にそこにいることを確認してください。ルートから始まり、私はルートの左の子が3であることを知っています。私はルートの右の子が9であることを知っている。その後、私が心配する残っているだけで、他の子 6は3の右の子です。この時点で、それはすべてかなりよさそうだ。私たちは、これらの行の一部を削除することもできる。これですべてがかなりよさそうだ。のが私たちの仕様に戻って、我々は次に何をしなければならないものを見てみましょう。この時点で、我々は 'が含まれている'という関数を記述する必要があります "ブールのcontains（int値）"のプロトタイプを持つ。そして、これは関数がtrueを返すように起こっている含まれていますツリーには、当社のグローバルroot変数が指す場合機能とそうでない場合はfalseに渡された値が含まれています。先に進み、それをやってみましょう。これはまさに我々がほんの少し前にiPad上で手でやったルックアップのようになるだろう。少しでズームインやスクロールアップしてみましょう。我々は右の私達の主な機能の上に、この関数を置くつもりだので、我々はプロトタイピングの任意の並べ替えを行う必要がないこと。だから、boolは（int値）が含まれています。そうしよう。私たちの決まり文句の宣言があります。ただ、これはコンパイルされていることを確認し、私は先に行くとちょうどfalseを返すことが等しくなるように設定するつもりです。今のところ、この関数は単に何もしないであろうと、常にそのを報告我々が捜している値は、ツリーではありません。この時点で、それはおそらく良いアイデアだ - 私たちはコードの全体の束を書いていると私たちも、まだそれをテストしようとしていないので - それがすべてコンパイルされることを確認します。私たちは、これが実際にコンパイルすることを確認するためにしなければならないという点がいくつかあります。まず、我々はまだ含まれていないことにあるライブラリに任意の関数を使用してきたかどうかを確認します。我々はこれまで使ってきた関数はmalloc関数であり、その後、我々はまた、このタイプを使用してきた - 'bool'と呼ばれるこの規格外のタイプを - 標準のブール値のヘッダーファイルに含まれている。我々は間違いなく、bool型の標準的なbool.hを含めたい我々はまた、＃標準ライブラリの標準lib.hを含めたいそれは、malloc、自由、そしてそのすべてが含まれています。だから、ズームアウト、我々はやめるつもりです。試してみて、これは実際にコンパイルを行っていることを確認してみましょう。我々はそれがないことがわかりますので、我々は正しい軌道に乗っている。さんが再びbinary_tree.cを開いてみましょう。これは、コンパイルされます。のが下がると我々は、CONTAINS関数にいくつかの呼び出しを挿入していることを確認してみよう - ただそれはそれで良いのことを確認します。たとえば、先ほど私たちのツリーにいくつかの検索を行ったとき、、我々は値6,10、および1をルックアップしよう、と我々は6ツリー内であることを知っていた 10には、ツリーではなかったし、1のいずれかのツリーではありませんでした。かどうかを把握する方法としてこれらのサンプル·コールを使用してみましょう私たちは、機能が働いているが含まれています。そのためには、私は、printf関数を使用するつもりだそして我々は含まれていますへの呼び出しの結果をプリントアウトするつもりだ。私は（％d）=が含まれているため "という文字列に置くつもりです私達は私達が見ていくつもりですした値をプラグインするつもりだ、と=％s \ n "が、我々の形式の文字列としてそれを使用しています。文字通り、画面にプリントアウトする - 我々は、ちょうど見に行くしている - 何が関数呼び出しのように見えます。これは実際には関数呼び出しではありません。これはただの関数呼び出しのように見えるように設計される文字列です。今、我々は値をプラグインするつもりだ。我々は試していくつもりですが、6日に含まれていますその後、我々はここでやろうとしているが、その三項演算子を使用しています。見てみましょう - 6が含まれている - そう、今私は6を含んでいたし、もし6が真である含まれており、我々は％sフォーマット文字に送信しようとしている文字列文字列 "true"になるだろう。レッツは、少し上をスクロール。そうでなければ、我々は偽6リターンが含まれている場合は、 "false"という文字列を送りたいのですが。これはちょっと間抜けに見えるのですが、私は、私は同様に説明するかもしれない把握何の三項演算子は、我々はしばらくの間、それを見ていないので、次のようになります。これが私たちのCONTAINS機能が働いているかどうかを把握するための良い、便利な方法となります。私は、左に上にスクロールバックするつもりですと私は何回かこの行をコピーして貼り付けるつもりです。それは、周りのこれらの値の一部を変更ので、これが1になるだろうが、これは10になるだろう。この時点で私たちは素敵な関数を含む持っている。我々はいくつかのテストを持っている、と我々はこのすべての作品かどうかを確認します。この時点で、我々はいくつかのより多くのコードを書きました。すべて終了させて、すべてがまだコンパイルされることを確認するために時間。途中で辞め、現在は再び二分木を作ってみてみましょう。我々はエラーを持っているようにまあ、それは、見えそして我々は、これは明示的にprintfライブラリ関数を宣言するんだ。私たちが行くと＃standardio.hをインクルードする必要がありように見えます。とということで、すべてがコンパイルされるはずです。我々は、すべての良いです。今度は、バイナリツリーを実行してみて、何が起こるか見てみましょう。ここでは、。/ binary_tree、アール、我々は、我々は予想通り、ことがわかります - 我々が実装していないので、まだ含まれていますあるいはむしろ、我々はちょうど偽見返りに入れてきた - 私たちは、それだけで、それらのすべてのためにfalseを返すていることがわかりそう、それはすべてかなりよく、ほとんどの部分のために働いている。のは、この時点で含まれています奥に行くと、実際に実装してみましょう。 - 私は、下にスクロールしてズームイン、とするつもりだ覚えて、我々が使用しているアルゴリズムは、我々はルートノードから開始されたことだったその後、我々が遭遇する各ノードで、我々は、比較を行うし、その比較に基づいて、我々はどちらか左の子か右の子に移動します。これは、我々は初期の用語で書いたバイナリ検索コードと非常によく似て見に行くされています。我々が始めたとき、我々は、現在のノードを保持することがわかっている我々は見ていると、現在のノードがルートノードに初期化されようとしていること。そして今、私たちは、木を通過維持するつもりだそして私達の停止条件を覚えて - 私たちは実際に手で例を通して働いていたとき - 我々はヌルノードに遭遇したとき、だった我々は、NULLの子を見ていないときに、むしろ我々が実際に、ツリー内のノードに移動するときそして我々がnullノードにいることがわかった。我々は、curがnullに等しいなくなるまで反復するつもりです。と私たちはどうするつもりですか？我々は、かどうかをテストするつもりだ（最新版 - >値==値）は、その後、我々は実際に我々が捜しているノードを見つけたことを知っています。だからここで、我々は、trueを返すことができます。そうでなければ、我々は値が値より小さいかどうかを見たいと思っています。現在のノードの値は、我々が探している値よりも小さい場合は、私たちは右に移動するつもりです。だから、電流は電流= - > right_child、そうでないと、我々は左に移動するつもりです。電流=電流 - > left_child;かなりシンプル。おそらくこれによく似たループを認識次に我々は、低域、中域、高扱ったことを除いて、以前の用語で二分探索、。ここでは、単に、現在の値を見ているので、それはいいと簡単です。レッツは、このコードが動作していることを確認してください。まず、コンパイルを確認してください。それがないように見えます。のはそれを実行してみましょう。そして実際、それは我々が期待するすべてのものを出力します。これは、ツリー内の6を見つけ、10はツリーではないので、10を見つけることができない 1ツリーでもありませんので、どちらか1が見つかりません。クールなもの。よし。のが私たちの仕様に戻って、次は何を見てみましょう。さて、それは私たちのツリーにいくつかのより多くのノードを追加したいと考えています。これは、5、2、および8を追加して、私たちのは、コードが含まれていることを確認したい期待どおりに動作します。そんな行きましょう。この時点ではなく、再びその迷惑なコピー＆ペーストを行うよりも、実際にノードを作成するための関数を書いてみましょう。我々は主にすべての方法を下にスクロールすると、我々はこれを行ってきたことがわかり我々はノードを作成するたびに何度も何度も非常によく似たコード。のは、実際に私たちのためにノードを構築し、それを返す関数を書いてみましょう。私はそれがbuild_node呼ぶつもりです。私は、特定の値を持つノードを構築するつもりです。ここでズーム。私は何をするつもりだ最初のものは、実際にヒープ上のノードのためのスペースを作成しています。だから、ノード* N =のmalloc（sizeofの（ノード））であり、n - >値=値; し、ここで、私はちょうど適切な値になるように、すべてのフィールドを初期化するつもりです。そして一番最後に、我々はノードを返すでしょう。よし。もう一つ注意すべき点は、この関数はそのまさにここですヒープ割り当てられたメモリへのポインタを返すために起こっている。これは何についての素晴らしいのは、今、このノードということです - 我々はそれをスタックに宣言した場合ので、私たちは、ヒープ上にそれを宣言しなければならない我々はこのように、この関数の中でそれを行うことができないでしょう。そのメモリの範囲の外に行くだろう我々は、後でそれにアクセスしようとした場合と無効になります。我々は、ヒープ上のメモリを宣言しているので、我々は、後でそれを解放するの世話をする必要があるとしている我々のプログラムのために、任意のメモリリークが発生しないように。我々は、コード内の他のすべてのためにそれにけってきたただ当時の簡略化のため、しかし、あなたは今までにこのような関数を記述する場合あなたが持っているどこに - いくつかは、その中にmallocやreallocを呼ぶ - あなたは、あなたが言う、ここにコメントのいくつかの並べ替えを置くことを確認したいねえ、あなたが知っている、渡された値で初期化されたヒープに割り当てられたノードを返します。そして、あなたが言うノートのいくつかの並べ替えに置くことを確認したい呼び出し元は、返されたメモリを解放する必要があります。そうすれば、誰かがこれまで行くとすると、その関数を使用しています彼らは、その関数から戻ってどんなことを知っているいくつかの時点で解放する必要があります。、すべてがここでいいであると仮定すると私達は私達のコードに下ると右ここで、これらのすべての行を置き換えることができます私たちのビルドノード関数への呼び出しを使用して。のは、本当に迅速にやってみましょう。我々は交換するつもりはないことを1の部分は、ダウンここでは、この部分です私たちが実際にお互いを指すようにノードを配線下部に、そのため、我々は関数の中で行うことはできません。しかし、聞かせてやるルート= build_node（7）;ノード* 3 = build_node（3）; ノード* 6 = build_node（6）;ノード* 9 = build_node（9）; そして今、我々はまたのためにノードを追加したい - ノード* 5 = build_node（5）;ノード* 8 = build_node（8）; そしてもう一方のノードは何でしたか？ここを参照してみましょう。我々はまた、2を追加したい - ノードには、* 2 = build_node（2）; よし。この時点で、我々は7、3,9、および6を持っていることを知っている適切に配線されたすべてが、どのような約5、8、2？適切な順序ですべてを保つために、我々は3つの右の子が6であることを知っています。だから、我々は5を追加するつもりなら、 5はまた、3ルートとなっている木の右側に属しので、5、6の左の子として所属しています。我々は、6を言って、これを行うことができます - > left_child = 5; その後8ので9、9の左の子として所属 - > left_child = 8; その後2が3の左の子ですので、我々はここまでそれを行うことができます - なた - > left_child = 2; あなたは非常にそれに沿って実行しなかった場合、私はあなたがそれを自分で引き出すお勧めします。よし。これを保存してみましょう。 Let 'sは、外に出て、それをコンパイルしていることを確認しそれから私達は私達のcontainsの呼び出しを追加することができます。すべてがまだコンパイルのように見えます。のがに行くといくつかの呼び出しが含まれているに追加してみましょう。繰り返しますが、私はコピー＆ペーストの少しを行うつもりです。今では5,8、および2の検索してみましょう。よし。レッツは、このすべてがまだ良く見えていることを確認してください。すばらしい！保存して終了します。さて、コンパイルしてみましょう、と今度は実行してみましょう。すべてがちょうどいいとうまく機能しているような結果から、それが見えます。すばらしい！だから今我々は我々のcontainsが書かれた関数持っている。レッツに移動し、ツリーにノードを挿入する方法で作業を開始我々は今それをやっているように、以来、物事は非常にきれいではありません。我々は、仕様に戻った場合は、それは、インサートと呼ばれる関数を記述することが求められます - もう一度、boolを返すかどうかのために私たちは実際にツリーにノードを挿入することができます - その後木に挿入する値は次のように指定されている私たちのinsert関数に引数のみ。我々は確かにツリーにノードを含む値を挿入することができれば、trueを返しますこれは、我々、人は、十分なメモリを持っていたことを意味しますその後2、そのノードは既に以来ツリーに存在していなかった - 覚えて、我々は物事を簡単にするには、ツリー内の重複する値を持っているつもりはありません。よし。コードに戻る。それを開く。少しのズームは、次にスクロールダウンします。のが右のcontains上記insert関数を入れてみましょう。再び、それはboolインサート（int値）と呼ばれるようになるだろう。デフォルトとして、それを少しより多くのスペースを与え、そして、のは非常に末尾のreturn falseを入れてみましょう。今すぐダウン下部に、先に進み、代わりに手動でノードを構築しましょうメインで自分自身と配線それらを我々がやっているようにお互いを指すように、我々はそれを行うために私達のinsert関数に依存します。我々は、ちょうどまだ最初からツリー全体を構築するために私達のinsert関数に依存しませんむしろ我々は、これらの行を取り除くでしょう - we'llは、これらの行をコメントアウトします - それは、ノード5,8、および2を構築します。そしてその代わりに、我々はinsert関数への呼び出しを挿入します実際に動作することを確認します。ここに私達は行く。今、私たちは、これらの行をコメントアウトしました。私たちはこの時点で私たちのツリーに7、3,9、および6を持っています。これがすべて動作していることを確認し、我々は、我々のバイナリツリーを作成し、ズームアウトすることができますそれを実行し、我々は今、我々は完全に右だということを告げている含まれていることがわかります - 5,8、および2は、ツリーではなくなっています。コードに戻って、そしてどのように我々は挿入するつもりですか？我々は実際に以前、8、2 5を挿入したときに我々が何をしたか覚えています。我々は、我々はルートで開始したPlinkoゲームをプレイ一つずつ、ツリー1を下った我々は適切なギャップを発見するまで、その後、我々は適切な場所にノードに配線。私たちは同じことをやろうとしている。これは、我々が含まれている関数の中で使われているコードを書くようなもの基本的にはノードがどこにあるべき場所を見つけるために、それから私達はちょうどそこにノードを挿入しようとしている。ことをやってみましょう。だから我々は、ノード*電流=ルートを持って、我々は、単にコードが含まれてフォローするつもりだ我々はそれが非常に私たちのために動作しないことに気づくまで。我々は、現在の要素がnullでないときにツリーを通過しようとしている、我々が発見した場合、その電流の値は、我々は挿入しようとしている値と等しいです - まあ、これは我々が実際にノードを挿入できませんでしたケースの一つであるツリーにこれは我々が重複した値を持つことを意味するので。ここでは、実際にはfalseを返すつもりだ。さて、誰か他の電流の値が値よりも小さい場合、今、我々は右に移動することを知っている値は、curの木の右半分に属しているため。そうでなければ、我々は左に移動するつもりです。それはすぐそこに、基本的に私たちのCONTAINS関数です。この時点で、一度我々は、このwhileループを完了しました当社curのポインタがNULLを指すことになるだろう場合、この関数は既に戻っていない。そこで我々は、我々は新しいノードを挿入したい箇所に電流を抱えている。何を行うことが残っていることは、実際に新しいノードを構築することであるその我々はかなり簡単に行うことができます。我々は、我々の超便利なビルドノード機能を使用することができます我々が以前行っていないことと何か - 我々だけの種類のは当然のことだが、今は念のためにやる - 我々は、新しいノードによって返された値が実際にあったことを確認するためにテストしますそれがnullである場合、我々は、そのメモリへのアクセスを開始したくないので、nullではない。私たちは、新しいノードがnullに等しくないことを確認するためにテストすることができます。またはその代わりに、私たちは、それが実際にnullであるかどうかを確認できますそれがnullである場合には、私たちはただ早いfalseを返すことができます。この時点で、我々は、ツリー内の適切な場所に新しいノードを配線する必要があります。私たちは主を振り返ると、ここで我々は、前に実際に値の配線だったら私たちはツリーに3を置きたいと思ったときの方法は、我々はそれをやっていたことがわかり我々は、ルートの左の子にアクセスしました。私たちはツリーに9を置くとき、私たちはルートの右の子にアクセスしなければならなかった。私たちは、木に新たな価値を置くために親へのポインタを持つ必要がありました。挿入するために戻って上にスクロールして、それはかなりここで働くことはないだろう私たちは、親のポインタを持っていないので。私たちに何ができるようにしたいことは、この時点では、ある親の値をチェックしてください - まあ、おやっ、親の値が現在の値よりも小さい場合、その後、親の右の子は、新しいノードでなければなりません。そうでなければ、親の左の子は、新しいノードでなければなりません。しかし、我々は非常にまだこの親のポインタを持っていない。私たちは木を通って行くようにそれを得るために、我々は実際にそれを追跡する必要があるとしているそして先ほどのループ内の適切な場所を見つける。私たちは、insert関数の先頭に戻って上にスクロールしていることを行うことができますと別のポインタ変数を追跡することで、親を呼んだ。我々は、最初はnullに等しいそれを設定しようとしている私たちは木を通過した後、毎回、我々は現在のポインタと一致するように、親のポインタを設定しようとしている。電流に等しい親を設定します。このように、我々が通過するたびに、我々は現在のポインタにインクリメントされるようにするつもりだ親ポインタは、それに続く - ツリーの現在のポインタよりもちょうど1レベル高い。それはすべてのかなりよさそうだ。私は我々が調整したいと思う一つのことは、これはnullを返すノードを構築だと思います。ためには実際には正常にnullを返すためにノードを構築し得るため、私たちは、そのコードを変更する必要がありますここにいるので、私たちは、mallocは有効なポインタが返されたことを確認するためにテストされない。だから、その後、（！N = NULL）の場合 - mallocが有効なポインタが返された場合、次に我々はそれを初期化します; そうでなければ、私達はちょうど帰る、それが私たちのためにnullを返すことになります。今やすべてがかなりよさそうだ。のは、これは実際にコンパイルしていることを確認してみましょう。バイナリツリーを確認して、ああ、私たちはここで何が起こっているいくつかのものを持っている。我々は関数の暗黙的な宣言がノードを構築するんだ。繰り返しますが、これらのコンパイラで、私たちは一番上から開始するつもりです。何を意味する必要があり、私は実際にそれを宣言した前に私はノードを構築呼んでいるということです。のは本当にすぐにコードに戻りましょう。下にスクロールして、案の定、私のinsert関数が宣言されていますビルドノード機能上、しかし、私はカバーの内側のノードを構築使用しようとしている。私は、そのコピーに行くつもりです - そして、一番上にここまでビルドノード機能の方法を貼り付けます。そうすれば、うまくいけば、それは動作します。これはもう行くのを挙げてみましょう。今ではすべてコンパイルされます。すべてが良いです。しかし、この時点で、我々は、実際に私たちのinsert関数を呼び出していない。我々は、ちょうどそれがコンパイルされることを知っているので、のがに行くといくつかのコールをインチ置くよう私たちの主な機能で、その処理を行いましょう。ここで、我々は、5,8、および2をコメントアウトそれから私達はここにそれらを配線しませんでした。いくつかのコールを挿入するようにしましょう、とのはまた、我々が使用したものと同じ種類を使用してみましょう我々はすべてが正しく挿入されなかったことを確認するためにこれらのprintf関数の呼び出しを行ったとき。私は、コピーして貼り付けるつもりだそして代わりに、我々は挿入をやろうとしているが含まれています。とはなく、6、10、1の、我々は5 8、2、を使用するつもりです。これはうまくいけば木に5,8、および2を挿入する必要があります。コンパイルします。すべてが良いです。今、私たちは、実際に我々のプログラムを実行することになるでしょう。すべてはfalseが返された場合。だから、5、8、2は行かなかった、とCONTAINSは、それらを見つけることができませんでしたように見えます。どうなってるの？ズームアウトしてみましょう。最初の問題は、インサートがfalseを返すように見えたということでしたそしてそれは私達が私達のリターン偽の呼び出しでおいたのでそれはだような、見えるそして我々は実際に本当返されることはありません。私たちは、それを設定することができます。第二の問題は、我々が行う場合であっても、今ある - 、これを終了し、これを保存する makeを再度実行し、それを実行して、コンパイルしました - 私たちは、何か他のものがここで起きていることがわかります。 5,8、および2はまだツリーで見つかることはありませんでした。だから、何が起こっているのですか？のは、コード内でこれを見てみましょう。我々はこれを理解できるかどうか見てみましょう。私たちは、親がNULLになることはないから始まります。我々は、ルートポインタに等しい現在のポインタを設定するそして我々は木を通って我々の道を降りていくつもりです。現在のノードがnullでない場合は、我々は少し下に移動することができることを知っている。我々は、現在のポインタと等しくなるように私たちの親のポインタを設定する値をチェック - 値が同じである場合、我々は、falseが返された場合。値が小さい場合、我々は右に移動; そうでなければ、我々は左に移動しました。その後、我々はノードを構築します。私は少しでズームインします。そしてここで、我々は同じになるように値を配線しようとするつもりだ。どうなってるの？おそらくValgrindは私たちにヒントを与えることができるかどうかを確認してみましょう。私はValgrindは本当にすぐに実行という理由だけでValgrindは使いたい任意のメモリエラーがある場合は、あなたに伝えます。我々は、コードにValgrindはを実行するとあなたが見ることができるように右here--Valgrind./binary_tree--andのエンターキーを押します。あなたは、私たちは任意のメモリエラーを持っていなかったことがわかりますので、すべてが今のところ大丈夫みたいだ。我々はわからないので、私たちは、私たちが知っているいくつかのメモリリークを、持っている私たちのいずれかのノードを解放するために起こっている。実際に何が起こっているのを見て、GDBを実行してみましょう。私たちは、gdbをやる。/ binary_tree。それだけで正常に起動。の挿入時にブレークポイントを設定してみましょう。のは、実行してみましょう。それは我々が実際にインサートと呼ばれることがないように見えます。問題は、私は主にここに降りて変更されたときだけのことであったように見えます - 含まれていますから、これらのprintfの呼び出しのすべて - 私は実際にインサートを呼び出すために、これらを変更することはありません。今度はそれを試してみましょう。コンパイルしてみましょう。すべてはそこに良さそうに見える。今それを実行してみましょう、何が起こるかを参照してください。よし！すべてがそこにかなりよさそうだ。考えるための最終的なものであり、この挿入に任意のエッジケースがありますか？そしてそれは常に考えることは興味深い1エッジケース、まあ、ことが判明あなたのツリーが空であり、このinsert関数を呼び出す場合に何が起こるか、ですか？それは動作しますか？まあ、のはそれを試してみましょう。 - binary_tree C - 我々はこれをテストするつもりだ方法は、我々は、私たちの主な機能にまで行くつもりさとではなく、このような配線はこれらのノードを構成するのではなく、我々だけで、全体の事をコメントアウトするつもりだそして代わりにノード自身、アップ配線私たちは実際にちょうど先に行くとこれのすべてを削除することができます。私たちはすべて挿入するための呼び出しをするつもりだ。それでは、やらせる - の代わりに5、8、2、我々は3,7を挿入して、9になるだろう。そして、我々はまた、同様に6を挿入したいと思う。保存します。終了します。バイナリツリーを作成します。それはすべてコンパイルされます。私たちはただ、それをそのまま実行すると何が起こるかを見ることができますそれはまたことを確認するために、本当に重要なことになるだろう我々は、任意のメモリエラーを持っていないこれは我々が知っている私たちの最先端の例の1つなので。レッツは、それがValgrindでうまく動作することを確認するその我々がちょうどValgrindの。/ binary_treeを実行してやる。我々は確かに一つの文脈からエラーを1つ持っているように見えます - 我々は、このセグメンテーションフォールトを持っています。何が起こったのか？それがどこにあるかValgrindは、実際に教えてくれる。少しズームアウトします。それが私たちのinsert関数で何が起こっているようにそれは、見え我々は挿入でサイズ4の不正な読み取りを持って、60行目。の前に戻って、ここで何が起こっているのか見てみましょう。本当に速いズームアウトします。私たちはすべてを見ることができるので、それが画面の端に行かないことを確認したい。少しでそれを引き出します。よし。下にスクロールして、問題はまさにここです。、私たちが降りる場合はどうなりますか、私たちの現在のノードがすでにnullである我々は非常に上、右ここで見上げるので、もし私たちの親ノードがnullの場合 - このwhileループは、実際には決して実行されない場合我々の現在の値がnullであるため - curがnullであるように私達のルートがnullである - その後、私たちの親は、最新版にするか、有効な値に設定されることはありませそう、親もnullになります。我々はそれをチェックするために覚えておく必要が時間によって、私たちはここで降りて、私たちは親の値へのアクセスを開始。だから、何が起こりますか？まあ、親がnullの場合 - （親== NULL）の場合 - その後、私たちは知っているツリーには何があってはなりません。我々はルートにそれを挿入しようとしなければなりません。私達はちょうど新しいノードに等しいルートを設定することにより、それを行うことができる。すると、この時点で、我々は実際にこれらの他のものを通過する必要はありません。代わりに、右ここで、我々は、のelse-if-elseのいずれかを行うことができますまたは我々は、他のここですべてのものを組み合わせることができますしかし、ここで我々はちょうど他の使用して、それをそのようにするつもりだ。今、私たちは私たちの親がnullでないことを確認するためにテストするつもりだその前に実際にそのフィールドにアクセスしようとしている。これは、私たちはセグメンテーションフォールトを避けるのを助けるでしょう。だから、我々が終了し、実行、コンパイル、ズームアウトします。エラーはありませんが、我々はまだメモリリークの束を持っているん我々は任意のノードを解放しなかったため。しかし、我々がここまで行くと、我々のプリントアウトを見れば、我々は良いです、trueを返したが、まあ、私たちのインサートのすべてのように見えることがわかります。挿入はすべてtrueになり、し、適切なCONTAINSコールもまた真である。仕事グッド！我々は正常にインサートを書いているように見えます。それは私たちが今週の問題セットの仕様のために持っているすべてです。考えるための一つの楽しいチャレンジは、あなたが実際に行くとどのようにそしてこのツリー内のノードのすべての自由。我々は、そう多くの異なった方法を行うことができますしかし、私は、実験にあなたにすることをお任せしますそして楽しい挑戦として試してみて、あなたが確認することができていることを確認してくださいこのValgrindのレポートは、エラーや漏れが返されないことを確認します。今週のハフマン符号化の問題セットで頑張って、そして我々は来週お会いしましょう！ [CS50.TV]