이진 트리(Binary Tree) 순회

이진 트리(Binary Tree) 순회란 ? 

트리의 모든 노드를 한 번씩 방문하는 것

 

이진 트리(Binary Tree) 순회의 예

현재 노드(V), 왼쪽 서브트리(L), 오른쪽 서브트리(R)중 어떤 것을 먼저 방문 할지에 따라 달라짐

 

 

1. 전위 순회

현재 노드(V) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R)

현재 노드를 방문함 : 현재 노드의 데이터를 처리함

 

 

2. 중위 순회

왼쪽 서브트리(L) -> 현재 노드(V) ->  오른쪽 서브트리(R)

현재 노드를 방문하기 전에 왼쪽 서브트리가 모두 방문 되어야 한다는 점이 핵심

 

 

3. 후위 순회

왼쪽 서브트리(L) -> 오른쪽 서브트리(R)  -> 현재 노드(V)

현재 노드를 방문하기 전에 왼쪽 서브트리와 오른쪽 서브트리가 모두 방문 되어야 한다는 점이 핵심

 

 

 

구현 방법

재귀 함수를 이용하여 구현한다.

Pros : 소스코드를 보면 비교적 쉽게 이해할 수 있음

Cons : OS 상의 스택을 요구해서 반복에 의한 구현에 비해 성능이 떨어짐

 

 

 

 

typedef struct BinTreeNodeType
{
	char data;

	struct BinTreeNodeType* pLeft;
	struct BinTreeNodeType* pRight;
}BinTreeNode;


typedef struct BinTreeType
{
	struct BinTreeNodeType* pRootNode;
}BinTree;




void preorder(BinTree *pBinTree) //전위
{
	if(pBinTree != NULL){
	preorder(pBinTree->pRootNode);
	printf("\n");
	}
}

void preordernode(BinTree *pNode)
{
	if(pNode!=NULL){
    	printf("%c ", pNode->data);
        preordernode(pNode->pLeft);
        preordernode(pNode->pRight);
        }
}


void inorder(BinTree *pBinTree) //중위
{
	if(pBinTree!=NULL){
	inorder(pBinTree->pRootNode);
	printf("\n");	
	}
}


void inordernode(BinTree *pNode)
{
	if(pNode!=NULL){
        inordernode(pNode->pLeft);
        printf("%c ", pNode->data);
        inordernode(pNode->pRight);
        }
}


void postorder(BinTree *pBinTree) //후위
{
	if(pBinTree!=NULL){
	postorder(pBinTree->pRootNode);
	printf("\n");
	}
}

void postordernode(BinTree *pNode)
{
	if(pNode!=NULL){
        postordernode(pNode->pLeft);
        postordernode(pNode->pRight);
        printf("%c ", pNode->data);
        }
}