트리(이진트리순회)

트리는 일대다의 관계를 가지는 자료구조이다. 트리를 구현하면 나무모양을 닮아 트리라고 한다. 

 

트리의 예

 

트리의 특징은 다음과 같다.

1. 노드 사이에 사이클이 존재하지 않는다.

2. 노드 사이에는 오직 하나의 경로만 존재한다.

 

트리는 비선형 구조이다. 앞서 설명한 스택, 리스트, 큐는 선형구조이다. 선형 구조는 순차적으로 데이터를 나열한 반면 비선형 구조는 데이터를 계층적으로 나열하였다. 

 

트리를 구현하기 위해서는 먼저 트리의 용어를 알아야 한다.

1. 노드 : 트리를 구성하는 요소, 각각의 value값을 가지고 있다.

2. 엣지 : 노드와 노드 사이를 연결하는 하나의 경로, 부모와 자식을 연결한다.

3. 루트 노드 : 트리에서 맨 꼭대기에 존재하는 노드, 부모 노드가 없다.

4. 리프 노드 : 트리에서 맨 마지막에 존재하는 노드, 자식 노드가 없다.

5. 부모 노드 : 자식 노드를 가지고 있는 노드

6. 형제 노드 : 부모가 같은 자식 노드들을 가리키는 말

7. 자식 노드 : 부모를 가지고 있는 노드

8. 조상 노드 : 어떤 노드의 모든 부모 노드를 가리키는 말

9. 차수 : 트리에서 부모가 가진 자식 노드의 수 중 최댓값

10. 깊이 : 트리의 높이, 트리의 최대 레벨

 

이진트리란 최대 차수가 2인 트리를 말한다. 즉 자식이 아무리 많아도 최대 2개로 존재한다는 것이다. 

 

이진 트리를 모두 순회하는 방법은 크게 세가지로 분류된다.

1. 전위 순회 : 왼쪽 대각선 아래로 노드를 순회한다.

 

전위 순회

 

2. 중위 순회 : 왼쪽 아래 -> 루트노드 -> 오른쪽 아래 순으로 순회한다.

 

중위 순회

 

3. 후위 순회 : 오른쪽 대각선 위 방향으로 노드를 순회한다.

 

후위 순회

 

트리의 구성요소인 노드는 클래스로 구현하였고 각각의 노드들이 연결되기 위한 트리도 클래스로 구현하였다. 노드를 객체 포인터를 이용해 동적할당을 받았고 인덱스를 이용하여 부모와 자식관계를 구분하였다.

 

다음은 이진트리순회를 구현하기 위해 필요한 함수들이다.

• makeNode : 노드를 만드는 함수, 노드의 value값을 지정
• makeTree : 트리를 만드는 함수, 부모와 자식 사이의 관계를 만드는 함수, 배열의 인덱스를 2로 나누어 나머지가 0이면 왼쪽 자식으로 배치, 나머지가 1이면 오른쪽 자식으로 배치
• preorder : 전위 순회 함수
• inorder : 중위 순회 함수 
• postorder : 후위 순회 함수 
• firstNode : 루트 노드의 주소값을 반환하는 함수

 

#include <iostream>
using namespace std;

class Node {
private:
	int data;
	Node* lptr; //왼쪽 자식
	Node* rptr; //오른쪽 자식
	friend class Tree; //freind선언으로 Tree클래스가 Node멤버에 접근이 가능하다.
public:
	Node() {
		data = 0;
		lptr = NULL;
		rptr = NULL;
	}
};

class Tree {
private:
	Node* nptr; //노드를 동적할당 받기위해 선언
	int n; //노드의 갯수
public:
	Tree() {
		cout << "원하는 노드의 갯수를 입력하세요 >> "; cin >> n;
		nptr = new Node[n + 1]; //1번째부터 n번째까지 사용하기 위해 n + 1개로 선언
	}	
	void makeNode(); //노드를 만드는 함수
	void makeTree(); //트리를 만드는 함수
	void preorder(Node* nodeptr); //전위 순회
	void inorder(Node* nodeptr); //중위 순회
	void postorder(Node* nodeptr); //후위 순회
	Node* firstNode(); //첫번째 노드의 주소 반환
};

//노드를 만드는 함수
void Tree::makeNode() {
	//n개의 데이터 입력
	for (int i = 1; i <= n; i++) {
		int data;
		cout << "입력할 데어터 >> ";  cin >> data;
		nptr[i].data = data;
	}
}

//트리를 만드는 함수
void Tree::makeTree() {
	//첫번째 노드는 제일 상위에 있는 부모노드여서 2번째 노드부터 진행
	for (int i = 2; i <= n; i++) {
		if (i % 2 == 0) { //짝수번째 노드이면
			nptr[i / 2].lptr = &nptr[i]; //부모노드에 왼쪽에 배치
		}
		else { //홀수번째 노드이면
			nptr[i / 2].rptr = &nptr[i]; //부모노드에 오른쪽에 배치
		}
	}
}

//전위 순회, 원하는 작업 수행 후 왼쪽 자식 방문하고 오른쪽 자식 방문
void Tree::preorder(Node* nodeptr) {
	if (nodeptr) {
		cout << nodeptr->data << ' ';
		preorder(nodeptr->lptr);
		preorder(nodeptr->rptr);
	}
}

//중위 순회, 왼쪽 자식 방문 후 원하는 작업하고 오른쪽 자식 방문
void Tree::inorder(Node* nodeptr) {
	if (nodeptr) {
		inorder(nodeptr->lptr);
		cout << nodeptr->data << ' ';
		inorder(nodeptr->rptr);
	}
}

//후위 순회, 왼쪽 자식 방문 후 오른쪽 자식 방문하고 원하는 작업
void Tree::postorder(Node* nodeptr) {
	if (nodeptr) {
		postorder(nodeptr->lptr);
		postorder(nodeptr->rptr);
		cout << nodeptr->data << ' ';
	}
}

//첫번째 노드의 주소 반환
Node* Tree::firstNode() {
	return &nptr[1];
}

int main() {
	int n;
	Tree* tree = new Tree;
	
	tree->makeNode();
	tree->makeTree();

	cout << "전위 순회 >> ";
	tree->preorder(tree->firstNode());
	cout << '\n';

	cout << "중위 순회 >> ";
	tree->inorder(tree->firstNode());
	cout << '\n';

	cout << "후위 순회 >> ";
	tree->postorder(tree->firstNode());
	cout << '\n';
}