10-1

1. 1. 트리의 산술식의 내부 표현
   • 산술식의 내부 표현(polish notation)
     
     • 중위 표기법(infix notation) : left - root - right 운행 -> 산술식의 표현에서 변수 - 연산자 - 변수의 순으로 표시된다.
     • 후위 표기법(postfix notation) : left - right - root 운행 -> 산술식의 표현에서 변수 - 변수 - 연산자의 순으로 표시된다.
     • 전위 표기법(prefix notation) : root - left - right 운행 -> 산술식의 표현에서 연산자 - 변수 - 변수의 순으로 표시된다.
2. 2. 이진 트리의 삽입
   • 어떤 새로운 노드를 입력한다면 그의 키를 이용하여 이진 트리의 성질을 만족 한 어떤 자식 노드가 될 것인가의 위치를 결정하여 저장하는데 키 값을 중심으로 키 값보다 큰 수는 오른쪽 자식 노드가 되고, 키 값보다 작은 수는 왼쪽 자식 노드가 된다.
3. 3. 이진 트리의 삭제
   • 삭제할 노드를 단 노드로 대치시킨다.
   • 대치시키기 위해 선택하는 단 노드는 삭제할 노드의 왼쪽 서브 트리 내에 있고, 맨 오른쪽에 있는 단 노드이다.
   • 먼저 삭제할 노드가 단 노드일 경우에는 바로 해당 노드를 삭제한다.
   • 삭제할 노드의 왼쪽 서브 트리에 오른쪽 노드가 없는 경우 해당 노드를 삭제 한 후 왼쪽 단 노드가 빈 자리로 옮겨 간다.
   • 삭제할 노드의 왼쪽 노드에 서브 트리가 있는 경우 해당 노드를 삭제한 후 왼쪽 서브 트리의 제일 오른쪽 노드를 삭제된 노드에 채워준다.