Binary Tree 구현

코딩 시험에 종종 나오는 Binary Tree를 구현해 보았다. Double Linked List와 구현방법은 비슷하다.

값이 작을때는 어느방향, 값이 클때는 어느방향 이것만 잘 생각하고 짜면 어렵지는 않음.

I have implemented the Binary Tree, which is often used in coding test. 

The implementation is similar to a double linked list.

When the value is small, it is necessary to consider only what direction it is, and what direction it is when the value is large.
 

typedef struct _node
{
	int Data;
	struct _node* L;
	struct _node* R;
}node;

node* createNode(int Data)
{
	node* newNode = (node*)malloc(sizeof(node));
	newNode->L = NULL;
	newNode->R = NULL;
	newNode->Data = Data;
	return newNode;
}

void insertNode(node* binaryTree, node* newNode)
{
	if(newNode->Data > binaryTree->Data)
	{
		if(binaryTree->R != NULL)
		{
			insertNode(binaryTree->R, newNode);
		}
		else
		{	
			binaryTree->R = newNode;
		}
	}
	else if(newNode->Data < binaryTree->Data)
	{
		if(binaryTree->L != NULL)
		{
			insertNode(binaryTree->L, newNode);
		}
		else
		{
			binaryTree->L = newNode;
		}
	}
}

node* findTargetNode(node* binaryTree)
{
	if(binaryTree == NULL) 
	{	
		return NULL;
	}
	if(binaryTree->L != NULL)
	{
		return findTargetNode(binaryTree->L);
	}
	else
	{
		return binaryTree;
	}
}

node* deleteNode(node* binaryTree, int data)
{
	node* targetNode;
	if(binaryTree->Data > data)
	{
		binaryTree->L = deleteNode(binaryTree->L, data);
	}
	else if(binaryTree->Data < data)
	{
		binaryTree->R = deleteNode(binaryTree->R, data);
	}
	else
	{
		if((binaryTree->L != NULL) && (binaryTree->R != NULL))
		{
			targetNode = findTargetNode(binaryTree->R);
			binaryTree->Data = targetNode->Data;
			binaryTree->R = deleteNode(binaryTree->R, targetNode->Data);
		}
		else 
		{
			targetNode = binaryTree;
			if(binaryTree->L == NULL)
			{
				binaryTree = binaryTree->R;
			}
			else if(binaryTree->R == NULL)
			{
				binaryTree = binaryTree->L;
			}
			free(targetNode);
		}
	}
	return binaryTree;
}