2022. 5. 23. 12:10ㆍ자료구조
👨🏫 BST공부하는 느낌으로 풀면 됨
Assignment #2
Data Structure Spring, 2022
It is expressed the node Structure of Binary search tree like below:
| struct node { int data; //node will store an integer struct node *right_child; // right child struct node *left_child; // left child }; |
1. You will be creating a BST using node structure.
2. You also need to be implementing the following methods for your BST:
- boolean isEmpty() 👉 트리가 비었는지 확인
Returns true if BST is empty, false otherwise
- void makeEmpty() 👉 트리 비우기
Clears BST so that it is empty
- void inOrder(struct node *root) 👉 inorder로 탐색
Returns a queue with the elements in-order
- void preOrder(struct node *root) 👉 preorder로 탐색
Returns a queue with the elements in pre-order
- void postOrder(struct node *root) 👉postorder로 탐색
Returns a queue with the elements in post-order
- boolean contains(int data) 👉data가 트리에 들어있는지 확인
Returns true if the BST contains the data, otherwise returns false
- void put(int data) 👉원소 삽입
If the data is already in the BST, then put will do nothing.
If the data is not in the BST, then put will add the data to the BST.
- void delete(int data) 👉 원소 삭제
Removes the specified data from the BST, if the data cannot be found, then delete does nothing
Traversing BSTs
💁Binary Search Tree(이진탐색트리)란?
-모든 원소는 유일한 키 값을 갖는다.(중복x)
-왼쪽 서브트리의 모든 원소들은 루트 키보다 작은 값을 갖는다.
-오른쪽 서브트리의 모든 원소들은 루트의 키보다 큰 값을 갖는다.
- 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다.
노드를 하나 통과할 때마다 검색 대상이 절반 줄어든다. O(logn)->우수한 성능의 알고리즘
💁 핵심 함수 구현 (원소 삽입, 원소 삭제, 검색)
- struct node* put(struct node*root, int data) 👉원소 삽입
->데이터가 이미 존재하면 아무일도 안함
-> 트리에 데이터가 없으면 data 추가
//Returns 1 if the BST contains the data, otherwise returns 0
int contains(struct node*root, int data) {
struct node*p = root;
while (p != NULL) {
if (p->data == data) {
return 1;
}
else if (p->data > data) {
p = p->left_child;
}
else if (p->data < data) {
p = p->right_child;
}
}
return 0;
}
struct node* put(struct node*root,int x) {
struct node*p = root;
//If the x is already in the BST, then put will do nothing.
if (contains(p, x)) {
printf("%d is already in the BST.", x);
return p;
}
//If the data is not in the BST, then put will add the data to the BST.
if (p == NULL) {
p = new_node(x); //p points to new node
}
else if (p->data > x) { //if x is smaller, should be inserted to left
p->left_child = put(p->left_child, x);
}
else{
p->right_child = put(p->right_child, x);
}
return p;
}트리탐색에는 재귀로 구현하는 방법과 while문으로 탐색하는 방법 두 가지가 있다.
- void delete(int data) 👉 원소 삭제
| 차수 | delete 구현 |
| 0(No children) |  |
| 1(one child) |   |
| 2(two children) |  |
//function to find the minimum value in a node
struct node*find_minimum(struct node*root) {
if (root== NULL) {
return NULL;
}
else if (root->left_child != NULL) {// node with minimum value will have no left child
return find_minimum(root->left_child);// left most element will be minimum
}
return root;
}
int isEmpty(struct node*root) {
if (root == NULL) {
puts("Tree is empty");
return 1; //Tree is empty
}
return 0;//Tree is not empty
}
struct node* delete(struct node*root, int x) {
if (isEmpty(root)) {
return;
}
//search
if (x<root->data) {
root->left_child = delete(root->left_child, x);
}
else if (x > root->data) {
root->right_child = delete(root->right_child, x);
}
else {
//No children
if (root->left_child == NULL && root->right_child == NULL) {
free(root);
return NULL;
}
//One child
else if (root->left_child == NULL || root->right_child == NULL) {
struct node*tmp;
if (root->left_child == NULL) {
tmp = root->right_child;
}
else {
tmp = root->left_child;
}
free(root);
return tmp;
}
//Two children
else {
struct node*tmp = find_minimum(root->right_child);
root->data = tmp->data;
root->right_child = delete(root->right_child, tmp->data);
}
}
return root;
}- void makeEmpty() 👉 트리 비우기
void makeEmpty(struct node*root) {
if (root==NULL)
return;
//delete subtrees
makeEmpty(root->left_child);
makeEmpty(root->right_child);
//delete current node
free(root);
root = NULL;
}
전체 소스코드
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data; //node will store an integer
struct node*right_child;
struct node*left_child;
};
//Returns a queue with the elements in-order
void inOrder(struct node*root) {
if (root != NULL) {
inOrder(root->left_child);
printf("%d ", root->data);
inOrder(root->right_child);
}
}
//Returns a queue with the elements in pre-order
void preOrder(struct node*root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left_child);
preOrder(root->right_child);
}
}
//Returns a queue with the elements in post-order
void postOrder(struct node*root) {
if (root != NULL) {
postOrder(root->left_child);
postOrder(root->right_child);
printf("%d ", root->data);
}
}
//Returns 1 if the BST contains the data, otherwise returns 0
int contains(struct node*root, int data) {
struct node*p = root;
while (p != NULL) {
if (p->data == data) {
return 1;
}
else if (p->data > data) {
p = p->left_child;
}
else if (p->data < data) {
p = p->right_child;
}
}
return 0;
}
struct node*new_node(int x) {
struct node*p = (struct node*)malloc(sizeof(struct node));
p->data = x;
p->left_child = NULL;
p->right_child = NULL;
}
struct node* put(struct node*root,int x) {
struct node*p = root;
//If the x is already in the BST, then put will do nothing.
if (contains(p, x)) {
printf("%d is already in the BST.", x);
return p;
}
//If the data is not in the BST, then put will add the data to the BST.
if (p == NULL) {
p = new_node(x); //p points to new node
}
else if (p->data > x) { //if x is smaller, should be inserted to left
p->left_child = put(p->left_child, x);
}
else{
p->right_child = put(p->right_child, x);
}
return p;
}
//function to find the minimum value in a node
struct node*find_minimum(struct node*root) {
if (root== NULL) {
return NULL;
}
else if (root->left_child != NULL) {// node with minimum value will have no left child
return find_minimum(root->left_child);// left most element will be minimum
}
return root;
}
int isEmpty(struct node*root) {
if (root == NULL) {
puts("Tree is empty");
return 1; //Tree is empty
}
return 0;//Tree is not empty
}
struct node* delete(struct node*root, int x) {
if (isEmpty(root)) {
return;
}
//search
if (x<root->data) {
root->left_child = delete(root->left_child, x);
}
else if (x > root->data) {
root->right_child = delete(root->right_child, x);
}
else {
//No children
if (root->left_child == NULL && root->right_child == NULL) {
free(root);
return NULL;
}
//One child
else if (root->left_child == NULL || root->right_child == NULL) {
struct node*tmp;
if (root->left_child == NULL) {
tmp = root->right_child;
}
else {
tmp = root->left_child;
}
free(root);
return tmp;
}
//Two children
else {
struct node*tmp = find_minimum(root->right_child);
root->data = tmp->data;
root->right_child = delete(root->right_child, tmp->data);
}
}
return root;
}
void makeEmpty(struct node*root) {
if (root==NULL)
return;
//delete subtrees
makeEmpty(root->left_child);
makeEmpty(root->right_child);
//delete current node
free(root);
root = NULL;
}
void main() {
struct node*root = new_node(6);
put(root, 2);
put(root, 7);
put(root, 1);
put(root, 4);
put(root, 3);
put(root, 5);
printf("Preorder traversal > "); preOrder(root); puts("");
printf("Inorder traversal > "); inOrder(root); puts("");
printf("Postorder traversal > "); postOrder(root);
printf("\ndelete 6\n");
root = delete(root, 6);
printf("Preorder traversal > "); preOrder(root); puts("");
printf("Inorder traversal > "); inOrder(root); puts("");
printf("Postorder traversal > "); postOrder(root);
printf("\ndelete 1\n");
root = delete(root, 1);
printf("Preorder traversal > "); preOrder(root); puts("");
printf("Inorder traversal > "); inOrder(root); puts("");
printf("Postorder traversal > "); postOrder(root);
printf("\nmake Tree empty >\n"); makeEmpty(root);
}'자료구조' 카테고리의 다른 글
| 👩💻중앙대 자료구조 assignment#3_Find MST using Kruskal alg.(C언어, C++) (0) | 2022.06.01 |
|---|---|
| 자료구조_스택을 활용한 미로찾기(대각선 이동 가능) (0) | 2022.05.09 |