Binary Search Tree 구현. 자료구조 공부

Data Structures 공부할겸, 이진탐색 트리 구현하였다.

이진탐색트리는 재귀호출 로직으로 구현하였다. 

이진트리의 장점은 (정렬이된 컨테이너의 탐색속도는 log2n 속도를 자랑한다.

재귀호출시 주의사항으론 재귀호출이 중단되는지점(종료조건)을 확실하게 해주어야한다.

sturct 로 간단하게 구현해보았다.

아래 내용을 출력결과 와 Code로 구현하였다.

Output:

Main.cpp

#include"Header.h"
#include<cstdio>


int main() {

	Node* root = nullptr;
	root = insert(root, 10);
	root = insert(root, 8);
	root = insert(root, 13);
	root = insert(root, 7);
	root = insert(root, 9);


	printf("PreOrderTraversal\n");
	preOrderTraversal(root);
	printf("\n");

	printf("InOrderTraversal\n");
	inOrderTraversal(root);
	printf("\n");

	printf("PostOrderTraversal\n");
	postOrderTraversal(root);
	printf("\n");

	fgetc(stdin);
	return 0;
}

Source.cpp

#include"Header.h"
#include<cstdio>

Node* insert(Node* root, int data) {
	if (root == nullptr) {
		Node* node = new Node();
		node->data = data;
		return node;
	}
	//노드값이 들어왔는데 nullptr 이라면 값을 넣는다.
	else if(root->data > data) {
		root->left = insert(root->left, data);
	}
	//값과 현재 값비교하여 작으면 left 크면 right 로 이동.
	else if (root->data < data) {
		root->right = insert(root->right, data);
	}
	return root;
}

void preOrderTraversal(Node* root) {
	
	if (root != nullptr) {

	printf("[%d] ", root->data);
	preOrderTraversal(root->left);
	preOrderTraversal(root->right);
	}
}
void inOrderTraversal(Node* root) {
	if (root != nullptr) {

	inOrderTraversal(root->left);
	printf("[%d] ", root->data);
	inOrderTraversal(root->right);
	}

}
void postOrderTraversal(Node* root) {
	if (root != nullptr) {

	postOrderTraversal(root->left);
	postOrderTraversal(root->right);
	printf("[%d] ", root->data);
	}

}

Header.h

#ifndef __HEADER_H__
#define __HEADER_H__

	struct Node {
		Node* left = nullptr;
		Node* right = nullptr;
		int data;
	};
	
	
	Node* insert(Node* root, int data);
	// 트리에값을 넣기위함.
	
	void preOrderTraversal (Node* root);
	//전위순회
	// 나 자신 을 출력하고 left 노드 , right 노드를 출력한다.
	void inOrderTraversal(Node* root);
	//중위순회
	// left 노드를 출력하고 나자신을 출력하고  right노드를 출력.
	void postOrderTraversal(Node* root);
	//후위 순회
	// left노드를 출력하고, right 노드 , 나자신을 마지막에 출력하는 것.

#endif