이진 트리 : 모든 차수가 2이하인 트리

한 레벨 당 최대 노드의 개수 : 2^(레벨) ex) 레벨 2의 최대노드 개수 : 2^2=4

최대 노드의 개수 : ∑(i=0~H)2^i = 2^(H+1) - 1 → N(최대 노드의 개수) = 2^(H+1) - 1 → H(높이) = O(logn) → 이진 트리의 시간복잡도는 O(logn)이다.(시간복잡도는 높이에 비례한다)

포화 이진 트리

(꽉 참)

완전 이진 트리

(왼쪽 노드부터 차례로 채움)

편향 이진 트리

(모든 노드가 한 방향)

순자 리스트를 이용한 구현

연결 리스트를 이용한 구현

#include<stdio.h>
typedef char element;

typedef struct treeNode {
	element data;
	struct treeNode* left_link;
	struct treeNode* right_link;
}treeNode

// 루트 노드 만듬
treeNode* make_tree(element value, element left_value, element right_value) {
	treeNode *root = (treeNode *) malloc(sizeof(treeNode));

	root -> data = value;
	root -> left_link = NULL;
	root -> right_link = NULL;

	return root;
}

// 왼쪽으로 갈라지는 노드 추가
treeNode* left_append(treeNode* node, element left_value, element right_value) {
	treeNode *left = (treeNode *) malloc(sizeof(treeNode));
	
	node -> left_link =left;

	left -> data = left_value;
	left -> left_link = NULL;
	left -> right_link = NULL;

	return left;
}.  

// 오른쪽으로 갈라지는 노드 추가
treeNode* right_append(treeNode* node, element left_value, element right_value) {
	treeNode *right = (treeNode *) malloc(sizeof(treeNode));
	
	node -> right_link =right;

	right -> data = left_value;
	right -> left_link = NULL;
	right -> right_link = NULL;

	return right;
}.  

딕셔너리 추가기능

이진 트리의 순회(보통 재귀함수)

순회 : 모든 원소를 빼거나 중복 없이 처리하는 연산

전위 순회(D(처리)→L(왼쪽 서브 트리로 이동)→R(오른쪽 서브 트리로 이동))

중위 순회(L→D→R)

후위 순회(L→R→D)