[Powered by Google Translate] [Phần 7] [Ít thoải mái] [Nate hardison] [Đại học Harvard] [Đây là CS50.] [CS50.TV] 

Chào mừng bạn đến với Mục 7. Nhờ bão Sandy, thay vì có một phần bình thường trong tuần này, chúng tôi đang làm điều này đi bộ qua, thông qua phần câu hỏi. Tôi sẽ đi theo cùng với Vấn Đề Đặt 6 Đặc điểm kỹ thuật, và đi qua tất cả các câu hỏi trong Một mục các câu hỏi phần. Nếu có bất kỳ câu hỏi nào, xin vui lòng gửi những ngày CS50 bàn. 

Được rồi. Hãy bắt đầu. Ngay bây giờ tôi đang tìm kiếm tại trang 3 của Problem Set Đặc điểm kỹ thuật. Chúng ta sẽ bắt đầu nói về cây nhị phân từ những người có rất nhiều liên quan để thiết lập vấn đề trong tuần này - Cây Huffman mã hóa. Một trong những cấu trúc dữ liệu đầu tiên chúng tôi nói chuyện về CS50 là các mảng. Hãy nhớ rằng một mảng là một chuỗi các phần tử - tất cả cùng loại - được lưu trữ ngay bên cạnh nhau trong bộ nhớ. Nếu tôi có một mảng số nguyên mà tôi có thể vẽ bằng cách sử dụng phong cách này hộp số số nguyên - Hãy nói rằng tôi có 5 trong hộp đầu tiên, tôi có 7 trong lần thứ hai, sau đó tôi có 8, 10, và 20 trong hộp cuối cùng. Hãy nhớ rằng, cả hai thực sự điều tốt về mảng này là chúng ta đã có thời gian truy cập thường xuyên để bất kỳ yếu tố cụ thể  trong mảng nếu chúng ta biết chỉ số của nó. Ví dụ, nếu tôi muốn lấy phần tử thứ ba trong mảng - chỉ số 2 bằng cách sử dụng hệ thống lập chỉ mục của chúng tôi không dựa trên - Tôi nghĩa là chỉ cần có để làm một phép tính toán học đơn giản, nhảy đến vị trí trong mảng, kéo ra 8 được lưu trữ ở đó, và tôi là tốt để đi. 

Một trong những điều xấu về mảng này mà chúng tôi nói chuyện về khi chúng ta thảo luận về danh sách liên kết - là nếu tôi muốn chèn một phần tử vào mảng này, Tôi sẽ phải làm một số thay đổi xung quanh. Ví dụ, mảng này ngay tại đây theo thứ tự sắp xếp được sắp xếp theo thứ tự tăng dần 5, sau đó 7, sau đó 8, sau đó 10, và 20 - nhưng nếu tôi muốn chèn số 9 vào mảng này, Tôi sẽ phải thay đổi một số trong những yếu tố để làm cho không gian. Chúng ta có thể rút ra điều này ở đây. Tôi sẽ phải di chuyển 5, 7, và sau đó là 8; tạo ra một khoảng cách nơi tôi có thể đặt 9, và sau đó là 10 và 20 có thể đi bên phải của 9. Đây là loại đau đớn bởi vì trong trường hợp xấu nhất - khi chúng tôi đang có để chèn hoặc ở đầu hoặc ở cuối của mảng, tùy thuộc vào cách chúng ta đang chuyển - chúng ta có thể kết thúc phải thay đổi tất cả các yếu tố chúng tôi hiện đang lưu trữ trong mảng. 

Vì vậy, khoảng cách này là những gì? Khoảng cách này là để đi đến phương pháp danh sách liên kết của chúng tôi, nơi thay vì lưu trữ các yếu tố 5, 7, 8, 10, và 20 tất cả các cạnh nhau trong bộ nhớ - những gì chúng ta thay vì đã được lưu trữ chúng loại ở bất cứ nơi nào chúng tôi muốn để lưu trữ chúng trong danh sách liên kết các nút này tôi rút ra ở đây, loại đặc biệt. Và sau đó chúng tôi kết nối chúng lại với nhau bằng cách sử dụng các con trỏ tiếp theo. Tôi có thể có một con trỏ từ 5 đến 7, một con trỏ từ 7 đến 8, một con trỏ từ 8 với 10, và cuối cùng, một con trỏ từ 10 đến 20, và sau đó một con trỏ null tại 20 chỉ ra rằng không có gì trái. Thương mại-off mà chúng ta có ở đây là bây giờ nếu chúng ta muốn chèn số 9 vào danh sách được sắp xếp của chúng tôi, tất cả chúng ta phải làm là tạo ra một nút mới với 9, dây nó lên để trỏ đến nơi thích hợp, và sau đó lại dây 8 chỉ với 9. Đó là khá nhanh, giả sử chúng ta biết chính xác nơi chúng ta muốn chèn 9. Tuy nhiên, thương mại-off trong trao đổi cho điều này là chúng ta đã mất thời gian truy cập thường xuyên bất kỳ yếu tố đặc biệt trong cấu trúc dữ liệu của chúng tôi. Ví dụ, nếu tôi muốn tìm các phần tử thứ tư trong danh sách liên kết này, Tôi sẽ phải bắt đầu vào lúc bắt đầu của danh sách và làm việc theo cách của mình thông qua tính node-by-nút cho đến khi tôi tìm thấy thứ tư. 

Để có được hiệu suất truy cập tốt hơn so với một danh sách liên kết - mà còn giữ lại một số những lợi ích mà chúng tôi đã có về thời gian chèn từ một danh sách liên kết - một cây nhị phân sẽ cần phải sử dụng bộ nhớ nhiều hơn một chút. Đặc biệt, thay vì chỉ có một con trỏ trong một nút cây nhị phân - như danh sách liên kết nút không - chúng ta sẽ thêm một con trỏ thứ hai để các nút cây nhị phân. Thay vì chỉ có một con trỏ trỏ tới phần tử tiếp theo, chúng ta sẽ có một con trỏ đến một con trái và một đứa trẻ phải. 

Chúng ta hãy vẽ một hình ảnh để xem những gì mà thực sự trông giống như. Một lần nữa, tôi sẽ sử dụng các hộp và mũi tên. Một nút cây nhị phân sẽ bắt đầu với một hộp đơn giản. Nó sẽ có một không gian cho các giá trị, và sau đó nó cũng sẽ có một không gian cho con trái và con phải. Tôi sẽ đánh giá chúng ở đây. Chúng tôi sẽ có con trái, và sau đó chúng ta sẽ có các con phải. Có nhiều cách khác nhau để làm điều này. Đôi khi cho không gian và tiện lợi, Tôi thực sự sẽ vẽ nó giống như tôi đang làm ở đây trên dưới cùng nơi tôi sẽ có giá trị ở đầu trang, và sau đó các con phải trên dưới cùng bên phải, và con trái phía dưới bên trái. Trở lại đầu trang sơ đồ này, chúng tôi có giá trị ở đầu, sau đó chúng tôi có con trỏ con trái, và sau đó chúng tôi có con trỏ bên phải con. 

Trong Vấn đề Set Đặc điểm kỹ thuật, chúng ta nói về vẽ một nút có giá trị 7, và sau đó một con trỏ con trái là null, và một con trỏ phải con là null. Chúng ta có thể viết NULL vốn trong không gian cả con trái và con phải, hoặc chúng tôi có thể vẽ các dấu gạch chéo chéo thông qua mỗi hộp để cho biết rằng đó là vô giá trị. Tôi sẽ làm điều đó chỉ vì đó là đơn giản. Những gì bạn thấy ở đây là hai cách biểu đồ cây nhị phân một nút rất đơn giản nơi chúng tôi có giá trị 7 và con trỏ con vô giá trị. 

Phần thứ hai của các cuộc đàm phán đặc điểm kỹ thuật của chúng tôi về việc làm thế nào với danh sách liên kết - nhớ rằng, chúng tôi chỉ có để giữ cho các yếu tố đầu tiên trong một danh sách nhớ toàn bộ danh sách - và tương tự, với một cây nhị phân, chúng tôi chỉ có để giữ cho một con trỏ cây để duy trì kiểm soát toàn bộ cấu trúc dữ liệu. Yếu tố đặc biệt của cây này được gọi là nút gốc của cây. Ví dụ, nếu một nút - nút này có chứa các giá trị 7 với con trỏ null trái và quyền trẻ em - là giá trị duy nhất trong cây của chúng tôi, thì đây sẽ là nút của chúng tôi gốc. Đó là sự khởi đầu của cây của chúng tôi. Chúng ta có thể thấy điều này một chút rõ ràng hơn khi chúng ta bắt đầu thêm các nút hơn cây của chúng tôi. Hãy để tôi kéo lên một trang mới. 

Bây giờ chúng ta sẽ vẽ một cây có 7 tại gốc, và 3 bên trong của con trái, và bên trong 9 của các con phải. Một lần nữa, điều này là khá đơn giản. Chúng tôi đã có 7, vẽ một nút cho 3, một nút cho 9, và tôi sẽ thiết lập con trỏ trái con của 7 để trỏ đến các nút có chứa 3, và con trỏ con phải của nút chứa 7 đến nút có chứa 9. Bây giờ, kể từ 3 và 9 không có bất kỳ trẻ em, chúng ta sẽ thiết lập tất cả các con trỏ của con em mình được null. Ở đây, các gốc cây của chúng tôi tương ứng với các nút có chứa số 7. Bạn có thể thấy rằng nếu tất cả chúng ta có là một con trỏ đến nút gốc đó, sau đó chúng tôi có thể đi bộ qua cây của chúng tôi và truy cập cả hai nút con - cả 3 và 9. Không cần để duy trì con trỏ cho mỗi nút duy nhất trên cây. Được rồi. Bây giờ chúng ta sẽ thêm một nút để sơ đồ này. Chúng ta sẽ thêm một nút chứa 6, và chúng ta sẽ thêm này như là các con phải của nút chứa 3. Để làm điều đó, tôi sẽ để xóa con trỏ null trong 3-nút và dây nó lên để trỏ đến các nút chứa 6. Được rồi. 

Tại thời điểm này, chúng ta hãy đi qua một chút thuật ngữ. Để bắt đầu, lý do rằng điều này được gọi là cây nhị phân đặc biệt là nó có hai con trỏ con. Có nhiều loại cây khác có con trỏ con hơn. Đặc biệt, bạn đã làm một 'thử' trong 5 Set vấn đề. Bạn sẽ nhận thấy rằng trong thử đó, bạn đã có 27 con trỏ khác nhau cho trẻ em khác nhau - một cho mỗi người trong số 26 chữ cái trong bảng chữ cái tiếng Anh, và sau đó là 27 dấu lược vậy, đó là tương tự như một loại cây. Nhưng ở đây, kể từ nhị phân của nó, chúng tôi chỉ có hai con trỏ con. 

Ngoài nút gốc này mà chúng ta đã nói, chúng tôi cũng đã được ném xung quanh thuật ngữ này 'đứa trẻ'. Cho một nút là một đứa con của một nút khác có nghĩa là gì? Nó theo nghĩa đen có nghĩa là một nút con là một đứa con của một nút khác nếu đó là nút khác có một con trỏ con của nó thiết lập để trỏ đến nút đó. Để đưa điều này vào điều kiện cụ thể hơn, nếu 3 được trỏ đến bởi một số các con trỏ con của 7, 3 là một đứa trẻ 7. Nếu chúng ta tìm ra những gì trẻ em của 7 tốt, chúng tôi thấy rằng 7 có một con trỏ đến 3 và một con trỏ đến 9, do đó, 9 và 3 là con cái của 7. Chín không có con vì con trỏ của nó đứa trẻ là vô giá trị, và 3 chỉ có một đứa con, 6. Sáu cũng không có con vì cả hai con trỏ của nó là null, mà chúng ta sẽ rút ra ngay bây giờ. 

Ngoài ra, chúng tôi cũng nói về cha mẹ của một nút cụ thể, và điều này là, như bạn mong muốn, ngược này mô tả con. Mỗi nút chỉ có một mẹ - thay vì hai như bạn mong đợi với con người. Ví dụ, phụ huynh của 3 là 7. Phụ huynh của 9 cũng là 7, và phụ huynh của 6 3. Không nhiều đến nó. Chúng tôi cũng có điều kiện để nói về ông bà nội, ông bà ngoại và cháu, và nói chung chúng ta nói về ông bà tổ tiên, và con cháu của một nút cụ thể. Tổ tiên của một nút hoặc tổ tiên, chứ không phải của một nút - là tất cả các nút nằm trên con đường từ gốc đến nút đó. Ví dụ, nếu tôi đang tìm kiếm tại nút 6, sau đó tổ tiên sẽ là 3 và 7. Tổ tiên của 9, ví dụ, nếu tôi đang tìm kiếm tại nút 9 - sau đó tổ tiên của 9 chỉ là 7. Và con cháu là chính xác ngược lại. Nếu tôi muốn nhìn vào tất cả các con cháu của 7, sau đó tôi phải nhìn vào tất cả các nút bên dưới nó. Vì vậy, tôi có 3, 9, và 6 tất cả như con cháu của 7. 

Thời hạn cuối cùng mà chúng ta sẽ nói về khái niệm này là một người anh em. Anh chị em ruột - loại theo các điều khoản trong gia đình - là các nút có cùng cấp trong cây. Vì vậy, 3 và 9 là anh chị em bởi vì họ có cùng cấp trong cây. Cả hai đều có cùng cha mẹ, 7. 6 không có anh chị em ruột vì 9 không có con cái. Và 7 không có anh chị em nào bởi vì đó là gốc rễ của cây của chúng tôi, và có duy nhất 1 root. Đối với 7 có anh chị em có phải là một nút trên 7. Sẽ có thể là cha mẹ của 7, trong đó Trường hợp 7 sẽ không còn là gốc rễ của cây. Sau đó, phụ huynh mới 7 cũng sẽ phải có một đứa con, và rằng con sau đó sẽ là anh, chị, em ruột của 7. 

Được rồi. Di chuyển trên. Khi chúng tôi bắt đầu cuộc thảo luận của chúng ta về cây nhị phân, chúng tôi nói chuyện về làm thế nào chúng ta sẽ sử dụng chúng để đạt được một lợi thế hơn cả hai mảng và danh sách liên kết. Và cách chúng tôi sẽ làm điều đó với khách sạn đặt hàng. Chúng ta nói rằng một cây nhị phân là ra lệnh, theo các đặc điểm kỹ thuật, nếu cho mỗi nút trong cây của chúng tôi, tất cả các hậu duệ của nó ở bên trái - con trái và tất cả các con cháu của con trái - có giá trị thấp hơn, và tất cả các nút trên bên phải - các con phải và tất cả các con cháu của các con phải - có các nút lớn hơn giá trị của nút hiện tại mà chúng tôi đang tìm kiếm. Chỉ cần cho đơn giản, chúng ta sẽ giả định rằng không có bất kỳ các nút trùng lặp trong cây của chúng tôi. Ví dụ, trong cây này chúng tôi sẽ không để đối phó với các trường hợp nơi chúng tôi có giá trị 7 ở gốc  và sau đó chúng tôi cũng có giá trị 7 ở những nơi khác trong cây. Trong trường hợp này, bạn sẽ nhận thấy rằng cây này thực sự là ra lệnh. Chúng tôi có giá trị 7 rễ cây. Tất cả mọi thứ để bên trái của 7 - nếu tôi lùi lại tất cả các nhãn hiệu nhỏ ở đây - tất cả mọi thứ để bên trái của 7 - 3 và 6 - những giá trị được cả hai ít hơn 7, và tất cả mọi thứ bên phải - mà chỉ là nay 9 - là lớn hơn 7. 

Đây không phải là cái cây chỉ đặt hàng có chứa các giá trị, nhưng chúng ta hãy vẽ một vài trong số họ. Có thật sự là một bó toàn bộ cách chúng tôi có thể làm điều này. Tôi sẽ sử dụng một cách viết tắt chỉ để giữ cho mọi thứ đơn giản, nơi chứ không phải vẽ ra toàn bộ hộp và mũi tên - Tôi chỉ cần đi để vẽ các con số và thêm vào mũi tên kết nối chúng. Để bắt đầu, chúng tôi sẽ chỉ viết gốc cây của chúng tôi một lần nữa, nơi chúng tôi đã có 7, và sau đó một 3, và sau đó 3 chỉ ở bên phải với 6, và 7 có một đứa con bên phải là 9. Được rồi. Một cách khác mà chúng ta có thể viết cây này là gì? Thay vì phải 3 là con trái của 7, chúng ta cũng có thể có 6 là con trái của 7 và sau đó 3 là con trái của 6. Điều đó sẽ trông giống như cây này ở đây, nơi tôi đã có 7, sau đó 6, sau đó 3, và 9 bên phải. Chúng tôi cũng không cần phải có 7 là nút gốc của chúng tôi. Chúng tôi cũng có thể có 6 nút gốc của chúng tôi. Những gì mà sẽ trông như thế nào? Nếu chúng ta sẽ phải duy trì tài sản ra lệnh, tất cả mọi thứ để bên trái của 6 có thể ít hơn. Có người chỉ có một khả năng, và đó là 3. Nhưng sau đó là các con phải của 6, chúng tôi có hai khả năng. Đầu tiên, chúng ta có thể có số 7 và sau đó 9, hoặc chúng ta có thể rút ra nó giống như tôi về để làm ở đây - nơi chúng tôi có 9 như các con phải của 6, và sau đó 7 là con trái của 9. 

Bây giờ, 7 và 6 không phải là giá trị chỉ có thể cho người chủ. Chúng tôi cũng có thể có 3 gốc. Điều gì sẽ xảy ra nếu 3 là ở gốc? Ở đây, những thứ có được một chút thú vị. Ba không có bất kỳ giá trị ít hơn, sao cho toàn bộ bên trái của cây là chỉ cần đi được null. Không có được bất cứ điều gì ở đó. Bên phải, chúng ta có thể liệt kê những thứ theo thứ tự tăng dần. Chúng tôi có thể có 3, sau đó 6, sau đó 7, sau đó 9. Hoặc, chúng ta có thể làm 3, sau đó 6, sau đó 9, sau đó 7. Hoặc, chúng ta có thể làm 3, sau đó 7, sau đó 6, sau đó 9. Hoặc, 3, 7 - thực sự không có, chúng tôi không thể làm một 7 nữa. Đó là một điều chúng tôi có. Chúng ta có thể làm 9, và sau đó từ 9, chúng tôi có thể làm 6 và sau đó 7. Hoặc, chúng ta có thể làm 3, sau đó 9, sau đó 7, và sau đó 6. 

Một trong những điều thu hút sự chú ý của bạn ở đây là rằng những cây có một chút lạ nhìn. Đặc biệt, nếu chúng ta nhìn vào 4 cây ở bên phải - Tôi sẽ vòng tròn, ở đây - những cây này trông gần như chính xác giống như một danh sách liên kết. Mỗi nút chỉ có một con, và vì vậy chúng tôi không có bất kỳ cấu trúc này giống như cây mà chúng ta thấy, ví dụ,  trong cây duy nhất ở đây trên dưới cùng bên trái. Những cây này đang thực sự được gọi là thoái hóa cây nhị phân, và chúng ta sẽ nói về những nhiều hơn trong tương lai - đặc biệt là nếu bạn đi vào để có các khóa học khoa học máy tính khác. Những cây này thoái hóa. Chúng không phải là rất hữu ích bởi vì, thực tế, cấu trúc này vay chính nó  để tra cứu thời gian tương tự như của một danh sách liên kết. Chúng tôi không nhận được để tận dụng lợi thế của bộ nhớ thêm con trỏ này thêm vì cấu trúc của chúng tôi là theo cách này. Thay vì đi vào và rút ra cây nhị phân có 9 ở gốc, đó là trường hợp cuối cùng mà chúng ta sẽ có, Thay vào đó, chúng tôi, vào thời điểm này, sẽ nói một chút về thuật ngữ này khác mà chúng tôi sử dụng khi nói về cây, được gọi là chiều cao. 

Chiều cao của cây là khoảng cách từ gốc đến nút xa nhất, hay đúng hơn là số lượng hoa bia mà bạn sẽ phải thực hiện để bắt đầu từ gốc và sau đó kết thúc tại nút xa nhất trong cây. Nếu chúng ta nhìn tại một số các cây mà chúng tôi đã rút ra ngay tại đây, chúng ta có thể thấy rằng nếu chúng ta lấy cây này ở góc trên bên trái và chúng tôi bắt đầu tại 3, thì chúng ta phải làm cho 1 hop để có được với 6, hop thứ hai để có được đến 7, và một bước nhảy thứ ba để có được có tới 9. Vì vậy, chiều cao của cây này là 3. Chúng tôi có thể làm các bài tập tương tự cho các cây nêu với màu xanh lá cây này, và chúng ta thấy rằng chiều cao của tất cả những cây này cũng là thực sự 3. Đó là một phần của những gì làm cho họ thoái hóa - chiều cao của họ chỉ là một trong ít hơn số lượng các nút trong cây. Nếu chúng ta nhìn vào cây này khác bao vây với màu đỏ, mặt khác, chúng ta thấy rằng các nút lá xa nhất là 6 và 9 - lá là những nút không có con. Vì vậy, để có được từ nút gốc hoặc 6 hoặc 9, chúng ta phải làm một hop để có được đến 7 và sau đó hop một lần thứ hai để có được có tới 9, và tương tự, chỉ có một bước nhảy thứ hai từ 7 với 6. Vì vậy, chiều cao của cây này ở đây là chỉ có 2. Bạn có thể quay trở lại và làm điều đó cho tất cả các loại cây khác mà chúng tôi đã thảo luận bắt đầu với 7 và 6, và bạn sẽ thấy rằng chiều cao của tất cả những cây này cũng có 2. 

Lý do chúng tôi đã nói về ra lệnh cho cây nhị phân và lý do tại sao họ đang mát mẻ là bởi vì bạn có thể tìm kiếm thông qua chúng trong 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. Đây là nơi mà chúng ta nói về nhận được rằng thời gian tra cứu cải tiến trên danh sách liên kết đơn giản. Với một danh sách liên kết - nếu bạn muốn tìm thấy một yếu tố cụ thể - bạn đang ở tốt nhất sẽ làm một số loại tìm kiếm tuyến tính nơi bạn bắt đầu vào lúc bắt đầu của một danh sách và một-by-hop một nút bằng một nút - thông qua toàn bộ danh sách cho đến khi bạn tìm thấy bất cứ điều gì bạn đang tìm kiếm. Trong khi đó, nếu bạn có một cây nhị phân được lưu trữ trong định dạng tốt đẹp này, bạn thực sự có thể nhận được nhiều hơn một tìm kiếm nhị phân nơi bạn chia và chinh phục và tìm kiếm thông qua một nửa thích hợp của cây ở mỗi bước. Chúng ta hãy xem làm thế nào mà. 

Nếu chúng ta có - một lần nữa, sẽ trở lại cây ban đầu của chúng tôi - chúng tôi bắt đầu vào lúc 7, chúng tôi có 3 bên trái, 9 bên phải, và dưới 3 thì chúng tôi có 6. Nếu chúng ta muốn tìm kiếm số 6 trong cây này, chúng tôi muốn bắt đầu ở gốc. Chúng tôi sẽ so sánh các giá trị mà chúng ta đang tìm kiếm, nói 6, với giá trị được lưu trữ trong các nút mà chúng ta đang nhìn vào, 7, thấy rằng 6 thực sự là ít hơn 7, vì vậy chúng tôi muốn di chuyển sang bên trái. Nếu giá trị của 6 đã lớn hơn 7, chúng tôi sẽ thay vì di chuyển về bên phải. Vì chúng ta biết rằng do cấu trúc của cây nhị phân ra lệnh cho chúng tôi - tất cả các giá trị nhỏ hơn 7 được sẽ được lưu trữ bên trái của 7 không cần phải bận tâm tìm kiếm thông qua phía bên phải của cây. Một khi chúng tôi di chuyển sang bên trái và chúng tôi tại các nút có chứa 3, chúng ta có thể làm điều đó so sánh cùng một lần nữa chúng ta so sánh 3 và 6. Và chúng ta thấy rằng trong khi 6 - giá trị mà chúng ta đang tìm kiếm - lớn hơn 3, chúng ta có thể đi về phía bên phải của nút chứa 3. Không có bên trái ở đây, vì vậy chúng ta có thể bỏ qua mà. Nhưng chúng tôi chỉ biết rằng bởi vì chúng tôi đang tìm kiếm bản thân cây, và chúng tôi có thể thấy rằng cây không có con. 

Nó cũng khá dễ dàng để tìm kiếm 6 trong cây này nếu chúng ta đang làm việc đó mình như con người, nhưng chúng ta hãy theo dõi quá trình này máy móc như một máy tính sẽ làm gì để thực sự hiểu các thuật toán. Tại thời điểm này, chúng tôi hiện đang tìm kiếm tại một nút có 6, và chúng tôi đang tìm kiếm giá trị 6, như vậy, quả thật vậy, chúng tôi đã tìm thấy các nút thích hợp. Chúng tôi đã tìm thấy giá trị 6 cây của chúng tôi, và chúng tôi có thể ngừng tìm kiếm của chúng tôi. Tại thời điểm này, tùy thuộc vào những gì đang xảy ra, chúng ta có thể nói, có, chúng tôi đã tìm thấy giá trị 6, nó tồn tại trong cây của chúng tôi. Hoặc, nếu chúng tôi đang lập kế hoạch để chèn một nút hoặc làm điều gì đó, chúng ta có thể làm điều đó vào thời điểm này. 

Hãy làm tra cứu một vài chi tiết chỉ để xem cách làm việc này. Chúng ta hãy nhìn vào những gì sẽ xảy ra nếu chúng ta cố gắng và tìm kiếm các giá trị 10. Nếu chúng ta để tìm kiếm giá trị 10, chúng ta sẽ bắt đầu từ gốc. Chúng tôi thấy rằng 10 là lớn hơn 7, vì vậy chúng tôi muốn di chuyển sang phải. Chúng tôi nhận được có tới 9 và so sánh 9 với 10 và thấy rằng 9 thực sự là ít hơn 10. Vì vậy, một lần nữa, chúng tôi sẽ cố gắng để di chuyển sang bên phải. Tuy nhiên, vào thời điểm này, chúng tôi nhận thấy rằng chúng ta đang ở một nút null. Không có gì ở đó. Không có gì nơi 10 nên. Đây là nơi mà chúng tôi có thể báo cáo thất bại - có thực sự là không 10 trong cây. Và cuối cùng, chúng ta hãy đi qua các trường hợp, nơi chúng tôi đang cố gắng để tìm kiếm 1 trong cây. Điều này tương tự như những gì sẽ xảy ra nếu chúng ta nhìn lên 10, ngoại trừ thay vì đi bên phải, chúng ta sẽ đi bên trái. Chúng tôi bắt đầu tại 7 và thấy rằng 1 là ít hơn 7, do đó, chúng tôi di chuyển sang bên trái. Chúng tôi nhận được cho 3 và thấy rằng 1 là ít hơn 3, vì vậy một lần nữa, chúng tôi cố gắng để di chuyển sang bên trái. Tại thời điểm này chúng tôi có một nút null, vì vậy một lần nữa chúng tôi có thể báo cáo thất bại. 

Nếu bạn muốn tìm hiểu thêm về cây nhị phân, có một bó toàn bộ các vấn đề thú vị mà bạn có thể làm gì với chúng. Tôi đề nghị thực hành vẽ các sơ đồ này một-by- và thông qua tất cả các bước khác nhau sau đây, vì điều này sẽ đến trong siêu tiện dụng không chỉ khi bạn đang thực hiện bộ vấn đề mã hóa Huffman mà còn trong các khóa học trong tương lai - chỉ học tập làm thế nào để rút ra những cấu trúc dữ liệu và suy nghĩ thông qua các vấn đề với bút và giấy hoặc, trong trường hợp này iPad, và bút stylus. 

Tại thời điểm này mặc dù, chúng ta sẽ chuyển sang làm một số thực hành mã hóa và thực sự chơi với những cây nhị phân và xem. Tôi sẽ chuyển về cho máy tính của tôi. Đối với phần này của phần, thay vì sử dụng CS50 Run hoặc CS50 Spaces, Tôi sẽ sử dụng thiết bị. 

Sau đây cùng với các đặc điểm kỹ thuật Set vấn đề, Tôi thấy rằng tôi là nghĩa vụ phải mở các thiết bị, đi vào thư mục Dropbox của tôi, tạo ra một thư mục có tên là Mục 7, và sau đó tạo ra một tập tin gọi binary_tree.c. Ở đây chúng tôi đi. Tôi đã có thiết bị đã được mở. Tôi sẽ kéo lên một thiết bị đầu cuối. Tôi sẽ đi vào thư mục Dropbox, làm cho một thư mục gọi là section7, và thấy nó hoàn toàn trống rỗng. Bây giờ tôi sẽ để mở ra binary_tree.c. Được rồi. Ở đây chúng tôi đi - tập tin rỗng. 

Hãy để quay trở lại với các đặc điểm kỹ thuật. Đặc điểm kỹ thuật yêu cầu để tạo ra 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 - giống như các giá trị mà chúng ta rút ra trong biểu đồ của chúng tôi trước khi. Chúng ta sẽ sử dụng boilerplate này typedef mà chúng tôi đã thực hiện ngay tại đây mà bạn nên nhận ra từ 5 Set Vấn đề - nếu bạn đã làm theo cách bảng băm của chương trình chinh phục speller. Bạn cũng nên nhận ra nó từ phần cuối cùng của tuần nơi mà chúng tôi nói chuyện về danh sách liên kết. Chúng tôi đã có này typedef của một nút struct, và chúng tôi đã cho nút này struct tên của nút struct trước để chúng ta có thể đề cập đến nó kể từ khi chúng tôi sẽ muốn có con trỏ nút struct như là một phần của cấu trúc của chúng tôi, nhưng sau đó chúng tôi đã bị bao vây này - hay đúng hơn, kèm theo này - trong một typedef do đó, sau này trong mã, chúng ta có thể tham khảo cấu trúc này như là một nút thay vì một nút struct. 

Điều này là có được rất giống với định nghĩa danh sách liên kết đơn lẻ mà chúng ta nhìn thấy tuần trước. Để làm điều này, chúng ta hãy bắt đầu bằng cách viết ra các boilerplate. Chúng ta biết rằng chúng ta phải có một giá trị số nguyên, do đó, chúng tôi sẽ đưa vào giá trị int, và sau đó thay vì chỉ là một con trỏ trỏ tới phần tử tiếp theo - như chúng ta đã làm với các danh sách liên kết đơn lẻ - chúng ta sẽ có con trỏ con trái và bên phải. Đó là khá đơn giản quá - struct nút con bên trái; và struct node * quyền trẻ em; Cool. Điều đó có vẻ như một sự khởi đầu khá tốt. Hãy để quay trở lại với các đặc điểm kỹ thuật. 

Bây giờ chúng ta cần phải khai báo một biến node * toàn cầu cho gốc rễ của một cái cây. Chúng ta sẽ làm cho toàn cầu giống như chúng ta đã thực hiện con trỏ đầu tiên trong danh sách liên kết của chúng tôi cũng toàn cầu. Điều này là để các chức năng mà chúng tôi viết chúng tôi không cần phải đi qua xung quanh gốc này - mặc dù chúng ta sẽ thấy rằng nếu bạn muốn để viết các chức năng đệ quy, nó có thể là tốt hơn để không vượt qua nó xung quanh như một toàn cầu ở nơi đầu tiên và thay vào đó khởi tạo nó tại địa phương trong chức năng chính của bạn. Tuy nhiên, chúng tôi sẽ làm nó trên toàn cầu để bắt đầu. Một lần nữa, chúng tôi sẽ cung cấp cho một vài không gian, và tôi sẽ tuyên bố một gốc * nút. Chỉ để chắc chắn rằng tôi không để lại điều này chưa được khởi tạo, tôi sẽ để thiết lập nó bằng giá trị null. Bây giờ, trong các chức năng chính - mà chúng ta sẽ viết thực sự nhanh chóng ngay tại đây - int main (int argc, char * argv []) - và tôi sẽ bắt đầu khai báo mảng argv của tôi như là const chỉ vì vậy mà tôi biết những đối số lập luận rằng tôi có lẽ không muốn thay đổi. Nếu tôi muốn thay đổi chúng tôi có lẽ nên được bản sao của chúng. Bạn sẽ thấy điều này rất nhiều trong mã. Đó là một trong hai cách. Đó là tốt để nó như bỏ qua const nếu bạn muốn. Tôi thường đặt nó trong chỉ để cho tôi nhắc nhở bản thân mình  rằng tôi có lẽ không muốn để chỉnh sửa những đối số. 

Như mọi khi, tôi sẽ bao gồm dòng return 0 ở cuối chính. Ở đây, tôi sẽ khởi tạo nút gốc của tôi. Vì nó đứng ngay bây giờ, tôi đã có một con trỏ được thiết lập để null, do đó, nó chỉ ở không có gì. Để thực sự bắt đầu xây dựng các nút, Lần đầu tiên tôi cần phải cấp phát bộ nhớ cho nó. Tôi sẽ làm điều đó bằng cách làm cho bộ nhớ trên heap sử dụng malloc. Tôi sẽ thiết lập gốc bằng kết quả của malloc, và tôi sẽ sử dụng toán tử sizeof để tính toán kích thước của một nút. Lý do mà tôi sử dụng sizeof nút như trái ngược với, nói, làm một cái gì đó như thế này - malloc (4 + 4 +4) hay malloc 12 - là vì tôi muốn mã của tôi để được như tương thích càng tốt. Tôi muốn để có thể lấy file này c, biên dịch nó trên thiết bị, và sau đó biên dịch nó trên 64-bit máy Mac của tôi - hoặc trên một kiến ​​trúc hoàn toàn khác nhau - và tôi muốn tất cả điều này làm việc như nhau. 

Nếu tôi là làm cho các giả định về kích thước của các biến kích thước của một int hoặc kích thước của một con trỏ - sau đó tôi cũng làm cho các giả định về các loại kiến ​​trúc mã của tôi có thể biên dịch thành công khi chạy. Luôn luôn sử dụng sizeof như trái ngược với tự tổng hợp các lĩnh vực struct. Một lý do khác là có cũng có thể là đệm mà trình biên dịch đặt vào cấu trúc. Thậm chí chỉ cần tổng hợp các lĩnh vực cá nhân không phải là một cái gì đó mà bạn thường muốn làm, như vậy, xóa dòng đó. Bây giờ, để thực sự khởi tạo nút gốc này, Tôi sẽ phải cắm vào giá trị cho mỗi lĩnh vực khác nhau của nó. Ví dụ, giá trị tôi biết tôi muốn khởi tạo đến 7, và bây giờ tôi sẽ đặt con trái được null và các con phải cũng được null. Great! Chúng tôi đã làm điều đó một phần của spec. 

Các đặc điểm kỹ thuật xuống ở dưới cùng của trang 3 yêu cầu tôi để tạo ra thêm ba nút - có chứa 3, chứa 6, và một với 9 - và sau đó dây chúng vì vậy nó trông giống hệt như sơ đồ cây của chúng tôi rằng chúng tôi đã nói về trước đó. Hãy làm điều đó khá nhanh chóng. Bạn sẽ thấy thực sự nhanh chóng rằng tôi sẽ để bắt đầu viết một loạt các mã trùng lặp. Tôi sẽ tạo ra một nút * và tôi sẽ gọi nó ba. Tôi sẽ thiết lập nó bằng malloc (sizeof (node)). Tôi sẽ thiết lập ba-> giá trị = 3. Ba -> left_child = NULL; ba> phải _child = NULL; là tốt. Điều đó có vẻ khá tương tự như khởi tạo thư mục gốc, và đó là chính xác những gì Tôi sẽ phải làm gì nếu tôi bắt đầu khởi tạo là 6 và 9 cũng. Tôi sẽ làm điều đó thực sự nhanh chóng ở đây - trên thực tế, tôi sẽ làm việc sao chép và dán ít, và làm cho chắc chắn rằng I - ổn.  Bây giờ, tôi đã nhận nó sao chép và tôi có thể đi trước và thiết lập này bằng 6. Bạn có thể thấy rằng điều này mất một thời gian và không phải là siêu hiệu quả. Trong một chút ít, chúng tôi sẽ viết một chức năng mà sẽ làm điều này cho chúng tôi. Tôi muốn thay thế này với một 9, thay thế với một 6. 

Bây giờ chúng ta đã có tất cả các nút của chúng tôi được tạo ra và khởi tạo. Chúng tôi đã có gốc rễ của chúng tôi thiết lập bằng 7, hoặc có chứa các giá trị 7, nút của chúng tôi có 3 nút của chúng tôi chứa 6, và nút của chúng tôi có chứa 9. Tại thời điểm này, tất cả chúng ta phải làm là dây điện tất cả mọi thứ. Lý do tôi khởi tạo tất cả các con trỏ để null là chỉ để cho tôi đảm bảo rằng Tôi không có bất kỳ con trỏ uninitialized trong đó do tai nạn. Và cũng kể từ thời điểm này, tôi chỉ có thực sự kết nối các nút với nhau - những người mà họ đang thực sự kết nối với - Tôi không phải đi qua và làm cho chắc chắn rằng tất cả các giá trị tương ứng là ở các vị trí thích hợp. 

Bắt đầu từ gốc rễ, tôi biết rằng con trái của gốc là 3. Tôi biết rằng con phải của gốc là 9. Sau đó, chỉ có một đứa trẻ mà tôi đã để lại phải lo lắng về là con bên phải 3, là 6. Tại thời điểm này, tất cả trông khá tốt. Chúng tôi sẽ xóa một số của những dòng này. Bây giờ tất cả mọi thứ có vẻ khá tốt. Hãy quay trở lại đặc điểm kỹ thuật của chúng tôi và xem những gì chúng ta phải làm gì tiếp theo. 

Tại thời điểm này, chúng ta phải viết một chức năng được gọi là 'chứa' với một nguyên mẫu của 'chứa bool (int giá trị). Và điều này có chức năng là để trở về đúng  nếu cây được trỏ đến bởi biến gốc toàn cầu của chúng tôi  chứa giá trị được thông qua vào các chức năng và sai khác. Hãy cho đi trước và làm điều đó. Điều này là có được chính xác như tra cứu mà chúng tôi đã làm bằng tay trên iPad chỉ là một chút trước. Hãy thu nhỏ lại một chút và di chuyển lên. Chúng ta sẽ đặt chức năng này ngay trên chức năng chính của chúng tôi do đó chúng tôi không phải làm bất kỳ loại công nghệ tạo mẫu. Vì vậy, bool chứa (int giá trị). Hiện chúng tôi đi. Có khai báo boilerplate của chúng tôi. Chỉ để chắc chắn rằng điều này sẽ biên dịch, Tôi sẽ đi trước và chỉ cần đặt nó bằng trả về false. Hiện tại chức năng này sẽ không làm bất cứ điều gì và luôn luôn báo cáo rằng giá trị mà chúng tôi đang tìm kiếm không phải là trong cây. 

Tại thời điểm này, nó có thể là một ý tưởng tốt - kể từ khi chúng tôi đã viết một bó toàn bộ các mã và chúng tôi thậm chí đã cố gắng thử nghiệm nó chưa - để đảm bảo rằng tất cả các biên dịch. Có một vài điều mà chúng ta phải làm gì để đảm bảo rằng điều này sẽ thực sự biên dịch. Trước tiên, hãy xem nếu chúng ta đã sử dụng bất kỳ chức năng trong bất kỳ thư viện mà chúng tôi đã chưa có. Các chức năng chúng tôi đã sử dụng cho đến nay là malloc, và sau đó chúng tôi cũng đã được sử dụng loại - loại không tiêu chuẩn được gọi là 'bool' - được bao gồm trong các tập tin tiêu đề chuẩn bool. Chúng tôi chắc chắn muốn bao gồm bool.h tiêu chuẩn cho các loại bool, và chúng tôi cũng muốn # bao gồm lib.h tiêu chuẩn cho các thư viện tiêu chuẩn bao gồm malloc, và miễn phí, và tất cả những điều đó. Vì vậy, thu nhỏ, chúng ta sẽ bỏ thuốc lá. Hãy thử và làm cho chắc chắn rằng điều này thực sự đã làm biên dịch. Chúng tôi thấy rằng nó không có gì, vì vậy chúng tôi đang đi đúng hướng. 

Hãy để mở binary_tree.c một lần nữa. Nó biên dịch. Chúng ta hãy đi xuống và làm cho chắc chắn rằng chúng ta chèn thêm một số cuộc gọi đến chức năng Chứa của chúng tôi - chỉ để chắc chắn rằng đó là tất cả tốt và tốt. Ví dụ, khi chúng tôi đã làm một số tra cứu trong cây của chúng tôi trước đó, chúng tôi đã cố gắng để tìm kiếm 6 giá trị, 10, và 1, và chúng tôi biết rằng 6 trong cây, 10 là không trong cây, và 1 lần trong cây. Hãy sử dụng những cuộc gọi mẫu như một cách để tìm ra hay không chức năng Chứa của chúng tôi đang làm việc. Để làm điều đó, tôi sẽ sử dụng chức năng printf, và chúng tôi sẽ để in ra các kết quả của các cuộc gọi đến có chứa. Tôi sẽ đặt trong một chuỗi chứa (% d) = vì  chúng ta sẽ cắm vào giá trị mà chúng tôi đang đi tìm, =% s \ n "và sử dụng như là một chuỗi định dạng của chúng tôi. Chúng tôi chỉ cần đi để thấy - theo nghĩa đen in ra trên màn hình - những gì trông giống như một cuộc gọi chức năng. Điều này là không thực sự các cuộc gọi chức năng.  Đây chỉ là một chuỗi được thiết kế để trông giống như một cuộc gọi chức năng. 

Bây giờ, chúng ta sẽ cắm vào các giá trị. Chúng tôi sẽ cố gắng chứa ngày 6, và sau đó những gì chúng tôi đang làm ở đây là sử dụng mà nhà điều hành ternary. Hãy xem - có 6 - vì vậy, bây giờ tôi đã có 6 và nếu có 6 là sự thật, chuỗi đó chúng ta sẽ gửi ký tự định dạng% s là có được chuỗi "true". Hãy di chuyển trên một chút. Nếu không, chúng tôi muốn gửi chuỗi "false" nếu nó bao gồm 6 trả về false. Đây là một chút ngu ngốc nhìn, nhưng tôi con số tôi cũng có thể minh họa nhà điều hành ternary vẻ như kể từ khi chúng tôi đã không nhìn thấy nó cho một lúc. Đây sẽ là một, đẹp, tiện dụng cách nào để tìm ra nếu chức năng Chứa của chúng tôi đang làm việc. Tôi sẽ di chuyển trở lại bên trái, và tôi sẽ để sao chép và dán dòng này một vài lần. Nó đã thay đổi một số các giá trị xung quanh, vì vậy đây là có được 1, và điều này sẽ là 10. 

Tại thời điểm này chúng tôi đã có một chức năng Chứa tốt đẹp. Chúng tôi đã có một số bài kiểm tra, và chúng tôi sẽ xem nếu điều này tất cả các công trình. Tại thời điểm này, chúng tôi đã viết một số mã hơn. Thời gian bỏ ra và đảm bảo rằng tất cả mọi thứ vẫn biên dịch. Bỏ ra, và bây giờ chúng ta hãy cố gắng làm cho cây nhị phân một lần nữa. Vâng, có vẻ như chúng tôi đã có một lỗi, và chúng tôi đã bị này một cách rõ ràng tuyên bố chức năng thư viện printf. Có vẻ như chúng ta cần đi vào và # bao gồm standardio.h. Và với điều đó, tất cả mọi thứ cần biên dịch. Chúng tôi tất cả đều tốt. Bây giờ chúng ta hãy thử chạy cây nhị phân và xem những gì sẽ xảy ra. Ở đây chúng ta, / binary_tree, và chúng ta thấy rằng, như chúng ta mong đợi - bởi vì chúng tôi đã không thực hiện có được nêu ra, hay đúng hơn, chúng tôi đã chỉ cần đặt lại sai chúng tôi thấy rằng nó chỉ trở về sai cho tất cả chúng, do đó tất cả đều làm việc cho hầu hết các phần khá tốt. 

Chúng ta hãy trở lại và thực sự thực hiện có vào thời điểm này. Tôi sẽ di chuyển xuống, phóng to, và - hãy nhớ rằng, các thuật toán mà chúng tôi sử dụng là chúng tôi bắt đầu tại nút gốc và sau đó tại mỗi nút mà chúng ta gặp phải, chúng tôi làm một so sánh, và trên cơ sở đó so sánh chúng tôi di chuyển con trái hoặc các con phải. Điều này sẽ trông rất giống với mã tìm kiếm nhị phân mà chúng tôi đã viết trước đó trong thời gian. Khi chúng tôi bắt đầu, chúng tôi biết rằng chúng tôi muốn để giữ cho các nút hiện tại mà chúng tôi đang tìm kiếm, và các nút hiện tại sẽ được khởi tạo nút gốc. Và bây giờ, chúng ta sẽ tiếp tục đi qua cây, và nhớ rằng điều kiện của chúng tôi dừng lại -  khi chúng tôi thực sự làm việc thông qua các ví dụ bằng tay - là khi chúng tôi gặp phải một nút null, không phải khi chúng ta nhìn một đứa trẻ null, mà là khi chúng ta thực sự di chuyển với một nút trong cây và thấy rằng chúng ta đang ở một nút null. Chúng ta sẽ lặp đi lặp lại cho đến khi hiện không bằng vô giá trị. Và chúng tôi sẽ làm gì? Chúng tôi sẽ kiểm tra nếu (hiện -> giá trị == giá trị), sau đó chúng tôi biết rằng chúng tôi đã thực sự tìm thấy các nút mà chúng tôi đang tìm kiếm. Vì vậy, ở đây, chúng ta có thể trở lại đúng sự thật. Nếu không, chúng tôi muốn thấy có hoặc không có giá trị nhỏ hơn giá trị. 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, chúng ta sẽ di chuyển sang phải. Vì vậy, hiện = hiện -> right_child; và nếu không, chúng ta sẽ di chuyển sang bên trái. hiện = hiện -> left_child; Khá đơn giản. 

Bạn có thể nhận ra những vòng lặp đó trông rất giống với điều này từ tìm kiếm nhị phân trước đó trong thời hạn, trừ trường hợp sau đó chúng tôi đã được giao dịch thấp, giữa, và cao. Ở đây, chúng tôi chỉ cần có để nhìn vào một giá trị hiện tại, vì vậy nó là tốt đẹp và đơn giản. Hãy chắc chắn rằng mã này đang làm việc. Trước tiên, hãy chắc chắn rằng nó biên dịch. Hình như nó. Chúng ta hãy thử chạy nó. Và quả thực, nó in ra tất cả mọi thứ mà chúng ta mong đợi. Nó tìm thấy 6 trong cây, không tìm thấy 10 bởi vì 10 không có trong cây, và không tìm thấy 1 hoặc vì 1 cũng không phải trong cây. Mát công cụ. 

Được rồi. Hãy quay trở lại đặc điểm kỹ thuật của chúng tôi và xem những gì tiếp theo. Bây giờ, nó muốn để thêm các nút thêm một số cây của chúng tôi. Nó muốn để thêm 5, 2, và 8, và làm cho chắc chắn rằng chúng tôi có chứa mã vẫn hoạt động như mong đợi. Hãy làm điều đó. Tại thời điểm này, thay vì làm điều đó bản sao gây phiền nhiễu và dán một lần nữa, chúng ta hãy viết một chức năng để thực sự tạo ra một nút. Nếu chúng ta di chuyển xuống tất cả các con đường chính, chúng tôi thấy rằng chúng tôi đã làm điều này mã rất giống nhau hơn và hơn nữa mỗi khi chúng tôi muốn tạo ra một nút. 

Hãy viết một chức năng đó sẽ thực sự xây dựng một nút cho chúng ta và trả lại nó. Tôi sẽ để gọi nó build_node. Tôi sẽ xây dựng một nút với một giá trị cụ thể. Phóng ở đây. Điều đầu tiên tôi sẽ làm là thực sự tạo ra không gian cho các nút trên heap. Vì vậy, node * n = malloc (sizeof (node)); n -> giá trị = giá trị; và sau đó ở đây, tôi chỉ cần đi để khởi tạo tất cả các trường là các giá trị thích hợp. Và cuối cùng, chúng tôi sẽ trả lại nút của chúng tôi. Được rồi. Một điều cần lưu ý rằng chức năng này ngay tại đây để trả về một con trỏ trỏ tới bộ nhớ đã được heap-phân bổ. Có gì đẹp về việc này là nút này - chúng ta phải khai báo nó trên heap bởi vì nếu chúng tôi tuyên bố nó trên stack chúng tôi sẽ không thể làm điều đó trong chức năng này như thế này. Rằng bộ nhớ sẽ đi ra khỏi phạm vi và không có giá trị nếu chúng ta đã cố gắng để truy cập nó sau này. Vì chúng ta đang tuyên bố đống phân bổ bộ nhớ, chúng ta sẽ phải chăm sóc giải phóng nó sau này chương trình của chúng tôi không bị rò rỉ bất kỳ bộ nhớ. Chúng tôi đã punting cho mọi thứ khác trong các mã để đơn giản vào thời điểm đó, nhưng nếu bạn đã bao giờ viết một chức năng mà trông như thế này nơi mà bạn đã có một số gọi nó là một malloc hoặc realloc bên trong - bạn muốn làm cho chắc chắn rằng bạn đặt một số loại bình luận ở đây nói rằng, hey, bạn biết đấy, trả về một nút đống phân bổ được khởi tạo với giá trị thông qua trong. Và sau đó bạn muốn đảm bảo rằng bạn đặt trong một số loại lưu ý nói rằng người gọi phải giải phóng bộ nhớ quay trở lại. Bằng cách đó, nếu ai đó bao giờ đi và sử dụng chức năng đó, họ biết rằng bất cứ điều gì họ nhận được từ chức năng đó tại một số điểm cần phải được giải phóng. 

Giả sử tất cả là tốt và tốt, chúng ta có thể đi xuống vào mã của chúng tôi và thay thế tất cả những dòng này ngay tại đây với các cuộc gọi chức năng nút xây dựng của chúng tôi. Hãy làm điều đó thực sự nhanh chóng. Một phần rằng chúng tôi không thể thay thế phần này xuống đây ở dưới cùng mà chúng tôi thực sự dây lên các nút để trỏ đến nhau, bởi vì chúng ta không thể làm chức năng của chúng tôi. Tuy nhiên, chúng ta hãy làm root = build_node (7); node * ba = build_node (3); node * 6 = build_node (6); node * 9 = build_node (9); Và bây giờ, chúng tôi cũng muốn để thêm các nút cho node * 5 = build_node (5); nút * 8 = build_node (8); và các nút khác là gì? Hãy xem ở đây. Chúng tôi cũng muốn thêm một 2 - nút * 2 = build_node (2); Được rồi. Tại thời điểm này, chúng tôi biết rằng chúng tôi đã có 7, 3, 9, và 6 tất cả các dây lên một cách thích hợp, nhưng những gì về 5, 8, và 2? Để giữ cho tất cả mọi thứ theo thứ tự thích hợp, chúng ta biết rằng con phải của 3 là 6. Vì vậy, nếu chúng ta sẽ thêm 5, 5 cũng thuộc về phía bên phải của cây trong đó có 3 là gốc rễ, như vậy 5 thuộc là con trái của 6. Chúng tôi có thể làm điều này bằng cách nói rằng, sáu -> left_child = 5; và sau đó là 8 thuộc là con trái của 9, vì vậy 9 -> left_child = 8; và sau đó 2 là con trái của 3, do đó, chúng ta có thể làm điều đó ở đây - ngươi -> left_child = 2; Nếu bạn không hoàn toàn theo cùng với điều đó, tôi đề nghị bạn vẽ nó ra cho mình. 

Được rồi. Hãy tiết kiệm này. Hãy đi ra ngoài và chắc chắn rằng nó biên dịch, và sau đó chúng ta có thể thêm vào Chứa các cuộc gọi của chúng tôi. Hình như tất cả mọi thứ vẫn còn biên dịch. Chúng ta hãy đi vào và thêm vào một số chứa các cuộc gọi. Một lần nữa, tôi sẽ làm một chút sao chép và dán. Bây giờ hãy tìm kiếm 5, 8, và 2. Được rồi. Hãy chắc chắn rằng điều này vẫn còn tất cả sẽ tốt. Great! Lưu và bỏ thuốc lá. Bây giờ chúng ta hãy làm biên dịch, và bây giờ hãy chạy. Từ những kết quả, có vẻ như tất cả mọi thứ đang làm việc chỉ tốt đẹp và tốt. Great! Vì vậy, bây giờ chúng tôi đã có Chứa của chúng tôi chức năng bằng văn bản. Hãy di chuyển và bắt đầu làm việc về việc làm thế nào để chèn nút vào cây vì, như chúng tôi đang làm nó ngay bây giờ, mọi thứ không phải là rất đẹp. 

Nếu chúng ta quay trở lại các đặc điểm kỹ thuật, nó yêu cầu chúng tôi viết một chức năng được gọi là chèn - một lần nữa, trả lại một bool hay không, chúng tôi thực sự có thể chèn các nút vào cây - và sau đó giá trị để chèn vào cây được quy định như Lý lẽ duy nhất chức năng chèn của chúng tôi. Chúng tôi sẽ trở lại đúng sự thật nếu chúng ta thực sự có thể chèn giá trị có chứa nút vào cây, điều đó có nghĩa rằng chúng ta, một, đã có đủ bộ nhớ, và sau đó hai, rằng nút không đã tồn tại trong cây từ - hãy nhớ rằng, chúng tôi sẽ không có giá trị nhân bản trong cây, chỉ để làm cho mọi thứ đơn giản. Được rồi. Sao để mã. Mở nó lên. Phóng to một chút, sau đó di chuyển xuống. Hãy đặt các chức năng chèn ngay bên trên có chứa. Một lần nữa, nó sẽ được gọi là bool chèn (int giá trị). Cung cấp cho nó không gian nhiều hơn một chút, và sau đó, như một mặc định, chúng ta hãy đặt return false vào cuối. Bây giờ xuống phía dưới, chúng ta hãy đi trước và thay vào đó tự xây dựng các nút trong chính bản thân mình và hệ thống dây điện để trỏ đến nhau như chúng tôi đang làm, chúng tôi sẽ dựa vào chức năng chèn của chúng tôi để làm điều đó. Chúng tôi sẽ không dựa vào chức năng chèn của chúng tôi để xây dựng toàn bộ cây từ đầu chỉ được nêu ra, mà đúng hơn là chúng tôi sẽ nhận được thoát khỏi những dòng này - we'll nhận xét ra những dòng này - xây dựng 5 nút, 8, và 2. Và thay vào đó, chúng ta sẽ chèn các cuộc gọi chức năng chèn của chúng tôi để chắc chắn rằng đó thực sự hoạt động. Ở đây chúng tôi đi. 

Bây giờ chúng ta đã nhận xét ra những dòng này. Chúng tôi chỉ có 7, 3, 9, và 6 trong cây của chúng tôi vào thời điểm này. Để chắc chắn rằng điều này là tất cả làm việc, chúng ta có thể thu nhỏ, làm cho cây nhị phân của chúng tôi, chạy nó, và chúng ta có thể thấy có nói với chúng tôi rằng chúng tôi hoàn toàn đúng - 5, 8, và 2 là không còn trong cây. Trở lại vào mã này, và làm thế nào chúng ta sẽ để chèn? Hãy nhớ những gì chúng ta đã làm khi chúng ta đã thực sự chèn 5, 8, và 2 trước đây. Chúng tôi chơi trò chơi Plinko nơi chúng tôi bắt đầu ở gốc, đã đi xuống một cây một cho đến khi chúng tôi tìm thấy khoảng cách thích hợp, và sau đó chúng tôi có dây trong nút tại vị trí thích hợp. Chúng ta sẽ làm điều tương tự. Điều này về cơ bản là giống như viết mã mà chúng tôi sử dụng trong có chứa chức năng để tìm ra nơi mà các nút nên, và sau đó chúng tôi chỉ cần đi để chèn các nút phải có. Hãy bắt đầu làm điều đó. 

Vì vậy, chúng tôi có một nút * hiện = root, chúng tôi chỉ đi theo có chứa mã cho đến khi chúng ta thấy rằng nó không hoàn toàn làm việc cho chúng tôi. Chúng ta sẽ phải đi qua cây trong khi các yếu tố hiện không phải là null, và nếu chúng ta thấy đó là hiện giá trị bằng với giá trị mà chúng tôi đang cố gắng để chèn , điều này là một trong các trường hợp trong đó chúng ta có thể không thực sự chèn các nút vào các cây bởi vì điều này có nghĩa là chúng ta có một giá trị trùng lặp. Ở đây chúng ta đang thực sự sẽ trả về false. Bây giờ, nếu người nào khác hiện của giá trị thấp hơn giá trị, bây giờ chúng ta biết rằng chúng tôi di chuyển ở bên phải  bởi vì giá trị thuộc về nửa bên phải của cây hiện. Nếu không, chúng ta sẽ di chuyển sang bên trái. Đó là cơ bản Chứa của chúng tôi hoạt động phải có. 

Tại thời điểm này, khi chúng tôi đã hoàn thành trong vòng lặp trong khi, con trỏ hiện của chúng tôi sẽ được trỏ đến null nếu chức năng này đã không được trả lại. Do đó, chúng ta đang có hiện tại chỗ, nơi chúng tôi muốn chèn các nút mới. Những gì còn lại phải được thực hiện là để thực sự xây dựng các nút mới, mà chúng ta có thể làm khá dễ dàng. Chúng tôi có thể sử dụng chức năng nút siêu tiện dụng của chúng tôi xây dựng, và một cái gì đó mà chúng ta không làm trước đó - chúng ta chỉ cần loại cho các cấp, nhưng bây giờ chúng tôi sẽ làm chỉ để chắc chắn - chúng tôi sẽ kiểm tra để đảm bảo rằng giá trị trả về bởi nút mới đã thực sự không phải null, bởi vì chúng tôi không muốn để bắt đầu truy cập bộ nhớ rằng nếu nó là null. Chúng tôi có thể kiểm tra để chắc chắn rằng nút mới không bằng vô giá trị. Hoặc thay vào đó, chúng tôi chỉ có thể nhìn thấy nếu nó thực sự là vô giá trị, và nếu nó là null, sau đó chúng tôi chỉ có thể trả về false sớm. 

Tại thời điểm này, chúng tôi có dây nút mới vào vị trí thích hợp của nó trong cây. Nếu chúng ta nhìn lại chính nơi mà chúng tôi đã thực sự hệ thống dây điện trong giá trị trước đây, chúng ta thấy rằng cách chúng tôi đã làm việc đó khi chúng tôi muốn đặt 3 trong cây chúng tôi truy cập con trái của gốc. Khi chúng tôi đặt 9 trong cây, chúng tôi đã có để truy cập vào các con phải của gốc. Chúng tôi đã có một con trỏ đến phụ huynh để đưa một giá trị mới vào cây. Di chuyển trở lại để chèn, đó là sẽ không khá làm việc ở đây vì chúng ta không có một con trỏ cha mẹ. Những gì chúng tôi muốn có thể làm được là, vào thời điểm này, kiểm tra giá trị của cha mẹ và xem - tốt, chúa ơi, nếu giá trị của cha mẹ ít hơn giá trị hiện tại, sau đó con phải của cha mẹ nên là nút mới; nếu không, con trái của cha mẹ nên là các node mới. Tuy nhiên, chúng tôi không có con trỏ này mẹ khá chưa. 

Để có được nó, chúng tôi đang thực sự sẽ phải theo dõi nó như chúng tôi đi qua cây và tìm thấy những vị trí thích hợp trong vòng lặp của chúng tôi ở trên. Chúng ta có thể làm điều đó bằng cách di chuyển trở lại lên đến trên cùng của chức năng chèn của chúng tôi và theo dõi một biến con trỏ khác được gọi là cha mẹ. Chúng tôi sẽ thiết lập nó bằng vô giá trị ban đầu, và sau đó mỗi khi chúng tôi đi qua cây, chúng ta sẽ đặt con trỏ phụ huynh để phù hợp với con trỏ hiện tại. Đặt cha mẹ bằng hiện. Bằng cách này, mỗi lần chúng tôi đi qua, chúng ta sẽ đảm bảo rằng, cũng như con trỏ hiện tại được tăng lên con trỏ mẹ sau nó chỉ là một mức độ cao hơn so với con trỏ hiện tại trong cây. Đó là tất cả có vẻ khá tốt. 

Tôi nghĩ rằng một điều rằng chúng tôi sẽ muốn điều chỉnh này là xây dựng vô nút quay trở lại. Để có được xây dựng nút để thực sự thành công trở về null, chúng tôi sẽ phải sửa đổi mã đó, bởi vì ở đây, chúng ta không bao giờ được thử nghiệm để đảm bảo rằng malloc trả về một con trỏ hợp lệ. Vì vậy, nếu (n = NULL!), Sau đó - nếu malloc trả về một con trỏ hợp lệ, sau đó chúng tôi sẽ khởi tạo nó; nếu không, chúng tôi sẽ chỉ quay trở lại và sẽ kết thúc trở về null cho chúng tôi. Bây giờ tất cả trông khá tốt. Hãy làm cho chắc chắn rằng điều này thực sự biên dịch. Làm cho cây nhị phân, và oh, chúng tôi đã có một số công cụ xảy ra ở đây. 

Chúng tôi đã có một tuyên bố tiềm ẩn của chức năng xây dựng nút. Một lần nữa, với các trình biên dịch, chúng ta sẽ bắt đầu ở đầu trang. Những gì mà phải có nghĩa là tôi đang kêu gọi xây dựng nút trước khi tôi thực sự tuyên bố nó. Hãy quay trở lại các mã thực sự nhanh chóng. Di chuyển xuống, và chắc chắn đủ, chức năng chèn của tôi được khai báo phía trên xây dựng chức năng nút, nhưng tôi đang cố gắng để sử dụng xây dựng nút bên trong chèn. Tôi sẽ đi và sao chép và sau đó dán cách xây dựng chức năng nút lên đây ở đầu trang. Bằng cách đó, hy vọng rằng sẽ làm việc. Hãy cung cấp cho khác đi. Bây giờ tất cả biên dịch. Tất cả là tốt. 

Tuy nhiên, vào thời điểm này, chúng tôi đã không thực sự được gọi là chức năng chèn của chúng tôi. Chúng tôi chỉ biết rằng nó biên dịch, do đó, chúng ta hãy đi vào và đặt một số cuộc gọi. Hãy làm điều đó trong chức năng chính của chúng tôi. Ở đây, chúng tôi nhận xét ra 5, 8, và 2, và sau đó chúng ta không dây lên xuống đây. Hãy làm cho một số cuộc gọi để chèn, và chúng ta hãy cũng sử dụng cùng một loại công cụ mà chúng tôi sử dụng khi chúng ta thực hiện những cuộc gọi printf để đảm bảo rằng tất cả mọi thứ đã lăp. Tôi sẽ để sao chép và dán, và thay vì chứa chúng ta sẽ làm chèn. Và thay vì 6, 10, và 1, chúng tôi sẽ sử dụng 5, 8, và 2. Điều này hy vọng sẽ chèn 5, 8, và 2 vào cây. Biên dịch. Tất cả là tốt. Bây giờ chúng ta sẽ thực sự chạy chương trình của chúng tôi. 

Tất cả mọi thứ trở lại sai. Vì vậy, 5, 8, và 2 không đi, và nó trông giống như Chứa không tìm thấy chúng hoặc. Chuyện gì đang xảy ra? Hãy thu nhỏ. Vấn đề đầu tiên là chèn dường như quay trở lại sai, và có vẻ như đó là bởi vì chúng tôi còn lại trong cuộc gọi giả trở lại của chúng tôi, và chúng tôi không bao giờ thực sự trở lại đúng sự thật. Chúng ta có thể thiết lập mà lên. Vấn đề thứ hai là, bây giờ ngay cả nếu chúng ta làm - tiết kiệm này, bỏ điều này, chạy làm lại, có nó biên dịch, sau đó chạy nó - chúng ta thấy rằng cái gì khác xảy ra ở đây. 5, 8, và 2 người vẫn không bao giờ được tìm thấy trong cây. Vì vậy, những gì đang xảy ra? 

Chúng ta hãy xem xét điều này trong các mã. Hãy xem nếu chúng ta có thể con số này ra. Chúng tôi bắt đầu với phụ huynh không phải là vô giá trị. Chúng tôi đặt con trỏ hiện tại bằng con trỏ gốc, và chúng tôi sẽ làm việc theo cách của chúng tôi thông qua cây. Nếu nút hiện tại không phải là null, sau đó chúng tôi biết rằng chúng tôi có thể di chuyển xuống một chút. Chúng tôi đặt con trỏ mẹ của chúng tôi để được bình đẳng với con trỏ hiện tại, kiểm tra giá trị nếu các giá trị đều giống nhau, chúng tôi quay trở lại sai. Nếu các giá trị ít, chúng tôi chuyển sang bên phải; nếu không, chúng tôi chuyển sang bên trái. Sau đó, chúng tôi xây dựng một nút. Tôi sẽ phóng to một chút. Và ở đây, chúng tôi sẽ cố gắng để dây lên các giá trị để được giống. Chuyện gì đang xảy ra? Hãy xem nếu có thể Valgrind có thể cung cấp cho chúng tôi một gợi ý. 

Tôi thích sử dụng Valgrind chỉ vì Valgrind thực sự nhanh chóng chạy và cho bạn biết nếu có bất kỳ lỗi bộ nhớ. Khi chúng tôi chạy Valgrind trên các mã, như bạn có thể nhìn thấy ngay here--Valgrind./binary_tree--and nhấn Enter. Bạn thấy rằng chúng tôi không có bất kỳ lỗi bộ nhớ, vì vậy nó trông giống như tất cả mọi thứ sao cho đến nay. Chúng tôi có một số rò rỉ bộ nhớ, mà chúng ta biết, bởi vì chúng tôi không xảy ra để giải phóng bất kỳ của các nút của chúng tôi. Chúng ta hãy thử chạy GDB để xem những gì đang thực sự xảy ra. Chúng tôi sẽ làm gdb / binary_tree. Nó khởi động tốt. Hãy thiết lập một điểm break trên chèn. Hãy chạy. Dường như chúng tôi không bao giờ thực sự được gọi là chèn. Có vẻ như vấn đề chỉ là khi tôi thay đổi trong chính tất cả các cuộc gọi printf từ chứa - Tôi không bao giờ thực sự thay đổi này gọi chèn. Bây giờ chúng ta hãy cho nó một thử. Hãy biên dịch. Tất cả sẽ tốt. Bây giờ chúng ta hãy thử chạy nó, xem những gì sẽ xảy ra. Ổn chứ! Tất cả mọi thứ trông khá tốt ở đó. 

Điều cuối cùng để suy nghĩ về, được có bất kỳ trường hợp cạnh để chèn này? Và nó quay ra rằng, tốt, một trong những trường hợp cạnh đó là luôn luôn thú vị để suy nghĩ về là, những gì sẽ xảy ra nếu cây của bạn là trống rỗng và bạn gọi chức năng này chèn? Nó sẽ làm việc? Vâng, chúng ta hãy cho nó một thử. - Binary_tree c. Cách chúng ta sẽ kiểm tra điều này, chúng ta sẽ đi xuống với chức năng chính của chúng tôi, và thay vì dây các nút lên như thế này, chúng tôi chỉ có nhận xét về toàn bộ điều, và thay vì dây lên các nút chính mình, chúng ta có thể thực sự đi trước và xóa tất cả những điều này. Chúng ta sẽ làm cho tất cả mọi thứ của một cuộc gọi để chèn. Vì vậy, chúng ta hãy làm - thay vì 5, 8, và 2, chúng ta sẽ để chèn 7, 3, và 9. Và sau đó chúng tôi cũng sẽ muốn chèn 6, cũng. Lưu. Bỏ thuốc lá. Cây nhị phân. Tất cả biên dịch. Chúng tôi chỉ có thể chạy nó như là và xem những gì sẽ xảy ra, nhưng nó cũng sẽ được thực sự quan trọng để đảm bảo rằng chúng tôi không có bất kỳ lỗi bộ nhớ, vì đây là một trong những trường hợp của chúng tôi mà chúng ta biết về. 

Hãy chắc chắn rằng nó hoạt động tốt dưới Valgrind, mà chúng tôi sẽ làm bằng cách chỉ chạy Valgrind / binary_tree. Có vẻ như chúng tôi thực sự có một lỗi từ một bối cảnh - chúng tôi có lỗi phân khúc này. Điều gì đã xảy ra? Valgrind thực sự cho chúng ta biết nó ở đâu. Thu nhỏ một chút. Có vẻ như nó đang xảy ra trong chức năng chèn của chúng tôi, nơi chúng tôi có một chi tiết không hợp lệ của kích thước 4 tại chèn, đường 60. Chúng ta hãy quay trở lại và xem những gì đang xảy ra ở đây. Thu nhỏ thực sự nhanh chóng. Tôi muốn làm cho chắc chắn rằng nó không đi đến các cạnh của màn hình, do đó chúng ta có thể nhìn thấy tất cả mọi thứ. Kéo mà một chút. Được rồi. Di chuyển xuống, và vấn đề là ngay tại đây. Điều gì sẽ xảy ra nếu chúng ta có được xuống và nút hiện tại của chúng tôi là đã được vô giá trị, nút cha của chúng tôi là vô giá trị, vì vậy nếu chúng ta nhìn ở đầu, ngay tại đây - nếu điều này vòng lặp trong khi không bao giờ thực sự thực hiện bởi vì giá trị hiện tại của chúng tôi là vô giá trị gốc của chúng tôi là null để hiện là null - sau đó mẹ của chúng tôi không bao giờ được thiết lập hiện hoặc giá trị hợp lệ, như vậy, cha mẹ cũng sẽ là null. Chúng ta cần nhớ để kiểm tra cho rằng theo thời gian, chúng tôi nhận được xuống ở đây, và chúng tôi bắt đầu truy cập giá trị của cha mẹ. Vì vậy, những gì sẽ xảy ra? Vâng, nếu phụ huynh là null - (cha mẹ == NULL) - sau đó chúng ta biết rằng đó không phải là bất cứ điều gì trong cây. Chúng ta phải cố gắng để chèn nó ở gốc. Chúng ta có thể làm điều đó bằng cách chỉ cần cài đặt gốc bằng các nút mới. Sau đó, vào thời điểm này, chúng tôi không thực sự muốn đi qua những thứ khác. Thay vào đó, ngay tại đây, chúng ta có thể làm một trong hai khác-nếu-khác, hoặc chúng ta có thể kết hợp tất cả mọi thứ ở đây trong một khác, nhưng ở đây chúng tôi chỉ sẽ sử dụng khác và làm theo cách đó. Bây giờ, chúng ta sẽ kiểm tra để đảm bảo rằng mẹ của chúng tôi không phải là null sau đó trước khi thực sự cố gắng để truy cập vào các lĩnh vực của mình. Điều này sẽ giúp chúng ta tránh được lỗi phân khúc. Vì vậy, chúng tôi bỏ thuốc lá, thu nhỏ, biên dịch, chạy. 

Không có lỗi, nhưng chúng tôi vẫn có một bó của rò rỉ bộ nhớ vì chúng tôi không giải phóng bất kỳ của các nút của chúng tôi. Tuy nhiên, nếu chúng ta đi lên ở đây và chúng ta nhìn vào bản in của chúng tôi, chúng ta thấy rằng, tốt, trông giống như tất cả của chèn của chúng tôi đã trở về đúng, đó là tốt. Việc chèn là tất cả sự thật, và sau đó có chứa các cuộc gọi phù hợp cũng đúng. 

Good job! Có vẻ như chúng tôi đã thành công bằng văn bản chèn. Đó là tất cả chúng tôi đã cho Đặc điểm kỹ thuật Set vấn đề này trong tuần. Một thách thức thú vị để suy nghĩ về cách bạn thực sự sẽ đi vào và miễn phí tất cả các nút trong cây này. Chúng ta có thể làm như vậy là một số cách khác nhau, nhưng tôi sẽ để lại cho bạn để thử nghiệm, và là một thách thức thú vị, hãy thử và đảm bảo rằng bạn có thể chắc chắn rằng rằng báo cáo này Valgrind trả về không có lỗi và không có rò rỉ. 

Chúc may mắn vào bộ Huffman tuần này vấn đề mã hóa, và chúng tôi sẽ nhìn thấy bạn trong tuần tới! [CS50.TV]