자료구조 (이진트리 Binary Tree 순회 , 이진순회)

---

참고자료

 

https://jung-story.tistory.com/28?category=826491 

자료구조 (이진트리) (binary tree)

 

---

개요

 

이번에는 자료구조 이진트리의 순회 방식에 대해서 알아본 후 그것을 코드로 구현하는 것을 해보도록 하겠습니다.

 

---

이진트리 순회(traversal)의 개념

 

• 모든 원소를 빠트리거나 중복하지 않고 처리하는 연산
• 작업 D : 현재 노드를 방문하여 처리합니다.
• 작업 L : 현재 노드의 왼쪽 서브 트리로 이동합니다.
• 작업 R: 현재 노드의 오른쪽 서브 트리로 이동합니다.

 

왼쪽 서브트리에 대한 순회를 오른쪽 서브트리서브 트리보다 먼저 수행

 

---

전위 순회(preorder traversal)

 

D → L → R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행합니다.

전위 순회의 예

 

---

중위 순회(inorder traversal)

 

L → D → R 순서로, 현재 노드를 방문하는 작업 D를 작업 L과 작업 R의 중간에 수행

중위 순회의 예

 

---

후위 순회(postorder traversal)

 

L-R-D 순서로 현재 노드를 방문하는 D 작업을 가장 나중에 수행

후위 순회의 예

 

---

순회 코드 작성

 

#include <stdio.h>

typedef struct treeNode {
	char data;
	struct treeNode* lchild;
	struct treeNode* rchild;
}treeNode;

treeNode* makeNode(char data, treeNode* lchildeNode, treeNode* rchildNode) {

	treeNode* Node = (treeNode*)malloc(sizeof(treeNode));
	Node->data = data;
	Node->lchild = lchildeNode;
	Node->rchild = rchildNode;
	return Node;
}
void RootDLR(treeNode* Node) {
	if (Node) {
		printf("%2c", Node->data);
		RootDLR(Node->rchild);
		RootDLR(Node->lchild);
	}

}
void RootLDR(treeNode* Node) {
	if (Node) {
		RootLDR(Node->lchild);
		printf("%2c", Node->data);
		RootLDR(Node->rchild);
	}
}
void RootLRD(treeNode* Node) {
	if (Node) {
		RootLRD(Node->lchild);
		RootLRD(Node->rchild);
		printf("%2c", Node->data);
	}
}


int main(void) {
	treeNode* n4 = makeNode('A', NULL, NULL);
	treeNode* n5 = makeNode('B', NULL, NULL);
	treeNode* n6 = makeNode('C', NULL, NULL);
	treeNode* n7 = makeNode('D', NULL, NULL);
	treeNode* n3 = makeNode('/', n6, n7);
	treeNode* n2 = makeNode('*', n4, n5);
	treeNode* n1 = makeNode('-', n2, n3);

	RootLRD(n1);
	printf("\n------------------\n");
	RootLDR(n1);

	return 0;
}

 

---

실행화면

 

실행 예

 

---