상세 컨텐츠

본문 제목

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

개발생활/DataStructure

by 한국인맛집 2017. 6. 8. 00:30

본문

반응형

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



반응형

'개발생활 > DataStructure' 카테고리의 다른 글

자료구조 기초  (0) 2017.12.06
Class 사용 Queue 구현  (0) 2017.05.25
Insertion_sort_ 구현  (0) 2017.05.25
[Data_Struct] Stack 구현  (0) 2017.05.23
Linked_list [data_struct]  (31) 2017.05.22

관련글 더보기