왕긍정
325
2018-04-16 19:36:19 작성 2018-04-16 19:37:33 수정됨
10
457

자바스크립트로 트리(자료구조) 공부 중에 질문이 있습니다!!


안녕하세요. 자바스크립트로 자료구조를 공부 중에 있습니다. 지금은 트리를 공부하고 있는데요. 

트리에서 중위순회를 공부하는 도중에 소스코드로 설명을 해주었는데, 도무지 이해가 가지 않습니다.



this.inOrderTraverse = function(callback){
	inOrderTraverseNode(root, callback);
}

var inOrderTraverseNode = function(node, callback){
	if (node != null){
		inOrderTraverseNode(node.left, callback);  // (1)
		callback(node.key);                        // (2)
		inOrderTraverseNode(node.right, callback); // (3)
	}
}


이렇게 코드가 있습니다. 제가 트리 구조를 보면서 이해하려고 해도 안되는 부분은,

inOrderTraverseNode()이 메소드 안에서 (1)번이 실행되면 재귀메소드니까 (2)나 (3)은 실행이 안되는 것 아닌가요 ? 

책에서는 (1)번을 하고 (2)번을 하고 (3)번을 실행하여 모든 노드 값을 하나 하나 확인할 수 있다고 씌여있는데, 제가 보기에는 왼쪽 맨 밑에 있는 노드에 멈출 것 같다는 생각이 듭니다.

0
0
  • 답변 10

  • aterilio
    176
    2018-04-16 19:49:56 작성 2018-04-16 19:50:36 수정됨

    (left) (key) (right)

    이렇게 되어있고 각각 호출하면

    각각은 다시 아래와 같은 형태로 호출되겠죠.


    ------ (left) ------ ------ (key) ------ ------ (right) ------

    (left) (key) (right) / ----------------- / (left) (key) (right)


    depth 가 여기서 끝이라고 해도 left 쪽 다 돌고 최종적으로 다 리턴이 되면

    key 로 넘어가서 진행이 되고..


    말하자면 이게 수학 계산 같은건데요,

    (5 - 4) + 2 + 3 이라는 계산식이 있으면, 5 - 4 (가장 안쪽 괄호) 계산을 다 끝내고

    +2 +3 계산 마저 하는 느낌으로?


    @_@

    설명하기 어렵군요..

    1
  • 왕긍정
    325
    2018-04-16 20:15:04

    @ aterilio 님


    만약 (1)에서 재귀를 부르고 부르고 부르고 null이 될 때까지 부르고 나서 null이 되면 다시 (1)로 돌아가서 (2)를 실행하고 그 다음에 (3)을 실행하고 또 재귀를 부르고 부르다가 null이 나오면 다시 (3)으로 돌아와서 빠져나간 후 .... 

    이렇게 계속 재귀함수가 실행된다는 말씀이신거죠 ?! 

    뭔가 이해가 되는 것 같습니다 !

    0
  • yukariko
    625
    2018-04-16 20:35:05

    네 재귀는 쭉 함수를타고 더이상 함수호출이 없을때까지 내려간다음

    다시 호출했던지점으로 한단계씩 돌아가서 다음코드를 수행합니다.

    1
  • 왕긍정
    325
    2018-04-16 20:53:09

    yukariko 님

    감사합니다 ! 재귀에 대해서 이해도가 부족했던 것 같습니다 ㅎㅎ 


    0
  • aterilio
    176
    2018-04-16 20:54:55

    네 이해하신 바가 맞습니다.

    그래서 재귀에는 빠져나가는 조건이 제일 중요하다고 그러죠

    (만약 null 체크를 하지 않고 계속 호출한다고 하면... 무한 루프가 되지, 리턴되지 않으니까요)

    그나저나 아이디 링크 어떻게 하나요...? 제가 오키 초보라..;ㅁ;

    0
  • 왕긍정
    325
    2018-04-16 20:57:19

    aterilio 님

    감사합니다 !! 빠져나가는 조건이 제일 중요하군요 ! ㅎㅎ

    그냥 아이디 복사해서 붙여넣기 했어요 !!

    0
  • aterilio
    176
    2018-04-16 21:00:06 작성 2018-04-16 21:00:17 수정됨
    0
  • 르라나
    192
    2018-04-16 22:41:46
    무슨 책 보시는지 ㅎ알 수 있을까요 ㅎㅎ
    0
  • 우헤헤
    186
    2018-04-17 10:18:41

    http://book.daum.net/detail/book.do?bookid=KOR9788960777842

    0
  • 르라나
    192
    2018-04-17 14:43:31
    0
  • 로그인을 하시면 답변을 등록할 수 있습니다.