[Powered by Google Translate] [第7條：更舒適]
羅布·鮑登] [哈佛大學]
[這是CS50] [CS50.TV]
好的。所以，像我在我的電子郵件中說，
這將是一個二進制樹密集的部分。
但也有很多問題。
因此，我們將嘗試並繪製出每一個問題
進入痛苦的細節做的事情的最好方法。
所以，在開始的時候，我們去通過二進制樹之類的東西的樣品圖紙。
所以在這裡，“請記住，一個二進制樹有類似的鍊錶節點，
除，而不是一個指針有兩種：一種為在左邊的'孩子'
和一個正確的'孩子'。“
因此，一個二進制樹就像是一個鍊錶，
除了結構有兩個指針。
三元樹，這將有個三分球，
有N-叉樹，其中有一個通用的指針
就是你必須對malloc足夠大，有
足夠的指點所有可能的孩子。
因此，二叉樹正好有兩個固定數量的。
如果你願意，你可以給一個鏈接列表為一元樹，
但我不認為任何人都需要它，。
“畫一個方框和箭頭圖的二進制樹節點
Nate的最喜歡的數字，7，每個孩子指針為空。“
因此，iPad模式。
>> 這將是非常簡單的。
我們只是有一個節點，我會畫一個矩形。
我會在這裡得出的值。
因此，該值將在這裡，
，然後在這裡我們將不得不在右邊的左指針在左，右指針。
這是非常多，所以約定來調用它左，右，指針名。
這些都將是空。
這將是空的，這只會是空的。
好吧。因此，回到這裡。
“一個鍊錶，我們只需要存儲一個指針
在列表中的第一個節點是為了記住整個鍊錶，或整個列表。
同樣，樹木，我們只需要存儲一個指針
為了記住整個樹到單個節點。
這是卡萊節點樹的“根”。
從之前建立在你的圖，或畫一個新的
這樣，你有一個盒子和箭頭描繪的二叉樹
與7的值，然後3在左，
然後9在右邊，然後6在右側的3。“
讓我們來看看，如果我能記得所有這一切在我的腦海。
因此，這將是我們的根在這裡。
的地方，我們還會有一些指針的東西，我們會打電話給根，
它指向了這個傢伙。
現在一個新的節點，
我們有什麼，在左邊嗎？
因此，一個新的節點3，並它最初指向空。
我就把N.
現在，我們希望去左邊的7。
因此，我們改變這個指針指向這個傢伙。
我們這樣做。我們希望有一個在這裡
它最初只是說空。
我們要改變這個指針，指向9，
現在我們要放6到右邊的3。
因此，它要 - 6。
那小子將指向。
好吧。所以，這一切都要求我們做的。
>> 現在，讓我們多一些術語。
我們已經討論了如何樹的根是最頂端的樹中的節點。
一個包含7。在樹的底部的節點被稱為葉子。
任何節點作為其子空是葉。
因此，它是可能的，如果我們的二進制樹只是一個單一的節點，
一棵樹是一片葉子，就是這樣。
“”高度“的樹是你必須做的跳數
得到從頂端到葉子。“
我們將進入，在第二，不同的
之間的平衡和非平衡二叉樹，
但現在，這種樹的整體高度
我想說的是3，但如果你的跳數計數
你必須為了得到9，那麼它真的只是一個身高2。
現在這是一個不平衡的二叉樹，
但我們會談論平衡時，它得到相關的。
所以，現在我們可以談論一棵樹的節點在條款
相對於樹中的其他節點。
所以，現在我們有父母，子女，兄弟姐妹，祖先和子孫。
他們是相當普遍的意義上說，他們的意思。
如果我們問 - 它的父母。
那麼，什麼是3的父？
[學生] 7。 >>呀。家長只是要分給你。
那麼什麼是兒童的7？
[學生] 3和9。 >>呀。
請注意，“孩子們”的字面意思是兒童，
所以將不適用，因為它就像一個孫子。
不過，如果我們去的後裔，所以是什麼7的後裔？
[學生] 3，第6和第9。 >>呀。
根節點的後代將是樹中的一切，
可能除了根節點，如果你不想認為的後裔。
最後，祖先，所以它是相反的方向。
那麼，什麼是6的祖先嗎？
[學生] 3和7。 >>呀。 9不包括在內。
這僅僅是直接的後裔回到根
將是你的祖先。
>> “我們說，一個二叉樹是”責令“如果在樹中的每個節點，
其後代在左側有小的值
和在右邊的所有的那些有較大的值。
例如，上面的樹是有序的，但它不是唯一可能的有序安排。“
在我們到達，
有序二元樹也被稱為二叉查找樹。
在這裡，我們要求有序二元樹，
但我從來沒有聽到它被稱為有序二元樹前，
一個測驗，我們更​​傾向於把二叉搜索樹。
它們是同一個，
重要的是你認識二叉樹和二叉搜索樹的區別。
二叉樹只是一棵樹，兩件事情。
每個結點兩件事情。
有沒有推理，它指向的值。
所以想在這裡，因為它是一個二叉搜索樹，
我們知道，如果我們向左走7，
然後，我們能接觸到的所有的值
將剩下的7必須是小於7。
請注意，所有的值小於7的第3和第6。
這些都是7左側。
如果我們去7的權利，一切都必須大於7，
因此9 7是正確的，所以我們是很好的。
這是一個不為一個二進制樹的情況下，
一個正規的二進制樹中，我們就可以有3個在頂部，7的左側，
9至7的左側; theres沒有的值的任何順序。
現在，我們將不能真正做到這一點，因為它的繁瑣和不必要的，
但“試圖吸引盡可能多的有序樹，你能想到的
使用的數字7，3，9和6。
有多少個不同的安排？的高度，每一個是什麼？“
>> 我們會做一對夫婦，但其主要思想是，
這是在沒有辦法包含這些值的二進制樹的一個唯一的表示。
我們需要的是一些二進制樹，它含有7，3，6，和9。
另一個可能的有效的將3根，
去的左側和它的6，去左邊，它是7，
去的左側和它的9。
這是一個非常有效的二叉搜索樹。
這是不是非常有幫助，因為它就像一個鍊錶
所有這些指針是空的。
但是，它是一個有效的樹。是嗎？
[學生]值必須在正確的嗎？
或者是這樣的 - ？ >>我的意思是這些走另一條路。
還有 - 是的，讓我們切換，。
9，7，6，3。良好的漁獲物。
它仍然有，服從什麼是二進制樹搜索是應該做的。
所以一切向左側是小於任何給定的節點。
我們可以只動，說，這6，把它放在這裡。
不，我們不能。我為什麼這樣做呢？
讓我們做 - 這裡是6，7，6點到3點。
這仍然是一個有效的二叉搜索樹。
什麼是錯的，如果我 - 讓我們來看看，如果我能想出​​的安排。
是啊，好吧。那麼，什麼是錯的這棵樹嗎？
我想我已經給你一個暗示，有什麼不對的地方。
我為什麼這樣做呢？
好吧。這看起來很合理的。
如果我們看一下在每個節點上，如7，然後到左邊的7 3。
因此，我們有3個，3的權利的東西是一個6。
如果你看的東西的權利6 6，9。
那麼，為什麼這不是一個有效的二叉搜索樹嗎？
[學生] 9仍是7左側。 >>呀。
它必須是真實的，所有你所能達到的左7的值都小於7。
如果我們向左走7，我們得到的，我們仍然可以到6，
我們仍然可以得到為9，但通過在經歷小於7，
我們不應該能夠得到一個數字，大於7。
因此，這是不是一個有效的二叉搜索樹。
>> 我哥哥其實是有一個面試問題，
這基本上是一些東西來驗證這一點，只是代碼
一棵樹是一個二叉搜索樹，
所以他做的第一件事是檢查，看看
如果左邊和右邊是正確的，然後循環。
但你不能做到這一點，你必須跟踪
的事實，現在，我已經走了剩下的7，
在這個子樹中的一切必須小於7。
正確的算法需要跟踪
的值的範圍可能裡鑽
通過所有這些，我們不會去。
有一個很好的遞推關係，
雖然我們沒有得到這些，我們不會讓那些，
確定有多少實際上是。
因此，有14人。
的想法，你會怎麼做數學是一樣的，
你可以選擇任何一個節點是根，
然後如果我選擇7根節點，
再有，說一些數字，可以去我的左節點，
有一些數字，可以成為我的右節點，
但如果我有n個總人數，然後可以去左邊的金額
加量，可以去右邊的是N - 1。
因此，剩餘的數字，它們可以去的左側或右側。
這似乎很難，如果我把第一，然後一切都去左邊，
但如果我把7，有些事情是可以走左邊，有些事情可以去正確的。
'3第一，我的意思是什麼都可以去正確的。
這是真的，你就必須把它作為，
有多少東西可以去上了一個層次的樹。
出來是14，或您可以繪製所有的這些，
然後你會得到14。
>> 讓我們再回到這裡，
非常酷，因為我們可以通過搜索“有序二叉樹
在一個非常類似的方式來尋找在一個排序的數組。
要做到這一點，我們從根開始和工作的方式，在樹
向葉，檢查每個節點的值與我們正在尋找的值。
如果當前節點的值是小於該值，我們正在尋找，
你去下一個節點的右孩子。
否則，你去結點的左孩子。
在某些時候，你會發現你正在尋找的價值，你會碰到一個空，
的價值不是在樹上。“
我要重繪我們面前的樹，要花幾秒鐘。
但是，我們想看看是否6，10，和1是在樹中。
因此，它是什麼，7，9，3，6。好吧。
你想看看這些數字，我們要查找6。
這種算法是如何工作的？
好了，我們也有一些到樹的根指針。
我們會去根說，這是價值相等的價值，我們正在尋找嗎？
因此，我們正在尋找6，所以它是不相等的。
因此，我們繼續前進，現在我們說，好了，所以6是小於7。
這是否意味著我們想要去的左側，我們要向右走？
[學生]。 >>呀。
這是明顯更容易，所有你必須做的就是畫一個可能的樹節點
然後你不知道不知道 - 而不是試圖想在你的頭上，
沒關係，如果它的不足，我去左邊或走右邊，
只是在看這幅畫，這是非常清楚的，我必須去左邊
如果此節點是大於我在尋找的值。
所以，你去左邊，現在我在3。
我想 - 3是不到我在尋找的價值，這是6。
所以，我們去正確的，現在我結束了在6，
這是我要找的，所以我返回真值。
我要尋找的下一個值是10。
好吧。所以，現在，10 - 切斷 - 要遵循的根本。
如今，10個是要大於7，所以我想看看的權利。
10我要到這裡來，是要大於9，
所以我想看看的權利。
我來這裡，但在這裡，現在我在空。
我該怎麼做，如果我打空？
[學生]：返回假的？ >>呀。我沒有找到10。
1將是幾乎相同的情況下，
除了它只是要翻轉，而不是尋找
右側向下，我要看看左側。
>> 現在，我認為我們真正的代碼。
這裡的地方 - 打開CS50設備和導航用自己的方式，
但你也可以做到這一點的空間。
做到這一點的空間，這也可能是理想的，
因為我們可以工作的空間。
他說：“首先，我們需要一個新的類型定義一個包含int值的二進制樹節點。
使用的typedef以下的樣板，
創建一個新的類型定義為一個二進制樹中的節點。
如果你被卡住。 。 。 “等等，等等，等等。好。
因此，讓我們把這裡的樣板，
typedef結構節點和節點。是啊，好吧。
那麼，什麼樣的領域，我們將要在我們的節點嗎？
[學生]：int，然後兩個指針嗎？
>> int值，兩個指針嗎？我怎樣寫指針嗎？
[學生]結構。 >>我要放大是啊，所以結構節點離開，
和結構節點*。
請記住最後一次討論，
這是沒有意義的，這是沒有意義的，
這是沒有意義的。
你需要的一切，以便確定這種遞歸結構。
好了，所以這就是我們的樹是怎麼回事的樣子。
如果我們做了一個三叉樹，然後一個節點可能看起來像B1，B2，結構節點* B3，
其中b是一個分支 - 其實，我更聽到它的左，中，右，但不管。
我們關心的只是二進制，右，左。
“現在，聲明一個全局變量為根的樹節點*。”
因此，我們不打算這樣做。
為了使事情變得稍微更困難，更廣義的，
我們不會有一個全球性的節點變量。
相反，在主，我們將宣布我們的所有節點的事情，
這意味著，在下面，當我們開始運行
包含函數和我們的插入功能，
而不是我們的CONTAINS函數只是使用這一全球性的節點變量，
我們將它作為參數樹，我們希望它來處理。
有全局變量應該使事情變得更容易。
我們將讓事情變得更糟糕。
現在只需要一分鐘左右的時間做這樣的事情，
內的主要你要創建這個樹，這就是所有你想做的事。
嘗試和構造這棵樹在您的主要功能。
>> 好吧。所以，你甚至不必構建了樹的整個方式。
但是，任何人有什麼我可以拉起來
如何開始構建這樣的樹嗎？
[學生]：有人撞，試圖擺脫。
鮑登]的任何舒適與自己的樹建設？
[學生]：當然可以。它沒有這樣做。 >>這是正常的。我們就可以完成 -
哦，你可以將它保存嗎？萬歲。
所以，在這裡，我們有 - 哦，我有點切斷。
我放大？
縮放，滾動。 >>我有一個問題。 >>呀？
[學生]：當你定義結構，是類的東西初始化到什麼？
[鮑登號>>好。所以，你必須初始化 -
[鮑登號當你定義，或當你聲明一個結構，
未初始化默認情況下，它就像如果你聲明一個int。
這是完全一樣的東西。這就像其各自的領域
可以有一個垃圾的價值所在。 “和它可能的定義 - 定義了一個struct
在一種方式，它初始化它們？
波頓：是的。所以，快捷的初始化語法
是怎麼回事的樣子 -
有兩種方法，我們可以做到這一點。我認為，我們應該編譯它
以確保鏘也這樣做了。
參數順序的結構，
你把這些花括號內的參數的順序。
所以，如果你想要初始化它9空，然後右邊是空的，
這將是9，NULL，NULL。
另一種方法是，編輯器不喜歡這種語法，
認為我想要一個新的塊，
但另一種方法是類似的東西 -
這裡，我把它放在一個新行。
你可以明確地說，我忘了確切的語法。
所以，你可以明確地解決他們的名字，並說，
c或。值= 9，左= NULL。
我猜這些需要逗號。
右= NULL，所以這樣一來，你不這樣做
確實需要知道的結構順序，
當你讀這篇文章，它更明確
什麼價值被初始化。
>> 這種情況發生的事情，是一個 -
因此，在大多數情況下，C + +是一個C的超集
你可以把C代碼，將其移動到C + +，和它應該編譯。
這是一個C + +不支持的事情，這樣的人往往不這樣做。
我不知道如果這是唯一的原因，人們往往不這樣做，
但需要的情況下，我需要使用C + +，所以我不能使用此工作。
另一個例子的東西，不與C + +是
如何malloc返回一個“無效*，”從技術上說，
但你可以說的char * x = malloc的什麼，
它會自動轉換為char *。
該自動轉換不會發生在C + +。
這將無法編譯，你會明確地說
是char *，malloc的，不管結果如何，將它轉換為一個char *。
不會有太多的事情，C和C + +不同意，
但這些都是兩個。
因此，我們將用這個語法。
但是，即使我們沒有去與語法，
是什麼 - 可能是錯的嗎？
[學生]：我不需要取消對它的引用？ >>呀。
請記住，箭頭有一個隱含的間接引用，
所以當我們只是處理與結構，
我們要使用的。在一個領域內的結構。
我們想要做的唯一的一次是，當我們使用箭頭 -
，箭頭相當於 -
這將意味著什麼，如果我用箭頭。
所有的箭頭表示，取消引用此，現在我在一個結構，我可以得到該領域。
要么領域直接或間接引用，並獲得字段 -
我想這應該是價值。
但是，我在這裡只是一個結構，而不是一個結構的指針來處理，
所以我不能使用的箭頭。
但是，這樣的事情我們可以做的所有節點上。
哦，我的上帝。
這是6，7，和3。
然後我們就可以在我們的樹，設立了分公司，我們可以有7個 -
我們可以有，其左應指向3。
那麼，如何才能做到這一點呢？
[學生，不知所云] >>呀。節點3的地址，
，如果你沒有地址，那麼就無法編譯。
但要記住，這些都是到下一個節點的指針。
正確的應該點到9，
3至6點。
我認為這是所有設置。有任何意見或問題？
[學生，不知所云]根正在為7。
我們只能說節點* =
或根，=＆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。
每個人都同意，構建一個節點的功能嗎？
所以，現在我們可以直接調用的任何節點，建立與給定值和空指針。
現在，我們可以調用，我們可以做節點* node9 = build_node（9）。
讓我們做。 。 。
6，3，7，6，3，7。
現在我們要設置相同的指針，
但現在一切都已經在指針
因此不再需要的地址。
好吧。那麼，什麼是我想要做的最後一件事嗎？
有一個錯誤檢查，我不這樣做。
什麼構建節點回報嗎？
[學生，不知所云] >>呀。如果malloc失敗，它會返回null。
所以，我要在這裡懶洋洋地把它放下，而不是做各自的條件。
如果（node9 == NULL，或者 - 甚至更簡單，
這相當於只是如果不node9。
因此，如果不node9，或不node6，或沒有節點3，或不node7，返回1。
也許我們應該打印的malloc失敗，或某事。
[學生]：是虛假等於NULL作為嗎？
鮑登任何零值是假的。
因此，null是一個零值。
零是零值。 False是一個零值。
任何 - 幾乎只有2個零值是空的，零，
假的就是哈希值被定義為“0”。
這也適用於我們聲明了全局變量。
如果我們確實有節點*的根在這裡，
- 有關全局變量是很好的事情，他們總是有一個初始值。
這是不正確的功能，在這裡，
如果我們有，像，節點*節點x。
我們不知道x.value，x.whatever，
或者我們也可以打印出來，他們可以是任意的。
這是不正確的全局變量。
所以的節點根或節點x。
默認情況下，這是全球的一切，如果沒有顯式初始化為某個值，
具有零值作為其值。
節點*根，所以在這裡，我們沒有顯式初始化它的任何事情，
所以它的默認值將是空的，這是零值的指針。
默認的x的值將表示x.value為零，
x.left為空，是空x.right。
所以，因為它是一個結構，該結構中的所有領域的零值。
我們並不需要使用，在這裡，雖然。
[學生]比其他變量的結構是不同的，和其它變量
垃圾值，這些都是零？
[鮑登其他值。因此，在x，x將是零。
如果它在全球範圍內，它有一個初始值。 “好了。
鮑登無論是初始值你給或零。
我認為所有這一切負責。
>> 好吧。所以接下來的部分是問，
“現在，我們要編寫一個函數調用包含
布爾的原型包含的int值。“
我們不打算做布爾包含的int值。
我們的原型看起來像
包含布爾（int值。
然後，我們也將傳遞給它的樹
它應該被檢查，看它是否具有該值。
因此，節點樹）。好吧。
然後，我們可以把它喜歡的東西，
也許我們會想printf或什麼的。
包含6，我們的根。
這應該返回一個或真，
而包含5根應該返回false。
因此，需要實現這一點。
你可以做到這一點的迭代或遞歸。
的方式，我們已經設置的東西是美好的事情，
它本身的遞歸解決方案更容易
比全局變量的方式。
因為如果我們只是有包含的int值，那麼我們就沒有辦法搜索子樹。
我們就必須有一個單獨的輔助函數，遞歸我們的子樹。
但因為我們已經改變了它的樹作為參數，
它應該一直擺在首位，
現在我們可以遞歸更容易。
因此，迭代或遞歸的，我們就去了兩種，
但我們會看到，遞歸端起來是很容易的。
好吧。有沒有人有什麼我們可以使用嗎？
>> [學生]：我有一個迭代的解決方案。 >>所有權利，迭代。
好吧，這看起來不錯。
所以，想通過它我們走？
[學生]：當然可以。所以我設置一個臨時變量來獲得的第一個節點樹。
然後我就通過，而溫度不等於空循環，
因此，雖然仍然在樹中，我猜。
並且如果該值是相等的值，temp被指向
然後它返回該值。
否則，它會檢查，如果是上的右側或左側。
如果你有機會的情況下，有沒有更多的樹，
那麼它的回報 - 退出循環，返回false。
鮑登]好吧。因此，這似乎不錯。
在任何問題上有任何人有任何意見？
我沒有在所有的正確意見。
有一件事我們可以做的就是這個傢伙。
哦，這是要去一個小稍長。
我會解決這個問題了。好吧。
>> 每個人都應該還記得三元工作。
有肯定是測驗在過去
給你一個三元運算符的功能，
說，翻譯，做一些不使用三元。
所以這是一個很常見的情況時，我會覺得使用三元，
其中，如果某些條件設置一個變量的東西，
其他設置相同的變量別的東西。
這件事情，這樣的事情很經常可以轉化為
在那裡設置該變量 - 或者說，好了，這是真的嗎？然後，否則這一點。
[學生]：第一個是，如果真實的，對不對？
鮑登]是啊。我總是看它的方式是，溫度大於等於溫度值，
然後，否則這一點。問一個問題。
它更大的嗎？然後做的第一件事。否則做的第二件事情。
我幾乎總是 - 結腸，我只是 - 我的頭，我讀別的。
>> 有沒有人有一個遞歸的解決方案嗎？
好吧。這一次，我們要 - 它可能已經是巨大的，
但我們要使其更好。
這幾乎是完全相同的想法。
好，只是，你想解釋一下嗎？
[學生]：當然可以。因此，我們確定該樹不為空，第一，
因為如果樹是空的，那麼它會返回false，因為我們還沒有找到它。
如果還是有一棵樹，我們進入 - 我們首先檢查該值是當前節點。
如果是，則返回true，如果沒有，我們遞歸向左或向右。
這聽起來是適當的嗎？ >>嗯，嗯。 （協議）
所以注意到這幾乎是 - 結構非常相似，迭代求解。
只是，而不是遞歸的，我們有一個while循環。
而基地的情況下，這裡的樹不等於空
的條件下，我們爆發出的while循環。
他們是非常相似的。但是，我們要進一步採取這一步。
現在，我們做同樣的事情在這裡。
請注意，我們正在返回同樣的事情在這些線路，
除了一個參數是不同的。
因此，我們要到一個三元。
我打選項的東西，它的象徵。好吧。
因此，我們將返回包含。
這是多行，好，放大它。
通常情況下，作為一個文體的事情，我不認為很多人
加一個空格後的箭頭，但我想，如果你是一致的，它的罰款。
如果值是小於樹的價值，我們希望在樹上左遞歸的，
否則，我們要遞歸樹權。
所以這是第一個步驟，使這個看起來小一些。
這個看起來小一些的第二步 -
我們可以將多行。
好吧。使它看起來更小的第二步是在這裡，
返回值等於樹的值，或包含什麼。
>> 這是一個重要的事情。
我不知道，如果他在課堂上說，它明確，
但它被稱為短路的評價。
這裡的想法是價值==樹價值。
如果這是真的，那麼這是真實的，我們要'或'，無論是在這裡。
因此，無論是在這裡，甚至沒有考慮，
整個表達式將返回是什麼？
[學生]：真？ >>是的，因為真實的東西，
用OR - 或真或運算與任何必然是真實的。
因此，只要我們看到的返回值= tree值，
我們只是返回true。
甚至不打算進一步遞歸包含了就行了。
我們可以採取這一步。
返回樹不等於空，所有的一切。
它做了一個在線的功能。
這也是一個例子短路評價。
但現在，它也是同樣的想法 -
而不是 - 所以，如果樹不等於空 - 或者說，好，
如果樹不等於空，這是不好的情況下，
如果樹等於null，那麼第一個條件是假的。
所以假“與”與什麼將是什麼？
[學生]假。 >>呀。這是短路評價的另一半，
如果樹不等於空，然後我們都不會，甚至去的地方 -
獨木等於空，那麼我們就不會做價值==樹價值。
我們只是要立即返回false。
這是非常重要的，因為如果沒有短路求值，
那麼，如果樹不等於空，這第二個條件是要賽格故障，
因為樹>的值被提領空。
所以，就是這樣。這一點 - 一旦過了轉移。
這是一個很常見的事情，這個沒有這一行，
但它是一個共同的東西的條件下，也許不正確的，
但如果（樹！= NULL，和樹>的值==值），做任何事情。
這是一個非常常見的情況，在那裡，而不必
要打破這個分為兩個中頻，在那裡一樣，是樹空？
好吧，這不是空的，所以現在是樹的值等於值嗎？做到這一點。
相反，這種情況下，這將永遠段錯誤
因為它會破壞，如果發生這種情況是空的。
嗯，我想，如果你的樹是完全無效的指針，它仍然可以賽格故障，
但它不能賽格故障，如果樹是空的。
如果是空的，這將打破之前你曾經解除引用的指針擺在首位。
[學生]：這是所謂的懶惰的評價嗎？
>> [鮑登]懶惰的評價是一個獨立的東西。
懶惰的評價更像是你要求的值，
你問計算出一個數值，種，但你並不需要它立即。
所以，直到你真正需要它，它不評估。
這是不完全一樣的東西，但在霍夫曼的pset，
它說，“懶洋洋”的編寫。
我們這樣做的原因是因為我們實際上是在緩衝寫 -
我們不希望在同一時間寫的各個位，
或單個字節的時間，而不是要得到一個塊的字節。
然後，一旦我們有一個塊的字節，然後我們將它寫出來。
即使你問它來寫 - FWRITE和fread做同樣的事情。
他們緩衝的讀取和寫入操作。
即使你要求它立即寫入，它可能不會。
你不能確定的東西都將被寫入
直到你調用hfclose或不管它是什麼，
然後說，好吧，我關閉我的文件，
這意味著更好，我寫的一切，但我沒有寫。
它不需要編寫了
直到您關閉該文件，​​然後需要的地方。
所以，這只是什麼懶 - 等待，直到它發生的。
- 以51你將進入更詳細，
因為OCaml和一切，一切都在51遞歸。
有沒有迭代的解決方案，基本上。
一切都是遞歸和懶惰的評價
很多情況下是非常重要的
在那裡，如果你沒有懶洋洋地評估，這將意味著 -
該示例是流，這是無限長。
從理論上講，你能想到的自然數為1-2-3-4-5-6-7流，
所以，懶洋洋地評估事情的罰款。
如果我說我想要的第十號，然後我就可以評估的10號。
如果我想百分之一的數量，然後我就可以評估到百分之數量。
沒有懶惰的評價，那麼它會嘗試立即評估所有的數字。
您正在評估無限多的數字，這是根本不可能的。
因此，有很多情況下，懶惰的評價
得到的東西的工作是必不可少的。
>> 現在，我們要編寫INSERT插入將是
同樣改變在其定義中。
所以，現在它的布爾插入（int值）。
我們要改變這種狀況為bool插入（int值，節點樹）。
我們實際上會改變，再次一點，我們就會明白為什麼。
讓我們繼續前進build_node，只為它赫克，
上面插入，所以我們沒有寫一個函數原型。
這是一個暗示，你將要使用build_node在插入。
好吧。 ，一分鐘的時間。
我想我保存的版本，如果你想拉，
或者，至少，我現在這樣。
我想稍作休息時間，思考的邏輯插入，
如果你無法想起來了。
基本上，你將永遠只能被插入的葉子。
想，如果我插入，然後我不可避免地將要插入1 -
我會改以黑色 - 我會在這裡插入1。
或者，如果我插入，我要在這裡插入4。
所以無論你做什麼，你要插入的葉​​子。
所有你必須做的是遍歷樹，直到你得到的節點
這應該是節點的父節點，新節點的父節點，
然後改變其向左或向右的指針，這取決於是否
它是大於或小於當前節點。
修改這個指針指向新節點。
所以遍歷樹的葉點到新的節點。
也覺得為什麼會禁止這類情況之前，
我構建二叉樹，它是正確的
如果你只看著一個單一的節點，
但9左側7，如果你遍歷了所有的方式。
所以在這種情況下這是不可能的，因為 -
想插入的東西;（9）在第一個節點，
我會看，我只是要到正確的。
所以不管我做什麼，如果我插入到葉，
，並使用合適的算法的葉，
這將是不可能的，我插入9日至7左
因為，只要我打7，我會去的權利。
有沒有人有東西開始？
[學生]：我做的。 “當然可以。
[學生，不知所云]
[其他學生，不知所云]
[鮑登的讚賞。好吧。要解釋？
>> [學生]因為我們知道，我們將
新的節點，在樹的結尾，
我循環通過迭代樹
直到我得到了一個節點，指出為空。
然後，我決定把它的右側或左側
使用此變量，它告訴我把它放在哪裡。
然後，從本質上講，我只是做，最後 -
該臨時結點，它是創造新的節點，
無論是在左側或右側，這取決於什麼值權。
最後，我設置了新的節點值，其測試值。
[鮑登]好了，所以我在這裡看到一個問題。
這是95％的方式存在的。
一個問題，我看到，沒有任何人看到一個問題嗎？
的情況下，他們跳出循環是什麼？
[學生]：如果temp是空的？ >>呀。因此，如何跳出循環，是如果溫度為空。
但是，我該怎麼辦就在這裡嗎？
我解引用的溫度，這是不可避免的空。
因此，其他的事情，你需要做的不只是跟踪，直到溫度是空的，
你要跟踪的父母在任何時候都。
我們也希望*父節點，我想我們可以保持，空第一。
這是要為根的樹有怪異的行為，
但我們會得到的。
如果值是大於任何，然後TEMP =臨時的權利。
但在此之前我們做到這一點，父母溫度。
或者父母總是平等的溫度嗎？是這樣呢？
如果溫度不為空，然後我要向下移動，不管是什麼，
temp是父節點。
所以，家長會為temp，然後我謹溫度下降。
現在的溫度是空的，但父母的事情是空的父。
所以在這裡，我不希望設置等於1。
所以，我移動到右側，因此，如果右= 1，
我猜你也想這樣做 -
如果你移動到左邊，你要設置等於0。
否則，如果你移動到右側。
所以右側= 0。如果右= 1，
現在我們要父權指針newnode，
否則，我們想使父左指針newnode。
該問題嗎？
好吧。因此，這是我們的方式 - 好吧，其實不是這樣做，而是
我們一半預計您使用build_node。
然後，如果newnode等於null，則返回false。
就是這樣。現在，這是我們希望你做什麼。
>> 這是工作人員解決方案做什麼。
我不同意這是“正確”的方式去了解它
但是，這是完全沒有問題的，它會工作。
有一件事，這是一個有點古怪，現在是
如果樹為空，我們傳遞了一個空樹。
我想這取決於你如何定義傳遞一個空樹的行為。
我認為，如果你傳遞一個空樹，
然後插入值到一個空的樹
應該只返回一個唯一的價值是單個節點的樹中。
人們同意嗎？你可以，如果你想，
如果你傳遞一個空的樹
你想插入值，則返回false。
它是由你來定義。
要我說，然後做的第一件事 -
好了，你打算這樣做有問題，因為
如果我們有一個全局指針的東西，它會更容易，
但我們沒有，所以，如果樹是空的，有什麼我們可以做的。
我們就可以返回false。
所以我要改變插入。
我們在技術上可以只改變這一權利在這裡，
它是如何遍歷的事情，
但我要改變插入一個節點**樹。
雙指針。
這是什麼意思呢？
而不是處理的節點的指針，
我要操作的東西是這樣的指針。
我要操縱這些指針。
我要直接操縱指針。
這是有道理的，因為，想想下來 -
好了，現在這點為空。
我想要做的是操作這個指針指向為NOT NULL。
我想它指向我的新節點。
如果我只是記錄我的指針的指針，
然後，我不需要跟踪的父指針。
我就可以跟踪看，如果指針指向空，
如果指針指向為null，
將其更改為指向我想要的節點。
我可以改變它，因為我有一個指針的指針。
讓我們來看看這個權利。
實際上，你可以遞歸很容易地做到這一點。
我們要做到這一點呢？
是的，我們做的。
>> 讓我們來看看它遞歸。
首先，什麼是我們的基本情況又如何呢？
幾乎永遠是我們的基本情況，但實際上，這是一種棘手的。
首先第一件事情，如果（樹== NULL）
我想我們只是要返回false。
樹是空的，這是不同的。
這就是指針到你的根指針為null
這意味著你的根指針不存在。
因此，在這裡，如果我這樣做
節點* - 讓我們只是重複。
節點根= NULL，
，然後我就打電話給插入，做這樣的事情，
和根中插入4。
因此，根，如果根是一個節點*
然後與根將是一個節點**。
這是有效的。在這種情況下，樹，在這裡，
樹不為空 - 或插入。
在這裡。樹不空; *樹為空，這是很好
*樹，因為如果是空的，那麼我可以操縱它
現在指向什麼，我想它指向。
但是，如果樹是空的，這意味著我來到這裡，說空。
這沒有任何意義。我不能做什麼用的。
如果樹是空的，則返回false。
所以，我基本上已經說了我們真正的基本情況是什麼。
那是什麼打算？
[學生，不知所云]
波頓：是的。所以，如果（*樹== NULL）。
這涉及到的情況下在這裡
我的紅色指針，如果指針，我很專注，
我集中在這指針一樣，現在我專注於這個指針。
現在我專注於這個指針。
所以，如果我的紅色指針，這是我的節點**
曾經是 - 如果*，我的紅色指針，是以往任何時候都為空，
這意味著，我在我專注於一個指針指向的情況下 -
這是一個指針，屬於一片葉子。
我想改變這個指針指向我的新節點。
快回來。
我的newnode將是節點* N = build_node（值）
那麼n，如果n = NULL，則返回false。
否則，我們要改變指針指向
現在我們新建的節點。
事實上，我們可以做到這一點。
而不是說Ň，我們說* = *樹的樹。
每個人都明白嗎？ ，處理指向指針的指針，
我們可以改變空指針指向它們指向我們想要的東西。
這是我們的基本情況。
>> 現在，我們的復發，或我們的遞歸，
將是非常相似，我們已經做了所有其他的遞歸。
我們將要插入的值，
現在我要再次使用三元，但我們的條件是什麼要？
它是什麼，我們要尋找的決定，我們是否要向左走還是向右？
讓我們這樣做在單獨的步驟。
（值）是什麼？
[學生]：這棵樹的價值？
鮑登所以請記住，我目前 -
[學生，不知所云]
[鮑登]是啊，所以就在這裡，讓我們說，這個綠色的箭頭
是什麼樹目前是一個例子，是一個指針，該指針。
因此，這意味著我是一個指針，指向一個指針，指向3。
兩次解引用聽起來不錯。
這是什麼 - 怎麼我做的是什麼？
[學生]：取消引用一次，然後做箭頭？
[鮑登]（樹）提領一次， - >值
是想給我的價值，我間接指向的節點。
所以我也可以寫它** tree.value的，如果你喜歡。
無論是工作的。
如果是這樣的話，那麼我想打電話給插入與價值。
什麼是我更新的節點**又如何呢？
我想往左走，所以** tree.left的將是我的左手。
我想這東西的指針
所以，如果左邊的結束是空指針，
我可以修改它指向我的新節點。
>> 其他情況下，可以是非常相似的。
其實，我的三元現在。
插入值，如果值<（**樹）。值。
然後我們要更​​新我們的**的左側，
否則，我們要更新我們的**的權利。
[學生]：那拿到的指針的指針？
鮑登 - ** tree.right是節點的明星。
[學生，不知所云] >>呀。
** tree.right是這樣的指針或什麼的。
因此，通過一個指向，這給了我我想要的
那傢伙的指針。
[學生]：我們能不能走一遍，為什麼我們使用的是兩個指針嗎？
鮑登]是啊。所以 - 不，你可以，而且該解決方案之前
一種方法做這件事而不做兩個指針。
你需要能夠了解兩個指針，
這是一個清潔的解決方案。
另外，請注意，會發生什麼，如果我的樹 -
發生什麼，如果我的根目錄為空？在這裡如果我這樣做的情況下，會發生什麼情況？
因此，節點*根= NULL，插入4到與根。
什麼是根將是在此之後呢？
[學生，不知所云] >>呀。
根值是4。
根左邊的這個是空的，根本的權利是空的。
的情況下，我們沒有通過根地址，
我們不能修改根。
樹 - 根為空的情況下，
我們剛剛返回false。我們沒有什麼可以做的。
我們不能插入到一個空的樹節點。
但現在我們可以到一個節點樹，我們只是一個空的樹。
這通常是預期的方式，它應該工作。
>> 此外，這是顯著短於
跟踪的父母，所以你遍歷了所有的方式。
現在，我有我的父母，我只是有我的父權的任何指針。
相反，如果我們這樣做迭代，它會是一個while循環同樣的想法。
但不是我的父指針處理，
而不是我現在的指針的東西
我直接修改指向我的新節點。
我沒有處理，無論是指向左邊。
我沒有處理是否指向正確的。
這只是不管這個指針，我將其設置為指向我的新節點。
每個人都明白它是如何工作的？
如果沒有，為什麼我們想這樣做，這樣一來，
但至少，這個工程作為一個解決方案？
[學生]：我們從哪裡傳回是真的嗎？
鮑登這很可能就在這裡。
如果我們正確地插入，則返回true。
否則，在這裡我們將要返回任何插入的回報。
>> 和有關這個遞歸函數有什麼特別呢？
這是尾遞歸的，所以只要我們編譯了一些優化，
它會認識到，你將永遠不會得到一個堆棧溢出，
即使我們的樹的高度1萬或10萬。
[學生，不知所云]
[鮑登]我認為它在短跑 - 優化級別
需要被認可為一個尾遞歸。
我認為它承認 - GCC和Clang的
也有不同的含義的優化水平。
我想說這是達紹2，為確保它會識別尾遞歸。
但是，我們 - 你可以構建這樣一個Fibonocci的例子或什麼的。
這是不容易的測試，因為它是難以建立
這麼大的一個二叉樹。
但是，是的，我認為這是達紹2，
如果在編譯時使用達紹2，它會尋找尾遞歸
並優化了這一點。
讓我們回去 - 插入從字面上它需要的最後一件事。
讓我們回到在這裡插入
我們要去的地方，做同樣的想法。
它仍然有缺陷，不能夠完全處理
當根目錄本身是空的，或在過去的項目是空的，
但是，而不是處理與父母指針，
讓我們應用同樣的邏輯，保持指針的指針。
如果我們保持我們的節點**當前，
而我們不需要跟踪了，
但節點**當前和樹。
現在，我們的while循環將是*電流不等於空。
不需要跟踪的父母了。
不要需要跟踪的左邊和右邊。
我會打電話給它溫度，因為我們已經使用溫度。
好吧。所以，如果（值> *溫度），
（臨時） - >右鍵
TEMP =＆（*溫度） - >離開。
而現在，在這一點上，這個while循環後，
我只能這樣做，因為也許它更容易比遞歸迭代想想，
但這個while循環後，
* temp是我們要改變的指針。
>> 之前，我們的父母，我們想改變父母任何一方左或父權，
但如果我們想改變家長的權利，
*溫度是父母的權利，我們可以直接改變它。
所以在這裡，我們可以做TEMP = newnode，這就是它。
因此，通知，我們在這行代碼。
為了保持軌道是額外的努力在所有的父。
在這裡，如果我們只是一味地跟踪指針的指針，
即使我們想擺脫現在所有這些大括號中，
使它看起來更短。
這現在是完全一樣的解決方案，
但更少的代碼行。
一旦你開始認識到這是一個有效的解決方案，
它也更容易的原因有關，而不像，沒關係，
為什麼我有這個標誌的詮釋權嗎？
這是什麼意思呢？哦，這是表示
我每次去正確的，我需要設置，
否則，如果我向左走，我需要將其設置為零。
在這裡，我沒有原因有關，它只是更容易思考的問題。
有問題嗎？
[學生，不知所云] >>呀。
好了，所以在最後一位 -
我想一個快速和簡單的函數，我們可以做的是，
let's - 一起，我想嘗試寫一個包含函數
不關心它是否是一個二叉搜索樹。
這包含函數應返回TRUE
如果在此二叉樹的價值是我們正在尋找的任何地方。
因此，讓我們第一次做遞歸和迭代，我們將做到這一點。
事實上，我們可以做起來，因為這將是非常短的。
>> 什麼是我的基本情況又如何呢？
[學生，不知所云]
[鮑登]所以，​​如果（樹== NULL），然後呢？
[學生]：返回false。
[鮑登否則，好了，我不需要別的。
如果是我的基本情況。
[學生]：樹的價值呢？ >>呀。
所以，如果（樹 - >值==值。
請注意，我們又回到了節點*，而不是節點的**嗎？
蘊涵永遠不會需要使用一個節點**
因為我們沒有修改指針。
我們只是遍歷。
如果出現這種情況，那麼，我們要返回true。
否則，我們要遍歷的孩子。
因此，我們不能推理是否所有的左邊是
的一切權利。
那麼，什麼是我們的條件，要在這裡 - 或者說，什麼是我們該怎麼辦？
[學生，不知所云] >>呀。
返回包含（價值樹 - >左）
或（價值樹 - >右）。就是這樣。
發現有短路的評價，
如果我們碰巧發現在左邊的樹形，
我們永遠需要尋找正確的樹。
這是整個函數。
現在，讓我們做迭代，
這將是那麼好。
我們將採取一貫的起始節點的電流=樹。
雖然（當前= NULL）。
快速將看到一個問題。
如果電流 - 在這裡，如果我們打破這個，
然後，我們已經用完了的事情來看待，所以返回false。
如果（當前值==值），則返回true。
所以，現在，我們是在一個地方 -
我們不知道，我們是否要向左走還是向右。
所以，隨意，讓我​​們去離開。
顯然，我遇到一個問題，我已經完全放棄一切 -
我將永遠只能檢查左側的樹。
我永遠都不會檢查任何孩子的東西是正確的。
我該如何解決這個問題？
[學生]：您有堆棧跟踪的左，右。
鮑登]是啊。所以，讓我們把它
結構列表，節點n，然後節點**嗎？
我認為正常工作。
我們想要去的左，或let's - 在這裡。
結構列表的列表=，它會開始
出在這個結構列表。
*列表= NULL。所以這將是我們的鍊錶
子樹，我們已經跳過了。
我們要遍歷現在剩下的，
但由於我們無可避免地要回來的右側，
我們要保持我們的結構列表內的右側。
然後，我們，將有new_list或結構，
結構列表，new_list的malloc（sizeof（列表）的）。
我要忽略錯誤檢查，但你應該檢查，看它是否為NULL。
New_list的節點，它的指向 -
哦，我想這就是為什麼它在這裡。要指出的第二個結構列表。
這是多麼鍊錶的工作。
這是相同的作為一個int鍊錶
除了我們剛剛更換的int節點*。
這是完全一樣的。
所以new_list，的價值我們的new_list節點，
會是電流>右鍵。
我們new_list的價值 - >明年將是我們原來的名單，
然後我們來更新我們的列表中指向new_list的。
>> 現在，我們需要某種方式拉的東西，
就像我們所走過的整個左子樹。
現在我們需要把它拉出來的東西，
如當前是空的，我們不希望只是返回false。
我們現在要在外面拉我們新的列表。
一種方便的方法，這樣做的 - 其實，有多種方式這樣做。
任何人有建議嗎？
在哪裡我應該這樣做，或者我應該這樣做嗎？
我們只有一兩分鐘，但有什麼建議？
相反 - 的一種方式，而不是我們的條件，同時，
我們目前正在不為空，
相反，我們要繼續走，直到我們的名單本身是空的。
因此，如果我們的列表為空，
然後我們跑出來的東西，尋找，搜尋。
但是，這意味著在我們的名單的第一件事，只是將第一個節點。
的第一件事是 - 我們不再需要看到的。
所以列表 - > n將是我們的樹。
列表 - >下一個會是空的。
而現在名單不等於空。
cur是要拉的東西從我們的名單。
因此，當前要平等列表 - > N。
，然後列出要平等列表 - > N，或列表下。
因此，如果當前值等於值。
現在我們可以添加我們的權利，指針和我們的左指針
只要他們不為空。
到這裡，我想我們應該這樣做，是擺在首位。
如果（電流>好吧！= NULL）
那麼，我們該節點將要插入到我們的名單。
如果（電流左），這是一點點額外的工作，但它的罰款。
如果（電流左！= NULL），
我們要我們的鍊錶中插入左，
這應該是它。
我們遍歷 - 只要我們有一些在我們的名單，
我們有另一個節點來看看。
因此，我們期待在該節點上，
我們推進我們的列表中的下一個。
如果該節點是我們正在尋找的價值，我們就可以返回true。
否則插入我們的左，右子樹，
只要他們不為空，進入我們的名單
所以，我們不可避免地走了他們。
所以，如果他們不為空，
如果我們的根指針指向兩件事情，
然後我們把車停在​​第一的東西，所以我們的列表為空。
然後我們把兩件事情回來，所以現在我們的名單是大小為2。
那我們是要循環，我們只是要拉，
比方說，我們的根結點的左指針。
那將只是不斷發生，我們將結束循環一切。
>> 請注意，這是顯著更複雜
在遞歸的解決方案。
我已經說過多次，
的遞歸解決方案通常有很多共同之處，與迭代求解。
在這裡，這是什麼做的遞歸解決方案。
唯一的變化是，而不是隱式地使用堆棧，程序堆棧，
跟踪哪些節點需要訪問的方式，
現在，你必須明確地使用鍊錶。
在這兩種情況下，你跟踪哪些節點仍然需要訪問。
在遞歸的情況下，它只是更容易，因為堆棧
你的程序堆棧來實現。
請注意，此鏈接的列表，這是一個堆棧。
無論我們只是把在堆棧上
我們馬上要去拉斷的堆棧訪問下。
我們沒時間了，但什麼問題嗎？
[學生，不知所云]
鮑登]是啊。所以，如果我們有我們的鏈接列表，
當前要指向這個傢伙，
現在我們只是推動我們的聯名單專注於這傢伙。
我們穿越過該行的鍊錶中。
然後，我想我們應該幫助我們的鍊錶之類的東西
前一次返回true或false，我們需要
我們的鍊錶遍歷，並一直在這裡，我想，
如果我們當前不等於，添加它，所以現在我們要釋放
電流，因為，我們完全忘了該列表？是啊。
所以，這就是我們想要做的。
指針在哪裡？
當前是 - 我們需要一個結構列表* 10等於列表旁邊。
免費列表，列表溫度。
的情況下，我們返回true，我們需要遍歷
在剩餘的聯繫列表中解放出來的東西。
美好的事情被釋放的遞歸解決方案
只是意味著會發生堆棧中彈出承購關閉。
因此，我們已經走了的東西，就像3行認為難以對代碼
顯著更多的東西，是很難認為有關的代碼行。
還有什麼問題嗎？
好的。我們是很好的。再見！
[CS50.TV]