[C++] 반복적트리순회 알고리즘 2
페이지 정보
작성일 23-03-20 03:59
본문
Download : [C++] 반복적트리순회 알고리즘.hwp
Stack의 초기화;
} end of while
cout t→data ` n`;
cout t→data ` n`; 노드의 데이터를 출력
Stack.Add(t→rightChild); 부모-왼쪽-오른쪽 순으로 방문하므로 오른쪽 삽입 후
[C++] 반복적트리순회 알고리즘 2
2. Iterative preorder의 구현
후위순회는 왼쪽자식-오른쪽자식-부모노드 순으로 트리를 순회하는 것으로서 recursive로 구현하면 아래와 같은 알고리즘으...
Ⅱ. Iterative postorder
순서
1. 전위순회의 방법
Ⅰ. Iterative preorder 1. 전위순회의 방법 전위순회는...
Ⅰ. Iterative preorder 1. 전위순회의 방법 전위순회는...
pre_order(t→rigntChild);
전위순회는 부모노드-왼쪽자식-오른쪽자식 순으로 트리를 순회하는 것으로서 recursive로 구현하면 아래와 같이 표현할수있다.
위 알고리즘과 같이 전위순회를 구현하면, 스택에는 항상 부모-왼쪽-오른쪽 노드 순으로 삽입되어 있으므로 스택이 비어있을 때까지 반복하여 삭제 삽입 동작을 수행하면, 전위순회를 비재귀적으로 수행할 수 있게 되는 것이다.
pre_order(t→leftChild);
while(Stack이 비어있지 않은 경우){
}
if(t){
Stack.Add(t→leftChild); 왼쪽 노드를 삽입한다.
} end of if
설명
Ⅰ. Iterative preorder
Download : [C++] 반복적트리순회 알고리즘.hwp( 78 )
전위순회는 스택을 사용하여 비재귀적으로 구현이 가능한데, 방문할 노드는 스택에서 delete하여 얻을 수 있으며, 앞으로 방문할 노드들은 스택에 add하여 주면 된다된다.
다.
if(t){ 방문할 노드가 존재하는 경우 순회를 계속한다. 이를 알고리즘으로 표현하면 아래와 같다.
![[C++] 반복적트리순회 알고리즘-6866_01.gif](https://sales.happyreport.co.kr/prev/200711/%5BC++%5D%20%EB%B0%98%EB%B3%B5%EC%A0%81%ED%8A%B8%EB%A6%AC%EC%88%9C%ED%9A%8C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-6866_01.gif)
![[C++] 반복적트리순회 알고리즘-6866_02_.gif](https://sales.happyreport.co.kr/prev/200711/%5BC++%5D%20%EB%B0%98%EB%B3%B5%EC%A0%81%ED%8A%B8%EB%A6%AC%EC%88%9C%ED%9A%8C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-6866_02_.gif)
Stack.Add(t); Stack에 노드를 삽입한다.
1. 후위순회의 방법
C++ 반복적트리순회 알고리즘 2
레포트 > 기타
void iter_preorder(treenode t){
void pre_order(treenode t){
}
}
t = Stack.Delete(); 방문할 노드를 스택에서 받아온다.
