[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]