Tree, Traversal, Binary Search Tree

tree

Tree

• 정의 : '노드'와 '간선'으로 구성 된 자료구조로, 그래프의 한 종류이다.

 

용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

트리 종류

• Binary Tree (이진 트리) : 각 노드가 최대 두 개의 자식을 갖는 트리 

• Complete Binary Tree (완전이진트리) : 트리의 마지막 레벨을 제외한 모든 레벨이 채워져있고, 마지막 레벨은 왼쪽에서 오른쪽으로 채워진 트리
• Full binary Tree (전이진트리) : 모든 노드가 0개 또는 2개의 자식을 갖는 트리
• Perfect Binary Tree (포화이진트리) : 트리의 모든 레벨이 꽉찬 이진트리. 완전이진트리이자 전이진트리

• Binary Search Tree (이진탐색트리) : 왼쪽 자식 <= 부모 <= 오른쪽 자식 을 만족하는 이진트리
• Balanced Tree (균형트리) : AVL tree, red-black tree
• Binary Heap (이진 힙) : min heap, max heap

 

Traversal, 순회

• pre-order (전위 순회) : 부모노드 -> 왼쪽자식노드 -> 오른쪽자식노드
• in-order (중위 순회) : 왼쪽자식노드 -> 부모노드 -> 오른쪽자식노드
• post-order (후위 순회) : 왼쪽자식노드 -> 오른쪽자식노드 -> 부모노드

 

 

예시코드

// binary search tree

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
	int data;
	Node* left;
	Node* right;
	Node(int d=-1, Node* pleft=NULL, Node* pright=NULL){
		data = d;
		left = pleft;
		right = pright;
	}
};

class BinarySearchTree {
public:
	Node* root;
	BinarySearchTree() {
		root = NULL;
	}
	void search(Node* par, int data) {
		if (par == NULL) {
			cout << data << ": 노드 존재 X" << endl;
			return;
		}
		else if (par->data == data) {
			cout << data << ": 노드 발견!" << endl;
			return;
		}
		else if (par->data > data) {
			cout << "left" << endl;
			search(par->left, data);
			return;
		}
		else if (par->data < data) {
			cout << "right" << endl;
			search(par->right, data);
			return;
		}
	}
	void insert(Node* & par, int data) {
		if (par == NULL) {
			par = new Node(data, NULL, NULL);
			return;
		}
		else {
			if (par->data <= data) {
				insert(par->right, data);
			}
			else if (par->data > data) {
				insert(par->left, data);
			}
			return;
		}
	}
	void remove(Node*& par, int data) {
		if (par == NULL) {
			cout << data << " 삭제 실패(노드 존재 X)" << endl;
			return;
		}
		else if (par->data == data) {
			cout << data << " 삭제 성공" << endl;
			delete par;
			par = NULL;
			return;
		}
		else if (par->data > data) {
			remove(par->left, data);
			return;
		}
		else if (par->data < data) {
			remove(par->right, data);
			return;
		}
	}
	void preOrder(Node* cur) {
		if (cur == NULL) {
			return;
		}
		cout << cur->data << " ";
		if (cur->left != NULL) {
			preOrder(cur->left);
		}
		if (cur->right != NULL) {
			preOrder(cur->right);
		}
	}
	void inOrder(Node* cur) {
		if (cur == NULL) {
			return;
		}
		if (cur->left != NULL) {
			inOrder(cur->left);
		}
		cout << cur->data << " ";
		if (cur->right != NULL) {
			inOrder(cur->right);
		}
	}
	void postOrder(Node* cur) {
		if (cur == NULL) {
			return;
		}
		if (cur->left != NULL) {
			postOrder(cur->left);
		}
		if (cur->right != NULL) {
			postOrder(cur->right);
		}
		cout << cur->data << " ";
	}
};

int main() {
	// binary search tree 생성
	BinarySearchTree bst;
	
    //노드 생성
	bst.insert(bst.root,100);
	bst.insert(bst.root, 123);
	bst.insert(bst.root, 32);
	bst.insert(bst.root, 77);
	bst.insert(bst.root, 15);
	bst.insert(bst.root, 453);
	bst.insert(bst.root, 46);
	bst.insert(bst.root, 84);
	bst.insert(bst.root, 256);
	
    // 탐색연산
	bst.search(bst.root, 99);
	cout << endl;
	bst.search(bst.root, 15);
	cout << endl;
    
	// 제거연산
	bst.remove(bst.root, 15);
	cout << endl;
	bst.remove(bst.root, 99);
	cout << endl;
	bst.search(bst.root, 15);
	cout << endl;
	
    // 순회
	cout << "pre-order : ";
	bst.preOrder(bst.root);
	cout << endl;

	cout << "in-order : ";
	bst.inOrder(bst.root);
	cout << endl;

	cout << "post-order : ";
	bst.postOrder(bst.root);
	cout << endl;
    
	return 0;
}