자료구조 트리(2)

저번에 이어서 마저 작성해 보도록 하겠습니다.

---

이진트리란?

이진트리는 순 근노드를 포함한 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 자료구조입니다.

즉 자식 노드가 2개를 넘어가면  이진트리가 아닙니다.

 

이진트리에는 종류가 있는데, 아래의 3가지입니다.

1) 모든 자식 노드가 2개인 경우를 포화 이진트리라고 합니다.

2) 자식노드가 2개인 노드도 있고 1개인 노드가 있는 경우 완전 이진트리라고 합니다.

3) 모든 자식 노드가 1개인 경우 편향 이진트리라고 합니다.

---

이진트리의 순회

순회: 모든 노드를 정해진 순서에 따라 한 번씩 방문하는 것입니다.

즉 모든 노드를 돌아보는 것이죠.

 

순회도 종류가 있습니다.

1) 전위 순회: 부모노드를 가장 먼저 방문하는 것입니다.

2) 중위 순회: 부모노드를 중간에 방문하는 것입니다.

3) 후위 순회: 부모노드를 가장 뒤에 방문하는 것입니다.

 

이렇게만 들으면 이해가 어려우니 그림으로 예시를 들어봅시다.

자식 노드가 모두 2개이기에 포화 이진트리입니다.

위 그림에서 전위 순회부터 해봅시다.

근노드인 A가 가장 먼저 오고 왼쪽부터 돌리게 B-D-E로 돌 거고 다음 오른쪽으로 가서 C-F-G순으로 돌게 됩니다.

그럼 A-B-D-E-C-F-G순이 됩니다.

 

다음은 중위 순회입니다.

부모노드가 중간에 와야 하기에 자식을 먼저봅니다. 그렇다면 D가 가장먼저오고 다음에 부모노드가 옵니다. 그렇다면

D-B-E-A-F-C-G순이 됩니다.

 

마지막으로 후위 순회입니다.

근노드가 가장마지막에 나오게 되고 부모가 마지막에 와야하기에

D-E-B-F-G-C-A가 됩니다.

---

마지막으로 순회를 구현해 보겠습니다.

 

이진트리를 돌면서 값을 비교하여 순회종류에 따라 다르게 값을 넣어줍니다. 

#pragma once
#include <iostream>
#include<stack>
using namespace std;

struct BTreeNode
{
	int data;
	struct BTreeNode* left;
	struct BTreeNode* right;
};

BTreeNode* MakeBTreeNode(void);
void DeleteBTreeNode(BTreeNode* bt);
int GetData(BTreeNode* bt);
void SetData(BTreeNode* bt, int data);
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub);
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub);

void PreorderTraverse(BTreeNode* bt);
void InorderTraverse(BTreeNode* bt);
void PostorderTraverse(BTreeNode* bt);​

#include "bt.h"

int main() {
    BTreeNode* bt1 = MakeBTreeNode();
    BTreeNode* bt2 = MakeBTreeNode();
    BTreeNode* bt3 = MakeBTreeNode();
    BTreeNode* bt4 = MakeBTreeNode();
    BTreeNode* bt5 = MakeBTreeNode();
    BTreeNode* bt6 = MakeBTreeNode();
    SetData(bt1, 1);
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);
    SetData(bt5, 5);
    SetData(bt6, 6);
    MakeLeftSubTree(bt1, bt2);
    MakeRightSubTree(bt1, bt3);
    MakeLeftSubTree(bt2, bt4);
    MakeRightSubTree(bt2, bt5);
    MakeRightSubTree(bt3, bt6);

    cout << "preorder : ";
    PreorderTraverse(bt1);
    cout << endl;
    cout << "inorder : ";
    InorderTraverse(bt1);
    cout << endl;
    cout << "postorder : ";
    PostorderTraverse(bt1);
    cout << endl;

}

#include "bt.h"

BTreeNode* MakeBTreeNode(void)
{
	BTreeNode* node = new BTreeNode;
	node->left = NULL;
	node->right = NULL;
	return node;
}
void DeleteBTreeNode(BTreeNode* bt) {
	delete bt;
}
int GetData(BTreeNode* bt) {
	return bt->data;
}
void SetData(BTreeNode* bt, int data) {
	bt->data = data;
}

void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub)
{
	if (main->left != NULL)
		delete main->left;
	else
		main->left = sub;
}
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
	if (main->right != NULL)
		delete main->right;
	else
		main->right = sub;
}
void PreorderTraverse(BTreeNode* bt)
{
	cout << bt->data;
	if (bt->left != NULL)	
		PreorderTraverse(bt->left);
	
	if (bt->right != NULL)
		PreorderTraverse(bt->right);
	
}
void InorderTraverse(BTreeNode* bt)
{

	if (bt->left != NULL)
		InorderTraverse(bt->left);
	cout << bt->data;
	if (bt->right != NULL)
		InorderTraverse(bt->right);

}
void PostorderTraverse(BTreeNode* bt)
{
	if (bt->left != NULL)
		PostorderTraverse(bt->left);
	if (bt->right != NULL)
		PostorderTraverse(bt->right);
	cout << bt->data;
}

이렇게 작성하면 작성한 숫자의 전위 순회, 중위 순회, 후위 순회가 콘솔창에 표시될 것입니다.

---

오늘글은 여기까지입니다.