[자료구조] 이진 트리의 표현 및 순회

1. 배열 표현법

- 이진트리를 완전 이진 트리라고 가정하고 연속적으로 값을 할당한다.

- 인덱스 0은 사용하지 않는다.

- 완전 이진 트리가 아닐 시 기억공간의 낭비가 심하다.

 

1) 특징

- 노드 i의 부모 노드 인덱스 = i/2

- 노드 i의 왼쪽 자식 노드 인덱스 = 2i

- 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

 

2. 링크 표현법

- 트리에서의 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법이다.

- 하나의 노드는 3개의 필드를 가지는데, 왼쪽자식 노드의 포인터, 데이터, 오른쪽 자식의 포인터를 가진다.

 

> 코드 구현

#include <iostream>
using namespace std;

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
}TreeNode;

int main() {
	TreeNode* n1, * n2, * n3;
	n1 = (TreeNode*)malloc(sizeof(TreeNode));
	n2 = (TreeNode*)malloc(sizeof(TreeNode));
	n3 = (TreeNode*)malloc(sizeof(TreeNode));
	n1->data = 10;
	n1->left = n2;
	n1->right = n3;
	n2->data = 20;
	n2->left = NULL;
	n2->right = NULL;
	n3->data = 30;
	n3->left = NULL;
	n3->right = NULL;
	free(n1); free(n2); free(n3);
	return 0;
}

3. 이진 트리의 순회

 

1) 종류

- 전순위 (루트가 제일 앞)

- 중순위 (루트가 중간)

- 후순위 (루트가 제일 뒤)

 

 

2) 순환 알고리즘 코드

#include <iostream>
using namespace std;


typedef TreeNode* tree_pointer;

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
}TreeNode;


void preorder(tree_pointer ptr) {
	if (ptr) {
		printf("%d ", ptr->data);
		preorder(ptr->left);
		preorder(ptr->right);
	}
}

void inorder(tree_pointer ptr) {
	if (ptr) {
		preorder(ptr->left);
		printf("%d ", ptr->data);
		preorder(ptr->right);
	}
}

void postorder(tree_pointer ptr) {
	if (ptr) {
		preorder(ptr->left);
		preorder(ptr->right);
		printf("%d ", ptr->data);
	}
}

- 연결리스트를 이용하여 구현하였다.

 

3) 비순환 알고리즘 코드

> 전체 코드

#include <iostream>

using namespace std;

typedef TreeNode* tree_pointer;
typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
}TreeNode;

#define N 100
int top = 0; //스택 초기화
tree_pointer stack[N];

void push(tree_pointer* p) {
	if (top < N - 1) {
		stack[++top] = p;
	}
}

TreeNode *pop() {
	tree_pointer p = NULL;
	if (top >= 0) {
		p = stack[top--];
	}
	return p;
}

void inorder2(tree_pointer ptr) {
	while (1) {
		for (; ptr; ptr = ptr->left) {
			push(ptr);
		}
		ptr = pop();
		if (!ptr) break;
		printf("%d ", ptr->data);
		ptr = ptr->right;
	}
}

 

4. 레벨 순회

- 각 노드를 레벨 순으로 검사하는 순회 방법이다.

- 루트 노드의 레벨이 0이고 아래로 내려갈수록 레벨은 증가한다. 

- 동일한 레벨의 경우에는 좌에서 우로 방문한다.

- 큐를 사용한다.