[Powered by Google Translate] [第7條]​​ [舒適] 內特 - 哈迪森] [哈佛大學] 這是CS50。[CS50.TV] 歡迎來到第7。 由於颶風沙地， 有一個正常的部分，而不是本週， 我們這樣做是步行通過，通過的部分問題。 我要跟著問題設置6規格， 和經歷中的問題 A組的問題部分。 如果有任何問題， 請上發布這些CS50討論。 好吧。讓我們開始吧。 現在，我期待在第3頁的習題集規範。 我們將第一次開始談論二叉樹 因為有很多這一周的問題集中相關 - Huffman樹的編碼。 我們談到CS50的第一個數據結構的數組。 請記住，數組是一個序列的元素 - 所有相同類型的 - 彼此旁邊存儲在內存中。 如果我有，我可以得出一個整數數組使用這盒數的整數風格 - 比方說，我在第一個框中有5個，我有7個在第二， 然後，我有8個，10和20在最後中。 記住，真正的好東西，關於這個數組 是，我們有這個固定時間的任何特定元素的訪問  在陣列中，如果我們知道它的索引。 例如，如果我想要抓住的第三個元素的數組 - 索引2處使用我們的從零開始的索引系統 - 我真的只是做一個簡單的數學計算， 跳，在數組中的位置， 拔出存儲8， 我好到哪裡去。 這個數組的一個不好的地方 - 我們談論 當我們討論鍊錶 - 是，如果我想這個數組中插入一個元素， 我將做一些轉移周圍。 例如，該陣列在這裡 在排序 - 升序排序 - 5，然後7，然後是8，然後10，然後20 - 但如果我要插入到這個數組中的數字9， 我將不得不改變一些元素，以騰出空間。 我們可以得出這樣的在這裡。 我要移動5星，7，然後是8; 創建一個差距在哪裡，我可以把9， ，然後在10和20可以去的9的權利。 這是一種痛苦，因為在最壞的情況下 - 當我們插入的開始或結束時 數組，取決於我們如何轉變 - 我們可能最終不得不將所有的元素 我們目前存儲在數組中。 那麼，究竟是什麼辦法解決這個問題？ 解決這個問題的辦法是去我們的鍊錶方法 - 代替存儲元件5，7，8，10和20的所有在內存中彼此旁邊 - 是我們，而不是沒有被存儲他們種的地方，我們希望將它們存儲 我在這些鍊錶節點繪製出在這裡，種專案。 然後我們使用這些next指針連接在一起的。 我可以有一個指針從5到7， 從7到8的指針， 從8到10的指針， 最後，從10到20，一個指針 然後在20表示一個空指針，有什麼也沒有留下。 說，我們這裡的權衡 是，現在如果我們要插入到我們的排序列表中的數字9， 所有我們要做的是創建一個新的節點9， 它添加到相應的地方， ，然後再線8點到9。 這是相當快的，如果我們確切地知道我們要插入的9。 但權衡，以換取這是我們現在已經失去了固定時間的訪問 任何特定的元素在我們的數據結構。 例如，如果我想找到這個鍊錶中的第四個元素， 我要開始在一開始的列表 通過計算節點的節點，直到我找到工作，我的第四個。 為了獲得更好的訪問性能比鍊錶 - 但也保留了一些的好處，我們有 在一個鍊錶插入時間方面 - 一個二叉樹將需要使用多一點的內存。 在特定的，而不是僅僅有一個二叉樹結點的指針 - ，如鍊錶節點 - 我們要添加第二個指針的二進制樹節點。 而不是僅僅有一個指針指向下一個元素， 我們將有一個左孩子和右孩子指針。 讓我們來畫一幅畫，看什麼，實際上看起來像。 同樣，我要使用這些方框和箭頭。 二叉樹節點將開始只是一個簡單的框。 這將有空間的價值， 然後它也有一個空格的左孩子和右孩子。 我要在這裡貼上標籤。 我們將有左孩子，然後我們要正確的孩子。 這樣做有很多不同的方式。 有時空間與便利性， 實際上，我會像我在這裡做的底部畫 我要去的地方在頂部的價值， 然後右子上的右下角， 和左子節點上的左下方。 回去這個頂部圖， 我們的價值在最高層， 然後我們有左孩子指針，然後我們有右孩子指針。 在問題設置規範， 我們談論繪製一個節點，有一個價值7， 然後左子指針，該指針是空值，和一個右子節點指針為null。 我們可以寫資本NULL的空間 無論是左孩子和右孩子，或者我們可以得出這樣的斜線 通過每個框的，以表明它是空的。 我要做的，只是因為這是簡單的。 你在這裡看到的是一個很簡單的二進制樹節點的繪圖兩種方式 我們的價值和空的子結點指針。 我們的規範談如何用鍊錶的第二部分 - 請記住，我們只需要保持在列表中的第一個元素 記得整個列表 - 同樣地，用二叉樹，我們只有堅持一個指針指向樹 為了保持控制在整個數據結構。 這種特殊的元件被稱為樹的樹的根節點。 例如，如果這一個節點 - 包含該值的7此節點 空的左和右孩子指針 - 在我們的樹是唯一的價值， 那麼這將是我們的根節點。 這是一開始我們的樹。 我們可以更清楚地看到這一點，一旦我們開始將更多的節點添加到樹中。 讓我牽了新的一頁。 現在，我們要畫一棵樹，有7根， 3內的左孩子，和9的右子內。 再次，這是非常簡單的。 我們已經拿到了7，為3，繪製一個節點一個節點9， 我要設置的左孩子指針指向的節點包含3， 和含有7到節點含有9的節點的右子節點指針。 現在，因為3和9沒有任何兒童， 我們要設置其所有的子結點指針為空。 這裡，我們的樹的根目錄對應到含的節點的數目7。 你可以看到，如果我們所擁有的是一個指針，該根節點， 然後，我們可以步行通過我們的樹和訪問這兩個子節點 - 3和9。 沒有需要保持樹的每一個節點上的指針。 好吧。現在，我們要到另一節點添加到這個圖。 我們要添加一個節點包含6， 我們要添加為右子節點包含3。 要做到這一點，我要抹去空指針在3個節點 ，並將其連接到指向的節點包含6。好吧。 在這一點上，讓我們去一點點的術語。 要啟動的原因，這就是所謂的二進制樹，特別是 是，它有兩個子結點指針。 還有其他類型的樹木，有更多的孩子指針。 特別是，你做了習題集5“嘗試”。 你會發現，在試圖，不同的孩子有27個不同的指針 - 在英語字母表的26個字母， 然後在27日的所有格符號 - 所以，這是一種類型的樹相似。 但在這裡，因為它是二進制的，我們只能有兩個子結點指針。 除了我們剛才談到這個根節點， 我們也被扔圍繞這個詞的孩子。“ 一個節點是一個孩子的另一個節點是什麼意思？ 它的字面意思，子節點是孩子的​​另一個節點 如果其子結點指針設置為指向該節點，其他節點有一個。 為了把這個更具體的條款， 如果有3所指向的孩子指針7，然後是一個孩子的7。 如果我們要弄清楚什麼是兒童的7 - 好，我們看到，7具有指針3至9和一個指針， 所以9和3的孩子7。 九無兒無女，因為它的子結點指針是空的， 3只生育一個孩子，6。 六還沒有孩子，因為它的指針是空的，現在我們將繪製。 此外，我們還談論一個特定節點的父母， 這是，正如你所期望的，這個孩子描述的相反。 每個節點只有一個父 - 你可能期望與人類，而不是兩個。 例如，父3是7。 的父9也是7，和3的父6是。沒有太多的不同。 我們也有談論的祖父母和孫子女的條款， 更普遍的是，我們談論的祖先 特定節點的後裔。 一個節點的祖先 - 祖先，而是一個節點 - 是位於從根到該節點的路徑上的所有節點。 例如，如果我期待在節點6， 然後祖先都將是3和7。 的祖先，例如，9 - 如果我在尋找的節點9 - 然後的祖先9 7。 及後裔剛好相反。 如果我想看7的後裔， 然後，我要看看它下面的所有的節點。 所以，我有3，9，和6 7所有的後裔。 最後一個學期，我們將談論的是這個概念的兄弟姐妹。 兄弟姐妹 - 種這些家庭的條款 - 的節點樹中，在同一水平。 因此，圖3和圖9是同級的，因為他們是在樹中的相同的水平。 他們都具有相同的父，7。 6有沒有兄弟姐妹，因為沒有任何兒童。 7並沒有任何兄弟姐妹，因為它是我們的樹的根， 而且也只有1根。 在未來的7到有兄弟姐妹就必須在7以上是一個節點。 將必須是有一個父如圖7所示，在這種情況下，7將不再是樹的根節點。 7新的母公司也必須有一個孩子， 和那個孩子，然後是兄弟姐妹7。 好吧。移動。 當我們開始討論二叉樹， 我們談到了我們如何去使用它們來 獲得數組和鍊錶的優勢。 的方式，我們要做到這一點，是這個順序屬性。 我們說，一個二進制樹是有序的，根據本說明書， 如果在我們的樹的每個節點，其後代在左側 - 左子的左子的後裔 - 有較小的值，並且在右邊的所有的節點 - 右邊的孩子和右孩子的後裔 - 有節點大於當前節點的值，我們正在尋找。 簡單起見，我們將假設在我們的樹，不會有任何重複的節點。 例如，在這棵樹中，我們要處理的情況下， 我們有7根  那麼我們也必須值7在樹中的其他地方。 在這種情況下，你會發現，這棵樹確實是有序的。 我們有7根。 一切以左側的7 - 如果我取消所有的這些小標記 - 一切左側的7 - 在3和6 - 這些值都小於7，一切的權利 - 這僅僅是這9 - 大於7。 這不是唯一的有序樹包含這些值， 但讓​​我們畫一些更多的人。 其實是有一大堆的方法，我們可以做到這一點。 我要使用速記，只是為了讓事情簡單的地方 - 而不是整個框和箭頭 - 我只是要繪製的數字和箭頭連接。 開始，我們就寫我們原來的樹又在哪裡，我們有7個，然後3， 然後3指出返回到6的權利， 孩子有權利為9。 好吧。另一種方式，我們可以寫這棵樹什麼？ 而不是有3的左子7， 我們也可以有6左子7， 然後是左子6。 這看起來像這棵樹在這裡我得到了7， 然後6，然後3，和一個9右側列表。 我們也不必作為我們的根結點中有7個。 我們也可以作為我們的根節點。 那麼，具體怎麼樣的？ 如果我們要保持這種有序的屬性， 6左側的​​一切有小於它。 只有一個可能，那就是3。 但是，當6的右孩子，我們有兩種可能性。 首先，我們可以有7，然後9， 或者我們可以借鑒 - 就像我要在這裡做的 - 我們有9 6的右子， 然後7的左子9。 現在，圖7和圖6是不是唯一可能的值為根。 我們還可以有3根。 如果是在根會發生什麼情況呢？ 在這裡，事情就變得有點有趣。 三不小於它的任何值， 使整個左側的樹是為空。 不會是什麼。 的權利，我們可以列出按升序排列。 我們可以有3，然後按6，然後按7，然後9。 或者，我們可以做3，然後6，然後按9，然後7。 或者，我們可以做3，然後按7，然後6，然後按9。 ，3，7 - 其實也沒什麼，我們不能做了。 這是我們的一件事。 我們可以做9，然後從9中，我們可以做6，然後7。 或者，我們可以做3，然後按9，然後7，然後6。 提請您注意，這裡的一件事是 這些樹是一個有點怪異的前瞻性。 特別是，如果我們看一下右側的4棵樹上的 - 我會圈，這裡 - 這些的樹木看起來幾乎完全一樣的一個鍊錶。 每個節點都只有一個孩子， 所以我們不具有任何類似樹的結構，我們看到，例如，  在這一個孤獨的樹在這裡的左下角。 事實上，這些樹被稱為退化二進制樹， 我們將討論這些更多的未來 - 特別是如果你採取其他的計算機科學課程。 這些樹是退化的。 他們不是非常有用的，因為事實上，這種結構本身  類似於一個鍊錶的查找時間。 我們沒有得到充分利用額外的內存 - 這額外的指針 - 因為我們的結構，這種方式是壞的。 而不是去和畫出來的二進制樹，有9根， 這是最後的情況下，我們將不得不， ，在這一點上，而不是我們要談一點點關於這個其他條款 我們使用時，談論的樹，這被稱為高度。 樹的高度是從根到的最遙遠的節點的距離， 或者更確切地說，跳數，你將不得不作出以 從根開始，然後結束在最遙遠的樹中的節點。 如果我們看一下這些樹在這裡，我們已經制定， 我們可以看到，如果我們採取這種樹在左上角，我們開始在3， 然後，我們有1跳6，第二跳的7， 和三分之一一跳得到的9。 所以，這種樹的高度是3。 我們可以做同樣的練習，概述了這個綠色的樹木， 我們看到，所有這些樹的高度也確實是3。 這是什麼使他們墮落的一部分 - 它們高度僅僅是一個小於在整個樹中的節點的數目。 如果我們看看這樹用紅色包圍，另一方面， 我們看到，最遠處的葉節點是6和9 - 的葉子有沒有孩子的節點。 所以，為了得到從根節點到6或9， 我們必須做出一個躍點得到的7，然後得到的第二跳到9， 同樣地，只有一個第二跳從7到6。 因此，這棵樹的高度，在這裡只有2個。 你可以回去和做到這一點，我們前面所討論的所有其他樹木 開始與7和6， 你會發現，所有這些樹的高度也是2。 究其原因，我們一直在談論有序二元樹 以及為什麼他們很酷，是因為你可以搜索他們的 在一個排序的數組中搜索一個非常類似的方式。 這是我們談論獲得該改進的查找時間 在簡單的鍊錶。 通過鏈接的列表中 - 如果你想找到一個特定的元素 - 你最好做某種線性搜索 你從哪裡開始的一個列表，跳一個接一個開始 - 一個節點由一個節點 - 整個列表，直到你發現你要尋找的。 然而，如果你有一個二叉樹的存儲在這個漂亮的格式， 實際上，你可以得到更多的二進制搜索 分而治之 通過適當的一半在每一步的樹和搜索。 讓我們來看看它是如何工作。 如果我們有 - 再次，要回我們原來的樹 - 我們從7點開始，我們有3個在左側，9的右邊， 和下方的3，我們有6。 如果我們想要搜索的數量在這棵樹，我們就從根開始。 我們將比較的價值，我們要尋找的，說6， 在節點中存儲的值，我們目前正在觀察，7， 找到6是確實小於7，所以我們會向左側移動。 6如果該值大於7，我們將，而不是移動到右側。 因為我們知道 - 由於我們的排序二叉樹的結構 - 所有的值小於7的將被存儲到7的左側， 有沒有必要通過右側的樹，甚至懶得看。 一旦我們移動到左邊，我們現在在節點3， 我們比較了3和6，我們可以再次做同樣的比較。 我們發現，6 - 我們正在尋找的價值 - 大於3， 我們可以去含有3的節點的右側。 這裡有沒有左側，因此，我們可以忽略了。 但是，我們只知道，因為我們正在尋找在樹的本身， 我們可以看到，樹有沒有孩子。 這也很容易看在這棵樹，如果我們這樣做，我們自己作為人類， 但機械，讓我們按照這個過程就像一台計算機做 要真正理解算法。 在這一點上，我們現在看到的一個節點，其中包含6， 我們正在尋找的價值6， 因此，事實上，我們已經找到了合適的節點。 我們發現，在我們的樹，和值6，我們可以停止我們的搜索。 在這一點上，這是怎麼回事， 我們可以說，是的，我們已經找到了價值6，它存在於我們的樹。 或者，如果我們打算插入一個節點，或者做了什麼，我們可以做的，在這一點。 讓我們做一對夫婦更多的查詢只是為了看看它是如何工作的。 讓我們來看看會發生什麼，如果我們要嘗試，並期待值10。 如果我們要查找的值是10，我們從根開始。 我們會看到，10比7，所以我們要移動到右邊。 我們會得到的9與比較9到10，請參閱圖9是確實小於10。 所以，再一次，我們會想辦法移動到正確的。 但在這一點上，我們會發現，我們正處在一個空節點。 什麼也沒有。其中10應該是沒有什麼。 這是我們可以報告失敗 - 這確實是樹中的10號。 最後，讓我們通過的情況下，我們試圖查找樹中的。 這是會發生什麼，如果我們看一下上漲了10，除了要正確的，而不是相似， 我們要去去左邊。 首先，我們在7和1小於7，所以我們向左側移動。 我們得到的3和1小於3，所以我們再次嘗試移動到左邊。 在這一點上，我們有一個空節點，所以我們可以再一次失敗。 如果你想了解更多有關二進制樹， 有一大堆有趣的小問題，你可以與他們無關。 我建議實行這些圖一 和之後通過的所有的不同步驟， 因為這會在超級方便 不僅是當你在做的霍夫曼編碼問題集 而且在未來的課程 - 只是在學習如何繪製出這些數據結構和思考的問題 筆和紙，在這種情況下，iPad和手寫筆。 雖然在這一點上，我們要繼續前進做一些編碼實踐 玩這些二進制樹和看到的。 我要切換回我的電腦。 對於這部分的部分，而不是使用CS50運行或CS50空間的， 我要使用的設備。 之後隨著習題集的規格， 我看我應該打開的設備， 去我的Dropbox文件夾，創建一個文件夾，名為第7， 然後創建一個名為binary_tree.c。 在這裡，我們走了。我有的家電已經打開。 我要拉一個終端。 我要到Dropbox文件夾，創建一個目錄稱為第七條第 這是完全空的。 現在，我要開拓binary_tree.c。 好吧。在這裡，我們走 - 空文件。 讓回去的規範。 該規範要求，以創建一個新的類型定義 包含int值的二進制樹節點 - 一樣的價值，我們在我們的圖表前抽出。 我們將使用這個樣板的typedef，我們在這裡做了 你應該認識到，從習題集5 - 如果你做了哈希表的方式征服了拼寫檢查程序。 你也應該認識到它從上週的部分 我們談到鍊錶。 我們走了這麼一個結構節點的typedef， ，我們給這個結構節點結構節點名稱事先 所以，我們就可以引用它，因為我們會希望有結構的節點指針 我們的結構的一部分，但我們已經包圍這 - 或者更確切地說，附上 - 一個typedef 這樣一來，後面的代碼中，我們可以參考這個結構只是一個節點，而不是一個結構節點。 這將是非常相似的單鍊錶的定義，我們看到上週。 要做到這一點，我們剛開始寫的樣板。 我們知道，我們必須有一個整數值， 所以我們把int值，然後，而不是只是一個指針指向下一個元素 - 我們做的單鍊錶 - 我們將有左，右孩子指針。 這是非常簡單 - 節點左孩子; 和節點右子樹。酷。 這看起來是一個不錯的開始。 讓回去的規範。 現在，我們需要聲明一個全局變量節點*樹的根。 我們將會使這個全球性的，就像我們第一個指針鍊錶也是全球。 這是如此，在我們寫的功能 我們不必通過圍繞這根 - 雖然我們會看到，如果你想遞歸寫的這些功能， 它可能會更好，甚至沒有傳遞它作為一個全球性擺在首位 ，而不是在本地初始化它的主要功能。 但是，我們會做它在全球範圍內啟動。 同樣，我們將一對夫婦的空間，我要聲明一個節點*根。 只是，以確保我不離開這個未初始​​化的，我將它設置為null。 現在，在主要功能 - 我們會寫的真的很快在這裡 - INT主要（INT ARGC，為const char *的argv []） - 我要開始我的argv數組聲明為const只是讓我知道 這些參數是，我可能不希望修改的參數。 如果我想修改我也許應該副本。 你會看到這是一個很大的代碼。 這是無論哪種方式。它的優良把它作為 - 省略cons​​t如果你想。 我通常把它放在這樣我提醒自己  我可能不希望修改這些參數。 與往常一樣，我要包括的主要在0線。 在這裡，我將我的根節點初始化。 既然這樣，現​​在，我有一個指針，該指針被設置為空， 因此，它指向不惜一切代價。 為了真正開始建設的節點， 我首先需要為它分配內存。 我要做到這一點，使內存使用malloc在堆上。 我要設置root的malloc的結果， 我，我會用sizeof運算符的大小來計算的節點。 究其原因，我使用sizeof節點，而不是，比方說， 做這樣的事情 - 的malloc（4 +4 +4）或malloc 12 - 是因為我想我的代碼是盡可能地兼容。 我希望能夠藉此c文件，在設備上編譯它， 然後編譯它在我的64位Mac - 或在一個完全不同的架構 - 我想這一切都是為了工作。 如果我的假設變量的大小 - 一個int或一個指針的大小尺寸 - 然後我也假設有關的各種架構 我的代碼可以成功編譯運行。 始終使用sizeof，而不是手動總結的結構域。 另一個原因是，也有可能是，編譯器將結構體的填充。 即使只是總結的各個字段，您通常需要做的事情， 因此，刪除該行。 現在，要真正初始化這個根節點， 我要為每個不同領域的價值有堵塞。 例如，我知道我要的值初始化為7， 現在我要設置的左孩子為空 和孩子也為空。太好了！ 我們已經這樣做了部分的規範。 規格在第3頁的底部，問我到創建三個節點 - 一個含有3，一個含有6，和一個與9 - 然後將它們連接起來，所以它看起來完全像我們的樹形圖 我們都在談論以前。 現在讓我們來很快在這裡。 你會看到，真的很快，我要開始寫一堆重複的代碼。 我要創建一個節點*，我會打電話給它3。 我將它設置為等於對malloc（如sizeof（節點））。 我要設置三個值= 3。 三 - > left_child = NULL; 3 - >右鍵_child = NULL;以及。 這看起來非常相似初始化的根，這正是 我會做，如果我開始初始化第6和第9。 我會做的真的很快在這裡 - 其實，我打算做一個小的複製和粘貼， ，並確保我 - 好吧。  現在，我已經把它複製，我可以去進取，這等於6。 你可以看到，這需要一段時間，而不是超高效。 只是一點點，我們將編寫一個函數，我們將做到這一點。 我想更換了9，將其更換為6。 現在我們已經得到了我們所有的節點創建和初始化。 我們有我們的根設置等​​於7，或包含該值的7， 我們的節點3，節點6，節點包含9。 在這一點上，我們需要做的是線的一切行動。 我初始化的指針為NULL的原因是，只是讓我確保 我沒有任何未初始化的指針，在那裡意外。 還因為，在這一點上，我只有實際連接的節點彼此 - 那些他們實際上是連接到 - 我沒有去，並 確保在適當的地方，所有的零點都在那裡。 從根開始，我知道根的左孩子是3。 我知道根的右孩子是9。 之後，其他的孩子，我已經離開了擔心 3的右孩子，這是6。 在這一點上，它看起來很不錯。 我們將刪除這些行。 現在，一切都看起來很不錯。 讓我們回到我們的規範，看看我們下一步需要做的。 在這一點上，我們必須寫一個函數叫做'包含' “布爾包含（int值）的原型。 這包含函數將返回true  如果樹指出，我們在全球的根目錄變量  包含的值傳遞到功能，否則返回false。 讓我們繼續這樣做。 這將是完全一樣的查找，我們沒有在iPad上只是一點點前的手。 讓我們在一點點放大，向上滾動。 我們打算把這個功能超出了我們的主要功能 所以，我們沒有做任何形式的原型設計。 因此，布爾（int值）。 我們走吧。這就是我們的樣板聲明。 只是為了確保這將編譯， 我要繼續前進，就設置它等於返回false。 現在這個功能只是不會做任何事情，總是報告說， 我們正在尋找的價值是不是在樹中。 在這一點上，它可能是一個好主意 -​​ 因為我們已經寫了一大堆的代碼，我們甚至還沒有嘗試過測試，但 - 以確保所有編譯。 有一對夫婦的事情，我們需要做的，以確保這實際上將編譯。 首先，看看我們是否已經使用在任何圖書館的任何功能，我們還沒有計算在內。 的功能，我們一直使用的是malloc的， 然後，我們也一直在使用這種類型的 - 這非標準型名為“bool'的 - 它包含在標準的bool頭文件。 我們一定要到包括標準bool.h的為bool類型， 我們也希望＃標準庫包括標準的lib.h 包括malloc和自由，所有這一切。 因此，縮小，我們要退出。 讓我們嘗試作出肯定，這確實編譯。 我們可以看到它，所以我們在正確的軌道。 讓我們再次打開binary_tree.c。 它編譯。讓我們下去，並確保我們將我們的包含函數調用 - 只是為了確保一切都很好，好。 例如，當我們做了一些我們的樹中查找， 我們試圖尋找的值6，10，1，我們知道在樹中， 10，是不是在樹中，1個是不是在樹中。 讓我們用這些樣本要求，以此來找出是否 我們包含了功能是否正常工作。 為了做到這一點，我要使用printf函數， 我們要打印出包含調用的結果。 我打算把字符串中的“包含（D）=因為  我們將插頭的價值，我們要去看看， =％S \ n“，並用它作為我們的格式化字符串。 我們只是從字面上看 - 在屏幕上打印出 - 什麼看起來像一個函數調用。 這是不是真正的函數調用。  這僅僅是一個字符串，看起來像一個函數調用。 現在，我們要插入的值。 我們將嘗試包含6， 然後我們要在這裡做的是使用該三元運算符。 讓我們來看看 - 包含6 - 所以，現在我已經含有6個，如果包含6個是真實的， ，我們將發送到％s格式字符的字符串 將是字符串“true”。 讓我們多一點點滾動。 否則，我們要發送的字符串“false”，如果包含6個返回false。 這是一個有點愚蠢的前瞻性，但我想我還不如說明 三元運算符看起來像什麼，因為我們還沒有看到它一段時間。 這將是一個不錯的，方便的方法計算出，如果我們的工作包含函數。 我要滾動到左邊， 我要複製和粘貼這行幾十倍。 它改變了一些值左右， 所以這會是1，而這將是10。 在這一點上，我們已經有了一個很好的包含函數。 我們已經有了一些測試，我們將看到如果這一切工作。 在這一點上，我們已經寫了一些代碼。 退出時間，確保一切都還編制。 退出了，現在讓我們嘗試再次二叉樹。 好了，看起來我們已經得到了一個錯誤， 我們已經得到了這個顯式聲明的庫函數printf的。 看起來我們需要去和＃include standardio.h。 有了這樣的，一切都應該編譯。我們都很好。 現在，讓我們嘗試運行的二進制樹，看看會發生什麼。 我們在這裡，/ binary_tree， 我們看到，正如我們的預期 - 因為我們還沒有實現，還包含， 或者說，我們剛剛返回false - 我們可以看到，它只是返回false，所有的人， 所以這一切都工作在大多數情況下，相當不錯。 讓我們回去，真正實現包含在這一點上。 我要向下滾動，放大， - 請記住，我們所使用的算法是，我們的根節點開始 然後我們遇到的每個節點，我們做了比較， 並根據對這樣的比較中，我們可以移動到左子或右子。 這是怎麼回事，我們先前寫在長期的二進制搜索代碼看起來非常相似。 當我們開始時，我們知道，我們要堅持到當前節點 ，我們正在尋找與當前節點將被初始化到根節點。 而現在，我們要繼續通過樹， 記住，我們的終止條件 -  當我們真正完成手頭的例子 - 當我們遇到一個空節點， 當我們看著一個空的孩子， 而當我們實際移動中的一個節點樹 並發現，我們正處在一個空節點。 我們要迭代，直到電流不等於空。 那我們該怎麼辦？ 如果我們要測試（電流 - >值==值）， 那麼我們就知道我們實際上已經發現的節點，我們正在尋找。 所以在這裡，我們可以返回true。 否則，我們希望看到與否的值小於該值。 如果當前節點的值是小於該值，我們正在尋找， 我們要移動到右邊。 因此，電流=電流 - > right_child;否則，我們將要移動到左邊。 電流=電流 - > left_child;。很簡單。 您可能認識的循環，看起來非常相似，這從 二進制搜索在長期，但那時我們正在處理的低，中，高。 在這裡，我們只需要看看在當前值， 所以這是不錯的，簡單的。 讓我們確保代碼工作。 首先，請確保它編譯。看起來喜歡它。 讓我們嘗試運行它。 而事實上，它打印出的一切，我們預計。 它發現樹中，沒有找到10，因為10是不是在樹中， 並沒有發現要么是因為1是不是在樹中。 很酷的東西。 好吧。讓我們回到我們的規範，看看接下來會發生什麼。 現在，要添加一些節點到樹中。 要加5，2，8，並確保我們的包含的代碼 仍如預期般運作。 讓我們做到這一點。 在這一點上，而不是再這樣做惱人的複製和粘貼， 讓我們寫一個函數創建一個節點。 如果我們向下滾動的方式為主，我們看到，我們一直在做這 一遍又一遍，每次，我們要創建一個節點非常相似的代碼。 讓我們寫一個函數，將實際為我們建立一個節點，並將其返回。 我要把它稱為build_node。 我要建立一個節點，一個特定的值。 在這裡放大。 我首先要做的是創造空間的節點上堆的。 因此，節點* N =的malloc（sizeof（節點）的）; N - >值=值; 那麼在這裡，我只是要初始化所有字段是適當的值。 在最後，我們將回到我們的節點。 好吧。有一點要注意的是，這個函數就在這裡 會返回一個指針一直堆分配的內存。 有什麼好有關的是，這個節點 - 我們要聲明，因為如果我們宣布它在棧上的堆 我們將無法在這個函數中這樣做。 該內存走出去的範圍 將是無效的，如果我們試圖稍後訪問。 自從我們宣布堆中分配的內存， 我們要照顧釋放後 我們的程序沒有任何內存洩漏。 我們一直在踢，一切在代碼中 只是為了簡單起見，在時間， 但如果你寫一個函數，看起來像這樣 ，你就有了 - 有人稱之為一個malloc或realloc內 - 你想知道，你提出某種意見在這裡說， 嘿，你知道，返回與傳入的值初始化堆分配的節點。 然後你要確保你把某種提示說 調用者必須釋放返回的內存。 這樣一來，如果有人會去，並使用該功能， 他們知道，無論他們獲得從該函數 在某些時候需要被釋放。 假設在這裡一切都很好，好， 我們可以去到我們的代碼，並更換所有這些線路在這裡 我們構建節點功能的調用。 讓我們做的真的很快。 在這裡的一個部分，我們不是要取代的是這部分 在底部，我們實際上連接起來的節點指向對方， 因為我們不能做我們的功能。 但是，讓我們做根* 3 = build_node（7）;節點= build_node（3）; 節點* 6 = build_node（6）;節點* 9 = build_node（9）;。 而現在，我們也想添加節點 - 節點* 5 = build_node（5）;節點* 8 = build_node（8）; 什麼是其他節點？讓我們來看看這裡。我們也想添加2 - 節點* 2 = build_node（2）; 好吧。在這一點上，我們知道，我們已經得到了，3，9，7和6 所有的有線，適當的，但5日，8日和2？ 為了保持一切以適當的順序， 我們知道，3的右孩子是6。 所以，如果我們要添加5， 5還屬於樹的右側，其中3是根 等5屬於左子6。 為此，我們可以說，6 - > left_child = 5; 然後在8屬於左子9，9 - > left_child = 8; ，然後是左子3，所以我們可以做的，在這裡 - 你 - > left_child = 2; 如果你沒有相當跟著，我建議你畫出來自己。 好吧。讓我們拯救。讓我們走出去，以確保編譯， 然後我們就可以加入我們的CONTAINS調用。 看起來一切都還編制。 讓我們去，並添加一些包含調用。 再次，我會做一點點的複製和粘貼。 現在，讓我們來搜索5，8，和2。好吧。 讓我們相信，這一切看起來還不錯。太好了！保存並退出。 現在，讓我們編譯，現在讓我們來運行。 從結果來看，它看起來一切都剛剛好工作和好。 太好了！所以，現在我們已經得到了我們的包含函數寫的。 讓我們繼續前進，並開始工作如何插入到樹中的節點 因為，我們現在做的是正確的，事情是不是很漂亮。 如果我們回去的規範， 它要求我們稱為“插入” - “再編寫一個函數，返回一個布爾值， 我們是否可以插入到樹節點 - 然後插入到樹中的值被指定為 我們的插入函數的唯一參數。 我們將返回true，如果我們確實可以插入到樹的節點上， 這意味著我們，一，有足夠的內存， 然後兩個，則該節點沒有已經存在的樹，因為 - 請記住，我們不會在樹中有重複的值，只是為了讓事情簡單。 好吧。回到代碼。 打開它。放大一點，然後向下滾動。 讓我們把正上方的contains插入功能。 再次，它被稱為布爾插入（int值）。 給它多一點空間，然後，在默認情況下， 讓我們在最後返回false。 現在已經降到底部，讓我們繼續前進，而不是手動構建的節點 在主自己，並把它們連接指向對方，就像我們正在做的， 要做到這一點，我們將依靠我們的插入功能。 我們將不依賴於我們的插入功能來構建整個樹從頭開始，只是還沒有， 而是我們將擺脫這些線路 - 我們就會註釋掉這些行 - 建立結點5，8，和2。 而我們將插入調用我們的插入功能 以確保實際工作。 在這裡，我們走了。 現在，我們已經發表了這些行。 我們只有7，3，9，和6在我們的樹在這一點上。 要知道，這是所有工作， 我們可以放大，使我們的二進制樹， 運行它，我們可以看到，包含現在告訴我們，我們是完全正確的 - 5，8，和圖2是不再在樹中。 返回到代碼中， 以及我們如何去插入呢？ 記住，我們做了什麼時，我們實際上是插入5個，8和2以前。 我們打了Plinko遊戲，我們開始從根本上， 逐一走下樹1 直到我們找到了合適的間隙， 然後我們有線該節點中，在適當的位置。 我們將做同樣的事情。 這基本上是喜歡寫代碼，我們使用包含功能 找到節點應該的地方， 然後我們要插入的節點就在那裡。 讓我們開始這樣做。 因此，我們有一個節點*電流=根源;我們只是按照包含的代碼 直到我們發現，它並沒有完全為我們工作。 我們要通過樹而目前的元素不為空， 如果我們發現，當前的價值等於價值，我們正試圖插入 - 好了，這是一個在何種情況下，我們不能真正地接入節點 樹，因為這意味著我們有一個重複的值。 在這裡，我們將返回false。 現在，否則，如果電流的值是小於值， 現在我們知道，我們向右移動，  因為該值屬於在右半當前樹。 否則，我們將要移動到左側。 這基本上是我們的包含函數在那裡。 在這一點上，我們已經完成了這個while循環， 我們當前的指針指向空 如果功能尚未恢復。 因此，我們當前在那個地方，我們要插入新的節點。 仍有許多工作要做的，是建立新的節點， 我們可以做很容易。 我們可以用我們的超級方便的構建節點功能， 的東西，我們並沒有做早期 - 我們只是一種想當然的，但現在我們要做的只是為了確保 - 我們將進行測試，以確保新的節點返回的值實際上是 不為null，因為我們不希望開始訪問的內存，如果它是空的。 我們可以測試，以確保新的節點是不等於空。 或相反，我們可以看到它實際上是空， ，如果它是空的，那麼我們就可以返回false早。 在這一點上，我們來連接新節點到其適當的位置在樹中。 如果我們回頭看主，我們實際上是價值佈線之前， 我們可以看到，我們用什麼方法做這件事的時候，我們希望把樹中的 我們訪問的左子根。 當我們把在樹中，我們不得不訪問右子樹的根。 我們必須有一個指針，指向父，為了把樹的一個新值。 滾動到插入，不會完全工作在這裡 因為我們沒有父指針。 我們希望能夠做到的，在這一點上，是 檢查父級的值 - 哦，天哪， 如果父級的值是小於當前值， 然後，父母的權利，孩子應該是新的節點; 否則，父的左孩子應該是新的節點。 但是，我們沒有這個父指針相當，但。 為了得到它，我們實際上是要跟踪它，因為我們去通過樹 在我們上面的循環，並找到適當的位置。 我們可以做到這一點的滾動備份到我們的頂部插入功能 跟踪另一個指針變量稱為父。 我們將它設置為null最初， 然後我們每次去通過樹， 我們要設置父指針，以匹配當前的指針。 設置等於當前父。 這樣一來，每次我們去通過， 我們要確保當前指針會遞增 父指針如下 - 只有一個級別高於當前指針在樹中。 這一切都看起來很不錯。 我認為，我們將要調整的一件事，這是構建節點則返回null。 為了構建節點，居然成功地返回null， 我們就必須修改的代碼， 因為在這裡，我們從來沒有進行測試，以確保的malloc返回一個有效的指針。 所以，如果（N = NULL），然後 - 如果malloc返回一個有效的指針，那麼我們就對它進行初始化; 否則，我們就返回，這將最終為我們返回null。 現在，一切看起來還不錯。讓我們相信，這實際上編譯。 使二進制樹，哦，我們有一些東西在這裡。 我們已經有了一個隱式聲明的函數構建節點。 同樣，使用這些編譯器，我們要開始的頂部。 什麼是必須的意思是，我給你打電話，構建節點之前，我已經宣布它。 讓我們回去的代碼真的很快。 向下滾動，果然，我的插入函數被聲明 上面構建節點的功能， 但我試圖用建立內部節點插入。 我要去和複製 - 然後將其粘貼在頂部構建節點的作用方式。 通過這種方式，希望這將工作。讓我們給另一個去。 現在，這一切編譯。一切都很好。 但在這一點上，我們實際上沒有叫我們插入功能。 我們只知道它編譯，所以讓我們進去，把一些調用中。 讓我們這樣做，在我們的主函數。 在這裡，我們註釋掉5，8，2， 然後我們並沒有將它們連接起來這裡。 讓我們打幾個電話插入， 讓我們也使用同一種東西，我們使用 當我們做這些printf調用，以確保一切都沒有得到正確插入。 我要複製和粘貼， 而不是包含我們要做的插入。 ，而不是6，10，1，我們要使用5，8，和2。 這應能插入5，8，2到樹中。 編譯。一切都很好。現在我們來運行我們的程序。 一切都返回false。 因此，5，8，和2沒有去，和它看起來像CONTAINS沒有找到他們。 這是怎麼回事呢？讓我們縮小。 第一個問題是，插入似乎返回false， 它看起來像，這是因為我們留在我們返回false，調用， 我們從來沒有真正返回true。 我們可以設置了。 第二個問題是，現在即使我們這樣做 - 保存這個，不干這個， 再次運行make，編譯，然後運行它 - 我們看到的東西都在這裡發生。 5，8，2例在樹中仍然沒有找到。 所以，這是怎麼回事呢？ 讓我們來看看在代碼中。 讓我們看看我們是否能夠明白這一點。 我們開始與父不空。 我們設定的電流等於根指針的指針， 我們要工作的方式，通過樹。 如果當前節點不為空，那麼我們就知道，我們可以向下移動一點點。 我們的父母是平等的當前指針指針， 檢查的價值 - 如果值是相同的，我們返回false。 如果值是我們移動到右邊; 否則，我們移動到左側。 然後，我們建立了一個節點。我會在一點點放大。 在這裡，我們要嘗試連接起來的值是相同的。 這是怎麼回事呢？讓我們來看看，如果可能Valgrind可以給我們一個暗示。 我喜歡用Valgrind的只是因為Valgrind的真的很快運行 告訴你，如果有任何的內存錯誤。 當我們的代碼運行Valgrind的， 你可以看到右here--Valgrind./binary_tree--and回車。 你看，我們沒有任何記憶錯誤，所以看起來一切都還好至今。 我們的確有一些內存洩漏，我們知道，因為我們不 發生在釋放我們的節點。 讓我們嘗試運行GDB來看看到底發生了。 我們會盡GDB / binary_tree。它啟動起來就好了。 讓我們設置插入一個破發點。 讓我們來運行。 看起來我們從來沒有真正被稱為插入。 它看起來只是，當我改變了這裡的主要問題是 - 所有這些printf調用包含 - 我從來沒有真正改變了這些調用插入。 現在，讓我們給它一個嘗試。讓我們編譯。 一切看起來很好。現在，讓我們嘗試運行它，看看會發生什麼。 好吧！一切看起來有相當不錯的。 最後一點要考慮的是，是否有任何邊緣的情況下，這個插入？ 而事實證明，好了，一個邊緣的情況下，始終是有趣的思考 是，會發生什麼情況，如果你的樹是空的，你調用這個插入的功能嗎？ 會奏效嗎？好了，讓我們給它一個嘗試。 - binary_tree C - 我們要測試的是，我們要深入到我們的主函數， ，而不是這樣的連接這些節點， 我們只是要註釋掉整個事情， ，而不是節點自己的佈線了， 實際上，我們可以繼續刪除所有這一切。 我們將調用插入，使一切。 所以，讓我們做的 - 而不是5，8和2，我們要插入7，3，和9。 然後，我們將要插入6。 保存。退出。二叉樹。 這一切都進行編譯。 我們可以直接運行它，看看會發生什麼， 但它也將是非常重要的，以確保 我們沒有任何的內存錯誤， 因為這是我們的優勢情況下，我們知道。 首先我們要確定它的工作原理以及在Valgrind下， 我們要做的只是運行Valgrind的/ binary_tree。 它看起來就像從一個背景下，我們確實有一個錯誤 - 我們有這樣的分割故障。 發生什麼事了嗎？ Valgrind的實際上告訴了我們它在哪裡。 縮小一點點。 它看起來就像是發生在我們的插入功能， 我們有一個在插入無效的讀取大小為4，第60行。 讓我們回去看看是怎麼回事。 縮小非常快的。 我想，以確保它不會去在屏幕的邊緣，所以我們所看到的一切。 拉一點點。好吧。 向下滾動，問題就在這裡。 會發生什麼事，如果我們得到了我們當前節點已經是空的， 我們的父節點是空的，所以如果我們在最高層，就在這裡看 - 如果從來沒有真正執行這個while循環 因為我們目前的值是空的 - 我們的根是空的，所以當前是空的 - 然後我們的父母從來沒有被設置為當前一個有效的值， 因此，家長也將是空的。 我們需要記住檢查 的時候，我們在這裡，我們開始訪問父級的值。 因此，會發生什麼呢？那麼，如果母公司是空的 - （“母公司”== NULL） - 那麼，我們知道， 絕不能在樹中的任何東西。 我們必須試圖將它的根。 我們能做到這一點，只需通過設置到新的節點等於根。 在這一點上，我們實際上並不想通過這些其他的東西。 相反，在這裡，我們可以做一個else if-else的， 或者我們可以將所有在這裡的其他， 但在這裡我們就用別人這樣做的。 現在，我們要進行測試，以確保我們的父母不為空 在此之前實際上是試圖訪問其字段。 這將有助於我們避免分割故障。 所以，我們就退出了，放大，編譯，運行。 沒有錯誤，但我們仍然有一堆的內存洩漏 因為我們沒有釋放任何對我們的節點。 但是，如果我們去了，我們期待在我們的打印輸出， 我們看到，嗯，看起來像我們所有的插入返回true，這是很好的。 刀片都是真實的， 再恰當不過了載有來電也是如此。 幹得好！看起來我們已經成功地寫入插入。 這是我們這個星期的習題集規範。 一個有趣的挑戰，要考慮的是你將如何去 免費在這棵樹的所有節點。 我們可以這樣做了一些不同的方法， 但我會離開，給你做實驗， 一個有趣的挑戰，嘗試，並確保您可以確保 Valgrind的報告，這不返回任何錯誤和無洩漏。 好運氣在這一周的Huffman編碼問題集 我們會下週見！ [CS50.TV]