성대아싸의 멍충한 프로그래밍

알고리즘2009. 9. 16. 23:53

BST (func)

/* in file bstree.h */

#include <stdio.h>
#include <stdlib.h>

typedef int 	DATA;

struct tree
{
	DATA 			d;
	struct tree 	*left;
	struct tree 	*right;
	struct tree 	*p;  //parent
};

typedef struct tree 	NODE;
typedef NODE 			*BSTREE;

BSTREE make_node(DATA input);
BSTREE insert_tree(BSTREE root, BSTREE z) ;
BSTREE tree_search(BSTREE tree, DATA key);
BSTREE iter_search(BSTREE tree, DATA key);
BSTREE tree_minimum(BSTREE root);
BSTREE tree_maximum(BSTREE root);
BSTREE tree_successor(BSTREE root);
BSTREE tree_delete(BSTREE root, BSTREE z);
void inorder(BSTREE root);
void preorder(BSTREE root);
void postorder(BSTREE root);

/* in file bt_make.c */

#include "btree.h"

BTREE make_node(DATA input)
{
	BTREE tmp;
	tmp 			= (BTREE)malloc(sizeof(NODE));
	tmp -> d 		= input;
	tmp -> left 	= NULL;
	tmp -> right 	= NULL;

return tmp;
}

BTREE insert_tree(BTREE root, BTREE z) 
{
	BTREE y;
	BTREE x;
	y = NULL;
	x = root;

while (x != NULL)
	{
		y = x;
		if ((z -> d) < (x -> d))
			x = x -> left;
		else
			x = x -> right;
	}
	z -> p = y;
	if (y == NULL)
		root = z;
	else
	{
		if ((z -> d) < (y -> d))
			y -> left = z;
		else
			y -> right = z;
	}
	return root;
}

BTREE tree_successor(BTREE root)
{
	BTREE tmp;
	if (root -> right != NULL)
		return tree_minimum(root -> right);
	
	tmp = root->p;
	
	while((tmp != NULL) && (root == tmp->right))
	{
		root = tmp;
		tmp = tmp -> p;
	}
	return tmp;
}

BTREE tree_delete(BTREE root, BTREE z)
{
	BTREE y;
	BTREE x;
	
	if ((z -> left ==NULL)||(z->right==NULL))
		y = z;
	else
		y = tree_successor(z);
	if(y->left != NULL)
		x = y -> left;
	else
		x = y ->right;
	if( x != NULL)
		x->p = y->p;
	if(y->p ==NULL)
		root = x;
	else
	{
		if ( y == y -> p ->left)
			y -> p -> left = x;
		else
			y -> p -> right = x;
	}
	if (y != x)
	{
		z->d = y->d;
	}
	return root;
}

/* in file bt_items.c */

#include "btree.h"

BTREE tree_search(BTREE tree, DATA key)
{
	if ((tree == NULL)||(key == tree->d))
	{
		return tree;
	}
	if (key < tree -> d)
		return tree_search(tree->left,key);
	else
		return tree_search(tree->right,key);
}

BTREE iter_search(BTREE tree, DATA key)
{
	BTREE root;
	root = tree;
	
	while ((root != NULL) && (key != root -> d))
	{
		if (key < root -> d)
			root = root -> left;
		else
			root = root -> right;
	}
	return root;
}

BTREE tree_minimum(BTREE root)
{
	BTREE tmp = root;

while (tmp -> left != NULL)
	{
		tmp = tmp -> left;
	}
	return tmp;
}

BTREE tree_maximum(BTREE root)
{
	BTREE tmp = root;

while (tmp -> right != NULL)
	{
		tmp = tmp -> right;
	}
	return tmp;
}

void inorder(BTREE root)
{
	if (root != NULL)
	{
		inorder(root -> left);
		printf("%d ", root -> d);
		inorder(root -> right);
	}
}
void preorder(BTREE root)
{
	if (root != NULL)
	{
		printf("%d ", root -> d);
		preorder(root -> left);
		preorder(root -> right);
	}
}
void postorder(BTREE root)
{
	if (root != NULL)
	{
		postorder(root -> left);
		postorder(root -> right);
		printf("%d ", root -> d);
	}
}
/* in file bt_main.c */

#include "btree.h"

int main(void)
{
	DATA arr[] = {6,3,1,7,8,5};
	int i;
	BTREE val;
	BTREE root = NULL;

for (i=0; i<6; i++)
	{
		val = make_node(arr[i]);
		root = insert_tree(root,val);
	}
	printf("inorder = ");
	inorder(root);
	printf("\n");
	printf("preorder= ");
	preorder(root);
	printf("\n============\n");

val = tree_minimum(root);
	printf("mini = %d\n", val -> d);
	val = tree_successor(val);
	printf("suce = %d\n", val -> d);

printf("\n=============\n");

for(i=0; i<6; i++)
	{
		val = tree_search(root,arr[i]);
		printf("pick = %d\n", val ->d); 
		root = tree_delete(root,val);
		inorder(root);
		printf("\n");
	}

return 0;
}

BTREE , BSTREE

ㅋㅋㅋㅋㅋㅋㅋㅋ

모를땐 둘이 같은줄

저작자표시

'알고리즘' 카테고리의 다른 글

red_black_tree (concept) (0)	2009.09.17
BST (평가) (0)	2009.09.16
BST (func) (0)	2009.09.16
binary search tree (concept) (0)	2009.09.16
hash_chain (평가) (0)	2009.09.16
hash_chain (func) (0)	2009.09.16

Posted by 멍충한아싸

Trackback 1 Comment 0

댓글을 달아 주세요

«이전 1 ··· 215 216 217 218 219 220 221 222 223 ··· 240 다음»

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

성대아싸의 멍충한 프로그래밍

BST (func)

'알고리즘' 카테고리의 다른 글

TRACKBACK

댓글을 달아 주세요

카테고리

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크