이진트리
모든 노드가 최대 2개의 서브 트리를 가질 수 있는 트리
높이가 h일 때 최소 h개의 노드, 최대 2^h-1개의 노드를 가짐
노드의 개수가 n개일 때 간선의 개수는 n-1
이진트리 종류
포화 이진트리 : 트리의 모든 레벨에 노드가 모두 차있는 이진트리
완전 이진트리 : 높이가 h일 때 레벨 1부터 h-1까지는 노드가 모두 채워져 있고 마지막 레벨 h에서는 왼쪽부터 오른쪽의 순서로 노드가 채워져 있는 이진트리
연결리스트를 이용한 이진트리
#include <iostream>
using namespace std;
typedef int element;
typedef struct Node{
element data;
Node* left;
Node* right;
}Node;
class BinaryTree{
public:
BinaryTree();
~BinaryTree();
Node* CreateNode(element data);
int getNodeCount(Node* node);
int getHeight(Node* node);
element getData(Node* node);
bool setData(Node* node, element data);
void preOrder(Node* node);
void inOrder(Node* node);
void postOrder(Node* node);
};
BinaryTree::BinaryTree(){}
BinaryTree::~BinaryTree(){}
Node *BinaryTree::CreateNode(element data){
Node* newNode = new Node();
newNode->left = nullptr;
newNode->right = nullptr;
newNode->data = data;
return newNode;
}
int BinaryTree::getNodeCount(Node* node){
int count = 0;
if(node != nullptr)count = 1 + getNodeCount(node->left) + getNodeCount(node->right);
return count;
}
int BinaryTree::getHeight(Node* node){
int height = 0;
if(node != nullptr)height = 1 + max(getHeight(node->left),getHeight(node->right));
return height;
}
element BinaryTree::getData(Node* node){
if(node == nullptr)return -1;
return node->data;
}
bool BinaryTree::setData(Node* node, element data){
if(node == nullptr)return false;
node->data = data;
return true;
}
void BinaryTree::preOrder(Node* node){
if(node != nullptr){
cout << getData(node) << " ";
preOrder(node->left);
preOrder(node->right);
}
}
void BinaryTree::inOrder(Node* node){
if(node != nullptr){
inOrder(node->left);
cout << getData(node) << " ";
inOrder(node->right);
}
}
void BinaryTree::postOrder(Node* node){
if(node != nullptr){
postOrder(node->left);
postOrder(node->right);
cout << getData(node) << " ";
}
}
int main(){
BinaryTree* tree = new BinaryTree();
Node* root = tree->CreateNode(1);
Node* nodeA = tree->CreateNode(2);
Node* nodeB = tree->CreateNode(3);
Node* nodeC = tree->CreateNode(4);
Node* nodeD = tree->CreateNode(5);
Node* nodeE = tree->CreateNode(6);
Node* nodeF = tree->CreateNode(7);
root->left = nodeA;
root->right = nodeB;
nodeA->left = nodeC;
nodeA->right = nodeD;
nodeB->left = nodeE;
nodeB->right = nodeF;
tree->preOrder(root);
cout << "\n";
tree->inOrder(root);
cout << "\n";
tree->postOrder(root);
cout << "\n";
/*
1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
*/
}
순회 종류
순회 : 트리의 노드들을 체계적으로 방문하는 것
- 전위순회 VLR (preorder) : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문
- 중위순회 LVR (inorder) : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문
- 후위순회 LRV (postorder) : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순서로 방문
'공부 > 자료구조' 카테고리의 다른 글
[자료구조] 우선 순위 큐(Priority Queue) (0) | 2023.05.12 |
---|---|
[자료구조] 덱(Deque) (0) | 2023.04.30 |
[자료구조] 큐(Queue) (0) | 2023.04.30 |
[자료구조] 스택(Stack) (0) | 2023.04.26 |