이진트리 구현

열혈 C 자료구조를 통해 공부한 내용을 가지고

 

계산기를 이진트리를 직접 구현 해보자

 

CPU 입장에서는 이진트리나 양방향 리스트로 똑같은 거 같다.

 

 

 

노드: node

트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 구성요소

 

간선: edge

노드와 노드를 연결하는 연결선

 

루트 노드: root node

트리 구조에서 최상위에 존재하는 A와 같은 노드

 

단말 노드: terminal node

아래로 또 다른 노드가 연결되어 있지 않은 D, E, F

 

내부 노드: internal node

단말 노드를 제외한 모든 노드로 A, B와 같은 노드

 

이진트리 구조체

typedef int BTData;

typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode *left;
	struct _bTreeNode *right;
} BTreeNode;

 

양방향 리스트와 비슷하다.

 

이진트리 함수

BTreeNode* MakeBTreeNode(void)
{
	BTreeNode *nd = (BTreeNode*) malloc(sizeof(BTreeNode));
	nd->data = 0;
	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

BTData GetData(BTreeNode *bt)
{
	return bt->data;
}

void SetData(BTreeNode *bt, BTData data)
{
	bt->data = data;
}

void DeleteTree(BTreeNode *bt)
{
	if(bt !=NULL)
		free(bt);
}

BTreeNode* GetLeftSubTree(BTreeNode *bt)
{
	return bt->left;
}

BTreeNode* GetRightSubTree(BTreeNode *bt)
{
	return bt->right;
}

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub)
{
	if (main->left != NULL)
		free(main->left);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode *main, BTreeNode *sub)
{
	if (main->right != NULL)
		free(main->right);

	main->right = sub;
}