트리 순회

순회(traverse) : 트리의 노드들을 차례로 방문하는 것

 

 

–전위 순회(preorder)

•자손보다 루트 노드를 먼저 방문. VLR

–중위 순회(inorder)

•왼쪽 자손, 루트, 오른쪽 자손의 순으로 방문. LVR

재귀 - 중위 순회

비재귀 - 중외 순회 (스택)

–후위 순회(postorder)

•자손을 먼저 방문한 후 루트 노드 방문

 

 

 

- 레벨 순회 : 각 노드를 레벨 순으로 순회 --> 큐 이용

레벨 순회

 

수식 트리 계산

 1. 후위 순회를 사용 (자손 먼저)

 2. 서브트리의 값을 순환 호출로 계산

 3. 비단말노드를 방문할 때 양쪽 서브트리의 값을 노드에 저장된 연산자를 이용하여 계산한다. 

 

int evaluate(TreeNode *root)
{
   if( root == NULL) //빈 트리
      return 0;
   if( root->left == NULL && root->right == NULL) //단말 노드에 방문
      return root->data; //해당 노드의 데이터 반환
   else {
      int op1 = evaluate(root->left); //왼쪽 자식 
      int op2 = evaluate(root->right); //오른쪽 자식 
      switch(root->data){ //연산자, 연산
         case '+':	return op1+op2;
         case '-':	return op1-op2;
         case '*':	return op1*op2;
         case '/':	return op1/op2;
      }
   }
   return 0;
}

- 노드 개수 세기

int get_node_count(TreeNode *node)
{
  int count=0;
  if( node != NULL ) //끝까지
    count = 1 + get_node_count(node->left)+get_node_count(node->right); //재귀
        //최상위 노드 + 왼쪽 모든 노드 + 오른쪽 모든 노드
  return count;
}