글 읽기 - [자료구조] - Binary Search Tree

tjdgns9246 7년 전 0

Binary Search Tree에 노드 삽입 insert()

Binary Search Tree에서 특정 노드 제거 delete()

<input>

30 5 40 2 80 35

<output>

Preorder traversal : 30 5 2 40 35 80
deleted key : 30
Preorder traversal : 5 2 40 35 80
deleted key : 35
Preorder traversal : 5 2 40 80
deleted key : 40
Preorder traversal : 5 2 80

#include <stdio.h>
#include <stdlib.h>
 
typedef struct
{
    int key;
} element;
 
typedef struct node* treePointer;
typedef struct node
{
    element data;
    treePointer leftChild, rightChild;
};
 
treePointer modifiedSearch(treePointer root, int k);
void insert(treePointer *root, int k);
element delete(treePointer root, int k);
void preorder(treePointer root);
 
int main()
{
    element temp;
    treePointer root = NULL;
    while(scanf("%d", &temp.key) != -1)
        insert(&root, temp.key);
    
    printf("Preorder traversal : ");
    preorder(root);
    temp = delete(root, 30);
    printf("\ndeleted key : %d\n", temp.key);
    printf("Preorder traversal : ");
    preorder(root);
    temp = delete(root, 35);
    printf("\ndeleted key : %d\n", temp.key);
    printf("Preorder traversal : ");
    preorder(root);
    temp = delete(root, 40);
    printf("\ndeleted key : %d\n", temp.key);
    printf("Preorder traversal : ");
    preorder(root);
}
 
treePointer modifiedSearch(treePointer root, int k)
{
    treePointer temp = root;
    while(root)
    {
        temp = root;
        if(k < root->data.key)
            root = root->leftChild;
        else if(k > root->data.key)
            root = root->rightChild;
        else
            return NULL;
    }
    return temp;
}
 
void insert(treePointer *root, int k)
{
    treePointer ptr, temp = modifiedSearch(*root, k);
    if(temp || !(*root))
    {
        ptr = (treePointer)malloc(sizeof(*ptr));
        ptr->data.key = k;
        ptr->leftChild = ptr->rightChild = NULL;
        if(*root)
            if(k < temp->data.key)
                temp->leftChild = ptr;
            else
                temp->rightChild = ptr;
        else
            *root = ptr;
    }
}

element delete(treePointer root, int k)
{
	element temp;
	treePointer current, target, previous;
	current = root;
	target = NULL;
	
	if(!current)
		return;
	while(1)
	{
		if(k > current->data.key)
		{
			if(current->rightChild == NULL)
				break;
			previous = current;
			current = current->rightChild;
		}
		else
		{
			if(k == current->data.key)
				target = current;
			if(current->leftChild == NULL)
				break;
			previous = current;
			current = current->leftChild;
		}
	}
	
	if(target == NULL)
		return;
	else
	{
		// root
		if(previous == NULL)
		{
			temp = current->data;
			free(current);
			root = NULL;
			return temp;
		}
		else
		{
			temp = target->data;
			target->data.key = current->data.key;
			
			if(previous->leftChild == current)
				previous->leftChild = current->leftChild;
			else
				previous->rightChild = current->rightChild;
			
			free(current);
			return temp;
		}
	}
}
 
void preorder(treePointer root)
{
    if(root)
    {
        printf("%d ", root->data.key);
        preorder(root->leftChild);
        preorder(root->rightChild);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[자료구조] - Binary Search Tree

tjdgns9246 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말