[C] 이진 탐색 트리(BST)

이진 탐색 트리(BST)

• 각각의 노드가 최대 2개의 자식 노드를 가지는 이진 트리의 구조를 갖추고 있다.
• 연결 리스트로 구현된다.

 

이진 탐색 트리

 

기본 원리

• 모든 노드의 값은 유일하다.
• 루트 노드를 기준으로 왼쪽에 있는 값들은 루트 노드의 값보다 작다.
• 루트 노드를 기준으로 오른쪽에 있는 값들은 루트 노드의 값보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 

 

문제

 

이진 탐색 순회

 

#include <iostream>
using namespace std;

typedef struct node_struct {
	int data;
	struct node_struct* left;
	struct node_struct* right;
}node;

node* insert_node(node* root, int value)
{
	if (root == NULL) {
		root = new node;
		root->left = root->right = NULL;
		root->data = value;
	}
	else {
		if (root->data > value)
			root->left = insert_node(root->left, value);
		else
			root->right = insert_node(root->right, value);
	}
	return root;
}

void pre(node* root) // 전위 순회  
{
	if (root) {
		printf("%d ", root->data);
		pre(root->left);
		pre(root->right);
	}
}

void ino(node* root) // 중위 순회
{
	if (root) {
		ino(root->left);
		printf("%d ", root->data);
		ino(root->right);
	}
}

void pos(node* root) // 후위 순회
{
	if (root) {
		pos(root->left);
		pos(root->right);
		printf("%d ", root->data);
	}
}

int main()
{
	node* root = NULL;
	root = insert_node(root, 10);
	root = insert_node(root, 5);
	root = insert_node(root, 7);
	root = insert_node(root, 13);
	root = insert_node(root, 1);
	root = insert_node(root, 17);

	pre(root);
	printf("\n\n");
	ino(root);
	printf("\n\n");
	pos(root);

	return 0;
}