Monday, July 21, 2008

Simple recursive functions for binary trees

//Depth of binary tree
int DepthOfBinaryTree(NODE *pHead)
{
if (NULL == pHead)
return 0;

int nLeft = DepthOfBinaryTree(pHead->pLeft);
int nRight = DepthOfBinaryTree(pHead->pRight);

if (nLeft < nRight)
return (nRight + 1);
else
return (nLeft + 1);
}

//Copy of binary tree
NODE* CopyTree(NODE *pHead)
{
if (NULL == pHead)
return NULL;

NODE *pTemp = (NODE *)malloc(sizeof(NODE));
pTemp->nValue = pHead->nValue;

pTemp->pLeft = CopyTree(pHead->pLeft);
pTemp->pRight = CopyTree(pHead->pRight);

return pTemp;
}

//Size of binary tree
//No. of nodes in a binary tree
int SizeOfTree(NODE *pHead)
{
if (NULL == pHead)
return 0;

int i = SizeOfTree(pHead->pLeft);
int j = SizeOfTree(pHead->pRight);

return (i + j + 1);
}

//Mirror image of a tree
void MirrorATree(NODE *pHead)
{
if (NULL == pHead)
return;

//Swap nodes
NODE *pTemp = pHead->pLeft;
pHead->pLeft = pHead->pRight;
pHead->pRight = pTemp;

//Move on to swap nodes of children
MirrorATree(pHead->pLeft);
MirrorATree(pHead->pRight);
}

//Tree traversal functions

void PreOrderTraversal(NODE *pRoot)
{
if (NULL == pRoot)
return;

printf("\n%d", pRoot->nValue);
PreOrderTraversal(pRoot->pLeft);
PreOrderTraversal(pRoot->pRight);
}

void InOrderTraversal(NODE *pRoot)
{
if (NULL == pRoot)
return;

InOrderTraversal(pRoot->pLeft);
printf("\n%d", pRoot->nValue);
InOrderTraversal(pRoot->pRight);
}

void PostOrderTraversal(NODE *pRoot)
{
if (NULL == pRoot)
return;

PostOrderTraversal(pRoot->pLeft);
PostOrderTraversal(pRoot->pRight);
printf("\n%d", pRoot->nValue);
}

0 comments: