[Powered by Google Translate] [제 7 조 : 더 편안한] [롭 보덴] [하버드 대학] [이 CS50입니다] [CS50.TV] 괜찮아요. 그래서 내 이메일에서 밝혔다 같은 이 바이너리 - 트리 위주의 섹션 될 것입니다. 그러나 많은 질문이 없습니다. 그래서 우리는 시도하고 각 질문을 뽑아 낼 것 그리고 일을하는 모든 가장 좋은 방법은 고통을 구체적으로 이동합니다. 그래서 지금 초에, 우리는 이진 나무와 물건 샘플 도면을 통해 이동합니다. 그래서 여기, "이진 나무가 연결리스트의 비슷한 노드를 가지고 기억 왼쪽의 '아이'의 하나 하나가 아닌 포인터의 경우를 제외하고 두 사람은 있습니다 그리고 오른쪽 '아이'한. " 그냥 링크 목록 같습니다 이진 트리 자 구조체를 제외하고이 포인터를하지 않을 수 있습니다. 세 포인터를해야합니다 trinary 나무가있어 단지 일반 포인터를 가지고 N-워 나무가있어, 그때 당신은 가질 정도로 크게 malloc해야한다는 가능한 모든 어린이들에게 충분한 포인터. 따라서 이진 트리가 두 상수가 발생합니다. 원하는 경우, 당신은 단항 트리 연결된 목록을 제공 할 수 있습니다 하지만 누군가가 그런 전화를 생각하지 않아요. "이진 트리 노드의 상자 - 및 - 화살표 다이어그램을 그립니다 각 하위 포인터가 null입니다 네이트 좋아하는 숫자, 7. "포함 그럼 아이 패드 모드를 사용합니다. 

그것은 매우 간단거야. 우리는 단지 노드를받을거야, 난 사각형으로 그려드립니다. 그리고 여기에 값을 그릴 수 있습니다. 그래서 값은 여기에 이​​동합니다 그리고 여기 우리는 왼쪽에있는 왼쪽 포인터와 오른쪽에있는 오른쪽 포인터를해야합니다. 그 왼쪽과 오른쪽, 포인터 이름 전화 컨벤션 있도록하고 매우이다. 이 모두 null이 될 것이다. 그건 그냥 null이됩니다, 그는 null이됩니다. 좋아요. 그래서 여기에 백업합니다. "연결리스트로 우리는 포인터를 저장했다 전체 연결 목록이나 전체 목록을 기억하기 위해 목록의 첫 번째 노드 있습니다. 마찬가지로, 나무, 우리는 포인터를 저장해야 전체 트리를 기억하기 위해 단일 ​​노드 있습니다. 이 노드는 트리의 '루트'칼레 수 있습니다. 이전에서 다이어그램에 구축하거나 새를 그릴 당신은 바이너리 트리의 상자 - 및 - 화살표의 묘사되어 있는지 등 로 왼쪽 3 다음 값을 7,, 3의 오른쪽에있는 다음 오른쪽에 9, 다음 6. " 내 머리에 모든 걸 다 기억 할 수 있는지 봅시다. 그래서 여기에 우리 루트까지가 될 것입니다. 우리는, 어딘가에 우리가 뿌리를 부를 것을 몇 가지 포인터를해야합니다 그리고이 남자는 눈치입니다. 이제 새 노드를하려면, 우리는 왼쪽에, 3을해야 하죠? 3 새로운 노드가 있으므로, 그것은 처음에 null을 가리 킵니다. 난 그냥 N. 놓을 게요 이제 7의 왼쪽로 이동하고 싶은데요. 그래서 우리는 지금이 남자를 가리 키도록이 포인터를 변경합니다. 그리고 우리는 동일한 기능을 수행. 우리는 여기에 9 원 이는 처음에 그냥 null을 말합니다. 우리는 9이 포인터 지점을 변경 할거야 지금 우리는 3 오른쪽에 6 놓고 싶어. 그럼 거예요 - 6합니다. 그리고 그 사람이 거기 가리 킵니다. 좋아요. 그러니까 그게 그거라도해야 할 우리를 요청합니다. 

지금의 몇 가지 용어를 통해 가자. 우리는 이미 트리의 루트는 트리에서 최상위 노드입니다 방법에 대해 이야기. 하나는 7 포함. 트리의 맨 아래에있는 노드가 잎이라고합니다. 단지의 자녀로 NULL이있는 노드는 잎입니다. 그럼 우리 이진 나무가 단지 하나의 노드 인 경우, 가능합니다, 나무는 잎이며, 그게 없잖아. "나무의 '높이'를해야 홉의 수입니다 상단에서 잎까지입니다. " 우리는 두 번째에로의 차이를 당할거야 균형과 불균형 이진 나무 사이, 이 나무의 지금 들어, 전체 높이 나는 3 말 비록 당신은 홉의 수를 계산하면 당신은 9 받기 위해해야​​ 다음, 정말 2 만 높이입니다. 지금이, 불균형 이진 트리입니다 이 관련에 도착하지만 우리는 균형에 대해 얘기합니다. 이제 우리는 측면에서 트리의 노드에 대해 이야기 할 수 있습니다 트리에서 다른 노드를 기준으로. 이제 우리는 부모, 자녀, 형제, 조상, 그리고 후손을 갖추고 있습니다. 그들은 무슨 뜻인지 아주 상식입니다. 우리가 묻는다면 - 그건 부모. 따라서 세의 부모는 무엇인가? [학생] 7. >> 그래. 부모가 당신을 가리 킵니다 일 될 것입니다. 그런 다음 7 아이들은 무엇입니까? [학생] 3 9. >> 그래. "어린이"는 문자 그대로 아이를 의미납니다, 가 손자 같은 거죠 여섯 있도록이 적용되지 않을 것입니다. 우리가 자손을 이동 없다면, 그래서 7 자손은 무엇입니까? [학생] 3, 6 및 9. >> 그래. 루트 노드의 자손은, 나무의 모든 될 것입니다 를 제외하고 어쩌면 루트 노드 자체, 그 자손 고려하지 않으려는 경우. 그리고 마지막으로, 선조 때문에 반대 방향입니다. 따라서 6의 조상은 무엇입니까? [학생] 3과 7. >> 그래. 9 포함되어 있지 않습니다. 그냥 루트에 직접 계보 (Lineage) 돌아 조상가 될 것입니다. 

"우리는 바이너리 트리가있는 경우 트리의 각 노드에 대해 '주문'이라는 말 왼쪽에있는 그 후손들 모두가 낮은 값을 가지고 그리고 오른쪽에있는 사람 모두가 더 큰 값을 가진다. 예를 들어, 위의 나무는 주문하지만 유일하게 가능한 명령을 배치 안합니다. " 우리가 그에게 가서 전에 주문 이진 트리도 이진 검색 트리로 알려져 있습니다. 여기 우리는 그것을 주문 이진 트리를 호출 할 일 하지만 내가들은 적이 없다가, 주문 이진 트리 전에 전화 그리고 퀴즈에 우리는 이진 검색 트리를 넣어 훨씬 더 높습니다. 그들은 하나 같은, 야 그리고 당신이 이진 트리와 이진 검색 트리의 차이를 인식 중요합니다. 이진 트리가 트리입니다 두 가지를 가리키는. 각 노드는 두 가지 가리 킵니다. 이를 가리 값에 대해 어떠한 추론이 없습니다. 가 이진 검색 트리니까 그래서, 여기에 좋아 우리는 7 우리가 가면 왼쪽 알 그리고 우리가 가능성이 도달 할 수있는 모든 값 7 왼쪽으로 이동하여 7 이하이어야합니다. 이하 7보다 모든 값은 3, 6 것을 확인할 수 있습니다. 그 7의 왼쪽에 있습니다. 우리는 7의 오른쪽에 가면, 모든 7보다 커야한다 그래서 9 7의 오른쪽에, 우리는 잘해. 이것은 이진 트리의 경우하지 않습니다 일반 이진 트리에 우리가, 왼쪽 상단, 7시 3 수 있습니다 7 왼쪽에 9; 더 어떠한 값의 순서가 없습니다. 이 지루하고 불필요한이기 때문에 이제, 우리는 실제로이 작업을 수행하지 않습니다 하지만 "당신이 생각 할 수있는만큼 많이 주문 그루의 나무를 그려보세요 숫자 7, 3, 9를 사용하고, 6. 뚜렷한 계획이 얼마나 많을 까? 각 하나의 높이가 무엇입니까? " 

, 우리는 몇을 다하겠습니다하지만, 주요 아이디어는 이 어떠한 방식으로이 값을 포함하는 이진 트리의 독특한 표현에 위치해 있습니다. 일부 이진 7이 포함되어 나무, 3, 6, 9 우리가 필요한 건 있습니다. 또 다른 가능한 유효 하나는 뿌리가 3 것 왼쪽으로 이동하고 6입니다, 왼쪽으로 이동하고 7로 왼쪽으로 이동하고 9입니다. 그건 완벽하게 유효한 이진 검색 트리입니다. 그냥 연결리스트처럼 때문에 매우 도움이 아닙니다 이러한 포인터의 모든은 null이됩니다. 그러나 유효한 나무입니다. 응? [학생] 값은 오른쪽에 더 있어야하지 않아? 아니면이는 -? >>이 나는 다른 길을 가려고했는데. 도 있습니다 - 그래, 그런 전환 보자. 9, 7, 6, 3. 좋은 지적이야. 아직 이진 트리 검색이하는 행동에 순종해야합니다. 그래서 왼쪽으로 모든 특정 노드 이하이어야합니다. 우리는 말은,이 6 이동 여기있게 할 수 있습니다. 아니, 할 수 없어요. 내가 왜 그걸하는 거예요? 하죠 - 여기 6는 여기 7, 3-6 점입니다. 이 여전히 유효한 이진 검색 트리입니다. 제가 배열을 가지고 올 수 있는지 보자고 - 내가 만약 잘못된 것입니다. 그래, 알았어. 이 나무와 그래서 뭐가 문제 야? 이미 너에게 그것을에 문제가 있다는 힌트를 제공 한 것. 내가 왜 그걸하는 거예요? 좋아요. 이 합리적인 보입니다. 우리가 각 노드에서, 7과 같은 다음 7 왼쪽에 보면 3. 그래서 우리는 3가, (3)의 오른쪽에있는 것은 6입니다. 당신이 6시에 보면, 6의 오른쪽에있는 것은 9입니다. 왜이 유효한 이진 검색 트리 안 그래요? [학생] 9 7의 왼쪽에 남아 있습니다. >> 그래. 당신이 가능한 7 왼쪽으로 이동하여 도달 할 수있는 모든 값이 7보다 적은 것이 사실이어야합니다. 우리는 7의 왼쪽 가면, 우리는 3하고 우리는 여전히 6 수 우리는 여전히, 9에 도착하지만, 이하 7을 사라함으로써 수 우리는 7보다 큰하다는 번호를받을 수 없습니다. 그래서이 유효한 이진 검색 트리가 아닙니다. 

내 동생은 실제로 면접 질문을했다 그 유효성을 검사 할 일 백업 기본적으로이 단지 코드를했습니다 나무는 이진 검색 트리입니다 여부 그래서 그는 처음으로 한 일 그냥 확인 확인하는 것이 었습니다 왼쪽과 오른쪽이 올바른지, 그리고 경우 다음과 거기 반복합니다. 하지만 당신은 그렇게하지 ​​못하는, 당신은 추적해야 나는 7의 왼쪽 갔어요 그 지금 사실의, 이 하위 트리의 모든 7 미만이어야합니다. 올바른 알고리즘을 추적 할 필요가 값은 가능한 집합 할 수있는 범위의 우리는 모두 통과하지 않습니다. 멋진 재발 관계가 있습니다 우리가 사람들에게 미치지 못하는, 또는 우리가 사람들에게하지 않습니다 있지만은, 실제로 얼마나 많은 정의. 그럼 그 14이 있습니다. 당신이 짓을 했을까하는 방법의 아이디어는 수학적으로 같은 것입니다 당신은 루트 노드로 단일 하나를 선택할 수 있습니다 그럼 내가, 루트 노드로 7 선택하면 그리고 내 왼쪽 노드가 될 갈 수있는 숫자는, 말있다 내 오른쪽 노드가 될 수있는 몇 가지 숫자가 있습니다 하지만 나는 그 총 숫자, 왼쪽으로 이동 할 수있는 금액을 습니 경우 플러스 오른쪽으로 이동 할 수있는 금액은 습니입니다 - 1. 그럼 나머지 숫자들은 왼쪽 또는 오른쪽으로가는 것도 할 수 있습니다. 그것은 내가 처음에 3 넣어 경우 모든 왼쪽으로 이동하는, 그런 어려운 것 같습니다 하지만 7을 돌리기 만한다면 다음 몇 가지의 왼쪽을 할 수 있으며 몇 가지 오른쪽으로 이동할 수 있습니다. 그리고 '3 첫 번째 '으로 나는 모든 오른쪽으로 갈 수 의미. 정말이야, 당신은 같은 생각해야 얼마나 많은 일들이 나무의 다음 수준에 갈 수 있습니다. 또는 당신은 모두를 그릴 수 있습니다 그리고 14으로 나오면 그리고 나서 14을드립니다. 

여기로 돌아갑니다, 우리가 그들을 통해 검색 할 수 있기 때문에 "순서 이진 나무는 멋진 정렬 배열을 통해 검색에 매우 유사한 방법 인치 이렇게하려면 우리는 루트에서 시작하여 트리 아래의 방식으로 작동 잎에 대한, 우리가 검색하는 값에 대해 각 노드의 값을 확인. 현재 노드의 값이 값보다 작 으면 우리는 찾고 당신은 노드의 오른쪽 자식 옆에 이동합니다. 그렇지 않으면, 당신은 노드의 왼쪽 자식으로 이동합니다. 어떤 시점에서, 여러분은 여러분이 원하는 값을 찾을 수 있습니다, 또는 당신은 널 (null)로 실행됩니다 값을 나타내는 것은 트리에 없습니다. " 나는 우리가 예전의 트리를 다시 그리기해야, 그 몇초 밖에 안 걸릴거야. 하지만 우리는 6, 10, 1 트리에 있는지 찾아하고 싶습니다. 그럼 그게 뭔지, 7, 9, 3, 6. 좋아요. 당신이보고 싶지 번호는, 우리는 6을보고 싶어요. 이 방법 알고리즘의 작동 원리는 무엇입니까? 음, 우리는 또한 우리 나무에 몇 가지 루트 포인터가 있습니다. 그리고 우리가 루트에 가서 말하면, 우리가 검색하는 값 같은이 값인가요? 그래서 우리는 6 찾고, 그래서 평등 없습니다. 그래서 6 7보다 적은, 좋아, 그래서 우리는 계속, 지금 우리는 말한다. 우리가 왼쪽으로 가고 싶어 의미합니까, 아니면 오른쪽으로 가고 싶어? [학생] 왼쪽. >> 그래. 그것은 상당히 쉽게, 당신이해야 할 모든 나무의 하나의 가능한 노드를 세우면 그리고 당신은 엔 - 머리에 생각하는 대신에, 그래, 덜 있다면, 난 왼쪽으로 이동하거나 권리를가는거야 단지이 사진을 본, 내가 왼쪽으로 가야한다는 아주 명확한 이 노드가 내가 찾는 그 값보다 큰 경우. 그래서 당신은 지금 3에있어 왼쪽으로 이동합니다. 전 가고 싶어요 - 3 6입니다 내가 찾는 값보다 작습니다. 그래서 우리는 오른쪽으로 가고, 지금은 6시 종료 이는 내가 진짜 돌아 있도록이 찾고있는 값입니다. 제가 찾으러 가겠어요 다음 값은 10입니다. 좋아요. 루트를 따라 오지 - 그 잘라 - 10 그래서, 지금, 것입니다. 지금 10은 7보다 큰 될 것입니다, 그래서 제가 오른쪽으로보고 싶어요. 내가 여기 올거야, 10, 9보다 더 될 것입니다 그래서 오른쪽으로보고 싶지 겠어. 여기 올 있지만, 여기에 지금은 널 (null)에 있어요. 나는 null을 친다면 어떻게해야합니까? [학생] False를 반환? >> 그래. I 10를 찾지 못했습니다. 1은 거의 동일 경우 될 것입니다, 를 제외하고 그냥 이성을 상실 할거야, 보는 대신 오른쪽 아래, 나는 왼쪽을 볼거야. 

지금은 우리가 실제로 코드를 얻을 생각합니다. 이곳이야 - CS50 어플라이언스를 열고이 길을 이동 뿐만 아니라 공간에서 할 만 할 수 있습니다. 그것은 아마도 공간에서 작업을 수행하는 것이 좋습니다 우리는 공간에서 일을 할수 있기 때문이다. "처음에 우리는 정수 값을 포함하는 이진 트리 노드에 대한 새 유형의 정의가 필요합니다. 아래 typedef 상용구를 사용하여 이진 트리에서 노드에 대해 새로운 유형의 정의를 만들 수 있습니다. 당신은 문제가 발생할 경우. . . "어쩌구 저쩌구. 좋아요. 그럼 여기서 반복을 놓고, typedef 구조체 노드와 노드. 그래, 알았어. 그래서 우리가 우리의 노드에서 원하는 거예요 필드는 무엇입니까? [학생] 두 포인터 후 INT와? >> int 값, 두 포인터? 어떻게 포인터를 작성하려면 어떻게해야합니까? [학생] 구조체. >> 저는 그래, 구조체 노드가 * 왼쪽 확대해야 그리고 구조체 노드 * 좋아. 그리고 마지막에서 논의를 기억 이 말이 안되는,이 말이 안 이 말도하지 않습니다. 이 재귀 구조체를 정의하기 위해 전 거기에 모든 것을해야합니다. 좋아, 그럼 우리 나무의 모습을 것입니다 수 있도록. 우리가 trinary 나무를 한 경우, 노드는 B1, B2, 구조체 노드 * B3, 같이 보일 수 있습니다 B는 지점입니다 - 사실,이, 중간, 오른쪽,하지만 무엇이든을 떠난 들었습니다. 우리는 바이너리 관심, 그래서 오른쪽, 왼쪽. "이제 트리의 루트에 대한 글로벌 노드 * 변수를 선언합니다." 그래서 우리가 그렇게 할 수 없어. 일 약간 더 어렵고 더 일반화하기 위해서는, 우리는 글로벌 노드 변수가 없습니다. 대신, 주에 우리는 우리의 모든 노드 것을 선언합니다 우리가 실행 시작할 때 그, 그 아래의 의미 우리가 포함되어 기능 및 삽입 기능, 대신에 우리가 포함을, 그냥이 글로벌 노드 변수를 사용하여 제대로 작동 우리는 우리가 처리 할가 인자로 나무를 할 겁니다. 전역 변수를 갖는다는 것은 일을 더 쉽게 만들고했는데. 우리는 일 열심히 할거야. 이제 이런 건 그냥하는 분 정도를 내부의 주요의이 트리를 만들려면, 바로 당신이 원하는 모든 어디. 시도 및 주요 기능에이 나무를 구성합니다. 

좋아요. 그래서 아직 나무에게 전체 방법을지었습니다 할 필요가 없습니다. 그러나 사람은 내가 끌어 수있는 일이 하나는 이러한 트리를 만들어야하는 방법을 표시합니다? [학생] 사람의 음탕 한 짓에서 벗어나려고 노력. [보덴]의 트리 구조를 갖춘 편안한 사람이 있나요? [학생] 그래. 그런데 아직. 아니, 괜찮아 >>. 우리가 끝낼 수 - 오, 당신을 절약 할 수 있습니다? 좋아. 그래서 여기에 우리가해야 - 아, 약간 잘라거야. 나는 확대 이유는 무엇입니까? 확대, 나가 스크롤됩니다. 제가 질​​문이 >>. >> 응? [학생]는 당신이 구조체를 정의 할 때, 아무로 초기화 같은 일이 있습니까? [보덴] 번호 >> 좋아요. 그래서 초기화해야 - [보덴] 번호 구조체를 사용자가 정의 할 때, 또는 선언 할 때, 그것은 기본적으로 초기화되지 않습니다, 당신은 정수를 선언하는 경우가 똑같아. 그것은 정확히 같은 일입니다. 이은 개별 필드의 각 같아요 거기에 쓰레기 값을 가질 수 있습니다. 구조체 또는 선언 - >> 그리고 정의 할 수 있습니다 가 않는 방식으로 그들을 초기화? [보덴] 예. 자, 바로 가기 초기화 구문 모양 것입니다 - 우리가 이런 일을 할 수있는 두 가지 방법이 있어요. 나는 우리가 그것을 컴파일해야한다고 생각 확실히 꽝를 만들기 위해하면이 작업을 수행합니다. 구조체에 제공 인자의 순서 당신은이 중괄호 내부 인자의 순서로 넣어. 당신은 9를 초기화하려면 왼쪽면을 마우스 오른쪽, null이 null이 될 수 있으며 그것은, 0, null이 9가 될 것입니다. , 대안이 있으며, 편집기는이 구문을 좋아하지 않아 그리고 내가 새로운 블록을 원하는 생각 하지만 대안은 무언가 같다 - 여기, 내가 새 줄에 올려 놓을 게요. 당신은 명시 적으로 말할 수, 나는 정확한 구문을 잊어 버려. 그래서 당신은 명시 적으로, 이름하여 해결하고, 말을 할 수 . c 또는. 값 = 9. 왼쪽 =의 NULL. 나는 쉼표 될 수있는 이러한 필요성을 추측거야. . 오른쪽 = NULL, 그래서 당신은 몰라요 이런 식으로 실제로 구조체의 순서를 알 필요가 당신이 이걸 읽는 때, 훨씬 더 명시 적입니다 일에 대해 값이로 초기화되고있어. 

이는 일 중 하나 일 - 따라서 대부분의 경우, C + + C.의 Superset 임 당신은 C + +,하고 컴파일해야합니다 이쪽으로 이동, C 코드를 취할 수 있습니다. 이 C + +에서 지원하지 않는 것 중 하나이기 때문에, 사람들은 그렇게하지 ​​경향이 있습니다. 그 사람들이 그렇게하지 ​​않는 경향이 유일한 이유인지는 모르겠지만 하지만 그것을 사용하는 데 필요한 경우는 C + +와 그래서이 장치를 사용할 수 작업이 필요합니다. 뭔가의 또 다른 예는 C + +과 함께 작동하지 않습니다 어떻게 malloc은 기술적으로 '공극 * "를 반환 하지만, 그냥 숯불 * X = malloc의 무엇이든을 말할 수 그리고 그것은 자동으로 숯불 *로 캐스트 될 것입니다. 그 자동 캐스트에서 발생하지 않는 C + +. 컴파일하지 않을, 당신은 명시 적으로 말을해야 그 숯불 * malloc, 뭐든간에, 숯불 *로 캐스팅 할 수 있습니다. C와 C + +에 동의한다는 여러 가지가 있는데,하지 않습니다 하지만 그건 두 가지입니다. 그래서 우리는이 구문 갈거야. 하지만 그 구문 가지 않았더라도하면, 무슨 -이 문제가 될 수 있을까요? [학생] 내가이 역 참조를 필요하지 않습니다? >> 그래. , 화살표가 암시 적 역 참조를 가지고 기억 그래서 우리는, 구조체를 처리 할 때 우리는 사용하고 싶습니다. 구조체의 필드 내에서 얻을합니다. 그리고 우리가 화살표를 사용하여 유일한 시간은 우리가 어떻게 할 때입니다 - 음, 화살표와 동일합니다 - 그건 내가 화살표를 사용한 경우가 의미했을거야. 모든 화살표 수단은 역 참조이 지금은 구조체에있어 있으며, 그 필드를 얻을 수 있습니다. 직접 또는 역 참조 필드를 가져 와서 현장을 - 나는이 값이어야합니다 같아요. 하지만 이곳은 그냥 구조체가 아닌 구조체에 대한 포인터가 좀있어서 .. 그래서 난 화살표를 사용할 수 없습니다. 그러나 이런 건 우리가 모든 노드에 대해 수행 할 수 있습니다. 오, 맙소사. 이 6, 7, 3입니다. 그런 다음 우리는 나무의 가지를 설정할 수 있습니다, 우리는 7 할 수 있습니다 - 우리는 그 왼쪽 3를 가리켜 수 있습니다. 그럼 어떻게 그렇게 우리합니까? [학생 이해할 수없는] >> 그래. node3의 주소, 당신이 주소를 가지고 있지 않은 경우, 그냥 컴파일되지 것입니다. 그러나 이러한 다음 노드에 대한 포인터임을 기억나요. 그래, 9 가리켜 야합니다 3는 6 오른쪽에 지정해야합니다. 이 모든 준비가 생각합니다. 의견이나 질문? [학생, 이해할 수없는] 루트 7가 될 것입니다. 우리는 노드를 말할 수 * PTR = 또는 루트 = & node7. 

우리의 목적을 위해, 우리는 삽입 처리 할 것 그래서 우리는이 이진 트리에 삽입 할 수있는 기능을 작성하려는거야 그리고 삽입은 필연적으로이 나무에 대한 새로운 노드를 만들 malloc를 호출 할 수 있습니다. 그래서 결국은 사실과 혼란 얻을 수있는 몇 가지 노드 스택에 현재 와 다른 노드 우리가 그들을 삽입 할 때 힙에 종료 할 수 있습니다. 이 완벽하게 유효하지만 유일한 이유는 우리는 스택에이 작업을 수행 할 수 우리가 알고있는 이러한 인위적인 예이기 때문입니다 나무는 7, 3, 6, 9로 건설 될 예정입니다. 우리가이하지 않은 경우, 우리는 처음에 malloc 할 필요가 없습니다 것입니다. 우리는 조금 나중에 보 겠지만, 우리는 malloc'ing해야합니다. 지금은 스택에 넣어 완벽하게 합리적 하지만 우린 malloc 구현이 변경 보자. 따라서 이러한 각각의 지금 뭔가 같은 것입니다 노드 * node9 = malloc (sizeof (노드)). 그리고 지금 우리는 우리의 검사를해야 할거야. (== NULL node9)가있는 경우 - 제가 그렇게 싫었 어 - 1을 반환하고, 지금은 포인터이기 때문에 다음에 우리가, node9->을 수행 할 수 값 = 6, node9 -> 왼쪽 = NULL, node9 -> 오른쪽 = NULL, 우리는 이러한 노드 각각에 대해 그렇게 할거야. 대신에, 그럼 별도의 함수의 내부하자. 하자, 그 노드 * build_node 전화 이 우리는 허프만 코딩을 위해 제공하는 API에 다소 비슷합니다. 우리는 나무를 위해 당신에게 초기화 기능을 제공 와 deconstructor 그 나무와 숲에 대해 동일한에 대해 "기능". 

그래서 여기에 우리가 초기화 기능을 할거야 단지 우리를 위해 노드를 구축합니다. 그리고 정확히 같은 꽤 많이 볼거야. 그리고 난 게으른 될거야 있으며, 변수의 이름을 변경 않아 node9는 더 이상 의미가 없잖아에도 마찬가지입니다. 아, node9의 가치는 6 말았어야 같아요. 이제 우리는 node9를 반환 할 수 있습니다. 그리고 여기에 우리는 null 반환해야합니다. 모두가 저 빌드 - 어 - 노드 기능에 동의합니까? 이제 우리는 주어진 값과 널 포인터가있는 모든 노드를 만들 것을 호출 할 수 있습니다. 지금 우리가 그를 호출 할 수 있습니다, 우리는 노드 * node9 = build_node (9) 할 수 있습니다. 그리고의는하자. . . 6, 3, 7, 6, 3, 7. 그리고 지금 우리는 같은 포인터를 설정하려면 지금 제외하고는 모든 포인터의 관점에서 이미 그래서 더 이상의 주소를 필요가 없습니다. 좋아요. 그래서 내가하고 싶은 마지막 것은 뭐죠? 내가 뭘하지 않는다는 오류 검사가 있습니다. 노드 수익 (ROI)을 어떻게 구축합니까? [학생, 이해할 수없는] >> 그래. malloc에​​ 실패하면 null을 반환합니다. 그래서 천천히 대신 각각에 대한 조건을 다하고을 여기에 내려 놓고거야. 경우 (node​​9 == NULL, 또는 - 심지어 간단, 이 단지 그렇지 않으면 node9 동일합니다. 그렇지 않으면 node9하지 않았거나 node6하지 않았거나 node3, 아니면 node7 따라서, 1을 반환합니다. 우리가 malloc에​​ 실패했습니다거나 인쇄해야합니다. [학생]뿐만 아니라 null로 같은 거짓입니까? [보덴] 모든 제로 값은 false입니다. 따라서 null은 제로 값입니다. 제로는 제로 값입니다. 거짓 제로 값입니다. 모든 - 꽤 많이 단 2 제로 값은 널 (null)과 제로이며, 거짓은 제로로 정의 단지 해시입니다. 우리가 전역 변수를 선언 않을 경우 그날이 적용됩니다. 여기 노드 * 루트를해야 했죠 경우 다음 - 전역 변수에 대한 좋은 점은 항상 초기 값을 가지고 있다는 것입니다. 그 함수 사실이 아니라고, 어떻게 안에서의, 우리가있는 경우와 같은, 노드 * 또는 노드 X. 우리는 무슨 생각 x.value, x.whatever를가 없습니다 또는 우리는 그들을 인쇄 할 수 있으며 임의의 수 있습니다. 그래서 전역 변수의 사실이 아닙니다. 따라서 노드 루트 나 노드 X. 기본적으로 글로벌의 모든 일이 아니라면 명시 적으로 어떤 값으로 초기화 의 값으로 0 값을 수 있습니다. 그래서 여기, 노드 * 루트, 우리는 명시 적으로 아무것도에 초기화하지 않습니다 그래서 기본 값은 포인터의 제로 값입니다, null이됩니다. X의 기본 값은 x.value이 0 인 것을 의미 것입니다 x.left가 null이며, x.right가 null입니다. 이 구조체가되도록 있기 때문에, 구조체의 필드의 모든 제로 값이 될 것입니다. 우리는하지만, 여기서는 그런 사용할 필요가 없습니다. [학생] structs는 다른 변수보다 다른, 다른 변수는 쓰레기 값은, 이것들은 제로인가요? 너무 [보덴] 기타 값입니다. 따라서 X에서, x는 0이 될 것입니다. 이 전역 유효 영역에있어 경우, 초기 값이 있습니다. 좋아요 >>. [보덴]도 당신이 또는 제로를 준 초기 값입니다. 나는이 모든을 담당한다 생각합니다. 

좋아요. 그래서 질문의 다음 부분은 묻습니다 "이제 우리는 포함되어라는 함수를 작성하려면 BOOL의 프로토 타입을 int 값이 포함되어 있습니다. " 우리는 BOOL은 int 값을 포함하지 않을 수 있습니다. 우리 프로토 타입은 다음과 같은 꼴 BOOL은 (int 값이 포함되어 있습니다. 그리고 우리는 그것을 트리를 통과 할거야 그것은 그 값을 가지고 있는지 확인해야한다고. 따라서 노드 * 나무). 좋아요. 그리고 우리는 같은 뭔가를 호출 할 수 있습니다 우리는 printf 또는 뭔가를 할 것입니다. 6, 우리의 뿌리를 포함합니다. 하나 또는 사실을 반환해야 함 포함 된 반면 5 뿌리는 false를 반환해야합니다. 그래서를 구현하는 두 번째를. 당신도 반복적으로 또는 반복적으로 할 수 있습니다. 우리가 물건을 설정 한 방법에 대한 좋은 것은, 그것은 훨씬 쉽게 우리의 재귀 솔루션을 자체적으로 글로벌 - 변수 방법보다. 우리가있는 경우는 int 값 포함되어 있기 때문에, 우리는 하위 트리를 recursing 방법이 없습니다. 우리는 우리 하위 트리를 recurses 별도의 도우미 기능을 가지고 있어야합니다. 하지만 우리가 변경 한 이후는, 인수로 나무를 사용하려면 어떤 항상 맨 처음에 있었어야 이제 우리는 재귀 호출을 더 쉽게 할 수 있습니다. 따라서 반복 또는 재귀, 우리는 모두 이상 갈거야 하지만 우리는 매우 쉽게되는 백업이 재귀 끝을 볼 수 있습니다. 좋아요. 사람이 우리가 일을 할 수있는 일이 있습니까? 

[학생] 나는이 솔루션을 반복적있어. >> 좋아, 반복. 좋아요, 좋아 보입니다. 그래서,을 통해 문의 걸어 줄까? [학생] 그래. 그래서 나무의 첫 번째 노드를 가져 오기 위해 임시 변수를 설정합니다. 그리고 난, 온도가 동일한 null을하지 않는 동안으로 고정 그래서 트리에서 여전히 동안 것 같아요. 값이 값 같은 경우 그리고 온도에 가리키고 있다는 지금 그 값을 반환합니다. 그 오른쪽이나 왼쪽에 있다면 그렇지 않으면, 확인합니다. 혹시 더 이상 나무가없는 곳 상황을했다면, 가 종료 루프를하고 false를 반환합니다 - 그럼 반환합니다. [보덴] 좋아. 그래서 좋은 것 같습니다. 누구에 어떤 의견이? 나는의 정확성에 댓글이 없습니다. 우리가 할 수있는 한 가지이 사람입니다. 아, 그건 좀 longish을 시작합니다. 나는 그걸 고칠거야. 좋아요. 

모두 삼원 작동 방식 기억해야합니다. 확실히 과거에 퀴즈되었습니다 즉, 당신에게 3 원 연산자와 함수를 제공 그리고 삼원를 사용하지 않는 일을, 말이 번역. 나는 삼원를 사용하는 생각 할 때이 매우 흔한 경우입니다하면 일부 조건은 뭔가 변수를 설정, 어디서하는 경우 다른 다른 뭔가를 같은 변수를 설정합니다. 자주 썼다로 변환 할 수 있다는 것이 바로 그 곳이에 해당 변수를 설정 - 또는, 글쎄, 이건 사실이야? 그런 다음이 다른이. [학생] 첫 번째 사실, 맞다면입니까? [보덴] 그래. 난 항상 읽어 방식은, 온도, 임시 값보다 더 큰 가치를 동일 다음이 다른이. 이 질문을 물어 보는거야. 가 큰가요? 그런 다음 첫 번째 일을. 다른 두 번째 일을. 난 거의 항상 - 콜론, 난 그냥 - 내 머리에, 나도 다른 읽습니다. 

사람이 재귀 솔루션이 있습니까? 좋아요. 우리가가는거야이 사람 -은 이미 훌륭한 될 수 하지만 우리는 더 만들려​​고하고 있습니다. 이 거의 똑같은 생각입니다. 이건 그냥, 음, 설명 하시겠습니까? [학생] 그래. 그래서 우리는, 나무가 먼저 null로되어 있지 않은지 확인하는거야 나무가 null 경우 다음 우리가 그것을 발견하지 않았기 때문에 false를 반환하는거야 때문입니다. 그리고 나무가 아직 거기 있다면, 우리는로 이동 - 값이 현재 노드 인 경우 먼저 확인합니다. 이 경우 TRUE를 반환하고, 왼쪽 또는 오른쪽에 있지 않은 경우 우리는 재귀 호출. 그 소리는 적절한합니까? >> 음. (계약) 그래서 거의 상태가됩니다 - 반복 솔루션 구조적으로 매우 유사. 그것은 대신 recursing의, 우리는 잠시 동안 루프를 가지고 단지. 그리고 나무가 동일한 null을하지 않습니다 여기에 기본 케이스 우리가하는 동안 루프의 탈옥하는 아래의 조건이었다. 그들은 매우 비슷 해요. 그러나 우리는 더 이상이 한 단계 데려 갈거야. 이제, 우리는 여기에 같은 일을 할. 우리가이 라인 모두에서 같은 일을 되돌아 공지 사항, 경우를 제외하고 하나의 인자가 다릅니다. 그래서 우리는 삼원로 만들거야. 나는 옵션 부딪히면, 그것은 상징했다. 좋아요. 그래서 우리가 돌​​아 간다하면 해당이 포함되어 있습니다. 일이 이렇게 확대, 음, 여러 줄로되고 있습니다. 보통 문체있어, 저는 많은 사람을 생각하지 않아요 화살표 뒤에 공백을 넣어,하지만 난 당신이 일관 경우, 괜찮아요 같아요. 값이 나무 값보다 작 으면, 우리는, 나무 왼쪽에있는 재귀 호출 원하는 다른 우리는 나무 오른쪽에있는 재귀 호출하고 싶습니다. 그래서 그런 표정이 작은 만드는 단계 하나였습니다. 이 모양을 낮춤의 두 단계 - 우리는 여러 줄이 분리 할 수​​ 있습니다. 좋아요. 이 작은 보이게의 2 단계는 여기 그래서 반환 값은 트리 값을 동일, 또는 무엇이든이 포함되어 있습니다. 

이 중요합니다. 그가 수업 시간에 명시 적으로 말한다면 그건, 잘 모르겠어요 그러나 그 단락 회로 평가라고. 여기 아이디어는 값 == 나무 값입니다. 그게 사실이라면,이 사실, 우리는 원하는 '또는'그 여기에 무엇이든을 갖추고 있습니다. 그래서, 여기에 무엇이든 생각없이 반환 할 전체 표현은 무엇입니까? [학생] 진정한? >> 네, 때문에 아무것도 진실, or'd - 아무와 함께 또는 진정한 or'd 반드시 사실입니다. 따라서 가능한 한 빨리 우리가 반환 값 = 트리 값을 참조로 우리는 TRUE를 반환거야. 도 재귀 호출로 이동하지 않는 것은 더 라인을 포함하고 있습니다. 우리는 더 이상이 한 단계를 취할 수 있습니다. 반환 나무는 동등 널 (null)이 모두하지 않습니다. 그것은 한 줄 기능을했다. 이것은 또한 단락 회로 평가의 예입니다. 그러나 지금은 같은 생각 - 대신 - 그래서, 만약 나무가없는 평등 한 널 않습니다 - 잘 또는, 나무가 같은 널을하면되는데,이, 나쁜 경우입니다 나무가 null이 동일 경우, 첫 번째 조건은 false가 될 것입니다. 뭐든지 anded 따라서 허위 어떻게하실 건가요? [학생] 거짓입니다. >> 그래. 이것은 단락 회로 평가의 나머지 절반이다 곳 나무, 우리는 더 갈 같지 않음 null이 안 간다 않는 경우 - 나무가 동일한 null을 수행하는 경우 나, 우리는 가치 == 나무 값을하지 않을 수 있습니다. 우리는 즉시 false를 반환하는거야. 이 단락 회로 평가하지 않은 경우 이후 어떤이 중요합니다 나무가 동일한 null을 수행하는 경우 다음이 두 번째 조건은, 감금 오류에 갈 나무> 값은 널 (null)을 dereferencing 때문입니다. 그래서 그런 걸. 이 할 수 있습니다 - 한 번 이상 이동. 이,이와 함께 한 줄을 벌어 또한 아주 흔한 일이 하지만, 여기 아마 조건에서 일반적인 일이 아닙니다 하지만 (나무! = NULL, 그리고 나무> 값 == 값), 뭐든지합니다. 이것은 아주 일반적인 상태이며, 어디에서 대신 문제의 이 IFS에이 침입하는 곳, 나무 널입니까? 좋아,이 null 아니라, 그래서 지금은 값 같은 나무 값? 이 작업을 수행합니다. 대신,이 조건이 잘못을 감금하지 않습니다 이 널 (null) 일 경우는 탈출합니다 때문입니다. 당신의 나무가 완전히 잘못된 포인터 인 경우 음, 내 생각, 그것은 여전히​​ 잘못을 감금 할 수 있습니다 나무가 null 인 경우이지만 잘못을 감금 할 수 없습니다. 가 널 (null)이라면 본 적 처음에 포인터를 역 참조하기 전에, 그것은 탈출합니다. [학생]이 소위 게으른 평가입니까? 

[보덴] 게으른 평가는 별도의 문제입니다. 게으른 평가는, 당신이 값을 요청보다 같​​습니다 당신은 가치의 종류를 계산하도록 요청하지만 당신은 즉시 필요하지 않습니다. 당신이 실제로 필요 때까지 그래서는 평가되지 않습니다. 이 정확히 똑같은 일이 아니라, 퍼레이드 pset에 우리가 "천천히"을 (를) 쓸 수 있다고 말한다. 우리가 실제로 쓰기를 버퍼링 때문에 우리가 할 이유는 - 우리는 한 번에 각각의 비트를 작성하지 않으 또는 한 번에 각각의 바이트는, 우리는 대신 바이트의 덩어리를 얻을 싶습니다. 우리가 바이트 덩어리가되면 그 다음에 우리는을 쓸 수 있습니다. 당신은 작성을 부탁에도 불구하고 - 그리고 fwrite와 fread는 것은 같은 종류의 작업을 수행. 그들은 당신의 읽고 쓰기를 버퍼. 당신은 즉시 쓰기를 요구하더라도, 아마 안돼. 그리고 당신은 일을 기록 할 것되어 있는지 확인 할 수 없습니다 당신이 hfclose 전화이든 그 때까지입니다 이라하는, 좋아, 내 파일을 닫 내가 더 나는 아직 작성하지 않은 모든를 써서 의미한다. 그것은 더 모든 걸 쓸 필요가 없다 이 파일을 닫는 후 때까지이 필요합니다. 그래서 그가 뭘 게으른거야 - 일해야 될 때까지 기다립니다. 이 - 51을하면 더 자세히로 갈 게요 51에서 OCaml과 모든, 모든 재귀 때문입니다. 더 기본적으로 솔루션을 반복 없습니다. 모든 재귀, 그리고 게으른 평가입니다 상황이 많이 중요 할 것입니다 당신은 천천히 평가하지 않은 경우 어디에, 그 의미 - 예 무한대 길이 스트림입니다. 이론적으로, 당신은 1-2-3-4-5-6-7의 스트림으로 자연의 숫자 생각할 수 그럼 천천히 평가 되가고 있습니다. 내가 열 번째 번호를 원하는 말한다면, 그래서 10 번까지 평가할 수 있습니다. 나는 백 번호를 원하는 경우, 나는 백 번까지 평가할 수 있습니다. 게으른 평가없이, 다음 즉시 모든 숫자를 평가하려고거야. 당신은 영원히 많은 숫자를 평가하고, 그는 불가능합니다. 따라서 상황이 많이 있습니다 곳 게으른 평가 일 일을 얻는 데 불과 필수적입니다. 

이제 우리는 삽입이 될 것입니다 곳 삽입을 작성하려면 마찬가지로 그 정의에 변화. 그래서 지금 당장은 BOOL 삽입 (int 값)가 있습니다. 우리는 BOOL 삽입 (int 값, 노드 * 나무)에있는 변경거야. 우리는 실제로 약간 다시 변경 할거야, 우리는 왜 볼 수 있습니다. 그리고하자, 그냥 그것의 대체를 들어, build_node 이동 우리는 함수 프로토 타입을 작성하지 않아도되도록 위의 삽입합니다. 어떤은 삽입에 build_node를 사용하여 될 거라는 생각이 힌트입니다. 좋아요. 거기에 시간이 좀 걸릴. 그에서 끌어하려는 경우 내가 수정을 구했다는 생각이 또는, 적어도, 지금은 했어요. 나는 삽입의 논리에 대해 생각하는 약간의 휴식을 원 당신이 생각 할 수없는 경우. 기본적으로, 당신은 어느 잎에 삽입됩니다. 제가 1 삽입하면, 그냥은 필연적으로 하나를 삽입 할거야 - 나는 검은 색으로 변경됩니다 - 금방 여기에 1을 삽입합니다. 제가 4 삽입하는 경우 또는, 나는 여기에 4 삽입 할 싶습니다. 더 당신이 뭘해도 상관 그래서, 당신은 잎에 삽입 할데도 못가. 당신이해야 할 모든이 노드에 얻을 때까지 트리를 반복 is 그 노드의 부모, 새로운 노드의 부모, 여야합니다 그리고 여부에 따라, 그 왼쪽 또는 오른쪽 포인터를 변경 그것은보다 크거나 현재 노드보다 적은 있습니다. 새 노드를 가리 키도록 해당 포인터를 변경합니다. 그래서, 나무를 반복하여 새 노드에 잎 지점을 확인합니다. 또한 이전 상황의 유형을 금지 이유에 대해 생각 가 정확 어디 이진 트리를 구축 곳 당신은 단지 하나의 노드를 바라 보았다, 경우 당신은 모든 방법을 반복한다면 9 7 왼쪽에이었다. 그럼 그거부터,이 시나리오에서 불가능 - 에 대해 9 무언가를 삽입 생각하고, 매우 첫 번째 노드에서 나는 7 참조하고 난 그냥 오른쪽으로 갈 게요거야. 그래서, 잎으로 이동하여 삽입 아니라면, 내가 뭘해도 상관 없다 하고 적절한 알고리즘을 사용하여 잎까지, 나 7의 왼쪽에있는 9 삽입 할 불가능할 거 같아 최대한 빨리 7 쓰러져서 오른쪽으로 갈거야 때문입니다. 사람이로 시작 할 일이 있습니까? [학생] 알아요. >> 물론이지. [학생, 이해할 수없는] [기타 학생, 이해할 수없는] [보덴]는 그것은 감​​사있어. 좋아요. 설명해 주실 래요? 

우리가 삽입 된 것으로 알고 있기 때문에 [학생] 나무의 끝에서 새로운 노드, 나는 반복적으로 나무를 통해 반복 나는 null로 지적 노드에 도착 할 때까지. 그리고 제가 오른쪽 또는 왼쪽에 하나 넣어하기로 결정 이 권리 변수를 사용하여, 어디 넣어 말해 줬어. 그리고, 기본적으로, 난 그냥 마지막 한 - 이 생성 된 새 노드에게 그렇게 임시 노드 지점 왼쪽 또는 오른쪽에 하나, 값이 오른쪽 뭔지에 따라 다릅니다. 마지막으로, 제가 테스트의 값으로 새 노드 값을 설정합니다. [보덴] 좋아, 내가 여기 문제를 참조하십시오. 이이 방법의 95 % 같다. 내가 볼 수있는 유일한 문제는, 그럼, 다른 사람이 문제를 볼 수 있습니까? 그 루프의 탈출하는 아래의 상황은 무엇입니까? [학생] 임시가 null 경우? >> 그래. 임시 널 (null) 인 경우 그래서 당신은 루프의 탈출 방법은 있습니다. 하지만 여기에 무엇을해야합니까? 필연적으로 null입니다 I 역 참조 온도. 당신이해야 할 또 다른 문제는 임시 null이 될 때까지, 그냥 추적하지 않습니다 당신은 항상 부모의 트랙을 유지하고 싶습니다. 우리는 또한 노드 * 부모를 원해, 난 우리가 널 (null)에서 처음하는을 유지할 수 있습니다 같아요. 이것은 트리의 루트에 이상한 행동을 것입니다 하지만 우리는 그로 연결됩니다. 값이 무엇이든보다 큰 경우, 온도 = 임시 좋아. 하지만 우리가 전에, 부모 = 온도. 부모는 항상 동일한 temp에가는거야? 경우 것이 있나요? 임시 null이 아닌 경우, 그럼, 무슨 일이 있어도 아래로 이동하지거야 임시 부모되는 노드 있습니다. 따라서 부모가 temp 될거야 그리고 난 아래로 온도 이동합니다. 지금 온도 널 (null)이지만, null입니다 일을 부모 부모를 가리 킵니다. 여기로, 바로 1 동일 설정 싶지 않아요. 그래서, 그래서 지금 = 1 경우, 오른쪽으로 이동 그리고 당신도하고 싶은 것 - 당신이 왼쪽으로 이동하면, 당신은 0 바로 같은 설정하고 싶습니다. 아니면 혹시 오른쪽으로 이동합니다. 그래서 지금 = 0. 오른쪽 = 1 경우, 지금 우리는 부모 오른쪽 포인터 newnode을 만들고 싶어 다른 우리는 부모 왼쪽 포인터 newnode를 제공​​하기 위해 노력하고 있습니다. 그 질문 있나? 좋아요. 그래서이 방법 우리입니다 - 음, 사실, 대신이 일을의, 우리 반은 당신이 build_node을 사용 할 것으로 예상. newnode이 null 동일하면 다음 false를 반환합니다. 그건 그거 고. 지금, 우리가 당신이 예상되는 상황이다. 

이 직원 솔루션 일 것입니다. 나는 그것에 대해 갈의 "오른쪽"방법으로 동의 하지만 완벽하게 되어도 작동됩니다. 지금은 좀 이상한 맞는 한가지입니다 나무 널로에서 시작하면, 우리는 널 (null) 나무에 전달합니다. 난 당신이 null이 나무에 전달의 동작을 정의하는 방법에 따라 달라집니다 같아요. 당신이 null이 나무에 통과하면 그렇게 생각 다음 null이 나무에 값을 삽입 유일한 값이 그 단일 노드입니다 단지는 나무를 반환해야합니다. 사람들이 그것에 동의하십니까? 당신은 어쩌면, 당신은 원하는 경우, 당신은 null이 나무에 합격 할 경우 그리고 당신이에 값을 삽입하려는 false를 반환합니다. 그게 무엇인지를 정의 할의 몫입니다. 그때 말과 처음으로 일을 - 싫어서 그런가, 당신은 문제가 그런 짓을 할거야 우리가에 대해서 글로벌 포인터가 있다면 그것은 쉽게 될 나무가 null 경우 우리는, 그래서 우리가 그것에 대해 할 수있는 건 아무 것도 없어요. 우리는 false를 반환 할 수 있습니다. 그래서 삽입을 변경거야. 우리는 기술적으로 단지 바로 지금이 순간을 변경할 수 있습니다 어떻게이 일을 통해 반복 있어요 하지만 노드에게 ** 나무를 취할 삽입을 변경하는거야. 더블 포인터. 이것은 무엇을 의미할까요? 대신 노드에 대한 포인터를 처리하는, 나는 조작 할 건데 것은이 포인터입니다. 이 포인터를 조작 할거야. 나는 직접 포인터를 조작 할거야. 아래로 생각 때문에이 의미가 - 물론, 지금은이 점은 null입니다. 내가하고 싶은 것은 null로하지 가리 키도록이 포인터를 조작 할 수 있습니다. 난 내 새 노드를 가리 싶습니다. 난 그냥 내 포인터 포인터를 추적, 경우 그때 부모 포인터를 추적 할 필요가 없습니다. 난 그냥 포인터가 null로 가리키고 있는지를 추적 할 수 있습니다 그리고 포인터가 가리키는 경우는 null로, 내가 원하는 노드를 가리 키도록을 변경합니다. 제가 포인터에 대한 포인터를 갖고 있기 때문에 그리고 그 일을 변경할 수 있습니다. 지금 당장 보자. 당신은 실제로 반복적으로 아주 쉽게 할 수 있습니다. 우리는 할까? 예, 우리는 할. 

가 재귀를 보자. 첫째, 어떤 우리의 기본 케이스는 거에요? 거의 항상 기본 케이스는, 그러나 사실은,이 까다로운 종류의 것입니다. 먼저 할 일이, 경우 (트리 == NULL) 난 그냥 우리가 false를 반환하는 것 같아요. 이 나무가되는 null이 다릅니다. 이 루트 포인터 null이되기 위해서는 포인터입니다 이는 루트 포인터가 존재하지 않는다는 것을 의미합니다. 여기로, 내가하면 노드 *은 - 그냥이 다시 보자. 노드 * 루트 = NULL, 그럼 내가 같은 일을 수행하여 삽입 한테 전화해서 및 루트에 4 삽입합니다. 따라서 & 루트, 루트 노드 * 인 경우 다음과 뿌리는 노드 **가 될 것입니다. 이 유효합니다. 여기이 경우, 나무, 또는 삽입 - 나무는 null이 아닙니다. 여기. 나무가 null가 아니라 * 나무는 null입니다, 아주 좋아하는 * 나무가 null 인 경우, 그럼 그것을 조작 할 수 있기 때문에 지금 난 그게을 가리 키도록 원하는 것을 가리합니다. 나무가 null이라면, 그건 내가 그냥 여기까지 와서 널 밝혔다 의미합니다. 이해가 안되는데. 난 그걸 아무 것도 할 수 없습니다. 나무가 null 인 경우 false를 반환합니다. 그래서 기본적으로 이미 실제 기본 케이스가 무엇인지했다. 그리고 그 거에요? [학생, 이해할 수없는] [보덴] 예. 따라서 (* 나무 == NULL)합니다. 이 여기에 사건에 관한 내 빨간색 포인터가 포인터 인 경우 I가에 초점을 맞춘 곳, 나는이 포인터에 초점을 맞춘 것처럼, 그래서 지금이 포인터에 초점을거야. 지금이 포인터에 초점을거야. 그래서, 만약 내 노드 ** 나만의 빨간색 포인터, 가 본 - * 경우, 빨간 포인터가,, 다시는 null입니다 그 내가 포인터 그 점에 초점을거야 경우에 오전을 의미합니다 - 이 잎에 속하는 포인터입니다. 내 새 노드를 가리 키도록이 포인터를 변경하고 싶습니다. 여기에 다시 와요. 내 newnode는 노드 * N = build_node (값)가 될것이다 다음에 n, N = NULL 경우 false를 반환합니다. 아니면 우리는 포인터가 현재 가리키고 있는지 변경하려면 이제 새로 지어진 노드를 가리 킵니다합니다. 우리는 실제로 여기 할 수 있습니다. 대신 n을 말하는, 우리는 말 * 나무 = * 나무 바랍니다. 누구나 다 알 겠어? 그 포인터에 대한 포인터를 처리하여, 우리는 그들에게 가리 싶은 일을 가리 키도록 널 포인터를 변경할 수 있습니다. 그게 우리 기지 케이스입니다. 

이제 재발, 또는 재귀, 우리가하고있어 다른 모든 recursions과 매우 유사가 될 것입니다. 우리는 가치를 삽입 할 거예요 지금은 다시 삼원를 사용하는거야,하지만 우리의 조건은하실 건가요? 우리는 우리가 왼쪽 또는 오른쪽으로 이동할지 여부를 결정 무엇을 찾고 무엇입니까? 별도의 단계를 수행하자. 경우 (값 <) 뭐? [학생] 나무의 가치? [보덴] 그래서 현재 걸 기억 - [학생 이해할 수없는] [보덴]이 (가) 그래, 바로 여기, 보자 그이 녹색 화살표 나무가 현재의 한 예입니다,이 포인터에 대한 포인터입니다. 그게 내가 3 포인터에 대한 포인터입니다 의미합니다. 역 참조는 두 번 그럴싸한. 내가 무슨 짓을 - 어떻게 그런 짓을합니까? [학생] 번 역 참조하고 수행 화살표를 그런 식으로? [보덴]이 자 (* 나무가) 번 역 참조이고, -> 값 내게는 간접적으로 가리키는 것만 노드의 값을 제공 예정이다. 그래서 또한 당신이 그렇게 원하는 경우가 tree.value을 ** 쓸 수 있습니다. 작동 중. 그런 경우라면, 나는 값이 삽입 호출하고 싶습니다. 그럼 내 업데이트 노드는 **하실 건가요? 나는 왼쪽으로 가고 싶어하므로 ** tree.left 내 왼쪽 될 것입니다. 그리고 그 일에 대한 포인터를 원하는 그래서 왼쪽은 NULL 포인터가되는 것을 포기 끝나는 경우는, 내 새 노드를 가리 키도록을 수정할 수 있습니다. 

또 다른 경우는 매우 유사 할 수 있습니다. 의 실제 제 삼원 지금 당장 만들어 보자. 경우 값 <(** 나무). 값을 값을 삽입합니다. 그런 다음 우리는 왼쪽으로 우리 **를 업데이트하려면 다른 우리는 오른쪽으로 우리 **를 업데이트하고 싶습니다. [학생] 그 포인터에 포인터를 얻을합니까? [보덴]을 기억 - ** tree.right가 노드 별입니다. [학생, 이해할 수없는] >> 그래. ** tree.right이 포인터 같은 거입니다. 그럼에 대한 포인터를 활용하여, 그게 내가 원하는 걸 할 수 그 사람에 대한 포인터의. 우리가 두 포인터를 사용하는 이유 [학생] 우리는 다시 갈 수 있을까요? [보덴] 그래. 그래서 - 아니, 전에 수, 그 솔루션 이 포인터를하지 않고 그 일을하는 방법이었다. 당신은 두 개의 포인터를 사용하여 이해 할 수 있어야합니다 이는 청소기 솔루션입니다. 또한, 내 나무하면 어떤 일이 벌어지는 지, 그런 것을 - 내 뿌리가 null이라면 어떻게됩니까? 바로 여기이 경우 작업을 수행하면 어떻게됩니까? 따라서 노드 * 뿌리는 = NULL, & 루트에 4 삽입합니다. 루트는이 이후로 어떻게되어 가고있는 건지? [학생, 이해할 수없는] >> 그래. 루트 값은 4가 될 것입니다. 루트 왼쪽은 null 될 것입니다, 루트 권한이 null가 될 것입니다. 경우 어디에서 우리는 주소로 루트를 통과하지 못했습니다 우리는 루트를 수정할 수 없습니다. 경우 트리 - 루트가 null이었고, 우리는 False를 반환했습니다. 우리가 할 수있는 일은 아무것도 없습니다. 우리는 빈 트리에 노드를 삽입 할 수 없습니다. 하지만 지금 우리는 수, 우리는 한 노드 트리에 빈 나무를합니다. 어떤은 일반적으로이 일을하고 싶은 거지 예상 방법입니다. 

또한,이보다 훨씬 짧은 또한 부모의 트랙을 유지하고, 그래서 당신은 모든 방법을 반복합니다. 지금은 내가 내 부모를 가지고 있고, 난 그냥 무엇이든 건 내 부모 오른쪽 포인터가 있습니다. 우리가 반복적으로 이런 짓을 대신, 그것은 잠시 동안 루프와 같은 생각 했어. 대신 내 부모 포인터를 처리해야하는, 대신 현재 포인터가있을 거예요 나는 바로 내 새 노드를 가리 키도록 수정 겁니다. 나는 왼쪽을 가리키는 지 알수 처리 할 필요가 없습니다. 나는 오른쪽으로는 눈치 여부를 처리 할 필요가 없습니다. 그것은이 포인터가, 내가 새 노드를 가리 키도록으로 설정 거예요 뭐든지 뿐이야. 모두가 어떻게 작동하는지 이해? 그렇지 않다면 왜 우리가 이렇게하고 싶지 않습니다 하지만 적어도이 솔루션으로 작동? [학생] 어디 ​​TRUE를 반환합니까? [보덴] 바로 여기 일거야. 우리가 올바르게 삽입하면 TRUE를 반환. 다른, 거기에 우리는 삽입 반품 무엇이든을 반환 할거야. 

그리고 재귀 함수에 대한 특별 뭐죠? 이 때문에 오래 우리는 몇 가지 최적화와의 연동으로, 재귀 꼬리입니다 , 그 인식하고이에서 스택 오버 플로우를하지 않습니다 우리 나무 만 또는 10 만 달러의 높이가 경우에도 마찬가지입니다. [학생, 이해할 수없는] [보덴]이 나는 대쉬에서합니까 생각 - 무엇을 최적화 수준 인식 할 꼬리 재귀가 필요합니다. 나는 인식 생각 - GCC와 꽝 또한 최적화 수준에 대해 서로 다른 의미가 있습니다. 나는이 꼬리 재귀를 인식 할 수 있는지에 대한 DashO 2, 야하고 싶은 말은. 그러나 우리는 - 당신은 Fibonocci 예제 같은 거 만들 수 있습니다. 가 건설하는 것은 어렵습니다 때문에, 이걸 테스트 할 쉬운 일이 아니지 너무 크고 이진 나무. 하지만 그래, 난 그 DashO 2, 생각 당신이 DashO 2 컴파일한다면, 그것은 꼬리 재귀을 찾습니다 및 최적화 아웃. 가로 돌아 가자 - 삽입은 말 그대로이 필요 마지막으로 한 일이야. 여기에 삽입로 돌아가 보자 우리가 같은 생각을 할 가는지. 아직 완전히 처리 할 수​​ 없다는 결함을해야합니다 루트 자체가 null, 또는 과거 항목은 널 (null) 인 경우 대신 부모 포인터를 처리하는, 가 포인터 to 유지 포인터의 동일한 논리를 적용 보자. 여기 있다면 우리는 우리의 노드 ** 현재 유지 우리는, 오른쪽 더이상를 추적 할 필요가 없습니다 하지만 노드 ** 현재 = & 나무. 그리고 이제 동안 루프는 *의 현재가 동일한 null을하지 않지만 될 것입니다. 더 이상 부모를 추적 할 필요가 없습니다. 왼쪽과 오른쪽을 추적 할 필요가 없습니다. 우리가 이미 온도를 사용하고 있기 때문에 난 그에게 온도를 호출합니다. 좋아요. 그래서, 만약 (값> * 임시) 그런 다음 & (* 온도) -> 오른쪽 다른 TEMP = & (* temp) -> 떠났다. 그리고 지금이 시점에서,이 동안 루프 후, 아마도 곧 반복적으로 재귀 적으로보다 생각보다 쉽게​​ 때문에 만이 작업을 수행 하지만이 동안 루프 후, * 온도 우리가 변경하고자하는 포인터입니다. 

전에, 우리는 부모를 갖고 있었는데, 우리는 부모 왼쪽 또는 부모 오른쪽 중 하나를 변경하고 싶어 우리는 부모 권리를 변경하고자하는 경우, 그리고 * 온도 부모 맞아, 우리는 직접 변경할 수 있습니다. 여기로, 우리는 * TEMP = newnode을 할 수 있으며, 바로 그 거에요. 통지 그래서 우리가이에서 한 코드의 줄을 꺼내했다. 추가 노력이 모두 부모의 트랙을 유지하기 위해. 여기, 우리가 그냥 포인터로 포인터를 추적한다면, 우리는 이제 이러한 모든 중괄호를 제거하려고해도, 짧게 보이게. 이 이제 동일한 솔루션입니다 하지만 코드를 적은 라인. 일단 당신이 유효한 솔루션으로이 인식 시작 건 상관도 같은보다 약 이유로 쉽게 왜 내가 INT 오른쪽이 플래그있어? 그게 무슨 뜻 이죠? 아, 뜻 야 바로 갈 때마다, 난 그것을 설정해야합니다 내가 떠난 가면 다른 나는 제로로 설정해야합니다. 자, 내가 그것에 대해 이유 필요 없어, 그것은 생각 만 쉬워졌습니다. 질문이 있으십니까? [학생, 이해할 수없는] >> 그래. 그래, 그럼 마지막 비트에서 - 내 말은, 우리가 할 수있는 한 빠르고 쉽게 기능 같네요 자 - 함께가, 내 생각에이 기능을 포함하고 시도 및 쓰기 가 이진 검색 트리인지 어느 쪽이던 상관하지 않습니다. 이 함수는 TRUE를 반환해야합니다 포함되어 있습니다 경우 어느 곳이 일반 이진 트리에 우리가 찾고있는 값입니다. 그래서 우리는 반복적으로 할 것 다음의 처음 재귀 적으로하자합니다. 이 정말 짧은 될 것입니다 때문에 실제로, 그것을 함께 할 수 있습니다. 

내 기본 케이스는 무엇을 할 것입니까? [학생, 이해할 수없는] [보덴] 그래서, 만약 (트리 == NULL), 그 다음은? [학생] 거짓으로 돌아갑니다. [보덴]이 아니면, 음, 난 다른 필요하지 않습니다. 경우 내 다른 기본 케이스했습니다. [학생] 나무의 가치? >> 그래. 그래서 (나무> 값 == 값을합니다. 우리가 노드 ** s의 노드 *로하지 보셨습니까? 이 포함은 노드 **를 사용할 필요하지 않습니다 우리는 포인터를 수정하지 않습니다 때문입니다. 우리가 그들을 가로 지르는하고 있습니다. 그렇게되면, 우리는 TRUE를 반환하고 싶습니다. 아니면 우리는 아이들을 통과하고 싶습니다. 그래서 우리는 왼쪽으로 모든 일이 덜 여부에 대해 이유를 할 수 없습니다 그리고 오른쪽에있는 모든 높습니다. 그래서 우리의 조건이 여기 것입니다 - 또는, 우리는 무엇을해야하지? [학생, 이해할 수없는] >> 그래. 돌아 가기이 포함 (값, 나무 -> 왼쪽) 또는 (값, 나무> 오른쪽)가 포함되어 있습니다. 그리고 바로 그 거에요. 그리고, 일부 단락 회로 평가가 발견 어디 우리가 왼쪽 트리에서 값을 찾으려면 어떻게하면 우리는 오른쪽 나무보고 할 필요가 없습니다. 전체 기능들입니다. 이제 반복적으로 한번 해보자 구 이는 덜 좋은 될 것입니다. 우리는 노드 * 현재 = 나무의 일반적인 시작 할게요. 동안 (현재! = NULL). 신속하게 문제를 만나러가는. 만약 현재 - 여기서, 우리가이 탈옥 경우, 그리고 우리가 볼을 떨쳐 버리게 한, 그래서 false를 반환합니다. (현재 -> 값 == 값), TRUE를 반환합니다. 이제, 우리가 여기에 있습니다 - 우리는 왼쪽이나 오른쪽으로 이동할지 여부를 모르겠어요. 따라서 임의로, 그냥 왼쪽으로 가자. 분명히 내가 전부 포기했습니다 문제로 실행했습니다 - 나는 문제가 있으면 나무의 왼쪽을 확인합니다. 난 아무의 오른쪽 자식 아무것도 확인하지 않습니다. 이 문제를 해결하려면 어떻게해야하나요? [학생] 당신은 스택에 왼쪽과 오른쪽을 추적해야합니다. [보덴] 그래. 그래서이가 만들어 먹자 구조체 목록, 노드 * N, 다음 노드 ** 다음은? 전 괜찮아요 작동 생각합니다. 여기까지 - 우리는 왼쪽, 또는 let's 넘어 가고 싶어요. 구조체 목록 목록 =이, 그것은 시작합니다 이 구조체 목록에서 아웃. * 목록 = NULL. 그래서 우리의 연결 목록이 될거에요 우리가 이상 생략 한 하위 트리의. 우리는 지금 왼쪽 통과 거예요 그러나 우리는 필연적으로 오른쪽으로 돌아와야 때문에, 우리는 우리의 구조체 목록의 내부 오른쪽을 유지거야. 그런 다음 우리는 new_list 또는 구조체를해야합니다 구조체 목록 * new_list = malloc (sizeof (목록)). 난 오류 검사 무시하는거야,하지만 당신은 경우 그건 null을 확인해야합니다. 가 가리 키도록거야 노드를 New_list - 난 여기를 원 왜 오, 그게. 이 두 번째 구조체 목록을 가리 키도록거야. 그 목록 작업을 연결 단지 방법입니다. 이 정수 연결리스트와 동일합니다 를 제외하고 우리는 노드 *로 정수를 대체하고 있습니다. 그것은 정확히 같은거야. 그럼 new_list 우리 new_list 노드의 값 현재 -> 오른쪽 될 것입니다. 우리의 가치 new_list -> 옆에있는 우리의 원본 목록 될 것입니다, 그리고 우리는 new_list를 가리 키도록 목록을 업데이트거야. 

이제 우리는, 당기는 가지 방법의 일종이 필요합니다 우리는 전체 왼쪽 하위 트리를 통과 한 것. 이제 우리는, 그것을 물건을 꺼내야 같은 현재이 Null입니다, 우리는 False를 반환하지 않습니다. 우리는 지금 새로운 목록을 외부 뽑아 줘. 이 일을하는 편리한 방법은 - 음, 사실,이 일을 여러 가지 방법이 있습니다. 누구든지 제안 사항이 있으십니까? 어디에서이 또는 어떻게이 작업을 수행해야해야하나요? 우리는 몇 분을 가지고 있지만, 제안? 대신 - 한 가지 방법 대신에 우리의 조건을 동시에하는 것 우리가 현재보고있는 것은 null이되지 않습니다 대신 우리는 우리의 목록 자체가 null이 될 때까지 계속해서 이동거야. 목록은 널 (null)가되는 것을 포기 끝나는면 그리고 우리는을 찾기 위해 이상 검색을 떨쳐 버리게했다. 하지만 그건 우리 목록의 첫 번째 일이 바로 첫 번째 노드가 될 것입니다 것을 의미합니다. 최초의 것은 될 것입니다 - 우리는 더 이상을 볼 필요가 없습니다. 따라서 목록 -> n은 우리 나무입니다. 목록 -> 다음은 null가 될 것입니다. 이제 목록은 동일한 null을하지 않지만. 현재 우리의 목록에서 무언가를 끌어 것입니다. 따라서 현재는 같은 목록 -> N로 이동합니다. 그리고 목록은 동일한 목록 -> N로 이동, 또는 목록 -> 다음 이예요. 그래서, 만약 현재 값이 값이 같습니다. 이제 우리는 우리의 권리 포인터와 왼쪽 마우스 포인터를 모두 추가 할 수 있습니다 오래 그들이 널 않는 한. 여기에, 난 우리가 그런 짓을 한 것 같아 처음부터 인치 경우 (현재 -> 오른쪽! = NULL) 그리고 우리는 우리의 목록에 노드를 삽입 할 수 있습니다. 경우 (현재 -> 왼쪽)이 추가 작업 약간이지만, 괜찮아요. 경우 (현재 -> 왼쪽! = NULL) 우리는 우리의 연결리스트에 왼쪽을 삽입 할 것 그리고 그게 있어야합니다. 우리는 반복 - 오래 우리는 목록에 게로 우리는 ... 다른 노드가 있습니다. 그래서 우리는 그 노드 살펴 우리는 다음 단계로 목록을 부활 시켰습니다. 그 노드가 우리가 찾는 값이 있으면, 우리는 TRUE를 반환 할 수 있습니다. 다른 두 우리의 왼쪽 및 오른쪽 하위 트리를 삽입 사람들이 널 안만큼, 목록에 우리는 필연적으로 그들에게 가서 수 있도록. 그들은 null이 아니었다,면 우리의 루트 포인터가 두 가지 점을 지적, 경우 목록이 null가되는 것을 포기 끝나는 그래서 처음에는 우리가 뭔가를 꺼냈다. 그리고 우리는 다시 두 가지를 넣어, 이제 목록의 크기는 2입니다. , 우리는 다시 루프로 갈 거에요, 그리고 우리가 끌어가는거야 가, 우리의 루트 노드의 왼쪽 포인터를 가정 해 보겠습니다. 그리고는 무슨 일이 계속됩니다, 우리는 모든 걸 반복하게 될 겁니다. 

이 훨씬 더 복잡 이었다는 재귀 솔루션 인치 그리고 여러 번 말을 한 재귀 솔루션은 일반적으로 솔루션을 반복적으로 공통점 많은이 있는지 확인합니다. 여기이 재귀 솔루션 짓 정확히 것입니다. 단 하나의 변화는 대신 암시 적으로 스택을 사용하여 프로그램 스택입니다 그래도 방문 할 필요가 무엇 노드의 트랙을 유지의 방법으로, 지금 당신은 명시 적으로 링크 된 목록을 사용해야합니다. 어떤 노드가 여전히 방문 할 필요 두 경우 모두에서 당신은 트랙을 유지하고 있습니다. 재귀 경우에는 그냥 쉽게 때문에 스택 프로그램 스택으로 당신을 위해 구현됩니다. 이 연결리스트, 그건 스택이납니다. 우리는 스택에 입력 한 우리가 다음에 방문 스택을 해낼 할 건지 당장. 우리는 질문 할 시간이 없어,하지만 ... [학생, 이해할 수없는] [보덴] 그래. 우리는 우리의 링크 목록을하면, 현재,이 사람을 가리 것입니다 지금 우리는이 사람에 초점을하기 위해 링크 된 목록을 발전하고 있습니다. 우리는 라인에 링크 된 목록으로 가로 지르는하고 있습니다. 그리고 나는 우리가 우리의 링크 목록과 물건을 확보해야겠군요 한 번에 true 또는 false 반환하기 전에, 우리는 필요 우리 연결리스트를 통해 반복하고 항상 여기, 내가, 추측 우리 현재 바로 동일하지 않을 경우, 이제 우리가 확보 할을 추가 현재 때문에, 잘, 우리는 완전히 목록을 잊어 버렸 을까? 그래. 그럼 우리가 여기서하고 싶은거야. 포인터가 어디있어? 현재는 있었어요 - 우리가 구조체 목록에 * 10 다음 목록을 동일 싶습니다. 무료 목록, 목록 = 임시. 그리고 경우에 우리가 TRUE를 반환 곳, 우리는 반복을해야하나요 물건을 자유롭게 우리의 연결 목록의 나머지 이상. 재귀 솔루션에 대해 좋은 점은 물건을 자유롭게하고 있습니다 당신을위한 일이 일어날 스택에서 터지는 factorings을 의미합니다. 그래서 우리는 어려운 것 -에 대한 코드의 3 라인 같은 것을이 됐어 상당히 많은 더 뭔가 어려운 것 -에 대한 코드 라인. 질문 더 있습니까? 괜찮아요. 우리는 잘해. 안녕! [CS50.TV]