최대 차수가 2인 트리
포인터를 이용한 구현
typedef struct BinTreeNodeType
{
char data;
struct BinTreeNodeType* pLeftChild;
struct BinTreeNodeType* pRightChild;
} BinTreeNode;
typedef struct BinTreeType
{
struct BinTreeNodeType* pRootNode;
} BinTree;
BinTree* makeBinTree(BinTreeNode rootNode);
BinTreeNode* getRootNodeBT(BinTree* pBinTree);
BinTreeNode* insertLeftChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);
BinTreeNode* insertRightChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);
BinTreeNode* getLeftChildNodeBT(BinTreeNode* pNode);
BinTreeNode* getRightChildNodeBT(BinTreeNode* pNode);
void deleteBinTree(BinTree** pBinTree);
void deleteBinTreeNode(BinTreeNode* pNode);
BinTree *makeBinTree(BinTreeNode rootNode)
{
BinTree *tree;
tree = (BinTree *)calloc(1, sizeof(BinTree));
if (tree == NULL)
return (NULL);
tree->pRootNode = (BinTreeNode *)calloc(1, sizeof(BinTreeNode));
if (tree->pRootNode == NULL)
{
free(tree);
return (NULL);
}
*(tree->pRootNode) = rootNode;
return (tree);
}
BinTreeNode *insertLeftChildNodeBT(BinTreeNode *pParentNode, BinTreeNode element)
{
if (pParentNode == NULL)
{
fprintf(stderr, "ERROR: 트리 없음\n");
return (NULL);
}
pParentNode->pLeftChild = (BinTreeNode *)calloc(1, sizeof(BinTreeNode));
if (pParentNode->pLeftChild == NULL)
{
fprintf(stderr, "ERROR: 노드 메모리 할당 X\n");
return (NULL);
}
*(pParentNode->pLeftChild) = element;
return (pParentNode->pLeftChild);
}
BinTreeNode *insertRightChildNodeBT(BinTreeNode *pParentNode, BinTreeNode element)
{
if (pParentNode == NULL)
{
fprintf(stderr, "ERROR: 트리 없음\n");
return (NULL);
}
pParentNode->pRightChild = (BinTreeNode *)calloc(1, sizeof(BinTreeNode));
if (pParentNode->pRightChild == NULL)
{
fprintf(stderr, "ERROR: 노드 메모리 할당 X\n");
return (NULL);
}
*(pParentNode->pRightChild) = element;
return (pParentNode->pRightChild);
}
BinTreeNode *getLeftChildNodeBT(BinTreeNode *pNode)
{
if (pNode == NULL)
{
fprintf(stderr, "ERROR: 노드 없음\n");
return (NULL);
}
return (pNode->pLeftChild);
}
BinTreeNode *getRightChildNodeBT(BinTreeNode *pNode)
{
if (pNode == NULL)
{
fprintf(stderr, "ERROR: 노드 없음\n");
return (NULL);
}
return (pNode->pRightChild);
}
void deleteBinTree(BinTree **pBinTree)
{
if (pBinTree == NULL || *pBinTree == NULL)
{
fprintf(stderr, "ERROR: 트리 없음\n");
return ;
}
deleteBinTreeNode((*pBinTree)->pRootNode);
free(*pBinTree);
*pBinTree = NULL;
}
void deleteBinTreeNode(BinTreeNode *pNode)
{
if (pNode == NULL)
return ;
deleteBinTreeNode(pNode->pLeftChild);
deleteBinTreeNode(pNode->pRightChild);
free(pNode);
}
void preorderTraverse(BinTreeNode *pNode);
void inorderTraverse(BinTreeNode *pNode);
void postorderTraverse(BinTreeNode *pNode);
V
: visited,L
: left,R
: right
void preorderTraverse(BinTreeNode *pNode)
{
if (pNode == NULL)
return ;
printf("%c ", pNode->data);
preorderTraverse(pNode->pLeftChild);
preorderTraverse(pNode->pRightChild);
}
void inorderTraverse(BinTreeNode *pNode)
{
if (pNode == NULL)
return ;
inorderTraverse(pNode->pLeftChild);
printf("%c ", pNode->data);
inorderTraverse(pNode->pRightChild);
}
void postorderTraverse(BinTreeNode *pNode)
{
if (pNode == NULL)
return ;
postorderTraverse(pNode->pLeftChild);
postorderTraverse(pNode->pRightChild);
printf("%c ", pNode->data);
}