이진 트리의 구현과 순회 방식

이 챕터는 알고리즘보다는 자료구조에 가까운 것 같아 자료구조 게시판에 게시한다.

 

이진 트리는 대표적인 비선형 자료구조이다.

 

완전 이진 트리와 이진 트리의 차이를 분명히 하고 넘어가야 한다.

--> 나도 처음에 배열로 표현하면 될 것 같은데? 라고 생각했는데 여기서 할 것은 !이진 트리! 이다.

 

충분히 배열로 표현이 가능하나, 오른쪽에만 노드가 이어져있다 생각해보면 메모리 낭비가 심하다고 생각할 수 있다.

 

순회 방식은 3개 있다.

 

1. 전위 순회

(1) 먼저 자기 자신을 처리.

(2) 왼쪽 자신을 방문

(3) 오른쪽 자식을 방문

 

2. 중위 순회

(1) 왼쪽 자신을 방문

(2) 먼저 자기 자신을 처리.

(3) 오른쪽 자식을 방문

 

3. 후위 순회

(1) 왼쪽 자신을 방문

(2) 오른쪽 자식을 방문

(3) 먼저 자기 자신을 처리.

--> 컴퓨터가 처리하는 방식이라고도 한다.

 

보면 알겠지만, 전위 중위 후위에 큰 차이는 자기 자신을 처리하는 순서에 있다. 이것을 요점으로 하여 기억하면 좋다.

 

이러한 알고리즘은 정보처리기사에 자주 출제되는 것으로 기억하고 있다.

 

#include <iostream>

using namespace std;

int number = 15;

typedef struct node* treePointer;

typedef struct node {
	int data;
	treePointer leftChild, rightChild;
};

void preorder(treePointer ptr)
{
	if (ptr)
	{
		cout << ptr->data << ' ';
		preorder(ptr->leftChild);
		preorder(ptr->rightChild);
	}
}

void inorder(treePointer ptr)
{
	if (ptr)
	{
		inorder(ptr->leftChild);
		cout << ptr->data << ' ';
		inorder(ptr->rightChild);
	}
}

void postorder(treePointer ptr)
{
	if (ptr)
	{
		postorder(ptr->leftChild);
		postorder(ptr->rightChild);
		cout << ptr->data << ' ';
	}
}

int main(void)
{
	node nodes[16];

	for (int i = 1; i <= number; i++)
	{
		nodes[i].data = i;
		nodes[i].leftChild = NULL;
		nodes[i].rightChild = NULL;
	}

	for (int i = 1; i <= number; i++)
	{
		if (i % 2 == 0)
		{
			nodes[i / 2].leftChild = &nodes[i];
		}
		else
		{
			nodes[i / 2].rightChild = &nodes[i];
		}
	}

	preorder(&nodes[1]);
	cout << endl;
	inorder(&nodes[1]);
	cout << endl;
	postorder(&nodes[1]);

}