[Powered by Google Translate] [Phần 7: thoải mái hơn] [Rob Bowden] [Đại học Harvard] [Đây là CS50] [CS50.TV] Được rồi. Vì vậy, như tôi đã nói trong email của tôi, điều này là có được một phần nhị phân cây thâm canh. Tuy nhiên, không phải là rất nhiều câu hỏi. Vì vậy, chúng tôi sẽ cố gắng và rút ra mỗi câu hỏi và đi vào chi tiết đau đớn của tất cả các cách thực hiện tốt nhất. Vì vậy, ngay từ đầu, chúng tôi đi qua các bản vẽ mẫu của cây nhị phân và các công cụ. Vì vậy, ở đây, "Hãy nhớ rằng một cây nhị phân có các nút tương tự như những người của một danh sách liên kết, ngoại trừ thay vì một con trỏ có hai: một cho 'con' bên trái và một cho đứa trẻ phải ". Vì vậy, một cây nhị phân giống như một danh sách liên kết, ngoại trừ cấu trúc là sẽ có hai con trỏ. Có cây trinary, mà sẽ có ba con trỏ, có cây N-ary, mà chỉ có một con trỏ chung chung mà sau đó bạn phải malloc để có đủ lớn để có con trỏ đủ để tất cả các trẻ em có thể. Vì vậy, cây nhị phân chỉ xảy ra để có một hằng số của hai. Nếu bạn muốn, bạn có thể cho một danh sách liên kết như là một cây unary, nhưng tôi không nghĩ rằng bất cứ ai gọi nó mà. "Vẽ một sơ đồ hộp và mũi tên của một nút cây nhị phân có chứa số yêu thích của Nate, 7, nơi mỗi con trỏ con là null. " Vì vậy, iPad chế độ. 

Nó sẽ là khá đơn giản. Chúng tôi chỉ cần đi để có một nút, tôi sẽ vẽ nó như một hình vuông. Và tôi sẽ rút ra những giá trị ở đây. Vì vậy, giá trị sẽ đi ở đây, và sau đó xuống đây chúng tôi sẽ có con trỏ bên trái bên trái và con trỏ bên phải bên phải. Và nó là rất nhiều để quy ước để gọi nó là trái và phải, tên con trỏ. Cả hai sẽ được null. Điều đó sẽ chỉ là vô giá trị, và đó sẽ chỉ là vô giá trị. Okay. Vì vậy, sao ở đây. "Với một danh sách liên kết, chúng tôi chỉ có để lưu trữ một con trỏ nút đầu tiên trong danh sách để nhớ những danh sách liên kết toàn bộ, hoặc tất cả danh sách. Tương tự như vậy, với cây xanh, chúng tôi chỉ có để lưu trữ một con trỏ một nút duy nhất để nhớ toàn bộ cây. Nút này calle 'root' của cây. Xây dựng dựa trên sơ đồ của bạn từ trước hoặc vẽ một cái mới như vậy mà bạn có một mô tả hộp và mũi tên của một cây nhị phân với các giá trị 7, sau đó 3 ở bên trái, sau đó 9 ở bên phải, và sau đó 6 trên bên phải của 3 ". Hãy xem nếu tôi có thể nhớ tất cả những điều đó trong đầu tôi. Vì vậy, đây sẽ là root của chúng tôi ở đây. Chúng tôi sẽ có một số con trỏ một nơi nào đó, một cái gì đó mà chúng ta sẽ gọi gốc, và nó chỉ với anh chàng này. Bây giờ để làm một nút mới, chúng ta có gì, 3 ở bên trái? Vì vậy, một nút mới có 3, và ban đầu nó chỉ vô giá trị. Tôi sẽ chỉ đưa N. Bây giờ chúng tôi muốn làm đó đi đến bên trái của 7. Vì vậy, chúng tôi thay đổi con trỏ trỏ đến anh chàng này. Và chúng tôi làm như vậy. Chúng tôi muốn có một 9 trên đây mà ban đầu chỉ nói null. Chúng tôi sẽ thay đổi con trỏ này, điểm đến 9, và bây giờ chúng tôi muốn đặt 6 đến bên phải của 3. Vì vậy, nó sẽ làm cho một 6. Và đó chàng sẽ chỉ ở đó. Okay. Vì vậy, đó là tất cả nó đòi hỏi chúng ta phải làm gì. 

Bây giờ chúng ta hãy đi qua một số thuật ngữ. Chúng tôi đã nói về gốc rễ của cây là nút trên cùng trong cây. Điều chứa 7. Các nút ở dưới cùng của cây được gọi là lá. Bất cứ nút nào mà chỉ cần có null như con của nó là một chiếc lá. Vì vậy, nó là có thể, nếu cây nhị phân của chúng tôi chỉ là một nút duy nhất, một cây là một chiếc lá, và đó là nó. "'Chiều cao của cây là số lượng hoa bia bạn có để làm để có được từ trên một chiếc lá. " Chúng tôi sẽ nhận được vào, trong một giây, sự khác biệt giữa các cây nhị phân cân bằng và không cân bằng, nhưng bây giờ, chiều cao tổng thể của cây này Tôi sẽ nói là 3, mặc dù nếu bạn đếm số bước nhảy bạn phải thực hiện để có được đến 9, sau đó nó thực sự chỉ là một chiều cao của 2. Ngay bây giờ đây là một cây nhị phân không cân bằng, nhưng chúng tôi sẽ nói về cân bằng khi nó được cho là có liên quan. Vì vậy, bây giờ chúng tôi có thể nói về các nút trong một cây về liên quan đến các nút khác trong cây. Vì vậy, bây giờ chúng tôi có bố mẹ, con, anh, chị, em ruột, ông bà tổ tiên và con cháu. Họ là khá phổ biến ý nghĩa, ý nghĩa của chúng. Nếu chúng ta hỏi - cha mẹ của nó. Vì vậy, cha mẹ của 3 là gì? [Sinh viên] 7. >> Yeah. Phụ huynh chỉ cần đi được những gì cho bạn. Sau đó, trẻ em của 7 là gì? [Sinh viên] 3 và 9. >> Yeah. Chú ý rằng "trẻ em" có nghĩa là trẻ em, để 6 sẽ không áp dụng, vì nó giống như một đứa cháu. Nhưng sau đó nếu chúng ta đi con cháu, vì vậy con cháu của 7 là gì? [Sinh viên] 3, 6 và 9. >> Yeah. Các con cháu của nút gốc là có được tất cả mọi thứ trong cây, ngoại trừ nút gốc riêng của mình, nếu bạn không muốn xem xét rằng một hậu duệ. Và cuối cùng, tổ tiên, vì vậy đó là hướng ngược lại. Vì vậy, các tổ tiên của 6 là gì? [Sinh viên] 3 và 7. >> Yeah. 9 không bao gồm. Nó chỉ trở lại dòng dõi trực tiếp vào thư mục gốc sẽ được tổ tiên của bạn. 

"Chúng tôi nói rằng một cây nhị phân được 'đặt hàng' nếu cho mỗi nút trong cây, tất cả các hậu duệ của nó ở bên trái có giá trị thấp hơn và tất cả những người ở bên phải có giá trị lớn. Ví dụ, cây ở trên được yêu cầu mà nó không phải là sự sắp xếp chỉ có thể ra lệnh. " Trước khi chúng tôi nhận được để mà, một cây nhị phân ra lệnh cũng được biết đến như là một cây tìm kiếm nhị phân. Ở đây chúng ta gọi đó là một cây nhị phân ra lệnh, nhưng tôi đã không bao giờ nghe nói nó được gọi là một cây nhị phân ra lệnh trước khi, và một bài kiểm tra, chúng tôi có rất nhiều khả năng để đưa cây tìm kiếm nhị phân. Họ là một và giống nhau, và điều quan trọng là bạn nhận ra sự khác biệt giữa cây nhị phân và cây tìm kiếm nhị phân. Một cây nhị phân chỉ là một cây mà điểm đến hai điều. Mỗi nút chỉ vào hai điều. Không có lý luận về những giá trị mà nó trỏ tới. Do đó, như ở đây, vì nó là một cây tìm kiếm nhị phân, chúng ta biết rằng nếu chúng tôi đi bên trái của 7, sau đó tất cả các giá trị mà chúng ta có thể có thể đạt được bằng cách đi bên trái của 7 có thể ít hơn 7. Chú ý rằng tất cả các giá trị nhỏ hơn 7 là 3 và 6. Đó là tất cả ở phía bên trái của 7. Nếu chúng tôi đi đến bên phải của 7, tất cả mọi thứ có thể lớn hơn 7, nên 9 là quyền của 7, vì vậy chúng tôi đang tốt. Đây không phải là trường hợp cho một cây nhị phân, cho một cây nhị phân thông thường, chúng tôi chỉ có thể có 3 ở đầu, 7 bên trái, 9 bên trái của 7, không có thứ tự của các giá trị nào. Bây giờ, chúng tôi sẽ không thực sự làm được điều này bởi vì nó tẻ nhạt và không cần thiết, nhưng "cố gắng rút ra cây ra lệnh như nhiều như bạn có thể nghĩ bằng cách sử dụng số 7, 3, 9, và 6. Có bao nhiêu thỏa thuận riêng biệt? Chiều cao của mỗi người là gì? " 

Chúng tôi sẽ làm một vài, nhưng ý tưởng chính là, điều này là không có cách nào một đại diện duy nhất của một cây nhị phân có chứa các giá trị. Tất cả chúng ta cần là một số cây nhị phân chứa 7, 3, 6, và 9. Khác có thể hợp lệ sẽ là một trong gốc là 3, đi bên trái và đó là 6, đi về bên trái và nó là 7, đi bên trái và đó là 9. Đó là một cây nhị phân tìm kiếm hoàn toàn hợp lệ. Đó không phải là rất hữu ích, bởi vì nó chỉ giống như một danh sách liên kết và tất cả các con trỏ chỉ là vô giá trị. Nhưng nó là một cây hợp lệ. Yeah? [Sinh viên không phải là các giá trị phải lớn hơn bên phải? Hoặc là điều này? >> Những tôi có nghĩa là đi theo con đường khác. Ngoài ra còn có - yeah, chúng ta hãy chuyển sang các. 9, 7, 6, 3. Catch. Nó vẫn còn phải tuân theo một cây nhị phân tìm kiếm là phải làm. Vì vậy, tất cả mọi thứ bên trái có thể ít hơn so với bất kỳ nút nào. Chúng tôi chỉ có thể di chuyển, nói, này 6 và đặt nó ở đây. Không, chúng tôi không thể. Tại sao tôi làm điều đó? Hãy làm - đây là 6, ở đây là 7, 6 điểm 3. Điều này vẫn còn là một cây nhị phân tìm kiếm hợp lệ. Điều gì là sai nếu tôi - chúng ta hãy xem nếu tôi có thể đến với một sự sắp xếp. Yeah, okay. Vì vậy, những gì là sai với cây này? Tôi đoán tôi đã đưa cho bạn một gợi ý rằng có cái gì đó sai trái với nó. Tại sao tôi làm điều đó? Okay. Điều này có vẻ hợp lý. Nếu chúng ta nhìn tại mỗi nút, giống như 7, sau đó đến bên trái của 7 là một 3. Vì vậy, chúng tôi có 3 điều ở bên phải của 3 là một 6. Và nếu bạn nhìn vào 6, điều ở bên phải của 6 là một 9. Vậy tại sao không phải là một cây nhị phân tìm kiếm hợp lệ? [Sinh viên] 9 vẫn còn để bên trái của 7. >> Yeah. Nó phải là sự thật rằng tất cả các giá trị mà bạn có thể có thể đạt được bằng cách bên trái của 7 ít hơn 7. Nếu chúng ta đi bên trái của 7, chúng tôi nhận được đến 3 và chúng ta vẫn có thể nhận được đến 6, chúng ta vẫn có thể nhận được đến 9, nhưng đã ít hơn 7, chúng ta không nên có thể nhận được một số lớn hơn 7. Vì vậy, đây không phải là một cây nhị phân tìm kiếm hợp lệ. 

Anh trai tôi thực sự đã có một câu hỏi phỏng vấn đã được cơ bản này, chỉ cần mã lên một cái gì đó để xác nhận cho dù một cây là một cây tìm kiếm nhị phân, và do đó, điều đầu tiên anh làm là chỉ cần kiểm tra xem nếu bên trái và bên phải là chính xác, và sau đó lặp lại ở đó. Nhưng bạn có thể không chỉ làm điều đó, bạn phải theo dõi thực tế rằng bây giờ tôi đã đi bên trái của 7, tất cả mọi thứ trong subtree này phải nhỏ hơn 7. Thuật toán chính xác cần phải theo dõi các giới hạn rằng các giá trị có thể có thể rơi. Chúng tôi sẽ không đi qua tất cả chúng. Có một mối quan hệ tái phát tốt đẹp, mặc dù chúng tôi đã không nhận những người, hoặc chúng tôi sẽ không nhận được với những người, xác định có bao nhiêu thực sự đang có. Vì vậy, có 14 người trong số họ. Ý tưởng về cách bạn sẽ làm điều đó toán học là như thế, bạn có thể chọn bất kỳ một trong duy nhất để được nút gốc, và sau đó nếu tôi chọn 7 là nút gốc, sau đó có, nói rằng, một số con số mà có thể đi được nút bên trái của tôi, và có một số con số đó có thể là nút phải của tôi, nhưng nếu tôi có n tổng số, sau đó số tiền mà có thể đi về bên trái cộng với số tiền mà có thể đi bên phải là n - 1. Vì vậy, các số còn lại, họ có để có thể đi một trong hai bên trái hoặc bên phải. Có vẻ như khó khăn đó, nếu tôi đặt 3 đầu tiên sau đó tất cả mọi thứ để đi đến bên trái, nhưng nếu tôi đặt 7, sau đó một số điều có thể đi bên trái và một số thứ có thể đi bên phải. '3 Đầu tiên, tôi có nghĩa là tất cả mọi thứ có thể đi bên phải. Nó thực sự, bạn chỉ cần có để suy nghĩ về nó như là, bao nhiêu thứ có thể đi vào cấp độ tiếp theo của cây. Và nó đi kèm là 14, hoặc bạn có thể vẽ tất cả trong số họ, và sau đó bạn sẽ nhận được 14. 

Trở lại ở đây, "Cây nhị phân theo thứ tự là mát mẻ bởi vì chúng ta có thể tìm kiếm thông qua họ một cách rất tương tự như tìm kiếm trên một mảng được sắp xếp. Để làm như vậy, chúng tôi bắt đầu từ gốc và làm việc theo cách của chúng tôi xuống cây đối với lá, kiểm tra giá trị của mỗi nút chống lại các giá trị mà chúng ta đang tìm kiếm. Nếu nút hiện tại giá trị thấp hơn giá trị, chúng tôi đang tìm kiếm, bạn đi bên cạnh con phải của nút. Nếu không, bạn đi đến con trái của nút. Tại một số điểm, bạn sẽ tìm thấy những giá trị mà bạn đang tìm kiếm, hoặc bạn sẽ chạy vào một null, cho thấy giá trị không phải trong cây. " Tôi phải vẽ lại cây chúng tôi đã có trước đây, mà sẽ mất một giây. Nhưng chúng tôi muốn tìm xem 6, 10, và 1 trong cây. Vì vậy, nó là cái gì, 7, 9, 3, 6. Okay. Những con số mà bạn muốn tìm kiếm, chúng tôi muốn tìm kiếm 6. Thuật toán này như thế nào làm việc? Vâng, chúng tôi cũng có một số con trỏ gốc cây của chúng tôi. Và chúng ta sẽ đi đến gốc và nói, là giá trị này bằng giá trị mà chúng ta đang tìm kiếm? Vì vậy, chúng tôi đang tìm kiếm 6, do đó, nó không bằng. Vì vậy, chúng tôi tiếp tục đi, và bây giờ chúng ta nói, okay, vì vậy 6 là ít hơn 7. Điều đó có nghĩa là chúng tôi muốn đi bên trái, hoặc làm chúng tôi muốn đi bên phải? [Sinh viên] Left. >> Yeah. Đó là dễ dàng hơn đáng kể, tất cả những gì bạn phải làm là vẽ một nút có thể có của cây và sau đó bạn đừng thay vì cố gắng suy nghĩ trong đầu của bạn, okay, nếu nó ít hơn, để tôi đi sang bên trái hoặc bên phải, chỉ cần nhìn vào bức ảnh này, nó rất rõ ràng rằng tôi phải đi về bên trái nếu nút này lớn hơn giá trị mà tôi đang tìm kiếm. Vì vậy, bạn đi sang bên trái, bây giờ tôi đang ở mức 3. Tôi muốn - 3 là ít hơn giá trị tôi đang tìm kiếm, mà là 6. Vì vậy, chúng tôi đi bên phải, và bây giờ tôi kết thúc lúc 6, đó là giá trị tôi đang tìm kiếm, vì vậy tôi trở lại đúng. Giá trị tiếp theo tôi sẽ đi tìm là 10. Okay. Vì vậy, 10, bây giờ, - cắt - sẽ thực hiện theo các gốc. Bây giờ, 10 sẽ được lớn hơn 7, vì vậy tôi muốn nhìn bên phải. Tôi sẽ đến đây, 10 là có được lớn hơn 9, vì vậy tôi sẽ muốn nhìn bên phải. Tôi đi qua ở đây, nhưng ở đây bây giờ tôi đang ở vô giá trị. Tôi phải làm gì nếu tôi nhấn vô giá trị? [Sinh viên] Quay trở lại sai? >> Yeah. Tôi không tìm thấy 10. 1 được sẽ là một trường hợp gần như giống hệt nhau, ngoại trừ nó chỉ cần đi được lộn, thay vì tìm kiếm xuống phía bên phải, tôi sẽ nhìn xuống phía bên trái. 

Bây giờ tôi nghĩ rằng chúng tôi thực sự có được mã. Đây là nơi mở thiết bị CS50 và điều hướng theo cách của bạn, nhưng bạn cũng có thể làm điều đó trong không gian. Đây có thể là lý tưởng để làm điều đó trong không gian, bởi vì chúng ta có thể làm việc trong không gian. "Trước tiên, chúng tôi sẽ cần một định nghĩa kiểu mới cho một nút cây nhị phân chứa các giá trị int. Sử dụng các boilerplate typedef dưới đây, tạo ra một định nghĩa kiểu mới cho một nút trong một cây nhị phân. Nếu bạn gặp khó khăn. . . "Blah, blah, blah. Okay. Vì vậy, chúng ta hãy đặt boilerplate đây, typedef struct node, và nút. Yeah, okay. Vì vậy, các lĩnh vực mà chúng tôi sẽ muốn trong nút của chúng tôi là gì? [Sinh viên] Int và sau đó hai con trỏ? >> Int giá trị, hai con trỏ? Làm thế nào để viết các con trỏ? [Sinh viên] Struct. >> Tôi nên phóng to. Yeah, vì vậy struct node * còn lại, và struct node bên phải *. Và hãy nhớ rằng các cuộc thảo luận từ lần cuối cùng, rằng điều này làm cho không có ý nghĩa, điều này làm cho không có ý nghĩa, điều này làm cho không có ý nghĩa. Bạn cần phải có tất cả mọi thứ để xác định cấu trúc đệ quy này. Được rồi, vì vậy đó là những gì cây của chúng tôi sẽ trông giống như. Nếu chúng ta làm một cây trinary, sau đó một nút có thể trông như b2, b1, struct node * b3, trong đó b là một chi nhánh - trên thực tế, tôi đã hơn nghe trái, giữa, phải, nhưng bất cứ điều gì. Chúng tôi chỉ quan tâm về nhị phân, do đó, phải, trái. "Bây giờ khai báo một biến node * toàn cầu cho thư mục gốc của cây". Vì vậy, chúng tôi sẽ không làm điều đó. Để thực hiện những điều hơi khó khăn hơn và tổng quát hơn, chúng tôi sẽ không có một nút biến toàn cầu. Thay vào đó, chính chúng ta sẽ khai báo tất cả các nút điều của chúng tôi, và điều đó có nghĩa là dưới đây, khi chúng tôi bắt đầu chạy Chứa chức năng và chức năng chèn của chúng tôi, thay vì Chứa của chúng tôi chức năng chỉ bằng cách sử dụng nút biến toàn cầu này, chúng ta sẽ có nó như là một đối số cây mà chúng ta muốn nó để xử lý. Có các biến toàn cầu được cho là để làm cho mọi việc dễ dàng hơn. Chúng ta sẽ làm cho những điều khó hơn. Bây giờ mất một phút hoặc lâu hơn để chỉ làm điều này loại điều, bên trong của chính bạn muốn để tạo ra cây này, và đó là tất cả những gì bạn muốn làm. Hãy thử và xây dựng cây này trong chức năng chính của bạn. 

Okay. Vì vậy, bạn thậm chí không có đã xây dựng cây cách toàn bộ. Nhưng bất cứ ai có một cái gì đó tôi có thể kéo lên để hiển thị như thế nào người ta có thể bắt đầu xây dựng một cây như vậy? [Sinh viên] của ai đó đập, cố gắng để có được ra ngoài. Bowden] Bất cứ ai cũng thoải mái với xây dựng cây của họ? [Sinh viên] Chắc chắn. Nó không phải thực hiện. >> Đó là tốt. Chúng tôi chỉ có thể kết thúc oh, bạn có thể lưu nó? Hoan hô. Vì vậy, ở đây chúng tôi có - oh, tôi hơi cắt. Tôi phóng to? Phóng to, di chuyển ra ngoài. >> Tôi có một câu hỏi. >> Yeah? [Sinh viên] Khi bạn xác định cấu trúc, những thứ như khởi tạo để bất cứ điều gì? Bowden] số >> Okay. Vì vậy, bạn sẽ phải khởi tạo - [Bowden] số Khi bạn xác định, hoặc khi bạn khai báo một cấu trúc, nó không được khởi tạo theo mặc định, nó giống như nếu bạn khai báo một int. Đó là chính xác những điều tương tự. Nó giống như mỗi người trong các lĩnh vực cá nhân của mình có thể có một giá trị rác trong nó. >> Và là nó có thể để xác định hoặc tuyên bố một struct trong một cách mà nó không khởi tạo cho họ? [Bowden]. Vì vậy, cú pháp khởi tạo shortcut sẽ trông giống như - Có hai cách chúng ta có thể làm điều này. Tôi nghĩ chúng ta nên biên dịch nó Clang chắc chắn cũng làm điều này. Thứ tự của các đối số trong đó có cấu trúc, bạn đặt như là thứ tự của các đối số bên trong các dấu ngoặc nhọn. Vì vậy, nếu bạn muốn khởi tạo nó đến 9 và để lại được vô giá trị và sau đó phải được null, nó sẽ là 9, null, null. Cách khác là, và biên tập viên không thích cú pháp này, và nó nghĩ rằng tôi muốn có một khối mới, nhưng thay thế là một cái gì đó như ở đây, tôi sẽ đặt nó trên một dòng mới. Bạn có thể nói một cách rõ ràng, tôi quên cú pháp chính xác. Vì vậy, bạn rõ ràng có thể giải quyết chúng theo tên, và nói, C, hoặc giá trị. = 9, trái = NULL. Tôi đoán những cần phải có dấu phẩy. Bên phải = NULL, do đó, cách này, bạn không thực sự cần phải biết thứ tự của cấu trúc, và khi bạn đang đọc này, nó rõ ràng hơn rất nhiều về những gì giá trị đang được khởi tạo. 

Điều này xảy ra là một trong những điều mà - như vậy, đối với hầu hết các phần, C + + là một superset của C. Bạn có thể lấy mã C, di chuyển nó trên C + +, và nó nên biên dịch. Đây là một trong những điều mà C + + không hỗ trợ, do đó, người dân có xu hướng không để làm điều đó. Tôi không biết nếu đó là lý do duy nhất người dân có xu hướng không để làm điều đó, nhưng trường hợp mà tôi cần thiết để sử dụng nó cần thiết để làm việc với C + + và vì vậy tôi không thể sử dụng. Một ví dụ khác của một cái gì đó không làm việc với C + + là cách malloc trả về một "void *", về mặt kỹ thuật, nhưng bạn chỉ có thể nói char * x bất cứ điều gì malloc = và nó sẽ tự động được đúc vào một char *. Đó là diễn viên tự động không xảy ra trong C + +. Điều đó sẽ không biên dịch, và bạn rõ ràng sẽ cần phải nói char * malloc, bất cứ điều gì, bỏ nó vào một char *. Không có nhiều điều rằng C và C + + không đồng ý về, mà còn cả hai. Vì vậy, chúng ta sẽ đến với cú pháp này. Nhưng ngay cả khi chúng tôi đã không đi với cú pháp đó, những gì là - có thể là sai với điều này? [Sinh viên] Tôi không cần phải tới đích của nó? >> Yeah. Hãy nhớ rằng mũi tên có một dereference ngầm, và do đó, khi chúng ta chỉ đối phó với một cấu trúc, chúng tôi muốn sử dụng. để có được ở một bên trong các trường của cấu trúc. Và thời gian duy nhất mà chúng tôi sử dụng mũi tên là khi chúng ta muốn làm - cũng, mũi tên tương đương với đó là những gì nó sẽ có nghĩa là nếu tôi sử dụng mũi tên. Tất cả các phương mũi tên, dereference này, bây giờ tôi đang ở một cấu trúc, và tôi có thể nhận được các lĩnh vực. Hoặc là có được lĩnh vực trực tiếp hoặc dereference và lĩnh vực - Tôi đoán này nên được giá trị. Nhưng ở đây tôi đang đối phó với một cấu trúc, không phải là một con trỏ đến một cấu trúc, và vì vậy tôi không thể sử dụng mũi tên. Tuy nhiên, các loại điều này chúng ta có thể làm cho tất cả các nút. Lạy Chúa tôi. Đây là 6, 7, và 3. Sau đó, chúng ta có thể thiết lập các chi nhánh trong cây của chúng tôi, chúng tôi có thể có 7 - chúng ta có thể có, bên trái của nó nên chỉ đến 3. Vì vậy, làm thế nào để chúng ta làm điều đó? [Sinh viên, không thể hiểu] >> Vâng. Địa chỉ của node3, và nếu bạn không có địa chỉ, sau đó nó chỉ sẽ không biên dịch. Nhưng hãy nhớ rằng đây là những con trỏ đến các hạch tiếp theo. Quyền nên chỉ đến 9, và 3 điểm trên bên phải đến 6. Tôi nghĩ rằng đây là tất cả các thiết lập. Bất kỳ ý kiến ​​hoặc câu hỏi? [Sinh viên, không thể hiểu] Gốc này sẽ là 7. Chúng tôi chỉ có thể nói node * ptr = hoặc root = & node7. 

Đối với mục đích của chúng ta, chúng ta sẽ được giao dịch với chèn, do đó, chúng ta sẽ muốn viết một chức năng để chèn vào cây nhị phân này và chèn chắc chắn sẽ gọi malloc để tạo ra một nút mới cho cây. Vì vậy, mọi thứ đang đi để có được lộn xộn với thực tế rằng một số nút Hiện tại trên stack và các nút khác sẽ kết thúc trên heap khi chúng ta chèn chúng. Điều này là hoàn toàn hợp lệ, nhưng lý do duy nhất chúng tôi có thể làm điều này trên stack là bởi vì nó là một ví dụ contrived mà chúng ta biết cây là vụ phải được xây dựng như là 7, 3, 6, 9. Nếu chúng ta không có điều này, thì chúng ta sẽ không phải malloc ở nơi đầu tiên. Như chúng ta sẽ thấy một chút sau đó, chúng ta nên malloc'ing. Ngay bây giờ nó hoàn toàn hợp lý để đưa vào ngăn xếp, nhưng hãy để thay đổi điều này với thực hiện malloc. Vì vậy, mỗi trong số này sẽ là một cái gì đó như nút * node9 = malloc (sizeof (node)). Và bây giờ chúng ta sẽ phải làm kiểm tra của chúng tôi. if (node9 == NULL) - Tôi không muốn điều đó - trở về 1, và sau đó chúng ta có thể làm node9-> bởi vì bây giờ nó là một con trỏ, giá trị = 6, node9-> trái = NULL, node9-> bên phải = NULL, và chúng ta sẽ phải làm điều đó cho mỗi người trong số những nút. Vì vậy, thay vào đó, hãy đặt nó bên trong một chức năng riêng biệt. Hãy gọi nó là node * build_node, và điều này là hơi tương tự như các API của chúng tôi cung cấp cho mã hóa Huffman. Chúng tôi cung cấp cho bạn chức năng khởi tạo cho một cây và deconstructor "chức năng" cho những cây và giống nhau đối với rừng. 

Vì vậy, ở đây chúng tôi đang đi để có một chức năng khởi tạo chỉ cần xây dựng một nút cho chúng tôi. Và nó sẽ nhìn khá nhiều chính xác như thế này. Và tôi thậm chí sẽ được lười biếng và không thay đổi tên của biến, mặc dù node9 làm cho không có ý nghĩa nữa. Ồ, tôi đoán giá trị của node9 không cần phải có được 6. Bây giờ chúng ta có thể trở lại node9. Và ở đây chúng ta nên trở về null. Mọi người đều đồng ý rằng chức năng xây dựng một nút? Vì vậy, bây giờ chúng tôi chỉ có thể gọi đó là xây dựng bất kỳ nút với một giá trị nhất định và con trỏ null. Bây giờ chúng ta có thể gọi đó, chúng ta có thể làm nút * node9 = build_node (9). Và chúng ta hãy làm. . . 6, 3, 7, 6, 3, 7. Và bây giờ chúng tôi muốn thiết lập các con trỏ, ngoại trừ bây giờ tất cả mọi thứ đã về của các con trỏ vì vậy không còn cần địa chỉ của. Okay. Vì vậy, điều cuối cùng tôi muốn làm là những gì? Có một kiểm tra lỗi mà tôi không làm. Những gì không xây dựng trở lại nút? [Sinh viên, không thể hiểu] >> Vâng. Nếu malloc không thành công, nó sẽ trả về null. Vì vậy, tôi sẽ uể oải đặt nó xuống ở đây thay vì làm một điều kiện cho mỗi. Nếu (node9 == NULL, hoặc thậm chí đơn giản, điều này là tương đương với chỉ nếu không node9. Vì vậy, nếu không node9, hoặc không node6, hoặc không node3, hoặc không node7, trở về 1. Có lẽ chúng ta nên in malloc không thành công, hoặc một cái gì đó. [Sinh viên giả bằng vô giá trị cũng? Bowden] Bất kỳ giá trị bằng không là sai. Vì vậy, null là một giá trị bằng không. Zero là một giá trị bằng không. Dối là một giá trị bằng không. Bất kỳ khá nhiều 2 giá trị không chỉ là vô giá trị và không, sai là chỉ băm được định nghĩa như là số không. Điều đó cũng được áp dụng nếu chúng ta khai báo biến toàn cầu. Nếu chúng ta đã có gốc * nút lên ở đây, sau đó - điều tốt đẹp về các biến toàn cầu là họ luôn luôn có một giá trị ban đầu. Điều đó không đúng chức năng, làm thế nào bên trong đây, nếu chúng ta có, như thế, node * hoặc nút x. Chúng tôi không có ý tưởng những gì x.value, x.whatever, hoặc chúng tôi có thể in ra và họ có thể được tùy ý. Đó là không đúng sự thật của các biến toàn cầu. Nút gốc hoặc nút x. Theo mặc định, tất cả mọi thứ đó là toàn cầu, nếu không rõ ràng khởi tạo một số giá trị, có một giá trị số không như giá trị của nó. Vì vậy, ở đây, node * gốc, chúng tôi không rõ ràng khởi tạo nó bất cứ điều gì, do đó, giá trị mặc định của nó sẽ được null, đó là giá trị số không của con trỏ. Giá trị mặc định của x được sẽ có nghĩa là x.value là số không, x.left là null, và là null x.right. Vì vậy, kể từ khi nó là một cấu trúc, tất cả các lĩnh vực của cấu trúc sẽ là không có giá trị. Chúng tôi không cần phải sử dụng điều đó ở đây, mặc dù. [Sinh viên] cấu trúc khác nhau hơn so với các biến số khác, và các biến khác các giá trị rác, đây là những số không? [Bowden] giá trị khác. Vì vậy, trong x, x sẽ bằng không. Nếu đó là ở phạm vi toàn cầu, nó có một giá trị ban đầu. >> Okay. [Bowden] Hoặc là giá trị ban đầu bạn đã cho nó hay không. Tôi nghĩ rằng sẽ chăm sóc của tất cả những điều này. 

Okay. Vì vậy, phần tiếp theo của câu hỏi yêu cầu, "Bây giờ chúng ta muốn viết một chức năng được gọi là có chứa với một nguyên mẫu của bool chứa giá trị int. " Chúng tôi sẽ không làm bool chứa giá trị int. Nguyên mẫu của chúng tôi là sẽ trông giống như bool chứa (giá trị int. Và sau đó chúng tôi cũng sẽ vượt qua nó là cây rằng nó phải được kiểm tra để xem nếu nó có giá trị đó. Do vậy, node * cây). Okay. Và sau đó chúng ta có thể gọi nó với một cái gì đó như, có lẽ chúng ta sẽ muốn printf hoặc một cái gì đó. Có 6, rễ của chúng tôi. Điều đó sẽ trở lại, hoặc đúng, trong khi đó có 5 gốc nên trả về false. Vì vậy, mất một giây để thực hiện điều này. Bạn có thể làm điều đó, hoặc lặp đi lặp lại hoặc đệ quy. Những điều tốt đẹp về cách mà chúng ta đã thiết lập những điều là nó vay chính nó để giải pháp đệ quy của chúng tôi dễ dàng hơn nhiều hơn so với cách biến toàn cầu. Bởi vì nếu chúng ta chỉ có chứa giá trị int, sau đó chúng tôi không có cách nào recursing xuống subtrees. Chúng tôi sẽ phải có một chức năng trợ giúp riêng biệt mà recurses xuống subtrees cho chúng tôi. Nhưng kể từ khi chúng tôi đã thay đổi nó để có những cây như một tham số, mà nó phải luôn luôn có được ở nơi đầu tiên, bây giờ chúng ta có thể recurse dễ dàng hơn. Vì vậy, lặp đi lặp lại hoặc đệ quy, chúng tôi sẽ đi qua cả hai, nhưng chúng ta sẽ thấy rằng kết thúc đệ quy lên được khá dễ dàng. Okay. Có ai có một cái gì đó chúng ta có thể làm việc với? 

[Sinh viên] Tôi đã có một giải pháp lặp. >> Tất cả phải, lặp đi lặp lại. Được rồi, đây có vẻ tốt. Vì vậy, muốn đi bộ chúng tôi thông qua nó? [Sinh viên] Chắc chắn. Vì vậy, tôi thiết lập một biến temp để có được nút đầu tiên của cây. Và sau đó tôi chỉ looped thông qua trong khi tạm thời không null bằng, do đó, trong khi vẫn còn trong cây, tôi đoán. Và nếu giá trị bằng với giá trị tạm thời đang trỏ đến, sau đó nó sẽ trả về giá trị đó. Nếu không, nó sẽ kiểm tra nếu nó trên bên phải hay bên trái. Nếu bạn đã bao giờ có được một tình huống mà không có cây hơn, sau đó nó sẽ trả về nó thoát ra khỏi vòng lặp và trả về false. [Bowden] Okay. Vì vậy, đó có vẻ tốt. Bất cứ ai có bất kỳ ý kiến ​​về bất cứ điều gì? Tôi không có ý kiến ​​đúng đắn ở tất cả. Một trong những điều chúng ta có thể làm là anh chàng này. Ồ, nó sẽ đi một hơi dài chút. Tôi sẽ sửa chữa mà lên. Okay. 

Mọi người nên nhớ ternary hoạt động như thế nào. Đã chắc chắn có được câu đố trong quá khứ cung cấp cho bạn một chức năng với một nhà điều hành ternary, và nói, dịch này, làm một cái gì đó mà không sử dụng ternary. Vì vậy, đây là một trường hợp rất phổ biến khi tôi sẽ nghĩ đến việc sử dụng ternary, nơi mà nếu một số điều kiện thiết lập một biến đến một cái gì đó, khác thiết lập mà cùng một biến cái gì khác. Đó là một cái gì đó rất thường xuyên có thể được chuyển đổi thành các loại điều này , nơi đặt biến này - hoặc, tốt, điều này là đúng? Sau đó, khác này. [Sinh viên] Người đầu tiên là nếu đúng sự thật, đúng không? [Bowden] Yeah. Tôi luôn luôn đọc nó, tạm thời bằng giá trị lớn hơn giá trị tạm thời, sau đó điều này, người nào khác. Nó hỏi một câu hỏi. Nó phải cao? Sau đó làm việc đầu tiên. Khác làm điều thứ hai. Tôi gần như luôn luôn - đại tràng, tôi chỉ - trong đầu tôi, tôi đọc là khác. 

Có ai có một giải pháp đệ quy? Okay. Điều này chúng ta sẽ nó đã có thể là tuyệt vời, nhưng chúng tôi sẽ làm cho nó tốt hơn. Này là khá nhiều cùng một ý tưởng chính xác. Nó chỉ là, tốt, bạn có muốn giải thích? [Sinh viên] Chắc chắn. Vì vậy, chúng tôi đảm bảo rằng cây không null đầu tiên, bởi vì nếu cây là null thì nó sẽ trả về false vì chúng ta đã không tìm thấy nó. Và nếu vẫn còn có một cái cây, chúng tôi đi vào - đầu tiên chúng ta kiểm tra nếu giá trị là nút hiện tại. Trả lại đúng sự thật nếu nó là, và nếu không recurse chúng tôi ở bên trái hoặc bên phải. Mà âm thanh thích hợp? >> Mm-hmm. (Hiệp định) Vì vậy, nhận thấy rằng điều này gần như là cấu trúc rất giống với các giải pháp lặp đi lặp lại. Nó chỉ là thay vì recursing, chúng tôi đã có một vòng lặp while. Và trường hợp cơ sở ở đây, nơi cây nào không null bằng là điều kiện theo đó chúng tôi đã nổ ra của vòng lặp while. Chúng tôi rất giống nhau. Nhưng chúng tôi sẽ phải mất thêm một bước này. Bây giờ, chúng tôi làm điều tương tự ở đây. Nhận thấy chúng ta đang quay trở lại điều tương tự trong cả hai của những dòng này, ngoại trừ một đối số là khác nhau. Vì vậy, chúng ta sẽ làm cho rằng vào một ternary. Tôi nhấn một cái gì đó tùy chọn, và nó được thực hiện một biểu tượng. Okay. Vì vậy, chúng ta sẽ quay trở lại chứa đó. Đây là nhận được nhiều dòng, tốt, phóng to nó. Thông thường, như là một điều phong cách, tôi không nghĩ rằng nhiều người đặt một không gian sau khi mũi tên, nhưng tôi đoán nếu bạn là nhất quán, đó là tiền phạt. Nếu giá trị thấp hơn giá trị cây, chúng tôi muốn để recurse bên trái cây, khác chúng tôi muốn để recurse bên phải cây. Vì vậy, đó là một bước làm cho cái nhìn nhỏ hơn. Bước hai làm cho cái nhìn nhỏ hơn - chúng ta có thể tách biệt này cho nhiều dòng. Okay. Bước hai làm cho nó trông nhỏ hơn là ở đây, do đó, giá trị trả về bằng giá trị cây, hoặc có chứa bất cứ điều gì. 

Đây là một điều quan trọng. Tôi không chắc chắn nếu ông nói nó rõ ràng trong các lớp học, nhưng nó được gọi là đánh giá ngắn mạch. Ý tưởng ở đây là giá trị == cây giá trị. Nếu điều đó đúng, thì đây là sự thật, và chúng tôi muốn "hoặc" chúng ta với bất cứ điều gì ở đây. Vì vậy, mà không cần suy nghĩ về bất cứ điều gì ở đây, sẽ trả lại toàn bộ biểu thức là gì? [Sinh viên] Đúng? >> Yeah, bởi vì thực sự của bất cứ điều gì, or'd or'd hoặc đúng với bất cứ điều gì là nhất thiết phải đúng. Vì vậy, ngay khi chúng tôi nhìn thấy giá trị trả về = giá trị cây, chúng ta chỉ cần đi để trở về đúng. Thậm chí không để recurse tiếp tục chứa xuống dòng. Chúng ta có thể thêm một bước này. Quay trở lại cây nào không null bằng nhau và tất cả những điều này. Nó làm cho nó một chức năng một dòng. Đây cũng là một ví dụ về đánh giá ngắn mạch. Nhưng bây giờ nó là ý tưởng tương tự - thay vì - vì vậy nếu cây không null bằng - hoặc, tốt, nếu cây vô giá trị bằng, đó là trường hợp xấu, nếu cây bằng null, sau đó điều kiện đầu tiên sẽ là sai lầm. Vì vậy, giả ANDed với bất cứ điều gì là có được những gì? [Sinh viên] False. >> Yeah. Đây là nửa kia của đánh giá ngắn mạch, nếu cây không bằng vô giá trị, sau đó chúng tôi sẽ không thậm chí đi - hoặc nếu cây vô giá trị bằng, sau đó chúng tôi sẽ không làm giá trị == cây giá trị. Chúng tôi sẽ ngay lập tức quay trở lại sai. Đó là quan trọng, vì nếu nó đã không ngắn mạch đánh giá các sau đó nếu cây vô giá trị bằng, điều kiện thứ hai này sẽ seg lỗi, bởi vì cây-> giá trị được dereferencing null. Vì vậy, đó là điều đó. Có thể làm cho thay đổi một lần trong suốt. Đây là một điều rất phổ biến cũng có, không làm điều này một dòng với điều này, nhưng đó là một điều phổ biến trong điều kiện, có thể không đúng ở đây, nhưng nếu (cây NULL =, và cây-> giá trị == giá trị), làm bất cứ điều gì. Đây là một tình trạng rất phổ biến, thay vì phải để phá vỡ thành hai ifs, thích, là null cây? Được rồi, nó không phải null, vì vậy bây giờ là giá trị cây bằng giá trị? Làm điều này. Thay vào đó, điều kiện này, điều này sẽ không bao giờ seg lỗi bởi vì nó sẽ phá vỡ nếu điều này xảy ra được null. Vâng, tôi đoán nếu cây của bạn hoàn toàn là một con trỏ không hợp lệ, nó vẫn có thể seg lỗi, nhưng nó không thể seg lỗi nếu cây là null. Nếu nó là null, nó sẽ phá vỡ trước khi bạn dereferenced con trỏ ở nơi đầu tiên. [Sinh viên này gọi là đánh giá lười biếng? 

Bowden] Lazy đánh giá là một điều riêng biệt. Lười biếng đánh giá là giống như bạn yêu cầu một giá trị, bạn yêu cầu để tính toán một giá trị, loại, nhưng bạn không cần nó ngay lập tức. Vì vậy, cho đến khi bạn thực sự cần nó, nó không phải là đánh giá. Đây không phải là chính xác những điều tương tự, nhưng trong pset Huffman, nó nói rằng chúng ta "lười biếng" viết. Lý do chúng tôi làm điều đó là vì chúng ta đang thực sự đệm viết chúng tôi không muốn để viết các bit riêng lẻ tại một thời điểm, hoặc byte cá nhân tại một thời điểm, chúng tôi thay vì muốn có được một đoạn byte. Sau đó, một khi chúng ta có một đoạn byte, sau đó chúng tôi sẽ viết nó ra. Mặc dù bạn yêu cầu nó để viết và fwrite và fread làm cùng một loại điều. Họ đệm đọc và viết. Mặc dù bạn yêu cầu nó để viết ngay lập tức, nó có thể sẽ không. Và bạn không thể chắc chắn rằng mọi thứ sẽ phải được viết cho đến khi bạn gọi hfclose hoặc bất cứ điều gì nó là, sau đó nói, không sao, tôi đang đóng tập tin của tôi, điều đó có nghĩa là tôi muốn viết tốt hơn tất cả mọi thứ tôi đã không viết. Nó không có cần phải viết ra tất cả mọi thứ cho đến khi bạn đóng file, và sau đó nó cần. Vì vậy, đó chỉ là những gì lười biếng - nó chờ đợi cho đến khi nó đã xảy ra. - Lấy 51 và bạn sẽ đi vào chi tiết hơn, vì OCaml và tất cả mọi thứ trong 51, tất cả mọi thứ là đệ quy. Không có lặp đi lặp lại các giải pháp, về cơ bản. Tất cả mọi thứ là đệ quy, và đánh giá lười biếng sẽ là quan trọng cho rất nhiều hoàn cảnh ở đâu, nếu bạn không lazily đánh giá, mà có nghĩa - Ví dụ là suối, là dài vô hạn. Về lý thuyết, bạn có thể nghĩ các số tự nhiên như là một dòng của 1-2-3-4-5-6-7, Vì vậy, lười biếng đánh giá là tốt. Nếu tôi nói rằng tôi muốn số thứ mười, sau đó tôi có thể đánh giá lên đến số thứ mười. Nếu tôi muốn số trăm, sau đó tôi có thể đánh giá lên đến số trăm. Nếu không có đánh giá lười biếng, sau đó nó sẽ cố gắng để đánh giá tất cả các con số ngay lập tức. Bạn đang đánh giá số lượng vô hạn, và đó là điều không thể. Vì vậy, có rất nhiều trường hợp đánh giá lười biếng chỉ là điều cần thiết để nhận được những điều để làm việc. 

Bây giờ chúng ta muốn viết chèn nơi chèn là có được tương tự như thay đổi trong định nghĩa của nó. Vì vậy, ngay bây giờ nó bool chèn (int giá trị). Chúng ta sẽ thay đổi điều đó để chèn bool (int giá trị, node * cây). Chúng tôi đang thực sự sẽ thay đổi điều đó một lần nữa trong một chút, chúng ta sẽ thấy lý do tại sao. Và chúng ta hãy di chuyển build_node, chỉ cần cho các heck của nó, trên chèn vì vậy chúng tôi không cần phải viết một mẫu thử nghiệm chức năng. Đó là một gợi ý rằng bạn sẽ được sử dụng build_node trong chèn. Okay. Hãy dành một phút cho điều đó. Tôi nghĩ rằng tôi đã lưu các sửa đổi nếu bạn muốn kéo từ đó, hoặc, ít nhất, tôi đã làm ngay bây giờ. Tôi muốn nghỉ ngơi một chút để suy nghĩ về logic chèn, nếu bạn không thể nghĩ về nó. Về cơ bản, bạn sẽ chỉ bao giờ được chèn tại lá. Giống như, nếu tôi chèn 1, sau đó tôi chắc chắn sẽ được chèn 1 - Tôi sẽ thay đổi sang màu đen - sẽ được chèn 1 trên đây. Hoặc nếu tôi chèn 4, tôi muốn được chèn 4 trên đây. Vì vậy, không có vấn đề gì bạn làm, bạn sẽ được chèn vào một chiếc lá. Tất cả những gì bạn phải làm là lặp xuống cây cho đến khi bạn nhận được để nút đó phải là của nút cha, nút mới của cha mẹ, và sau đó thay đổi con trỏ của nó sang trái hoặc phải, tùy thuộc vào việc nó lớn hơn hoặc ít hơn so với các nút hiện tại. Thay đổi con trỏ để trỏ đến nút mới của bạn. Vì vậy, lặp xuống cây, làm cho điểm lá để các nút mới. Cũng nghĩ về lý do tại sao mà cấm các loại tình hình trước khi, nơi mà tôi xây dựng cây nhị phân mà nó là chính xác nếu bạn chỉ nhìn một nút duy nhất, nhưng 9 là bên trái của 7 nếu bạn lặp tất cả các cách. Vì vậy, đó là không thể trong kịch bản này, kể từ khi nghĩ về chèn 9 hoặc một cái gì đó, tại nút đầu tiên, Tôi sẽ xem 7 và tôi chỉ cần đi bên phải. Vì vậy, không quan trọng những gì tôi làm, nếu tôi chèn bằng cách đi một lá, và một chiếc lá bằng cách sử dụng các thuật toán thích hợp, nó sẽ là không thể cho tôi để chèn 9 đến bên trái của 7 bởi vì ngay sau khi tôi nhấn 7 tôi sẽ đi về bên phải. Có ai có một cái gì đó để bắt đầu? [Sinh viên] tôi làm. >> Chắc chắn rồi. [Sinh viên, không thể hiểu] [Sinh viên, không thể hiểu] [Bowden] Nó được đánh giá cao. Okay. Muốn giải thích? 

[Sinh viên] Kể từ khi chúng ta biết rằng chúng tôi đã được chèn các nút mới vào cuối của cây, Tôi looped thông qua cây lặp đi lặp lại cho đến khi tôi có một nút chỉ để null. Và sau đó tôi đã quyết định để đặt nó hoặc bên phải hay bên trái bằng cách sử dụng biến này, nó nói với tôi nơi để đặt nó. Và sau đó, về cơ bản, tôi chỉ cần thực hiện mà cuối cùng - rằng nút tạm thời trỏ đến nút mới mà nó đã được tạo ra, hoặc là ở phía bên trái hoặc bên phải, tùy thuộc vào những gì giá trị. Cuối cùng, tôi thiết lập giá trị nút mới vào giá trị của thử nghiệm của nó. [Bowden] Được rồi, vì vậy tôi thấy một vấn đề ở đây. Điều này cũng giống như 95% của con đường đó. Một vấn đề mà tôi thấy, tốt, không ai khác nhìn thấy một vấn đề? Hoàn cảnh, theo đó họ thoát ra khỏi vòng lặp là gì? [Sinh viên] Nếu temp là null? >> Yeah. Vì vậy, làm thế nào bạn thoát ra khỏi vòng lặp nếu tạm thời là null. Nhưng tôi phải làm gì phải ở đây? Tôi dereference temp, mà chắc chắn là vô giá trị. Vì vậy, điều khác bạn cần làm không phải là chỉ cần theo dõi cho đến khi temp là null, bạn muốn theo dõi của cha mẹ ở tất cả các lần. Chúng tôi cũng muốn cha mẹ * nút, tôi đoán chúng ta có thể giữ cho rằng tại vô giá trị lần đầu tiên. Điều này sẽ có hành vi lạ cho thư mục gốc của cây, nhưng chúng tôi sẽ nhận được để mà. Nếu giá trị lớn hơn bất cứ điều gì, sau đó tạm thời = temp đúng. Nhưng trước khi chúng tôi làm điều đó, cha mẹ = temp. Hoặc là cha mẹ vẫn luôn sẽ tạm thời bằng? Có đúng như vậy không? Nếu tạm thời không phải là null, sau đó tôi sẽ di chuyển xuống, không có vấn đề gì, đến một nút mà tạm thời là cha mẹ. Vì vậy, cha mẹ sẽ là tạm thời, và sau đó tôi di chuyển tạm thời xuống. Bây giờ tạm thời là null, nhưng phụ huynh để phụ huynh trong những điều đó là null. Vì vậy, ở đây, tôi không muốn để thiết lập bằng 1. Vì vậy, tôi chuyển sang bên phải, do đó, nếu bên phải = 1, và tôi đoán bạn cũng muốn làm - nếu bạn di chuyển sang bên trái, bạn muốn thiết lập bằng 0. Hoặc người nào khác nếu bạn di chuyển sang phải. Vì vậy, ngay = 0. Nếu bên phải = 1, bây giờ chúng tôi muốn làm cho cha mẹ con trỏ phải newnode, khác, chúng tôi muốn làm cho cha mẹ con trỏ trái newnode. Câu hỏi về điều đó? Okay. Vì vậy, đây là cách chúng ta tốt, thực sự, thay vì làm điều này, chúng tôi một nửa dự kiến ​​bạn sử dụng build_node. Và sau đó nếu newnode bằng null, trả về false. Đó là điều đó. Bây giờ, đây là những gì chúng ta mong đợi bạn làm. 

Đây là những gì các giải pháp nhân viên làm. Tôi không đồng ý với điều này như là cách "đúng" đi về nó nhưng điều này là hoàn toàn tốt đẹp và nó sẽ làm việc. Một điều đó là một chút quyền tại nếu cây bắt đầu như là null, chúng tôi vượt qua trong một cây null. Tôi đoán nó phụ thuộc vào cách bạn định nghĩa hành vi của đi qua trong một cây null. Tôi sẽ nghĩ rằng nếu bạn vượt qua trong một cây null, sau đó chèn giá trị vào một cây null chỉ phải trả lại một cây nơi mà các giá trị duy nhất là nút duy nhất. Mọi người đồng ý với điều đó? Bạn có thể, nếu bạn muốn, nếu bạn vượt qua trong một cây null và bạn muốn chèn một giá trị vào nó, trả về false. Đó là vào bạn để xác định điều đó. Để làm được điều đầu tiên tôi nói và sau đó - tốt, bạn sẽ gặp khó khăn khi làm điều đó, bởi vì nó sẽ dễ dàng hơn nếu chúng ta có một con trỏ toàn cầu để điều, nhưng chúng tôi không, vì vậy nếu cây là vô giá trị, có gì chúng ta có thể làm về điều đó. Chúng tôi chỉ có thể trả về false. Vì vậy, tôi sẽ thay đổi chèn. Chúng tôi về mặt kỹ thuật chỉ có thể thay đổi quyền này ở đây, làm thế nào nó lặp lại về những điều, nhưng tôi sẽ thay đổi chèn vào một nút ** cây. Đôi con trỏ. Điều này có nghĩa là gì? Thay vì đối phó với con trỏ đến các nút, điều tôi sẽ được thao tác này là con trỏ. Tôi sẽ được thao tác con trỏ này. Tôi sẽ được thao tác với con trỏ trực tiếp. Điều này là do, suy nghĩ về xuống - tốt, ngay bây giờ điều này dẫn đến giá trị null. Những gì tôi muốn làm là thao tác này con trỏ để trỏ đến không vô giá trị. Tôi muốn nó để trỏ đến nút mới của tôi. Nếu tôi chỉ theo dõi của các con trỏ đến con trỏ của tôi, sau đó tôi không cần phải theo dõi của một con trỏ mẹ. Tôi chỉ có thể theo dõi xem con trỏ đang trỏ đến null, và nếu con trỏ trỏ null, thay đổi nó để trỏ đến các nút tôi muốn. Và tôi có thể thay đổi kể từ khi tôi có một con trỏ đến con trỏ. Hãy xem này ngay bây giờ. Bạn thực sự có thể làm điều đó đệ quy khá dễ dàng. Chúng ta muốn làm điều đó? Có, chúng tôi làm. 

Hãy xem nó đệ quy. Đầu tiên, trường hợp cơ sở của chúng tôi sẽ làm gì? Hầu như luôn luôn trường hợp cơ sở của chúng tôi, nhưng trên thực tế, đây là loại phức tạp. Trước tiên, nếu (cây == NULL) Tôi đoán chúng tôi chỉ sẽ trả về false. Điều này là khác nhau từ cây là vô giá trị của bạn. Đây là con trỏ đến con trỏ gốc của bạn đang được null có nghĩa là con trỏ gốc của bạn không tồn tại. Vì vậy, xuống đây, nếu tôi làm node * - chúng ta hãy tái sử dụng. Node * root = NULL, và sau đó tôi sẽ gọi chèn bằng cách làm một cái gì đó như, chèn 4 vào & gốc. So & root, nếu thư mục gốc là một nút * sau đó & gốc là có được một ** nút. Điều này là hợp lệ. Trong trường hợp này, cây, lên đây, cây không phải là null - hoặc chèn. Ở đây. Cây là không null * cây là vô giá trị, mà là tốt bởi vì nếu cây * là null, sau đó tôi có thể thao tác nó đến nay chỉ những gì tôi muốn nó để trỏ đến. Nhưng nếu cây là vô giá trị, có nghĩa là tôi chỉ cần đến đây và nói vô giá trị. Điều đó không có ý nghĩa. Tôi không thể làm bất cứ điều gì với điều đó. Nếu cây là null, trả về false. Vì vậy, về cơ bản tôi đã nói những gì trường hợp cơ sở thực của chúng tôi là. Và đó là những gì được? [Sinh viên, không thể hiểu] [Bowden]. Vì vậy, nếu (* cây == NULL). Điều này liên quan đến các trường hợp trên đây nếu con trỏ màu đỏ của tôi là con trỏ tôi đang tập trung vào, như tôi đang tập trung vào con trỏ này, bây giờ tôi đang tập trung vào con trỏ này. Bây giờ tôi đang tập trung vào con trỏ này. Vì vậy, nếu con trỏ màu đỏ của tôi, mà là ** nút, bao giờ hết - nếu *, con trỏ màu đỏ của tôi, bao giờ là vô giá trị, điều đó có nghĩa là tôi đang ở trường hợp mà tôi đang tập trung vào một con trỏ trỏ - đây là một con trỏ thuộc về một chiếc lá. Tôi muốn thay đổi con trỏ để trỏ đến nút mới của tôi. Trở lại ở đây. Newnode của tôi sẽ chỉ được node * n = build_node (giá trị) sau đó n, nếu n = NULL, trả về false. Khác, chúng tôi muốn thay đổi những gì con trỏ trỏ đến trỏ đến nút mới được xây dựng của chúng tôi. Chúng tôi thực sự có thể làm điều đó ở đây. Thay vì nói n, chúng ta nói * cây = nếu * cây. Mọi người đều hiểu rằng? Đó là bằng cách giao dịch với các con trỏ để trỏ, chúng ta có thể thay đổi con trỏ null để trỏ đến những điều chúng tôi muốn họ để trỏ đến. Đó là trường hợp cơ sở của chúng tôi. 

Bây giờ chúng tôi tái phát, hoặc đệ quy của chúng tôi, sẽ là rất tương tự như tất cả các recursions khác chúng tôi đã làm. Chúng tôi sẽ muốn để chèn giá trị, và bây giờ tôi sẽ sử dụng ternary một lần nữa, nhưng tình trạng của chúng tôi sẽ làm gì? Đó là những gì chúng tôi đang tìm kiếm để quyết định xem chúng ta muốn đi sang trái hoặc phải? Hãy làm điều đó trong các bước riêng biệt. Nếu (giá trị <)? [Sinh viên] giá trị của cây? [Bowden] Vì vậy, hãy nhớ rằng tôi là hiện nay - [Sinh viên, không thể hiểu] [Bowden] Yeah, vì vậy ngay tại đây, chúng ta hãy nói rằng mũi tên màu xanh lá cây này là một ví dụ về cây hiện nay là gì, là một con trỏ đến con trỏ này. Vì vậy, điều đó có nghĩa là tôi là một con trỏ đến một con trỏ đến 3. Dereference hai lần nghe có vẻ tốt. Những gì tôi - làm thế nào để tôi làm điều đó? [Sinh viên] tham chiếu đến một lần, và sau đó mũi tên làm theo cách đó? [Bowden] Vì vậy, (cây) dereference một lần, -> giá trị sẽ đưa cho tôi giá trị của các nút mà tôi đang gián tiếp chỉ ra. Vì vậy, tôi cũng có thể viết nó ** tree.value nếu bạn thích điều đó. Hoặc là công trình. Nếu đó là trường hợp, sau đó tôi muốn gọi chèn có giá trị. Và nút của tôi cập nhật được những gì ** sẽ được? Tôi muốn đi bên trái, vì vậy ** tree.left là có được trái của tôi. Và tôi muốn con trỏ để điều đó do đó nếu bên trái kết thúc lên được con trỏ null, Tôi có thể sửa đổi nó để trỏ đến nút mới của tôi. 

Và các trường hợp khác có thể rất giống nhau. Hãy để thực sự làm cho ternary của tôi ngay bây giờ. Chèn giá trị nếu giá trị <(** cây). Giá trị. Sau đó, chúng tôi muốn để cập nhật ** của chúng tôi sang bên trái, khác, chúng tôi muốn để cập nhật ** bên phải. [Sinh viên] mà có được con trỏ đến con trỏ? [Bowden Hãy nhớ rằng - ** tree.right là một ngôi sao nút. [Sinh viên, không thể hiểu] >> Vâng. ** Tree.right là như thế này con trỏ hoặc một cái gì đó. Vì vậy, bằng cách tham gia một con trỏ vào đó, điều đó mang lại cho tôi những gì tôi muốn của con trỏ để anh chàng đó. [Sinh viên] chúng ta có thể đi qua một lần nữa lý do tại sao chúng tôi đang sử dụng hai con trỏ? [Bowden] Yeah. Vì vậy, - không có, bạn có thể, và giải pháp đó trước khi là một cách để làm việc đó mà không làm hai con trỏ. Bạn cần để có thể hiểu được bằng cách sử dụng hai con trỏ, và đây là một giải pháp sạch hơn. Ngoài ra, lưu ý rằng, những gì sẽ xảy ra nếu cây của tôi - điều gì sẽ xảy ra nếu thư mục gốc của tôi là vô giá trị? Điều gì sẽ xảy ra nếu tôi làm trường hợp này ngay tại đây không? Vì vậy, node * gốc = NULL, chèn 4 vào & gốc. Gốc được sẽ làm gì sau này? [Sinh viên, không thể hiểu] >> Vâng. Gốc giá trị là 4. Gốc bên trái sẽ được null, root quyền sẽ được null. Trong trường hợp chúng tôi đã không vượt qua gốc theo địa chỉ, chúng ta không thể sửa đổi root. Trong trường hợp cây gốc là vô giá trị, chúng tôi chỉ phải trả về false. Không có gì chúng ta có thể làm. Chúng tôi không thể chèn một nút vào một cây rỗng. Nhưng bây giờ chúng ta có thể, chúng ta chỉ cần thực hiện một cây đổ vào một cây một nút. Mà thường là cách dự kiến ​​rằng nó là nghĩa vụ phải làm việc. 

Hơn nữa, điều này là đáng kể ngắn hơn cũng theo dõi của cha mẹ, và do đó bạn lặp lại tất cả các cách. Bây giờ tôi có cha mẹ của tôi, và tôi chỉ có con trỏ phải cha mẹ của tôi bất cứ điều gì. Thay vào đó, nếu chúng ta đã làm điều này lặp đi lặp lại, nó muốn được cùng ý tưởng với một vòng lặp trong khi. Nhưng thay vì phải đối phó với con trỏ cha mẹ của tôi, thay vì con trỏ hiện tại của tôi sẽ là điều mà tôi đang trực tiếp sửa đổi để trỏ đến nút mới của tôi. Tôi không có để đối phó với cho dù đó là chỉ bên trái. Tôi không có để đối phó với cho dù đó là chỉ bên phải. Nó chỉ là bất cứ điều gì con trỏ này, tôi sẽ thiết lập nó để trỏ đến nút mới của tôi. Mọi người đều hiểu nó hoạt động như thế nào? Nếu không tại sao chúng ta muốn làm điều đó theo cách này, nhưng ít nhất đó công trình này như là một giải pháp? [Sinh viên] Nơi nào chúng ta trở lại đúng sự thật? Bowden] Đó có thể là ngay tại đây. Nếu chúng ta một cách chính xác chèn nó, trả lại đúng sự thật. Khác, xuống đây chúng ta sẽ muốn quay trở lại trả về chèn bất cứ điều gì. 

Và những gì đặc biệt về chức năng này đệ quy? Đó là đệ quy đuôi, như vậy miễn là chúng tôi biên dịch với một số tối ưu, nó sẽ nhận ra điều đó và bạn sẽ không bao giờ nhận được một chồng tràn từ này, ngay cả khi cây của chúng tôi có độ cao 10.000 hoặc 10 triệu. [Sinh viên, không thể hiểu] [Bowden] Tôi nghĩ rằng nó có phải nó Dash - hoặc những gì tối ưu hóa mức độ là cần thiết cho một đệ quy đuôi để được công nhận. Tôi nghĩ rằng nó nhận ra - GCC và Clang cũng có ý nghĩa khác nhau cho các mức độ tối ưu hóa của họ. Tôi muốn nói đó là 2 DashO, chắc chắn rằng nó sẽ nhận ra đệ quy đuôi. Nhưng chúng ta - bạn có thể xây dựng giống như một ví dụ Fibonocci hoặc một cái gì đó. Nó không phải dễ dàng để thử nghiệm với điều này, bởi vì rất khó để xây dựng một cây nhị phân đó là quá lớn. Nhưng yeah, tôi nghĩ rằng đó là 2 DashO, nếu bạn biên dịch với DashO 2, nó sẽ tìm kiếm đệ quy đuôi và tối ưu hóa mà ra. Hãy quay trở lại - chèn nghĩa là điều cuối cùng cần thiết. Hãy quay trở lại để chèn ở đây nơi mà chúng tôi đang đi để làm cùng một ý tưởng. Nó vẫn sẽ có lỗ hổng không thể hoàn toàn xử lý khi người chủ là null, hoặc nhập cảnh qua là null, nhưng thay vì đối phó với một con trỏ cha mẹ, hãy áp dụng cùng một logic của con trỏ giữ cho con trỏ. Nếu ở đây chúng tôi giữ nút của chúng tôi ** hiện, và chúng tôi không cần phải theo dõi nữa, nhưng nút ** hiện = & cây. Và bây giờ vòng lặp trong khi của chúng tôi là có được trong khi * hiện không null bằng. Bạn không cần phải theo dõi của cha mẹ nữa. Bạn không cần phải theo dõi của trái và bên phải. Và tôi sẽ gọi nó là tạm thời, bởi vì chúng tôi đã sử dụng tạm thời. Okay. Vì vậy, nếu (giá trị> * temp), sau đó & (* temp) -> quyền khác temp = & (* temp) -> còn lại. Và bây giờ, thời điểm này, sau khi vòng lặp trong khi, Tôi chỉ làm điều này bởi vì có thể nó dễ dàng hơn để suy nghĩ về lặp đi lặp lại hơn đệ quy, nhưng sau khi vòng lặp trong khi, * Temp là con trỏ chúng ta muốn thay đổi. 

Trước khi chúng tôi đã có cha mẹ, và chúng tôi muốn thay đổi trái cha hoặc mẹ hoặc phải cha mẹ, nhưng nếu chúng ta muốn thay đổi quyền cha mẹ, sau đó * temp là cha mẹ phải, và chúng ta có thể thay đổi trực tiếp. Vì vậy, ở đây, chúng ta có thể làm * temp = newnode, và đó là nó. Vì vậy, thông báo, tất cả những gì chúng ta đã làm trong này là đưa ra dòng mã. Để theo dõi của cha mẹ trong tất cả là nỗ lực thêm. Ở đây, nếu chúng ta chỉ theo dõi của con trỏ đến con trỏ, và thậm chí nếu chúng tôi muốn để có được loại bỏ tất cả các dấu ngoặc nhọn, làm cho nó trông ngắn hơn. Điều này bây giờ là cùng một giải pháp chính xác, nhưng ít dòng mã. Một khi bạn bắt đầu nhận ra điều này như là một giải pháp hợp lệ, nó cũng dễ dàng hơn về lý do như, được rồi, tại sao tôi có lá cờ này ở bên phải int? Điều đó có nghĩa là gì? Ồ, nó báo hiệu rằng mỗi khi tôi đi ngay, tôi cần phải đặt nó, khác nếu tôi đi để lại tôi cần phải đặt nó không. Ở đây, tôi không có lý do về điều đó, nó chỉ là dễ dàng hơn để suy nghĩ về. Câu hỏi? [Sinh viên, không thể hiểu] >> Vâng. Được rồi, do đó, trong các bit cuối cùng - Tôi đoán một cách nhanh chóng và dễ dàng chức năng chúng ta có thể làm là, let's - cùng, tôi đoán, thử và viết có chứa chức năng mà không quan tâm cho dù đó là một cây tìm kiếm nhị phân. Này bao gồm các chức năng nên trở lại đúng sự thật nếu bất cứ nơi nào trong cây nhị phân này nói chung là các giá trị mà chúng ta đang tìm kiếm. Vì vậy, hãy đầu tiên làm cho nó đệ quy và sau đó chúng tôi sẽ làm điều đó lặp đi lặp lại. Chúng ta có thể thực sự chỉ làm điều đó với nhau, bởi vì điều này là có được thực sự ngắn. 

Trường hợp cơ sở của tôi là gì được không? [Sinh viên, không thể hiểu] [Bowden] Vì vậy, nếu (cây == NULL), sau đó những gì? [Sinh viên] Quay trở lại sai. [Bowden] khac, tốt, tôi không cần gì khác. Nếu là trường hợp cơ sở khác của tôi. [Sinh viên] Tree của giá trị? >> Yeah. Vì vậy, nếu (cây-> giá trị == giá trị. Chú ý chúng tôi đang trở lại nút *, không phải nút ** s? Chứa sẽ không bao giờ cần phải sử dụng một ** nút, vì chúng tôi không thay đổi con trỏ. Chúng tôi chỉ đi qua chúng. Nếu điều đó xảy ra, sau đó chúng tôi muốn để trở về đúng. Khác, chúng tôi muốn đi qua các con. Vì vậy, chúng ta không thể lý luận về việc liệu tất cả mọi thứ bên trái là ít và tất cả mọi thứ bên phải là lớn hơn. Vì vậy, điều kiện của chúng tôi là những gì sẽ ở đây - hoặc, những gì chúng ta sẽ làm gì? [Sinh viên, không thể hiểu] >> Vâng. Quay lại chứa (giá trị, cây bên trái) hoặc có chứa (giá trị, cây-> phải). Và đó là nó. Và nhận thấy có một số đánh giá ngắn mạch, nơi mà nếu chúng xảy ra để tìm giá trị ở cây bên trái, chúng tôi không bao giờ cần phải nhìn vào cây bên phải. Đó là toàn bộ chức năng. Bây giờ chúng ta hãy làm điều đó lặp đi lặp lại, đó là sẽ được tốt đẹp ít. Chúng ta sẽ bắt đầu thông thường của hiện node = cây. Trong khi (hiện = NULL). Sẽ nhanh chóng thấy một vấn đề. Nếu hiện ra ở đây, nếu chúng ta đã bao giờ thoát ra khỏi điều này, sau đó chúng tôi đã chạy ra khỏi những điều để xem xét, trả về false. Nếu (hiện-> giá trị == giá trị), trở lại đúng sự thật. Vì vậy, bây giờ, chúng ta đang ở một nơi - chúng tôi không biết liệu chúng tôi muốn đi sang trái hoặc phải. Vì vậy, tùy tiện, chúng ta hãy đi lại. Tôi đã rõ ràng là chạy vào một vấn đề mà tôi đã hoàn toàn bị bỏ rơi tất cả mọi thứ - Tôi sẽ chỉ bao giờ kiểm tra phía bên trái của một cái cây. Tôi sẽ không bao giờ kiểm tra bất cứ điều gì mà là một đứa trẻ bên phải của bất cứ điều gì. Làm thế nào để sửa lỗi này? [Sinh viên] Bạn có theo dõi bên trái và bên phải trong một ngăn xếp. [Bowden] Yeah. Vì vậy, hãy làm cho nó cấu trúc danh sách, node * n, và sau đó nút ** tiếp theo? Tôi nghĩ rằng hoạt động tốt. Chúng tôi muốn đi qua bên trái, hoặc let's lên ở đây. Struct = danh sách danh sách, nó sẽ bắt đầu trong cấu trúc danh sách này. * List = NULL. Vì vậy, đó sẽ là danh sách liên kết của chúng tôi subtrees mà chúng ta đã bỏ qua. Chúng tôi sẽ đi qua còn lại bây giờ, nhưng kể từ khi chúng tôi chắc chắn cần phải quay trở lại bên phải, Chúng tôi sẽ tiếp tục ở bên phải trong danh sách cấu trúc của chúng tôi. Sau đó, chúng tôi sẽ có hoặc struct new_list, struct list * new_list = malloc (sizeof (danh sách)). Tôi sẽ bỏ qua lỗi kiểm tra, nhưng bạn nên kiểm tra để xem nếu nó là vô giá trị. New_list nút nó sẽ để trỏ đến - oh, đó là lý do tại sao tôi muốn nó lên đây. Nó sẽ để trỏ đến một danh sách cấu trúc thứ hai. Đó chỉ là cách các danh sách liên kết công việc. Điều này tương tự như là một danh sách liên kết int ngoại trừ chúng ta chỉ cần thay thế int * nút. Nó chính xác như nhau. Vì vậy, new_list, giá trị của nút new_list của chúng tôi, sẽ hiện ngay. Giá trị của chúng tôi new_list-> tiếp theo là có được danh sách ban đầu của chúng tôi, và sau đó chúng tôi sẽ cập nhật danh sách của chúng tôi để trỏ đến new_list. 

Bây giờ chúng tôi cần một số loại của cách điều kéo, như chúng ta đã đi qua bên trái toàn bộ cây con. Bây giờ chúng ta cần công cụ để kéo ra khỏi nó, như hiện null; chúng tôi không muốn chỉ cần trả về false. Chúng tôi muốn đến nay kéo bên ngoài danh sách mới của chúng tôi. Một cách thuận tiện để làm điều này, trên thực tế, có nhiều cách để làm điều này. Bất cứ ai cũng có một đề nghị? Tôi nên làm điều này hoặc làm thế nào tôi nên làm điều này? Chúng tôi chỉ có một vài phút, nhưng bất cứ đề nghị? Thay vì một cách, thay vì tình trạng của chúng tôi là trong khi đó, những gì chúng tôi hiện đang xem xét không phải là null, thay vào đó, chúng ta sẽ tiếp tục đi cho đến khi danh sách của chúng tôi chính nó là null. Vì vậy, nếu danh sách của chúng tôi kết thúc đang được null, sau đó chúng tôi đã chạy ra khỏi những điều để tìm, để tìm kiếm trên. Nhưng điều đó có nghĩa rằng điều đầu tiên trong danh sách của chúng tôi là chỉ cần đi sẽ làm nút đầu tiên. Điều đầu tiên sẽ được - chúng ta không còn cần phải thấy rằng. Vì vậy, danh sách> n sẽ là cây của chúng tôi. list-> tiếp theo sẽ được null. Và bây giờ, trong khi danh sách không phải là null bằng. Cur sẽ kéo một cái gì đó từ danh sách của chúng tôi. Vì vậy, hiện đang đi vào danh sách> bằng n. Và sau đó danh sách sẽ vào danh sách> bằng n, hoặc danh sách-> tiếp theo. Vì vậy, nếu hiện giá trị bằng giá trị. Bây giờ chúng ta có thể thêm cả con trỏ quyền của chúng ta và con trỏ trái của chúng tôi miễn là chúng tôi không phải là null. Xuống đây, tôi đoán chúng ta nên đã làm điều đó ở nơi đầu tiên. Nếu (hiện> bên phải = NULL!) sau đó chúng ta sẽ để chèn nút vào danh sách của chúng tôi. Nếu (hiện-> bên trái), đây là một chút công việc phụ, nhưng nó tốt. Nếu (hiện-> trái = NULL!) và chúng tôi sẽ để chèn phía bên trái vào danh sách liên kết của chúng tôi, và đó nên được nó. Chúng tôi lặp đi lặp lại - miễn là chúng ta có một cái gì đó trong danh sách của chúng tôi, chúng tôi có một nút khác để xem xét. Vì vậy, chúng ta nhìn vào nút đó, chúng ta tiến danh sách của chúng tôi đến tiếp theo. Nếu nút đó là giá trị mà chúng ta đang tìm kiếm, chúng tôi có thể trở lại đúng sự thật. Khác chèn cả hai chúng tôi subtrees trái và bên phải, miễn là họ không phải là null, vào danh sách của chúng tôi để chúng ta chắc đã đi qua chúng. Vì vậy, nếu họ không phải là vô giá trị, nếu con trỏ gốc của chúng tôi chỉ ra hai điều, sau đó lần đầu tiên chúng tôi kéo một cái gì đó ra khỏi danh sách của chúng tôi kết thúc đang được null. Và sau đó chúng tôi đặt hai điều trở lại, vì vậy bây giờ danh sách của chúng tôi là kích thước 2. Sau đó, chúng tôi đang đi để lặp trở lại và chúng tôi chỉ cần đi để kéo, hãy nói, con trỏ bên trái của nút gốc của chúng tôi. Và đó sẽ chỉ tiếp tục xảy ra, chúng ta sẽ kết thúc vòng lặp qua tất cả mọi thứ. 

Chú ý rằng điều này là phức tạp hơn đáng kể trong các giải pháp đệ quy. Và tôi đã nói nhiều lần rằng các giải pháp đệ quy thường có nhiều điểm chung với các giải pháp lặp. Ở đây là chính xác những gì các giải pháp đệ quy là làm. Sự thay đổi duy nhất là thay vì ngầm bằng cách sử dụng ngăn xếp, ngăn xếp chương trình, như cách của bạn theo dõi những nút bạn vẫn cần phải truy cập, bây giờ bạn phải sử dụng một cách rõ ràng một danh sách liên kết. Trong cả hai trường hợp bạn đang theo dõi những gì nút vẫn cần phải được truy cập. Trong trường hợp đệ quy nó chỉ dễ dàng hơn bởi vì một chồng được thực hiện cho bạn, như ngăn xếp chương trình. Chú ý rằng danh sách liên kết này, nó là một ngăn xếp. Bất cứ điều gì chúng ta chỉ cần đặt trên stack là ngay lập tức những gì chúng ta sẽ để kéo ra khỏi ngăn xếp đến thăm tiếp theo. Chúng tôi đang trên thời gian, nhưng bất kỳ câu hỏi nào? [Sinh viên, không thể hiểu] [Bowden] Yeah. Vì vậy, nếu chúng ta có danh sách liên kết của chúng tôi, hiện nay là để trỏ đến anh chàng này, và bây giờ chúng tôi chỉ tiến danh sách liên kết của chúng tôi tập trung vào anh chàng này. Chúng tôi đang đi qua trong danh sách liên kết trong dòng đó. Và sau đó tôi nghĩ chúng ta nên miễn phí danh sách liên kết của chúng tôi và các công cụ một lần trước khi quay trở lại đúng hay sai, chúng ta cần lặp trên danh sách liên kết của chúng tôi và luôn luôn xuống đây, tôi đoán, nếu chúng tôi hiện phải là không bằng, thêm nó, vì vậy bây giờ chúng tôi muốn giải phóng hiện bởi vì, tốt, chúng tôi đã hoàn toàn quên về danh sách? Yeah. Vì vậy, đó là những gì chúng tôi muốn làm ở đây. Trường hợp của con trỏ? Cur là sau đó - chúng tôi muốn đến một danh sách struct * 10 bằng danh sách tiếp theo. Danh sách miễn phí, danh sách = temp. Và trong trường hợp nơi mà chúng tôi trả lại sự thật, chúng ta cần để lặp hơn phần còn lại của danh sách liên kết của chúng tôi giải phóng những thứ. Những điều tốt đẹp về các giải pháp đệ quy được giải phóng những thứ chỉ có nghĩa là factorings popping ra khỏi ngăn xếp sẽ xảy ra cho bạn. Vì vậy, chúng tôi đã đi từ một cái gì đó giống như 3 dòng khó khăn để suy nghĩ về mã cái gì đó là đáng kể nhiều khó suy nghĩ về dòng mã. Bất kỳ câu hỏi? Được rồi. Chúng tôi đang tốt. Bye! [CS50.TV]