Tree traversal

Jelkov Ahn·2021년 10월 12일
0

자료구조

목록 보기
10/11


⊙ 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
★전위 순회는 뿌리->왼쪽 자식->오른쪽 자식 순
전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6

preorder(callback) {
		callback(this.value);
    if (this.left) {
      this.left.preorder(callback)
    };
    if (this.right) {
      this.right.preorder(callback)
    };
  }

⊙ 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
★중위 순회는 왼쪽자식-> 뿌리-> 오른쪽 자식
중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6

  inorder(callback) {
    if (this.left){
      this.left.inorder(callback)
    }
    callback(this.value);
    if(this.right){
      this.right.inorder(callback)
    }
		//TODO: 전위 순회를 바탕으로 중위 순회를 구현하세요.
  }

⊙ 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문
★후위 순회는 왼쪽자식->오른쪽 자식-> 뿌리
후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0

  postorder(callback) {
    if(this.left){
      this.left.postorder(callback)
    }
    if(this.right){
      this.right.postorder(callback)
    }
    callback(this.value)
		//TODO: 전위 순회를 바탕으로 후위 순회를 구현하세요.
  }
profile
끝까지 ... 가면 된다.

0개의 댓글