반복적 트리순회 알고리즘

소개글

이진트리의 전위 및 후위순회를 반복적 알고리즘으로 구현하였습니다.

목차

Ⅰ. Iterative preorder
1. 전위순회의 방법
2. Iterative preorder의 구현

Ⅱ. Iterative postorder
1. 후위순회의 방법
2. Iterative postorder의 구현

본문내용

Ⅰ. Iterative preorder
1. 전위순회의 방법
전위순회는 부모노드-왼쪽자식-오른쪽자식 순으로 트리를 순회하는 것으로서 recursive로 구현하면 아래와 같이 표현할 수 있다.

void pre_order(treenode *t){
if(t){
cout<<t→data<<"\n";
pre_order(t→leftChild);
pre_order(t→rigntChild);
}
}

2. Iterative preorder의 구현
전위순회는 스택을 사용하여 비재귀적으로 구현이 가능한데, 방문할 노드는 스택에서 delete하여 얻을 수 있으며, 앞으로 방문할 노드들은 스택에 add하여 주면 된다. 이를 알고리즘으로 표현하면 아래와 같다.

void iter_preorder(treenode *t){
Stack의 초기화;
Stack.Add(t); // Stack에 노드를 삽입한다.
while(Stack이 비어있지 않은 경우){
t = Stack.Delete(); // 방문할 노드를 스택에서 받아온다.
if(t){ // 방문할 노드가 존재하는 경우 순회를 계속한다.
cout<<t→data<<"\n"; // 노드의 데이터를 출력
Stack.Add(t→rightChild); // 부모-왼쪽-오른쪽 순으로 방문하므로 오른쪽 삽입 후
Stack.Add(t→leftChild); // 왼쪽 노드를 삽입한다.
} // end of if
} // end of while
}

참고 자료

없음